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

DOI10.1007/s10107-013-0716-2zbMath1297.90105arXiv1309.3000OpenAlexW2094753536WikidataQ59241515 ScholiaQ59241515MaRDI QIDQ463723

Vaithilingam Jeyakumar, Guoyin Li

Publication date: 17 October 2014

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

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

Mathematics Subject Classification ID

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

Related Items (58)

An efficient algorithm for the extended trust-region subproblem with two linear constraints ⋮ On duality gap with polynomial multipliers for polynomial optimization problems ⋮ Trust region subproblem with an additional linear inequality constraint ⋮ On Convex Hulls of Epigraphs of QCQPs ⋮ On the tightness of SDP relaxations of QCQPs ⋮ An active-set algorithm for norm constrained quadratic problems ⋮ A necessary and sufficient condition of convexity for SOC reformulation of trust-region subproblem with two intersecting cuts ⋮ Convex envelopes of separable functions over regions defined by separable functions of the same type ⋮ Exactness conditions for an SDP relaxation of the extended trust region problem ⋮ Unnamed Item ⋮ A fast eigenvalue approach for solving the trust region subproblem with an additional linear inequality ⋮ Quadratic programs with hollows ⋮ Refined bounds on the convergence of block Lanczos method for extended trust-region subproblem ⋮ On globally solving the extended trust-region subproblems ⋮ 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 ⋮ 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 ⋮ Primal or dual strong-duality in nonconvex optimization and a class of quasiconvex problems having zero duality gap ⋮ A Second-Order Cone Based Approach for Solving the Trust-Region Subproblem and Its Variants ⋮ Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problems ⋮ On Local Non-Global Minimizers of Quadratic Optimization Problem with a Single Quadratic Constraint ⋮ KKT-based primal-dual exactness conditions for the Shor relaxation ⋮ (Global) optimization: historical notes and recent developments ⋮ Finding second-order stationary points in constrained minimization: a feasible direction approach ⋮ Convex hull results on quadratic programs with non-intersecting constraints ⋮ A new technique to derive tight convex underestimators (sometimes envelopes) ⋮ Quadratically adjustable robust linear optimization with inexact data via generalized S-lemma: exact second-order cone program reformulations ⋮ Exact SDP relaxations for quadratic programs with bipartite graph structures ⋮ Exact Second-Order Cone Programming Relaxations for Some Nonconvex Minimax Quadratic Optimization Problems ⋮ A Trust Region Method for Finding Second-Order Stationarity in Linearly Constrained Nonconvex Optimization ⋮ Online First-Order Framework for Robust Convex Optimization ⋮ A Block Lanczos Method for the Extended Trust-Region Subproblem ⋮ Globally solving extended trust region subproblems with two intersecting cuts ⋮ Extensions of the standard quadratic optimization problem: strong duality, optimality, hidden convexity and S-lemma ⋮ A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs ⋮ An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints ⋮ Local nonglobal minima for solving large-scale extended trust-region subproblems ⋮ On minimizing difference of a SOS-convex polynomial and a support function over a SOS-concave matrix polynomial constraint ⋮ How to convexify the intersection of a second order cone and a nonconvex quadratic ⋮ Generalized Lagrangian duality for nonconvex polynomial programs with polynomial multipliers ⋮ Convexifiability of continuous and discrete nonnegative quadratic programs for gap-free duality ⋮ A Note on Polynomial Solvability of the CDT Problem ⋮ Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations ⋮ An SOCP relaxation based branch-and-bound method for generalized trust-region subproblem ⋮ Centered solutions for uncertain linear equations ⋮ A Two-Variable Approach to the Two-Trust-Region Subproblem ⋮ Exact dual bounds for some nonconvex minimax quadratic optimization problems ⋮ A copositive Farkas lemma and minimally exact conic relaxations for robust quadratic optimization with binary and quadratic constraints ⋮ On Conic Relaxations of Generalization of the Extended Trust Region Subproblem ⋮ Strong duality in minimizing a quadratic form subject to two homogeneous quadratic inequalities over the unit sphere ⋮ Novel Reformulations and Efficient Algorithms for the Generalized Trust Region Subproblem ⋮ Quadratic optimization with two ball constraints ⋮ Copositive Relaxation Beats Lagrangian Dual Bounds in Quadratically and Linearly Constrained Quadratic Optimization Problems ⋮ Characterizing Convexity of Images for Quadratic-Linear Mappings with Applications in Nonconvex Quadratic Optimization ⋮ A gentle, geometric introduction to copositive optimization ⋮ Narrowing the difficulty gap for the Celis-Dennis-Tapia problem ⋮ S-lemma with equality and its applications

Cites Work

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