A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
From MaRDI portal
Publication:263189
DOI10.1007/s10107-015-0874-5zbMath1342.90123OpenAlexW2083411653MaRDI QIDQ263189
Kim-Chuan Toh, Sunyoung Kim, Kojima, Masakazu
Publication date: 4 April 2016
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-015-0874-5
iterative solverbisection methodLagrangian-conic relaxationlinearly constrained quadratic optimization problems with complementarity constraints
Convex programming (90C25) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20)
Related Items (31)
Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints ⋮ Exactness conditions for an SDP relaxation of the extended trust region problem ⋮ Conic approximation to quadratic optimization with linear complementarity constraints ⋮ Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures ⋮ Facial Reduction and Partial Polyhedrality ⋮ SDP-based branch-and-bound for non-convex quadratic integer optimization ⋮ Misspecified nonconvex statistical optimization for sparse phase retrieval ⋮ A Geometrical Analysis on Convex Conic Reformulations of Quadratic and Polynomial Optimization Problems ⋮ A regularization-patching dual quaternion optimization method for solving the hand-eye calibration problem ⋮ Conic formulation of QPCCs applied to truly sparse QPs ⋮ A matrix nonconvex relaxation approach to unconstrained binary polynomial programs ⋮ Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming ⋮ Amenable cones: error bounds without constraint qualifications ⋮ Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations ⋮ ADMM for the SDP relaxation of the QAP ⋮ An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints ⋮ Binary quadratic optimization problems that are difficult to solve by conic relaxations ⋮ A robust Lagrangian-DNN method for a class of quadratic optimization problems ⋮ Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems ⋮ On construction of upper and lower bounds for the HOMO-LUMO spectral gap ⋮ Second order cone constrained convex relaxations for nonconvex quadratically constrained quadratic programming ⋮ A proximal DC approach for quadratic assignment problem ⋮ Polyhedral approximations of the semidefinite cone and their application ⋮ Algorithm 996 ⋮ $L_p$-norm Regularization Algorithms for Optimization Over Permutation Matrices ⋮ An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs ⋮ Completely Positive Tensors: Properties, Easily Checkable Subclasses, and Tractable Relaxations ⋮ A Newton-bracketing method for a simple conic optimization problem ⋮ Copositive Relaxation Beats Lagrangian Dual Bounds in Quadratically and Linearly Constrained Quadratic Optimization Problems ⋮ Completely positive reformulations for polynomial optimization ⋮ On Degenerate Doubly Nonnegative Projection Problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- Extension of completely positive cone relaxation to moment cone relaxation for polynomial optimization
- Erratum to: ``On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets
- Alternating direction augmented Lagrangian methods for semidefinite programming
- Copositive and semidefinite relaxations of the quadratic assignment problem
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Optimizing a polyhedral-semidefinite relaxation of completely positive programs
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- On the copositive representation of binary and continuous nonconvex quadratic programs
- Approximation of the Stability Number of a Graph via Copositive Programming
- Hankel Matrix Rank Minimization with Applications to System Identification and Realization
- A Newton-CG Augmented Lagrangian Method for Semidefinite Programming
- Cone-valued maps in optimization
- Rigorous Error Bounds for the Optimal Value in Semidefinite Programming
- Some NP-complete problems in quadratic and nonlinear programming
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- CSDP, A C library for semidefinite programming
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- On Doubly Positive Semidefinite Programming Relaxations
- An Adaptive Linear Approximation Algorithm for Copositive Programs
- A Convergent 3-Block SemiProximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type Constraints
- A Quadratically Constrained Quadratic Optimization Model for Completely Positive Cone Programming
- The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
This page was built for publication: A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
