Optimization over structured subsets of positive semidefinite matrices via column generation
From MaRDI portal
Publication:1751222
Abstract: We develop algorithms for inner approximating the cone of positive semidefinite matrices via linear programming and second order cone programming. Starting with an initial linear algebraic approximation suggested recently by Ahmadi and Majumdar, we describe an iterative process through which our approximation is improved at every step. This is done using ideas from column generation in large-scale linear and integer programming. We then apply these techniques to approximate the sum of squares cone in a nonconvex polynomial optimization setting, and the copositive cone for a discrete optimization problem.
Recommendations
Cites work
- A comparison of the Delsarte and Lovász bounds
- A new bound for Pólya's theorem with applications to polynomials positive on polyhedra.
- A semidefinite programming based polyhedral cut and price approach for the maxcut problem
- An effective branch-and-bound algorithm for convex quadratic integer programming
- Applications of second-order cone programming
- Approximation of the stability number of a graph via copositive programming
- Branch-and-price: Column generation for solving huge integer programs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Cones of diagonally dominant matrices
- Copositive programming
- Enhancing RLT relaxations via a new class of semidefinite cuts
- Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
- Extremal positive semidefinite forms
- Global optimization with polynomials and the problem of moments
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 1489808 (Why is no real title available?)
- scientific article; zbMATH DE number 1490041 (Why is no real title available?)
- Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions
- On Polyhedral Approximations of the Second-Order Cone
- On the Shannon capacity of a graph
- Second-order cone programming
- Semidefinite programming relaxations for semialgebraic problems
- Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
- Some applications of polynomial optimization in operations research and real-time decision making
- Some NP-complete problems in quadratic and nonlinear programming
- The difference between \(5\times 5\) doubly nonnegative and completely positive matrices
Cited in
(23)- An optimization problem on subsets of the symmetric positive-semidefinite matrices
- LP-based tractable subcones of the semidefinite plus nonnegative cone
- Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods
- Polyhedral approximations of the semidefinite cone and their application
- Decomposed structured subsets for semidefinite and sum-of-squares optimization
- Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems
- Generating valid linear inequalities for nonlinear programs via sums of squares
- Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices
- On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones
- Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes
- Sum of squares basis pursuit with linear and second order cone programming
- Scalable Optimization Methods for Incorporating Spatiotemporal Fractionation into Intensity-Modulated Radiotherapy Planning
- A Scalable Algorithm for Sparse Portfolio Selection
- Bounding extrema over global attractors using polynomial optimisation
- Computing the best approximation over the intersection of a polyhedral set and the doubly nonnegative cone
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- LMI Approximations for Cones of Positive Semidefinite Forms
- Evaluating approximations of the semidefinite cone with trace normalized distance
- A Sum of Squares Characterization of Perfect Graphs
- Tighter bounds on transient moments of stochastic chemical systems
- Regional stability conditions for recurrent neural network-based control systems
- A predictor-corrector algorithm for semidefinite programming that uses the factor width cone
- A matrix generation approach for eigenvalue optimization
This page was built for publication: Optimization over structured subsets of positive semidefinite matrices via column generation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1751222)
