Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices
From MaRDI portal
Publication:2301196
DOI10.1007/S10898-019-00861-3zbMATH Open1435.90114arXiv1807.00379OpenAlexW2992111132MaRDI QIDQ2301196FDOQ2301196
Authors: João Gouveia, Ting Kei Pong, Mina Saee 
Publication date: 28 February 2020
Published in: Journal of Global Optimization (Search for Journal in Brave)
Abstract: Motivated by the expressive power of completely positive programming to encode hard optimization problems, many approximation schemes for the completely positive cone have been proposed and successfully used. Most schemes are based on outer approximations, with the only inner approximations available being linear programming based methods proposed by Bundfuss and D"ur and also Y{i}ld{i}r{i}m, and a semidefinite programming based method proposed by Lasserre. In this paper, we propose the use of the cone of nonnegative scaled diagonally dominant matrices as a natural inner approximation to the completely positive cone. Using projections of this cone we derive new graph-based second-order cone approximation schemes for completely positive programming, leading to both uniform and problem-dependent hierarchies. This offers a compromise between the expressive power of semidefinite programming and the speed of linear programming based approaches. Numerical results on random problems, standard quadratic programs and the stable set problem are presented to illustrate the effectiveness of our approach.
Full work available at URL: https://arxiv.org/abs/1807.00379
Recommendations
- New approximations for the cone of copositive matrices and its dual
- Approximation of copositive programming via linear programming using second order sum of square decomposition
- Optimization over structured subsets of positive semidefinite matrices via column generation
- On the accuracy of uniform polyhedral approximations of the copositive cone
- An adaptive linear approximation algorithm for copositive programs
Approximation methods and heuristics in mathematical programming (90C59) Nonconvex programming, global optimization (90C26)
Cites Work
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Matrix Analysis
- Variational Analysis
- Convex Analysis
- On the copositive representation of binary and continuous nonconvex quadratic programs
- Approximation of the stability number of a graph via copositive programming
- An adaptive linear approximation algorithm for copositive programs
- Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
- On factor width and symmetric \(H\)-matrices
- Title not available (Why is that?)
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
- Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization
- New approximations for the cone of copositive matrices and its dual
- Copositive programming
- On the accuracy of uniform polyhedral approximations of the copositive cone
- Special issue: Selected papers of the international workshop on global optimization, GO '99. Firenze, Italy, 1999
- Optimization over structured subsets of positive semidefinite matrices via column generation
- Sum of squares basis pursuit with linear and second order cone programming
- Inner approximations of completely positive reformulations of mixed binary quadratic programs: a unified analysis
Cited In (9)
- Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
- On standard quadratic programs with exact and inexact doubly nonnegative relaxations
- On the longest chain of faces of the completely positive and copositive cones
- Title not available (Why is that?)
- A Sum of Squares Characterization of Perfect Graphs
- Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems
- An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs
- Approximation hierarchies for copositive cone over symmetric cone and their comparison
- Symmetric tensor approximation hierarchies for the completely positive cone
Uses Software
This page was built for publication: Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2301196)
