On the Slater condition for the SDP relaxations of nonconvex sets

DOI10.1016/S0167-6377(01)00093-1zbMath0993.90075OpenAlexW2089914558MaRDI QIDQ1604046

Tunçel, Levent

Publication date: 3 July 2002

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(01)00093-1

zbMATH Keywords

combinatorial optimizationdimensionnonconvex optimizationinterior-point methodssemidefinite programming relaxationsfeasible solutionsaffine hull

Mathematics Subject Classification ID

Semidefinite programming (90C22) Convex programming (90C25) Interior-point methods (90C51) Combinatorial optimization (90C27)

Related Items

Conic approximation to quadratic optimization with linear complementarity constraints ⋮ Quadratic programs with hollows ⋮ SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning ⋮ Interplay of non-convex quadratically constrained problems with adjustable robust optimization ⋮ Strong duality and minimal representations for cone optimization ⋮ Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms ⋮ Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs ⋮ Partitioning through projections: strong SDP bounds for large graph partition problems ⋮ Optimization under uncertainty and risk: quadratic and copositive approaches ⋮ A New Approach to the Stable Set Problem Based on Ellipsoids ⋮ Preprocessing and Regularization for Degenerate Semidefinite Programs ⋮ On Solving the Quadratic Shortest Path Problem ⋮ FLOW ON DATA NETWORK AND A POSITIVE SEMIDEFINITE REPRESENTABLE DELAY FUNCTION

Cites Work

• Unnamed Item
• Unnamed Item
• Regularizing the abstract convex program
• Semidefinite programming relaxation for nonconvex quadratic programs
• Semidefinite programming relaxations for the quadratic assignment problem
• Approximating quadratic programming with bound and quadratic constraints
• Semidefinite programming relaxations for the graph partitioning problem
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Strong Duality for Semidefinite Programming
• Semidefinite relaxation and nonconvex quadratic optimization
• Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets
• Discretization and localization in successive convex relaxation methods for nonconvex quadratic optimization.
• Restarting after branching in the SDP approach to MAX-CUT and similar combinatorial optimization problems