American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Coordinating the supplier-retailer supply chain under noise effect with bundling and inventory strategies
  • JIMO Home
  • This Issue
  • Next Article
    Asymptotic convergence of stationary points of stochastic multiobjective programs with parametric variational inequality constraint via SAA approach
October  2019, 15(4): 1677-1699. doi: 10.3934/jimo.2018117

Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints

Jinyu Dai 1, , Shu-Cherng Fang 2, and  Wenxun Xing 1,,

1. 

Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China
2. 

Edward P. Fitts Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, NC 27695, USA

* Corresponding author: Wenxun Xing < wxing@tsinghua.edu.cn >

Received  April 2017 Revised  April 2018 Published  October 2019 Early access  August 2018

Fund Project: Xing's research has been supported by the NNSF of China Grants #11571029 and #11771243, Fang's research has been supported by the US ARO Grant #W911NF-15-1-0223.

In this paper, we study an extended trust region subproblem (eTRS) in which the unit ball intersects with $m$ linear inequality constraints. In the literature, Burer et al. proved that an SOC-SDP relaxation (SOCSDPr) of eTRS is exact, under the condition that the nonredundant constraints do not intersect each other in the unit ball. Furthermore, Yuan et al. gave a necessary and sufficient condition for the corresponding SOCSDPr to be a tight relaxation when $m = 2$. However, there lacks a recovering algorithm to generate an optimal solution of eTRS from an optimal solution $X^*$ of SOCSDPr when rank $(X^*)≥ 2$ and $m≥ 3$. This paper provides such a recovering algorithm to complement those known works.

Keywords: Trust region subproblem, SOC-SDP relaxation, slater condition, matrix decomposition, recovering algorithm.
Mathematics Subject Classification: Primary: 90C20, 90C22, 90C26.
Citation: Jinyu Dai, Shu-Cherng Fang, Wenxun Xing. Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1677-1699. doi: 10.3934/jimo.2018117
References:
[1]

A. Ben-Tal, L. E. Ghaoui and A. Nemirovski, Robust Optimization, Princeton Series in Applied Mathematics, 2009 doi: 10.1515/9781400831050.

[2]

D. Bertsimas, D. Brown and C. Caramanis, Theory and applications of robust optimization, SIAM Review, 53 (2011), 464-501.  doi: 10.1137/080734510.

[3]

D. Bertsimas, D. Pachamanova and M. Sim, Robust linear optimization under general norms, Operations Research Letters, 32 (2004), 510-516.  doi: 10.1016/j.orl.2003.12.007.

[4]

S. Burer, A gentle, geometric introduction to copositive optimization, Mathematical Progamming, 151 (2015), 89-116.  doi: 10.1007/s10107-015-0888-z.

[5]

S. Burer and K. M. Anstreicher, Second-order cone constraints for extended trust-region problems, SIAM Journal on Optimization, 23 (2013), 432-451.  doi: 10.1137/110826862.

[6]

S. Burer and B. Yang, The trust region subproblem with non-intersecting linear constraints, Mathematical Progamming, 149 (2015), 253-264.  doi: 10.1007/s10107-014-0749-1.

[7]

A. R. Conn, N. I. M. Gould and P. L. Toint, Trust-Region Methods, MPS-SIAM Series in Optimization, SIAM, Philadelphia, PA, 2000. doi: 10.1137/1.9780898719857.

[8]

W. Gander, G. H. Golub and U. Von Matt, A constrained eigenvalue problem, Linear Algebra and its Applications, 114/115 (1989), 815-839.  doi: 10.1016/0024-3795(89)90494-1.

[9]

G. H. Golub and U. Von Matt, Quadratically constrained least squares and quadratic problems, Numerische Mathematik, 59 (1991), 561-580.  doi: 10.1007/BF01385796.

[10]

V. Jeyakumar and G. Li, A robust von-Neumann minimax theorem for zero-sum games under bounded payoff uncertainty, Operations Research Letters, 39 (2011), 109-114.  doi: 10.1016/j.orl.2011.02.007.

[11]

V. Jeyakumar and G. Li, Strong duality in robust convex programming: Complete characterizations, SIAM Journal on Optimization, 20 (2010), 3384-3407.  doi: 10.1137/100791841.

[12]

J. J. More, Generalizations of the trust region subproblem, Optimization Methods and Software, 2 (2008), 189-209.  doi: 10.1080/10556789308805542.

[13]

P. Pardalos and H. Romeijn, Handbook in Global Optimization, vol. 2. Kluwer Academic Publishers, Dordrecht, 2002. doi: 10.1007/978-1-4757-5362-2.

[14]

M. J. D. Powell and Y. Yuan, A trust region algorithm for equality constrained optimization, Mathematical Programming, 49 (1990), 189-211.  doi: 10.1007/BF01588787.

[15] R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970. 
[16]

R. J. Stern and H. Wolkowicz, Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations, SIAM Journal on Optimization, 5 (1995), 286-313.  doi: 10.1137/0805016.

[17]

J. F. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267.  doi: 10.1287/moor.28.2.246.14485.

[18]

Y. Ye and S. Zhang, New results on quadratic minimization, SIAM Journal on Optimization, 14 (2003), 245-267.  doi: 10.1137/S105262340139001X.

[19]

J. H. Yuan, M. L. Wang, W. B. Ai and T. P. Shuai, A necessary and sufficient condition of convexity for SOC reformulation of trust-region subproblem with two intersecting cuts, Science China Mathematics, 59 (2016), 1127-1140.  doi: 10.1007/s11425-016-5130-9.

[20]

Y. Yuan, On a subproblem of trust region algorithms for constrained optimization, Mathematical Programming, 47 (1990), 53-63.  doi: 10.1007/BF01580852.

show all references

References:
[1]

A. Ben-Tal, L. E. Ghaoui and A. Nemirovski, Robust Optimization, Princeton Series in Applied Mathematics, 2009 doi: 10.1515/9781400831050.

[2]

D. Bertsimas, D. Brown and C. Caramanis, Theory and applications of robust optimization, SIAM Review, 53 (2011), 464-501.  doi: 10.1137/080734510.

[3]

D. Bertsimas, D. Pachamanova and M. Sim, Robust linear optimization under general norms, Operations Research Letters, 32 (2004), 510-516.  doi: 10.1016/j.orl.2003.12.007.

[4]

S. Burer, A gentle, geometric introduction to copositive optimization, Mathematical Progamming, 151 (2015), 89-116.  doi: 10.1007/s10107-015-0888-z.

[5]

S. Burer and K. M. Anstreicher, Second-order cone constraints for extended trust-region problems, SIAM Journal on Optimization, 23 (2013), 432-451.  doi: 10.1137/110826862.

[6]

S. Burer and B. Yang, The trust region subproblem with non-intersecting linear constraints, Mathematical Progamming, 149 (2015), 253-264.  doi: 10.1007/s10107-014-0749-1.

[7]

A. R. Conn, N. I. M. Gould and P. L. Toint, Trust-Region Methods, MPS-SIAM Series in Optimization, SIAM, Philadelphia, PA, 2000. doi: 10.1137/1.9780898719857.

[8]

W. Gander, G. H. Golub and U. Von Matt, A constrained eigenvalue problem, Linear Algebra and its Applications, 114/115 (1989), 815-839.  doi: 10.1016/0024-3795(89)90494-1.

[9]

G. H. Golub and U. Von Matt, Quadratically constrained least squares and quadratic problems, Numerische Mathematik, 59 (1991), 561-580.  doi: 10.1007/BF01385796.

[10]

V. Jeyakumar and G. Li, A robust von-Neumann minimax theorem for zero-sum games under bounded payoff uncertainty, Operations Research Letters, 39 (2011), 109-114.  doi: 10.1016/j.orl.2011.02.007.

[11]

V. Jeyakumar and G. Li, Strong duality in robust convex programming: Complete characterizations, SIAM Journal on Optimization, 20 (2010), 3384-3407.  doi: 10.1137/100791841.

[12]

J. J. More, Generalizations of the trust region subproblem, Optimization Methods and Software, 2 (2008), 189-209.  doi: 10.1080/10556789308805542.

[13]

P. Pardalos and H. Romeijn, Handbook in Global Optimization, vol. 2. Kluwer Academic Publishers, Dordrecht, 2002. doi: 10.1007/978-1-4757-5362-2.

[14]

M. J. D. Powell and Y. Yuan, A trust region algorithm for equality constrained optimization, Mathematical Programming, 49 (1990), 189-211.  doi: 10.1007/BF01588787.

[15] R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970. 
[16]

R. J. Stern and H. Wolkowicz, Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations, SIAM Journal on Optimization, 5 (1995), 286-313.  doi: 10.1137/0805016.

[17]

J. F. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267.  doi: 10.1287/moor.28.2.246.14485.

[18]

Y. Ye and S. Zhang, New results on quadratic minimization, SIAM Journal on Optimization, 14 (2003), 245-267.  doi: 10.1137/S105262340139001X.

[19]

J. H. Yuan, M. L. Wang, W. B. Ai and T. P. Shuai, A necessary and sufficient condition of convexity for SOC reformulation of trust-region subproblem with two intersecting cuts, Science China Mathematics, 59 (2016), 1127-1140.  doi: 10.1007/s11425-016-5130-9.

[20]

Y. Yuan, On a subproblem of trust region algorithms for constrained optimization, Mathematical Programming, 47 (1990), 53-63.  doi: 10.1007/BF01580852.

[1]

Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104
[2]

Yannan Chen, Jingya Chang. A trust region algorithm for computing extreme eigenvalues of tensors. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 475-485. doi: 10.3934/naco.2020046
[3]

Xin Zhang, Jie Wen, Qin Ni. Subspace trust-region algorithm with conic model for unconstrained optimization. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223
[4]

Jirui Ma, Jinyan Fan. On convergence properties of the modified trust region method under Hölderian error bound condition. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021222
[5]

Zhou Sheng, Gonglin Yuan, Zengru Cui, Xiabin Duan, Xiaoliang Wang. An adaptive trust region algorithm for large-residual nonsmooth least squares problems. Journal of Industrial and Management Optimization, 2018, 14 (2) : 707-718. doi: 10.3934/jimo.2017070
[6]

Jun Takaki, Nobuo Yamashita. A derivative-free trust-region algorithm for unconstrained optimization with controlled error. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 117-145. doi: 10.3934/naco.2011.1.117
[7]

Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171
[8]

Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control and Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237
[9]

Jun Chen, Wenyu Sun, Zhenghao Yang. A non-monotone retrospective trust-region method for unconstrained optimization. Journal of Industrial and Management Optimization, 2013, 9 (4) : 919-944. doi: 10.3934/jimo.2013.9.919
[10]

Lijuan Zhao, Wenyu Sun. Nonmonotone retrospective conic trust region method for unconstrained optimization. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 309-325. doi: 10.3934/naco.2013.3.309
[11]

Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283
[12]

Bülent Karasözen. Survey of trust-region derivative free optimization methods. Journal of Industrial and Management Optimization, 2007, 3 (2) : 321-334. doi: 10.3934/jimo.2007.3.321
[13]

Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2087-2102. doi: 10.3934/jimo.2019044
[14]

Liang Zhang, Wenyu Sun, Raimundo J. B. de Sampaio, Jinyun Yuan. A wedge trust region method with self-correcting geometry for derivative-free optimization. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169
[15]

Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041
[16]

Chifaa Ghanmi, Saloua Mani Aouadi, Faouzi Triki. Recovering the initial condition in the one-phase Stefan problem. Discrete and Continuous Dynamical Systems - S, 2022, 15 (5) : 1143-1164. doi: 10.3934/dcdss.2021087
[17]

Jaakko Ketola, Lars Lamberg. An algorithm for recovering unknown projection orientations and shifts in 3-D tomography. Inverse Problems and Imaging, 2011, 5 (1) : 75-93. doi: 10.3934/ipi.2011.5.75
[18]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[19]

Giuseppe Geymonat, Françoise Krasucki. Hodge decomposition for symmetric matrix fields and the elasticity complex in Lipschitz domains. Communications on Pure and Applied Analysis, 2009, 8 (1) : 295-309. doi: 10.3934/cpaa.2009.8.295
[20]

Huseyin Coskun. Nonlinear decomposition principle and fundamental matrix solutions for dynamic compartmental systems. Discrete and Continuous Dynamical Systems - B, 2019, 24 (12) : 6553-6605. doi: 10.3934/dcdsb.2019155

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (281)
  • HTML views (1186)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy