Second order cone programming relaxation of nonconvex quadratic optimization problems

DOI10.1080/10556780108805819zbMath1109.90327OpenAlexW2043677016MaRDI QIDQ2770189

Sunyoung Kim, Kojima, Masakazu

Publication date: 7 February 2002

Published in: Optimization Methods and Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/10556780108805819

zbMATH Keywords

Global optimizationNonconvex quadratic programPrimal-dual interior-point methodLift-and-project convex relaxation methodSecond-order-cone program

Mathematics Subject Classification ID

Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20)

Related Items

Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems, A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming, Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations, Generating cutting planes for the semidefinite relaxation of quadratic programs, Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem, SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances, Partial Lasserre relaxation for sparse Max-Cut, Disjunctive Cuts for Non-convex Mixed Integer Quadratically Constrained Programs, A new global algorithm for max-cut problem with chordal sparsity, Bounds for Random Binary Quadratic Programs, A simultaneous diagonalization based SOCP relaxation for portfolio optimization with an orthogonality constraint, Nonconvex quadratically constrained quadratic programming: Best D.C. Decompositions and their SDP representations, Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations, Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques, Portfolio selection with the effect of systematic risk diversification: formulation and accelerated gradient algorithm, A branch-and-cut algorithm using polar cuts for solving nonconvex quadratic programming problems, A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs, Unnamed Item, Relaxations and discretizations for the pooling problem, How to convexify the intersection of a second order cone and a nonconvex quadratic, Second Order Cone Programming Relaxation of a Positive Semidefinite Constraint, Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods, Lagrangian decomposition of block-separable mixed-integer all-quadratic programs, A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs, Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization, A globally convergent non-interior point algorithm with full Newton step for second-order cone programming, An SOCP relaxation based branch-and-bound method for generalized trust-region subproblem, Exact dual bounds for some nonconvex minimax quadratic optimization problems, On polyhedral and second-order cone decompositions of semidefinite optimization problems, Faster, but weaker, relaxations for quadratically constrained quadratic programs, Conic relaxation approaches for equal deployment problems, Optimal trade-off portfolio selection between total risk and maximum relative marginal risk^†, Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming, Template polyhedra and bilinear optimization, On the Composition of Convex Envelopes for Quadrilinear Terms, A simultaneous diagonalization based SOCP relaxation for convex quadratic programs with linear complementarity constraints, New SOCP relaxation and branching rule for bipartite bilinear programs, A new SOCP relaxation of nonconvex quadratic programming problems with a few negative eigenvalues

Uses Software

• SDPA
• SeDuMi
• SDPT3

Cites Work

• Unnamed Item
• Dual quadratic estimates in polynomial and Boolean programming
• A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique
• A collection of test problems for constrained global optimization algorithms
• A new technique for generating quadratic programming test problems
• Semidefinite programming relaxation for nonconvex quadratic programs
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite relaxation and nonconvex quadratic optimization
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• A Spectral Bundle Method for Semidefinite Programming
• Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets