Approximation hierarchies for copositive cone over symmetric cone and their comparison

Mitsuhiro Nishijima () and Kazuhide Nakata ()
Additional contact information
Mitsuhiro Nishijima: Tokyo Institute of Technology
Kazuhide Nakata: Tokyo Institute of Technology

Journal of Global Optimization, 2024, vol. 88, issue 4, No 2, 870 pages

Abstract: Abstract We first provide an inner-approximation hierarchy described by a sum-of-squares (SOS) constraint for the copositive (COP) cone over a general symmetric cone. The hierarchy is a generalization of that proposed by Parrilo (Structured semidefinite programs and semialgebraic geometry methods in Robustness and optimization, Ph.D. Thesis, California Institute of Technology, Pasadena, CA, 2000) for the usual COP cone (over a nonnegative orthant). We also discuss its dual. Second, we characterize the COP cone over a symmetric cone using the usual COP cone. By replacing the usual COP cone appearing in this characterization with the inner- or outer-approximation hierarchy provided by de Klerk and Pasechnik (SIAM J Optim 12(4):875–892, https://doi.org/10.1137/S1052623401383248 , 2002) or Yıldırım (Optim Methods Softw 27(1):155–173, https://doi.org/10.1080/10556788.2010.540014 , 2012), we obtain an inner- or outer-approximation hierarchy described by semidefinite but not by SOS constraints for the COP matrix cone over the direct product of a nonnegative orthant and a second-order cone. We then compare them with the existing hierarchies provided by Zuluaga et al. (SIAM J Optim 16(4):1076–1091, https://doi.org/10.1137/03060151X , 2006) and Lasserre (Math Program 144:265–276, https://doi.org/10.1007/s10107-013-0632-5 , 2014). Theoretical and numerical examinations imply that we can numerically increase a depth parameter, which determines an approximation accuracy, in the approximation hierarchies derived from de Klerk and Pasechnik (SIAM J Optim 12(4):875–892, https://doi.org/10.1137/S1052623401383248 , 2002) and Yıldırım (Optim Methods Softw 27(1):155–173, https://doi.org/10.1080/10556788.2010.540014 , 2012), particularly when the nonnegative orthant is small. In such a case, the approximation hierarchy derived from Yıldırım (Optim Methods Softw 27(1):155–173, https://doi.org/10.1080/10556788.2010.540014 , 2012) can yield nearly optimal values numerically. Combining the proposed approximation hierarchies with existing ones, we can evaluate the optimal value of COP programming problems more accurately and efficiently.

Keywords: Approximation hierarchy; Copositive cone; Completely positive cone; Symmetric cone; Copositive programming (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-023-01319-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:88:y:2024:i:4:d:10.1007_s10898-023-01319-3

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-023-01319-3

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().