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

Jinyu Dai; Shu-Cherng Fang; Wenxun Xing

doi:10.3934/jimo.2018117

Article Contents

2019, Volume 15, Issue 4: 1677-1699. Doi: 10.3934/jimo.2018117

This issue Previous Article Asymptotic convergence of stationary points of stochastic multiobjective programs with parametric variational inequality constraint via SAA approach Next Article Coordinating the supplier-retailer supply chain under noise effect with bundling and inventory strategies

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

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

Received: April 2017

Revised: April 2018

Early access: August 2018

Published: July 2019

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.

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90C20, 90C22, 90C26.

Citation:

Full Text(HTML)

Related Papers

Cited by

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.