Hidden convexity in some nonconvex quadratically constrained quadratic programming

DOI10.1007/BF02592331zbMath0851.90087MaRDI QIDQ1919813

Aharon Ben-Tal, Marc Teboulle

Publication date: 8 December 1996

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

zbMATH Keywords

indefinite quadratic objective functioninterior-point polynomial-time algorithms

Mathematics Subject Classification ID

Quadratic programming (90C20)

Related Items (66)

On the complexity of quadratic programming with two quadratic constraints ⋮ Convex hull of two quadratic or a conic quadratic and a quadratic inequality ⋮ On box-constrained total least squares problem ⋮ On Convex Hulls of Epigraphs of QCQPs ⋮ On the tightness of SDP relaxations of QCQPs ⋮ A linear-time algorithm for trust region problems ⋮ A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming ⋮ An Algorithm for Maximizing a Convex Function Based on Its Minimum ⋮ SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices ⋮ Partial stabilizability and hidden convexity of indefinite LQ problem ⋮ Difference of convex functions optimization algorithms (DCA) for globally minimizing nonconvex quadratic forms on Euclidean balls and spheres ⋮ An efficient algorithm for solving the generalized trust region subproblem ⋮ Double well potential function and its optimization in the \(N\)-dimensional real space. I ⋮ Double well potential function and its optimization in the \(N\)-dimensional real space. II ⋮ On the augmented subproblems within sequential methods for nonlinear programming ⋮ Globally Solving the Trust Region Subproblem Using Simple First-Order Methods ⋮ On Lagrangian duality gap of quadratic fractional programming with a two-sided quadratic constraint ⋮ Second-order analysis of penalty function ⋮ A survey of hidden convex optimization ⋮ Canonical Dual Approach for Minimizing a Nonconvex Quadratic Function over a Sphere ⋮ Kalman-Popov-Yakubovich Lemma and the \(S\)-procedure: a historical essay ⋮ A Second-Order Cone Based Approach for Solving the Trust-Region Subproblem and Its Variants ⋮ A linear-time algorithm for the trust region subproblem based on hidden convexity ⋮ Theorems of the alternative for multivalued mappings and applications to mixed convex \(\backslash\) concave systems of inequalities ⋮ On Local Non-Global Minimizers of Quadratic Optimization Problem with a Single Quadratic Constraint ⋮ An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem ⋮ Implicit Regularity and Linear Convergence Rates for the Generalized Trust-Region Subproblem ⋮ Effective algorithms for separable nonconvex quadratic programming with one quadratic and box constraints ⋮ On zero duality gap in nonconvex quadratic programming problems ⋮ Effective algorithms for optimal portfolio deleveraging problem with cross impact ⋮ An Approximation Scheme for Distributionally Robust Nonlinear Optimization ⋮ Hidden conic quadratic representation of some nonconvex quadratic optimization problems ⋮ Convexity of quadratic transformations and its use in control and optimization ⋮ Minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint ⋮ Strong duality for generalized trust region subproblem: S-lemma with interval bounds ⋮ Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices ⋮ On the convexity of a class of quadratic mappings and its application to the problem of finding the smallest ball enclosing a given intersection of balls ⋮ Global optimization of truss topology with discrete bar areas. I: Theory of relaxed problems ⋮ A geometric characterization of strong duality in nonconvex quadratic programming with linear and nonconvex quadratic constraints ⋮ Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint ⋮ LMI approximations for the radius of the intersection of ellipsoids: Survey. ⋮ The trust region subproblem and semidefinite programming* ⋮ Tractable ADMM schemes for computing KKT points and local minimizers for \(\ell_0\)-minimization problems ⋮ Some results for quadratic problems with one or two quadratic constraints ⋮ Convexity/Nonconvexity Certificates for Power Flow Analysis ⋮ Mathematical properties of optimization problems defined by positively homogeneous functions ⋮ Maximizing the sum of a generalized Rayleigh quotient and another Rayleigh quotient on the unit sphere via semidefinite programming ⋮ On Barrier and Modified Barrier Multigrid Methods for Three-Dimensional Topology Optimization ⋮ Simultaneous diagonalization under weak regularity and a characterization ⋮ Computational Methods for Solving Nonconvex Block-Separable Constrained Quadratic Problems ⋮ On Conic Relaxations of Generalization of the Extended Trust Region Subproblem ⋮ A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid ⋮ Hidden Convexity in the l0 Pseudonorm ⋮ Primal-Dual Interior Point Multigrid Method for Topology Optimization ⋮ A variational model with hybrid hyper-Laplacian priors for Retinex ⋮ On Robust Solutions to Uncertain Linear Complementarity Problems and their Variants ⋮ Novel Reformulations and Efficient Algorithms for the Generalized Trust Region Subproblem ⋮ Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming ⋮ A simple duality proof in convex quadratic programming with a quadratic constraint, and some applications ⋮ Matrix pencils and existence conditions for quadratic programming with a sign-indefinite quadratic equality constraint ⋮ Second-order global optimality conditions for convex composite optimization ⋮ A Linear-Time Algorithm for Generalized Trust Region Subproblems ⋮ Bounds for global optimization of capacity expansion and flow assignment problems ⋮ Hidden invariant convexity for global and conic-intersection optimality guarantees in discrete-time optimal control ⋮ The generalized trust region subproblem: solution complexity and convex hull results ⋮ S-lemma with equality and its applications

Cites Work

• Unnamed Item
• On a subproblem of trust region algorithms for constrained optimization
• Least squares with a quadratic constraint
• Quadratically constrained least squares and quadratic problems
• On affine scaling algorithms for nonconvex quadratic programming
• Duallity and sensitivity in nonconvex quadratic optimization over an ellipsoid
• Über das Vorkommen definiter und semidefiniter Formen in Scharen quadratischer Formen
• Duality in Homogeneous Programming
• Matrix Analysis
• A tight bound for the boolean quadratic optimization problem and its use in a branch and bound algorithm¹
• Computing Optimal Locally Constrained Steps
• Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations
• Convex Analysis

This page was built for publication: Hidden convexity in some nonconvex quadratically constrained quadratic programming