-
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
Recovering optimal solutions via SOC-SDP relaxation of trust region subproblem with nonintersecting linear constraints
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 |
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.
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
Other articles
by authors
[Back to Top]