2016

A Second-Order Cone Based Approach for Solving the Trust Region Subproblem and Its Variants

Ho-Nguyen, Nam, Kilinc-Karzan, Fatma

Understand

We study the trust-region subproblem (TRS) of minimizing a nonconvex quadratic function over the unit ball with additional conic constraints.

Despite having a nonconvex objective, it is known that the classical TRS and a number of its variants are polynomial-time solvable.
In this paper, we follow a second-order cone (SOC) based approach to derive an exact convex reformulation of the TRS under a structural condition on the conic constraint.
Our structural condition is immediately satisfied when there is no additional conic constraints, and it generalizes several such conditions studied in the literature.

Built on

On the mapping of quadratic forms
L. L. Dines · 1941
Earlier work this paper cites.
The S-procedure and duality relations in nonconvex problems of quadratic programming
A. L. Fradkov and V. A. Yakubovich · 1979
Earlier work this paper cites.
Computing a trust region step
J. J. Moré and D. C. Sorensen · 1983
Earlier work this paper cites.
A method for solving a convex programming problem with rate of convergence O ⁡ ( 1 / k 2 ) O(1/k^{2})
Y. Nesterov · 1983
Earlier work this paper cites.
A trust region strategy for nonlinear equality constrained optimization
M. Celis, J. Dennis, and R. Tapia · 1985
Earlier work this paper cites.
A constrained eigenvalue problem
W. Gander, G. H. Golub, and U. von Matt · 1989
Earlier work this paper cites.
Estimating the largest eigenvalue by the power and lanczos algorithms with a random start
J. Kuczynski and H. Wozniakowski · 1992
Earlier work this paper cites.
Interior-Point Polynomial Algorithms in Convex Programming
Y. Nesterov and A. Nemirovski · 1994
Earlier work this paper cites.
Interior point methods in semidefinite programming with applications to combinatorial optimization
F. Alizadeh · 1995
Earlier work this paper cites.
Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations
R. J. Stern and H. Wolkowicz · 1995
Earlier work this paper cites.
Hidden convexity in some nonconvex quadratically constrained quadratic programming
A. Ben-Tal and M. Teboulle · 1996
Earlier work this paper cites.
Matrix Computations
G. H. Golub and C. F. Van Loan · 1996
Earlier work this paper cites.
A semidefinite framework for trust region subproblems with applications to large scale minimization
F. Rendl and H. Wolkowicz · 1997
Earlier work this paper cites.
Minimization of a large-scale quadratic function subject to a spherical constraint
D. C. Sorensen · 1997
Earlier work this paper cites.
Solving the trust-region subproblem using the Lanczos method
N. I. M. Gould, S. Lucidi, M. Roma, and P. L. Toint · 1999
Earlier work this paper cites.
Trust-Region Methods
A. R. Conn, N. I. M. Gould, and P. L. Toint · 2000
Earlier work this paper cites.
Numerical Optimization
J. Nocedal and S. Wright · 2000
Earlier work this paper cites.
A new matrix-free algorithm for the large-scale trust-region subproblem
M. Rojas, S. A. Santos, and D. C. Sorensen · 2001
Earlier work this paper cites.

Similar

On cones of nonnegative quadratic functions
J. F. Sturm and S. Zhang · 2003
Cited alongside, same era.
New results on quadratic minimization
Y. Ye and S. Zhang · 2003
Cited alongside, same era.
The trust region subproblem and semidefinite programming
C. Fortin and H. Wolkowicz · 2004
Cited alongside, same era.
Strong duality in nonconvex quadratic optimization with two quadratic constraints
A. Beck and Y. C. Eldar · 2006
Cited alongside, same era.
A survey of the s-lemma
I. Pólik and T. Terlaky · 2007
Cited alongside, same era.
Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming
A. Beck · 2009
Cited alongside, same era.
Robust Optimization
A. Ben-Tal, L. El Ghaoui, and A. Nemirovski · 2009
Cited alongside, same era.
Iterative methods for finding a trust-region step
J. B. Erway, P. E. Gill, and J. D. Griffin · 2009
Cited alongside, same era.
A subspace minimization method for the trust-region step
J. B. Erway and P. E. Gill · 2010
Cited alongside, same era.
On solving trust-region and other regularized subproblems in optimization
N. I. M. Gould, D. P. Robinson, and H. S. Thorne · 2010
Cited alongside, same era.
A derivative-free algorithm for least-squares minimization
H. Zhang, A. R. Conn, and K. Scheinberg · 2010
Cited alongside, same era.
Theory and applications of robust optimization
D. Bertsimas, D. B. Brown, and C. Caramanis · 2011
Cited alongside, same era.

Then

Polynomial solvability of variants of the trust-region subproblem
D. Bienstock and A. Michalka · 2014
Later among the works it cites.
The trust region subproblem with non-intersecting linear constraints
S. Burer and B. Yang · 2014
Later among the works it cites.
Convex hull of two quadratic or a conic quadratic and a quadratic inequality
S. Modaresi and J. Vielma · 2014
Later among the works it cites.
The generalized trust region subproblem
T. K. Pong and H. Wolkowicz · 2014
Later among the works it cites.
Solving the trust region subproblem by a generalized eigenvalue problem
S. Adachi, S. Iwata, Y. Nakatsukasa, and A. Takeda · 2015
Later among the works it cites.
Lectures on modern convex optimization
A. Ben-Tal and A. Nemirovski · 2015
Later among the works it cites.
A gentle, geometric introduction to copositive optimization
S. Burer · 2015
Later among the works it cites.
A fast eigenvalue approach for solving the trust region subproblem with an additional linear inequality
M. Salahi and A. Taati · 2015
Later among the works it cites.
A note on polynomial solvability of the CDT problem
D. Bienstock · 2016
Closest in time.
How to convexify the intersection of a second order cone and a nonconvex quadratic
S. Burer and F. Kılınç-Karzan · 2016
Closest in time.
A linear-time algorithm for trust region problems
E. Hazan and T. Koren · 2016
Closest in time.
Online first-order framework for robust convex optimization
N. Ho-Nguyen and F. Kılınç-Karzan · 2016
Closest in time.
A second-order cone based approach for solving the trust region subproblem and its variants
Original
N. Ho-Nguyen and F. Kılınç-Karzan · 2016
Closest in time.
Exactness conditions for an sdp relaxation of the extended trust region problem
M. Locatelli · 2016
Closest in time.
Trust region subproblem with an additional linear inequality constraint
M. Salahi and S. Fallahi · 2016
Closest in time.
Local nonglobal minima for solving large-scale extended trust-region subproblems
M. Salahi, A. Taati, and H. Wolkowicz · 2016
Closest in time.
A linear-time algorithm for the trust region subproblem based on hidden convexity
J. Wang and Y. Xia · 2016
Closest in time.
Quadratic programs with hollows
B. Yang, K. Anstreicher, and S. Burer · 2016
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…