Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/93307
Title: | Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices | Authors: | Gouveia, J Pong, TK Saee, M |
Issue Date: | Feb-2020 | Source: | Journal of global optimization, Feb. 2020, v. 76, no. 2, p. 383-405 | 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 a linear programming based method proposed by Bundfuss and Dür (SIAM J Optim 20(1):30–53, 2009) and also Yıldırım (Optim Methods Softw 27(1):155–173, 2012), and a semidefinite programming based method proposed by Lasserre (Math Program 144(1):265–276, 2014). 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. | Keywords: | Completely positive cones Inner approximations Scaled diagonal dominant matrices |
Publisher: | Springer | Journal: | Journal of global optimization | ISSN: | 0925-5001 | EISSN: | 1573-2916 | DOI: | 10.1007/s10898-019-00861-3 | Rights: | © Springer Science+Business Media, LLC, part of Springer Nature 2019 This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use (https://www.springernature.com/gp/open-research/policies/accepted-manuscript-terms), but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/s10898-019-00861-3 |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Pong_Inner_Approximating_Completely.pdf | Pre-Published version | 954.41 kB | Adobe PDF | View/Open |
Page views
127
Last Week
0
0
Last month
Citations as of May 5, 2024
Downloads
52
Citations as of May 5, 2024
SCOPUSTM
Citations
8
Citations as of Apr 26, 2024
WEB OF SCIENCETM
Citations
8
Citations as of May 2, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.