More Web Proxy on the site http://driver.im/

research-article

Exploiting Constant Trace Property in Large-scale Polynomial Optimization

Authors:

Ngoc Hoang Anh Mai,

J. B. Lasserre,

Jie WangAuthors Info & Claims

ACM Transactions on Mathematical Software, Volume 48, Issue 4

Article No.: 40, Pages 1 - 39

https://doi.org/10.1145/3555309

Published: 19 December 2022 Publication History

Abstract

We prove that every semidefinite moment relaxation of a polynomial optimization problem (POP) with a ball constraint can be reformulated as a semidefinite program involving a matrix with constant trace property (CTP). As a result, such moment relaxations can be solved efficiently by first-order methods that exploit CTP, e.g., the conditional gradient-based augmented Lagrangian method. We also extend this CTP-exploiting framework to large-scale POPs with different sparsity structures. The efficiency and scalability of our framework are illustrated on some moment relaxations for various randomly generated POPs, especially second-order moment relaxations for quadratically constrained quadratic programs.

References

[1]

MOSEK ApS. 2019. The MOSEK Optimization Toolbox. Version 9.1. Retrieved from https://www.mosek.com/documentation.

[2]

Stephen Boyd, Neal Parikh, and Eric Chu. 2011. Distributed Optimization and Statistical Learning Via the Alternating Direction Method of Multipliers. Now Publishers Inc.

[3]

Samuel Burer and Renato D. C. Monteiro. 2005. Local minima and convergence in low-rank semidefinite programming. Math. Program. 103, 3 (2005), 427–444.

Digital Library

[4]

Sabine Burgdorf, Igor Klep, and Janez Povh. 2016. Optimization of Polynomials in Non-commuting Variables. Springer, Cham. DOI:

[5]

Yair Carmon and John C Duchi. 2020. First-order methods for nonconvex quadratic minimization. SIAM Rev. 62, 2 (2020), 395–436.

Digital Library

[6]

Tong Chen, Jean B. Lasserre, Victor Magron, and Edouard Pauwels. 2020. Semialgebraic optimization for Lipschitz constants of ReLU networks. Adv. Neural Inf. Process. Syst. 33 (2020).

[7]

Chris Coey, Lea Kapelevich, and Juan Pablo Vielma. 2020. Towards practical generic conic optimization. arXiv preprint arXiv:2005.01136 (2020).

[8]

Lijun Ding and Benjamin Grimmer. 2020. Revisit of spectral bundle methods: Primal-dual (sub) linear convergence rates. arXiv preprint arXiv:2008.07067 (2020).

[9]

Yoshio Ebihara, Hayato Waki, Victor Magron, Ngoc Hoang Anh Mai, Dimitri Peaucelle, and Sophie Tarbouriech. 2021. l2 induced norm analysis of discrete-time LTI systems for nonnegative input signals and its application to stability analysis of recurrent neural networks. Eur. J. Contr. 62 (2021), 99–104.

[10]

Michael Garstka, Mark Cannon, and Paul Goulart. 2021. COSMO: A conic operator splitting method for convex conic problems. J. Optim. Theor. Applic. 190, 3 (2021), 779–810.

Digital Library

[11]

Hadrien Godard, Sourour Elloumi, Amélie Lambert, Jean Maeght, and Manuel Ruiz. 2019. Novel approach towards global optimality of optimal power flow using quadratic convex optimization. In 6th International Conference on Control, Decision and Information Technologies (CoDIT). IEEE, 1227–1232.

[12]

Marjo Haarala, Kaisa Miettinen, and Marko M. Mäkelä. 2004. New limited memory bundle method for large-scale nonsmooth optimization. Optim. Meth. Softw. 19, 6 (2004), 673–692.

[13]

Napsu Haarala, Kaisa Miettinen, and Marko M. Mäkelä. 2007. Globally convergent limited memory bundle method for large-scale nonsmooth optimization. Math. Program. 109, 1 (2007), 181–205.

[14]

Christoph Helmberg, Michael L. Overton, and Franz Rendl. 2014. The spectral bundle method with second-order information. Optim. Meth. Softw. 29, 4 (2014), 855–876.

Digital Library

[15]

Christoph Helmberg and Franz Rendl. 2000. A spectral bundle method for semidefinite programming. SIAM J. Optim. 10, 3 (2000), 673–696.

Digital Library

[16]

Christoph Helmberg, Franz Rendl, Robert J. Vanderbei, and Henry Wolkowicz. 1996. An interior-point method for semidefinite programming. SIAM J. Optim. 6, 2 (1996), 342–361.

Digital Library

[17]

Didier Henrion, Milan Korda, and Jean Bernard Lasserre. 2020. The Moment-SOS Hierarchy: Lectures in Probability, Statistics, Computational Geometry, Control and Nonlinear PDEs. Vol. 4. World Scientific.

[18]

Mingyi Hong and Zhi-Quan Luo. 2017. On the linear convergence of the alternating direction method of multipliers. Math. Program. 162, 1–2 (2017), 165–199.

Digital Library

[19]

Cédric Josz, Stéphane Fliscounakis, Jean Maeght, and Patrick Panciatici. 2016. AC power flow data in MATPOWER and QCQP format: iTesla, RTE snapshots, and PEGASE. arXiv preprint arXiv:1603.01533 (2016).

[20]

Cédric Josz and Daniel K. Molzahn. 2018. Lasserre hierarchy for large scale polynomial optimization in real and complex variables. SIAM J. Optim. 28, 2 (2018), 1017–1048.

Digital Library

[21]

Napsu Karmitsa. 2007. LMBM–FORTRAN subroutines for large-scale nonsmooth minimization: User’s manual. TUCS Tech. Rep. 77, 856 (2007).

[22]

Krzysztof C. Kiwiel. 1991. A tilted cutting plane proximal bundle method for convex nondifferentiable optimization. Oper. Res. Lett. 10, 2 (1991), 75–81.

Digital Library

[23]

Igor Klep, Victor Magron, and Janez Povh. 2021. Sparse noncommutative polynomial optimization. Math. Program. 193, 2 (2022). 789–829.

[24]

Jean B. Lasserre. 2001. Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 3 (2001), 796–817.

Digital Library

[25]

Jean B. Lasserre. 2006. Convergent SDP-relaxations in polynomial optimization with sparsity. SIAM J. Optim. 17, 3 (2006), 822–843.

Digital Library

[26]

Jean-Bernard Lasserre. 2010. Moments, Positive Polynomials and Their Applications. Vol. 1. World Scientific.

[27]

J. B. Lasserre. 2016. A MAX-CUT formulation of 0/1 programs. Oper. Res. Letters 44 (2016), 158–164.

Digital Library

[28]

Jongwon Lee, Venkataramanan Balakrishnan, Cheng-Kok Koh, and Dan Jiao. 2009. From \(O(k^2 N)\) to \(O(N)\): A fast complex-valued eigenvalue solver for large-scale on-chip interconnect analysis. In IEEE MTT-S International Microwave Symposium Digest. IEEE, 181–184.

[29]

Richard B. Lehoucq, Danny C. Sorensen, and Chao Yang. 1998. ARPACK Users’ Guide: Solution of Large-scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods. SIAM.

[30]

N. H. A. Mai, J.-B. Lasserre, and V. Magron. 2020. A hierarchy of spectral relaxations for polynomial optimization. arXiv preprint arXiv:2007.09027 (2020).

[31]

M. Marshall. 2009. Representations of non-negative polynomials, degree bounds and applications to optimization. Canad. J. Math. 61, 1 (2009), 205–221.

[32]

Brendan O’Donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. 2016. Conic optimization via operator splitting and homogeneous self-dual embedding. J. Optim. Theor. Applic. 169, 3 (2016), 1042–1068.

Digital Library

[33]

Dávid Papp and Sercan Yildiz. 2019. Sum-of-squares optimization without semidefinite programming. SIAM J. Optim. 29, 1 (2019), 822–851.

Digital Library

[34]

Dávid Papp and Sercan Yıldız. 2021. Alfonso: Matlab package for nonsymmetric conic optimization. Accepted in INFORMS Journal on Computing 34, 1 (2022). 11–19.

[35]

Kim-Chuan Toh, Michael J. Todd, and Reha H. Tütüncü. 1999. SDPT3-a MATLAB software package for semidefinite programming, version 1.3. Optim. Meth. Softw. 11, 1–4 (1999), 545–581.

[36]

Lieven Vandenberghe, V. Ragu Balakrishnan, Ragnar Wallin, Anders Hansson, and Tae Roh. 2005. Interior-point algorithms for semidefinite programming problems derived from the KYP lemma. In Positive Polynomials in Control. Springer, 195–238.

[37]

Lieven Vandenberghe and Stephen Boyd. 1996. Semidefinite programming. SIAM Rev. 38, 1 (1996), 49–95.

Digital Library

[38]

Hayato Waki, Sunyoung Kim, Masakazu Kojima, and Masakazu Muramatsu. 2006. Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. 17, 1 (2006), 218–242.

Digital Library

[39]

H. Waki, S. Kim, M. Kojima, and M. Muramatsu. 2006. Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. 17, 1 (2006), 218–242.

Digital Library

[40]

Hayato Waki, Sunyoung Kim, Masakazu Kojima, Masakazu Muramatsu, and Hiroshi Sugimoto. 2008. Algorithm 883: SparsePOP—A sparse semidefinite programming relaxation of polynomial optimization problems. ACM Trans. Math. Softw. 35, 2 (2008), 15.

Digital Library

[41]

Irene Waldspurger and Alden Waters. 2020. Rank optimality for the Burer-Monteiro factorization. SIAM J. Optim. 30, 3 (2020), 2577–2602.

Digital Library

[42]

Jie Wang and Victor Magron. 2020. A second order cone characterization for sums of nonnegative circuits. In 45th International Symposium on Symbolic and Algebraic Computation. 450–457.

[43]

Jie Wang and Victor Magron. 2021. Exploiting term sparsity in noncommutative polynomial optimization. Computat. Optim. Applic. 80, 2 (2021), 483–521.

Digital Library

[44]

Jie Wang, Victor Magron, and Jean-Bernard Lasserre. 2021. Chordal-TSSOS: A moment-SOS hierarchy that exploits term sparsity with chordal extension. SIAM J. Optim. 31, 1 (2021), 114–141.

Digital Library

[45]

Jie Wang, Victor Magron, and Jean-Bernard Lasserre. 2021. TSSOS: A moment-SOS hierarchy that exploits term sparsity. SIAM J. Optim. 31, 1 (2021), 30–58.

Digital Library

[46]

Jie Wang, Victor Magron, Jean B. Lasserre, and Ngoc Hoang Anh Mai. 2020. CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization. arXiv preprint arXiv:2005.02828 (2020).

[47]

Tillmann Weisser, Benoît Legat, Chris Coey, Lea Kapelevich, and Juan Pablo Vielma. 2019. Polynomial and moment optimization in Julia and JuMP. In JuliaCon. Retrieved from https://pretalx.com/juliacon2019/talk/QZBKAU/.

[48]

Alp Yurtsever, Olivier Fercoq, and Volkan Cevher. 2019. A conditional-gradient-based augmented Lagrangian framework. In International Conference on Machine Learning. PMLR, 7272–7281.

[49]

Alp Yurtsever, Joel A. Tropp, Olivier Fercoq, Madeleine Udell, and Volkan Cevher. 2021. Scalable semidefinite programming. SIAM J. Math. Data Sci. 3, 1 (2021), 171–200.

Cited By

Guo FWang J(2024)A Moment-Sum-of-Squares Hierarchy for Robust Polynomial Matrix Inequality Optimization with Sum-of-Squares ConvexityMathematics of Operations Research10.1287/moor.2023.0361Online publication date: 23-Jul-2024
https://doi.org/10.1287/moor.2023.0361
Häring HGramlich DEbenbauer CScherer C(2024)Trajectory generation for the unicycle model using semidefinite relaxationsEuropean Journal of Control10.1016/j.ejcon.2024.10106380(101063)Online publication date: Nov-2024
https://doi.org/10.1016/j.ejcon.2024.101063
Mai NLasserre JMagron V(2023)A hierarchy of spectral relaxations for polynomial optimizationMathematical Programming Computation10.1007/s12532-023-00243-715:4(651-701)Online publication date: 22-May-2023
https://doi.org/10.1007/s12532-023-00243-7
Show More Cited By

Index Terms

Exploiting Constant Trace Property in Large-scale Polynomial Optimization
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms
      2. Optimization algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Semidefinite programming

Recommendations

The Constant Trace Property in Noncommutative Optimization
ISSAC '21: Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation

In this article, we show that each semidefinite relaxation of a ball-constrained noncommutative polynomial optimization problem can be cast as a semidefinite program with a constant trace matrix variable. We then demonstrate how this constant trace ...
A sublevel moment-SOS hierarchy for polynomial optimization
Abstract
We introduce a sublevel Moment-SOS hierarchy where each SDP relaxation can be viewed as an intermediate (or interpolation) between the d-th and $(d + 1)$ -th order SDP relaxations of the Moment-SOS hierarchy (dense or sparse version). With the flexible ...
Convergent Semidefinite Programming Relaxations for Global Bilevel Polynomial Optimization Problems

In this paper, we consider a bilevel polynomial optimization problem where the objective and the constraint functions of both the upper-and the lower-level problems are polynomials. We present methods for finding its global minimizers and global minimum ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 48, Issue 4

December 2022

339 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/3572845

Editors:
Zhaojun Bai
University of California at Davis, USA
,
Wolfgang Bangerth
Colorado State University, USA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 December 2022

Online AM: 08 August 2022

Accepted: 21 July 2022

Revised: 02 March 2022

Received: 16 December 2020

Published in TOMS Volume 48, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Funding Sources

MESRI
FMJH Program PGMO
EDF, Thales, Orange et Criteo
Tremplin ERC Stg
European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Actions
French “Investing for the Future PIA3”

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
330
Total Downloads

Downloads (Last 12 months)75
Downloads (Last 6 weeks)10

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Guo FWang J(2024)A Moment-Sum-of-Squares Hierarchy for Robust Polynomial Matrix Inequality Optimization with Sum-of-Squares ConvexityMathematics of Operations Research10.1287/moor.2023.0361Online publication date: 23-Jul-2024
https://doi.org/10.1287/moor.2023.0361
Häring HGramlich DEbenbauer CScherer C(2024)Trajectory generation for the unicycle model using semidefinite relaxationsEuropean Journal of Control10.1016/j.ejcon.2024.10106380(101063)Online publication date: Nov-2024
https://doi.org/10.1016/j.ejcon.2024.101063
Mai NLasserre JMagron V(2023)A hierarchy of spectral relaxations for polynomial optimizationMathematical Programming Computation10.1007/s12532-023-00243-715:4(651-701)Online publication date: 22-May-2023
https://doi.org/10.1007/s12532-023-00243-7
Lasserre J(2023)Polynomial Optimization, Certificates of Positivity, and Christoffel FunctionPolynomial Optimization, Moments, and Applications10.1007/978-3-031-38659-6_1(1-22)Online publication date: 28-Dec-2023
https://doi.org/10.1007/978-3-031-38659-6_1

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents