• 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

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.

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. BertsimasD. Brown and C. Caramanis, Theory and applications of robust optimization, SIAM Review, 53 (2011), 464-501.  doi: 10.1137/080734510.  Google Scholar

[3]

D. BertsimasD. 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. GanderG. 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. YuanM. L. WangW. 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. BertsimasD. Brown and C. Caramanis, Theory and applications of robust optimization, SIAM Review, 53 (2011), 464-501.  doi: 10.1137/080734510.  Google Scholar

[3]

D. BertsimasD. 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. GanderG. 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. YuanM. L. WangW. 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]

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

[2]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[3]

Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109

[4]

Y. Latushkin, B. Layton. The optimal gap condition for invariant manifolds. Discrete & Continuous Dynamical Systems - A, 1999, 5 (2) : 233-268. doi: 10.3934/dcds.1999.5.233

[5]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781

[6]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247

[7]

Carlos Gutierrez, Nguyen Van Chau. A remark on an eigenvalue condition for the global injectivity of differentiable maps of $R^2$. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 397-402. doi: 10.3934/dcds.2007.17.397

[8]

Mansour Shrahili, Ravi Shanker Dubey, Ahmed Shafay. Inclusion of fading memory to Banister model of changes in physical condition. Discrete & Continuous Dynamical Systems - S, 2020, 13 (3) : 881-888. doi: 10.3934/dcdss.2020051

[9]

Yizhuo Wang, Shangjiang Guo. A SIS reaction-diffusion model with a free boundary condition and nonhomogeneous coefficients. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1627-1652. doi: 10.3934/dcdsb.2018223

[10]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

[11]

Zhiming Guo, Zhi-Chun Yang, Xingfu Zou. Existence and uniqueness of positive solution to a non-local differential equation with homogeneous Dirichlet boundary condition---A non-monotone case. Communications on Pure & Applied Analysis, 2012, 11 (5) : 1825-1838. doi: 10.3934/cpaa.2012.11.1825

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (156)
  • HTML views (1079)
  • Cited by (1)

Other articles
by authors

[Back to Top]