Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization
From MaRDI portal
(Redirected from Publication:463723)
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.
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
Cites work
- Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- On the mapping of quadratic forms
- Robust Solutions of Uncertain Quadratic and Conic-Quadratic Problems
- Robust linear optimization under general norms.
- Robust optimization
- Second-order-cone constraints for extended trust-region subproblems
- Strong Duality in Nonconvex Quadratic Optimization with Two Quadratic Constraints
- Theory and applications of robust optimization
- Trust Region Methods
Cited in
(72)- Exact SDP relaxations for quadratic programs with bipartite graph structures
- Convex hull results on quadratic programs with non-intersecting constraints
- Extensions of the standard quadratic optimization problem: strong duality, optimality, hidden convexity and S-lemma
- Semidefinite representable reformulations for two variants of the trust-region subproblem
- Exact second-order cone programming relaxations for some nonconvex minimax quadratic optimization problems
- S-lemma with equality and its applications
- Trust region subproblem with an additional linear inequality constraint
- Online first-order framework for robust convex optimization
- An efficient algorithm for the extended trust-region subproblem with two linear constraints
- Globally solving extended trust region subproblems with two intersecting cuts
- Regularized Lagrangian duality for linearly constrained quadratic optimization and trust-region problems
- Interplay of non-convex quadratically constrained problems with adjustable robust optimization
- A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints
- A new technique to derive tight convex underestimators (sometimes envelopes)
- 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
- Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations
- Convex envelopes of separable functions over regions defined by separable functions of the same type
- On duality gap with polynomial multipliers for polynomial optimization problems
- On the tightness of SDP relaxations of QCQPs
- A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs
- On local non-global minimizers of quadratic optimization problem with a single quadratic constraint
- 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
- 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
- Generalized Lagrangian duality for nonconvex polynomial programs with polynomial multipliers
- Quadratic programs with hollows
- An active-set algorithm for norm constrained quadratic problems
- Further development in convex conic reformulation of geometric nonconvex conic optimization problems
- Novel reformulations and efficient algorithms for the generalized trust region subproblem
- A block Lanczos method for the extended trust-region subproblem
- Centered solutions for uncertain linear equations
- The trust region subproblem and semidefinite programming*
- 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
- 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
- New results on eliminating the duality gap of the second-order-cone reformulation for extended trust-region subproblem with two intersecting cuts
- 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
- 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
- Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained quadratic optimization problems
- 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
- On globally solving the extended trust-region subproblems
- Solving trust-region subproblem augmented with linear inequality constraints
- 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
- Accelerated first-order methods for a class of semidefinite programs
- (Global) optimization: historical notes and recent developments
- A gentle, geometric introduction to copositive optimization
- Local nonglobal minima for solving large-scale extended trust-region subproblems
- Quadratically adjustable robust linear optimization with inexact data via generalized S-lemma: exact second-order cone program reformulations
- New Results on Quadratic Minimization
- Zero-scale asymptotic functions and quasiconvex 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
- Exactness Conditions for Semidefinite Programming Relaxations of Generalization of the Extended Trust Region Subproblem
- A trust region method for finding second-order stationarity in linearly constrained nonconvex optimization
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)
