Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization

DOI10.1007/S10107-013-0716-2zbMATH Open1297.90105DBLPjournals/mp/JeyakumarL14arXiv1309.3000OpenAlexW2094753536WikidataQ59241515 ScholiaQ59241515MaRDI QIDQ463723FDOQ463723

Authors: V. Jeyakumar, G. Li 

Publication date: 17 October 2014

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: The trust-region problem, which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having extra linear constraints. This paper shows that two useful and powerful features of the classical trust-region problem continue to hold for an extended trust-region problem with linear inequality constraints under a new dimension condition. First, we establish that the class of extended trust-region problems has an exact SDP-relaxation, which holds without the Slater constraint qualification. This is achieved by proving that a system of quadratic and affine functions involved in the model satisfies a range-convexity whenever the dimension condition is fulfilled. Second, we show that the dimension condition together with the Slater condition ensures that a set of combined first and second-order Lagrange multiplier conditions is necessary and sufficient for global optimality of the extended trust-region problem and consequently for strong duality. Finally, we show that the dimension condition is easily satisfied for the extended trust-region model that arises from the reformulation of a robust least squares problem (LSP) as well as a robust second order cone programming model problem (SOCP) as an equivalent semi-definite linear programming problem. This leads us to conclude that, under mild assumptions, solving a robust (LSP) or (SOCP) under matrix-norm uncertainty or polyhedral uncertainty is equivalent to solving a SDP and so, their solutions can be validated in polynomial time.

Full work available at URL: https://arxiv.org/abs/1309.3000

Recommendations

• Exactness conditions for an SDP relaxation of the extended trust region problem
• On Conic Relaxations of Generalization of the Extended Trust Region Subproblem
• The trust region subproblem and semidefinite programming*
• New Results on Quadratic Minimization
• On globally solving the extended trust-region subproblems

Mathematics Subject Classification ID

Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22) Problems with incomplete information (optimization) (49N30)

Cites Work

• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Theory and applications of robust optimization
• Robust optimization
• Trust Region Methods
• Strong Duality in Nonconvex Quadratic Optimization with Two Quadratic Constraints
• On the mapping of quadratic forms
• Robust linear optimization under general norms.
• Second-order-cone constraints for extended trust-region subproblems
• Robust Solutions of Uncertain Quadratic and Conic-Quadratic Problems
• Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming

Cited In (72)

• Exact second-order cone programming relaxations for some nonconvex minimax quadratic optimization problems
• Extensions of the standard quadratic optimization problem: strong duality, optimality, hidden convexity and S-lemma
• S-lemma with equality and its applications
• Online first-order framework for robust convex optimization
• Trust region subproblem with an additional linear inequality constraint
• An efficient algorithm for the extended trust-region subproblem with two linear constraints
• Globally solving extended trust region subproblems with two intersecting cuts
• Interplay of non-convex quadratically constrained problems with adjustable robust optimization
• Regularized Lagrangian duality for linearly constrained quadratic optimization and trust-region problems
• A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints
• Exact dual bounds for some nonconvex minimax quadratic optimization problems
• Primal or dual strong-duality in nonconvex optimization and a class of quasiconvex problems having zero duality gap
• On minimizing difference of a SOS-convex polynomial and a support function over a SOS-concave matrix polynomial constraint
• Narrowing the difficulty gap for the Celis-Dennis-Tapia problem
• A necessary and sufficient condition of convexity for SOC reformulation of trust-region subproblem with two intersecting cuts
• On duality gap with polynomial multipliers for polynomial optimization problems
• Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations
• On local non-global minimizers of quadratic optimization problem with a single quadratic constraint
• Convex envelopes of separable functions over regions defined by separable functions of the same type
• A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs
• On the tightness of SDP relaxations of QCQPs
• Convexifiability of continuous and discrete nonnegative quadratic programs for gap-free duality
• A second-order cone based approach for solving the trust-region subproblem and its variants
• An SOCP relaxation based branch-and-bound method for generalized trust-region subproblem
• Exactness conditions for an SDP relaxation of the extended trust region problem
• How to convexify the intersection of a second order cone and a nonconvex quadratic
• Generalized Lagrangian duality for nonconvex polynomial programs with polynomial multipliers
• Quadratic programs with hollows
• Novel reformulations and efficient algorithms for the generalized trust region subproblem
• An active-set algorithm for norm constrained quadratic problems
• A block Lanczos method for the extended trust-region subproblem
• The trust region subproblem and semidefinite programming*
• Centered solutions for uncertain linear equations
• The equivalence of optimal perspective formulation and Shor's SDP for quadratic programs with indicator variables
• On indefinite quadratic optimization over the intersection of balls and linear constraints
• A copositive Farkas lemma and minimally exact conic relaxations for robust quadratic optimization with binary and quadratic constraints
• Quadratic optimization with two ball constraints
• On Conic Relaxations of Generalization of the Extended Trust Region Subproblem
• Characterizing Convexity of Images for Quadratic-Linear Mappings with Applications in Nonconvex Quadratic Optimization
• On Convex Hulls of Epigraphs of QCQPs
• Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained quadratic optimization problems
• A note on polynomial solvability of the CDT problem
• A two-variable approach to the two-trust-region subproblem
• Strengthened SDP relaxation for an extended trust region subproblem with an application to optimal power flow
• Solving trust-region subproblem augmented with linear inequality constraints
• On globally solving the extended trust-region subproblems
• Strong duality in minimizing a quadratic form subject to two homogeneous quadratic inequalities over the unit sphere
• Globally and superlinearly convergent trust-region algorithm for convex \(SC^ 1\)-minimization problems and its application to stochastic programs
• An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints
• A gentle, geometric introduction to copositive optimization
• New Results on Quadratic Minimization
• Zero-scale asymptotic functions and quasiconvex optimization
• Local nonglobal minima for solving large-scale extended trust-region subproblems
• A trust region method for finding second-order stationarity in linearly constrained nonconvex optimization
• Finding second-order stationary points in constrained minimization: a feasible direction approach
• Refined bounds on the convergence of block Lanczos method for extended trust-region subproblem
• Exact SDP relaxations for quadratic programs with bipartite graph structures
• Semidefinite representable reformulations for two variants of the trust-region subproblem
• A new technique to derive tight convex underestimators (sometimes envelopes)
• A new global optimization algorithm for mixed-integer quadratically constrained quadratic fractional programming problem
• On exact and inexact RLT and SDP-RLT relaxations of quadratic programs with box constraints
• Further development in convex conic reformulation of geometric nonconvex conic optimization problems
• Nonconvex homogeneous optimization: a general framework and optimality conditions of first and second-order
• Optimal neural network approximation of Wasserstein gradient direction via convex optimization
• New results on eliminating the duality gap of the second-order-cone reformulation for extended trust-region subproblem with two intersecting cuts
• Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problems
• KKT-based primal-dual exactness conditions for the Shor relaxation
• Accelerated first-order methods for a class of semidefinite programs
• (Global) optimization: historical notes and recent developments
• Quadratically adjustable robust linear optimization with inexact data via generalized S-lemma: exact second-order cone program reformulations
• Exactness Conditions for Semidefinite Programming Relaxations of Generalization of the Extended Trust Region Subproblem
• Convex hull results on quadratic programs with non-intersecting constraints

This page was built for publication: Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q463723)