Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy

DOI10.1016/J.DAM.2017.12.015MaRDI QIDQ2297658zbMATHOpenAlexFDO

Authors Ahmadreza Marandi, Joachim Dahl, E. de Klerk

Publication date 20 February 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.optimization-online.org/DB_HTML/2017/03/5889.html

zbMATH Keywords

polynomial optimizationdiscrete-time optimal controlsemi-definite programmingpooling problemchordal sparsity structuresparse sum-of-squares hierarchy

Mathematics Subject Classification ID

Semidefinite programming (90C22) Existence theories for optimal control problems involving ordinary differential equations (49J15) Discrete approximations in optimal control (49M25) Polynomial optimization (90C23)

Recommendations

• Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
• A numerical evaluation of the bounded degree sum-of-squares hierarchy of Lasserre, Toh, and Yang on the pooling problem
• TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
• Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity

Cites work

• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 1024734 (Why is no real title available?)
• A bounded degree SOS hierarchy for polynomial optimization
• Advances for the pooling problem: modeling, global optimization, and computational studies (Survey)
• An Approximate Minimum Degree Ordering Algorithm
• An efficient trust region method for unconstrained discrete-time optimal control problems
• Analysis of MILP techniques for the pooling problem
• Anneaux preordonnes
• Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
• Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
• Generalized Lagrangian Duals and Sums of Squares Relaxations of Sparse Polynomial Optimization Problems
• Global optimization with polynomials and the problem of moments
• Polynomial Programming: LP-Relaxations Also Converge
• Quadratic programming with one negative eigenvalue is NP-hard
• Relaxations and discretizations for the pooling problem
• Some applications of polynomial optimization in operations research and real-time decision making
• Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
• Strong formulations for the pooling problem
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity

Cited in

(4)

• TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
• A numerical evaluation of the bounded degree sum-of-squares hierarchy of Lasserre, Toh, and Yang on the pooling problem
• Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
• Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity

Describes a project that uses

Uses Software

• BARON
• CONOPT
• Mosek
• AIMMS
• Sparse-BSOS
• StdPooling-PolyAlgos

This page was built for publication: Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2297658)