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]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076
[3]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005
[4]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340
[5]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073
[6]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321
[7]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012
[8]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012
[9]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017
[10]

Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107
[11]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018
[12]

S. Sadeghi, H. Jafari, S. Nemati. Solving fractional Advection-diffusion equation using Genocchi operational matrix based on Atangana-Baleanu derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020435
[13]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375
[14]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016
[15]

Nalin Fonseka, Jerome Goddard II, Ratnasingham Shivaji, Byungjae Son. A diffusive weak Allee effect model with U-shaped emigration and matrix hostility. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020356

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (141)
  • HTML views (1078)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences