Copositive Relaxation Beats Lagrangian Dual Bounds in Quadratically and Linearly Constrained Quadratic Optimization Problems
From MaRDI portal
Publication:5501200
DOI10.1137/140987997zbMath1317.90224OpenAlexW2131712693MaRDI QIDQ5501200
Publication date: 3 August 2015
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/21df1106f50b79e31696e26139e982cfa42ca22b
nonconvex optimizationpolynomial optimizationcopositive matricesglobal optimality conditionquadratically constrained problemapproximation hierarchies
Nonconvex programming, global optimization (90C26) Quadratic programming (90C20) Optimality conditions and duality in mathematical programming (90C46)
Related Items
Exactness conditions for an SDP relaxation of the extended trust region problem ⋮ Interplay of non-convex quadratically constrained problems with adjustable robust optimization ⋮ A fresh CP look at mixed-binary QPs: new formulations and relaxations ⋮ Optimization under uncertainty and risk: quadratic and copositive approaches ⋮ (Global) optimization: historical notes and recent developments ⋮ Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems ⋮ New bounds for nonconvex quadratically constrained quadratic programming ⋮ Kronecker Product Constraints with an Application to the Two-Trust-Region Subproblem ⋮ Completely positive and completely positive semidefinite tensor relaxations for polynomial optimization ⋮ Conic formulation of QPCCs applied to truly sparse QPs ⋮ Extensions of the standard quadratic optimization problem: strong duality, optimality, hidden convexity and S-lemma ⋮ An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints ⋮ A new algorithm for concave quadratic programming ⋮ Convexifiability of continuous and discrete nonnegative quadratic programs for gap-free duality ⋮ Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations ⋮ Copositivity for second-order optimality conditions in general smooth optimization problems ⋮ Strong duality for general quadratic programs with quadratic equality constraints
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
- On conic QPCCs, conic QCQPs and completely positive programs
- On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods
- Copositive optimization -- recent developments and applications
- On the computational complexity of membership problems for the completely positive cone and its dual
- Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization
- Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons
- Faster, but weaker, relaxations for quadratically constrained quadratic programs
- On extensions of the Frank-Wolfe theorems
- Semidefinite programming relaxation for nonconvex quadratic programs
- On the complexity of approximating a KKT point of quadratic programming
- A Frank--Wolfe type theorem for convex polynomial programs
- A fresh CP look at mixed-binary QPs: new formulations and relaxations
- Globally solving nonconvex quadratic programming problems via completely positive programming
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- A note on Burer's copositive representation of mixed-binary QPs
- Narrowing the difficulty gap for the Celis-Dennis-Tapia problem
- On the copositive representation of binary and continuous nonconvex quadratic programs
- Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem
- Algorithmic copositivity detection by simplicial partition
- Partial Lagrangian relaxation for general quadratic programming
- Global Optimization with Polynomials and the Problem of Moments
- Copositive Programming
- New results on the cp-rank and related properties of co(mpletely )positive matrices
- An improved characterisation of the interior of the completely positive cone
- KKT Solution and Conic Relaxation for Solving Quadratically Constrained Quadratic Programming Problems
- New Lower Bounds and Asymptotics for the cp-Rank
- Alternative Theorems for Quadratic Inequality Systems and Global Quadratic Optimization
- Semidefinite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization
- Strong Duality for the CDT Subproblem: A Necessary and Sufficient Condition
- Some NP-complete problems in quadratic and nonlinear programming
- Robust Solutions of Uncertain Quadratic and Conic-Quadratic Problems
- An Adaptive Linear Approximation Algorithm for Copositive Programs
- Strong Duality in Nonconvex Quadratic Optimization with Two Quadratic Constraints
