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  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, 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.  Google Scholar

[2]

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

[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.  Google Scholar

[4]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

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

[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.  Google Scholar

[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.  Google Scholar

[15] R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970.   Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[18]

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

[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.  Google Scholar

[20]

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

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.  Google Scholar

[2]

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

[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.  Google Scholar

[4]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

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

[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.  Google Scholar

[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.  Google Scholar

[15] R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970.   Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[18]

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

[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.  Google Scholar

[20]

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

[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 & 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 & 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 & Optimization, 2013, 3 (2) : 223-234. doi: 10.3934/naco.2013.3.223
[4]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (179)
  • HTML views (1117)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences