Polyhedral approximations of the semidefinite cone and their application
From MaRDI portal
Publication:2028478
Abstract: We develop techniques to construct a series of sparse polyhedral approximations of the semidefinite cone. Motivated by the semidefinite (SD) bases proposed by Tanaka and Yoshise (2018), we propose a simple expansion of SD bases so as to keep the sparsity of the matrices composing it. We prove that the polyhedral approximation using our expanded SD bases contains the set of all diagonally dominant matrices and is contained in the set of all scaled diagonally dominant matrices. We also prove that the set of all scaled diagonally dominant matrices can be expressed using an infinite number of expanded SD bases. We use our approximations as the initial approximation in cutting plane methods for solving a semidefinite relaxation of the maximum stable set problem. It is found that the proposed methods with expanded SD bases are significantly more efficient than methods using other existing approximations or solving semidefinite relaxation problems directly.
Recommendations
- On polyhedral approximations of the positive semidefinite cone
- Semidefinite programming and integer programming
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones
- On the accuracy of uniform polyhedral approximations of the copositive cone
Cites work
- A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems
- A cutting plane algorithm for semi-definite programming problems with applications to failure discriminant analysis
- A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
- A projected gradient algorithm for solving the maxcut SDP relaxation
- A Quadratically Constrained Quadratic Optimization Model for Completely Positive Cone Programming
- A robust Lagrangian-DNN method for a class of quadratic optimization problems
- A semidefinite programming based polyhedral cut and price approach for the maxcut problem
- A unifying framework for several cutting plane methods for semidefinite programming
- An iterative criterion for \(H\)-matrices
- Approximation of the stability number of a graph via copositive programming
- Cones of diagonally dominant matrices
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- Elementare Theorie der konvexen Polyeder
- Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
- Facial reduction algorithms for conic optimization problems
- Handbook of semidefinite programming. Theory, algorithms, and applications
- scientific article; zbMATH DE number 47926 (Why is no real title available?)
- scientific article; zbMATH DE number 1234104 (Why is no real title available?)
- scientific article; zbMATH DE number 734901 (Why is no real title available?)
- scientific article; zbMATH DE number 1182569 (Why is no real title available?)
- scientific article; zbMATH DE number 1757962 (Why is no real title available?)
- Implementation and evaluation of SDPA 6.0 (Semidefinite Programming Algorithm 6.0)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Lagrangian-conic relaxations. I: A unified framework and its applications to quadratic optimization problems
- LP-based tractable subcones of the semidefinite plus nonnegative cone
- On a linear-programming, combinatorial approach to the traveling-salesman problem
- On factor width and symmetric \(H\)-matrices
- On the computational complexity of membership problems for the completely positive cone and its dual
- On the copositive representation of binary and continuous nonconvex quadratic programs
- Optimization over structured subsets of positive semidefinite matrices via column generation
- Outline of an algorithm for integer solutions to linear programs
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Polyhedral approximation in mixed-integer convex optimization
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Semidefinite optimization
- Semidefinite Optimization and Convex Algebraic Geometry
- Solution of a Large-Scale Traveling-Salesman Problem
- Some NP-complete problems in quadratic and nonlinear programming
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Cited in
(10)- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Sparse PSD approximation of the PSD cone
- Semidefinite descriptions of cones defining spectral mask constraints
- New approaches for optimizing over the semimetric polytope
- On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones
- On polyhedral approximations of the positive semidefinite cone
- Hyperbolic Relaxation of $k$-Locally Positive Semidefinite Matrices
- Semidefinite approximations of conical hulls of measured sets
- Evaluating approximations of the semidefinite cone with trace normalized distance
- Instance-specific linear relaxations of semidefinite optimization problems
This page was built for publication: Polyhedral approximations of the semidefinite cone and their application
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2028478)
