American Institute of Mathematical Sciences

Advanced
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  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 & Management Optimization, 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]

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

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 & Management Optimization, 2018, 14 (2) : 707-718. doi: 10.3934/jimo.2017070
[3]

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

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

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

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

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

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

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

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

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 & Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169
[12]

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

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

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
[15]

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

Xianchao Xiu, Lingchen Kong. Rank-one and sparse matrix decomposition for dynamic MRI. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 127-134. doi: 10.3934/naco.2015.5.127
[17]

Huseyin Coskun. Nonlinear decomposition principle and fundamental matrix solutions for dynamic compartmental systems. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-53. doi: 10.3934/dcdsb.2019155
[18]

Lingling Lv, Zhe Zhang, Lei Zhang, Weishu Wang. An iterative algorithm for periodic sylvester matrix equations. Journal of Industrial & Management Optimization, 2018, 14 (1) : 413-425. doi: 10.3934/jimo.2017053
[19]

Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial & Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71
[20]

Anwa Zhou, Jinyan Fan. A semidefinite relaxation algorithm for checking completely positive separable matrices. Journal of Industrial & Management Optimization, 2019, 15 (2) : 893-908. doi: 10.3934/jimo.2018076

2017 Impact Factor: 0.994

Tools

Metrics

  • PDF downloads (38)
  • HTML views (662)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences