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

DOI10.1016/j.dam.2017.12.015zbMath1433.90110OpenAlexW2737848107MaRDI QIDQ2297658

Ahmadreza Marandi, Joachim Dahl, Etienne 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

semi-definite programmingpolynomial optimizationpooling problemdiscrete-time optimal controlchordal 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)

Related Items

TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity

Uses Software

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some applications of polynomial optimization in operations research and real-time decision making
• Relaxations and discretizations for the pooling problem
• Quadratic programming with one negative eigenvalue is NP-hard
• Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
• An efficient trust region method for unconstrained discrete-time optimal control problems
• Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
• Strong formulations for the pooling problem
• Anneaux preordonnes
• A bounded degree SOS hierarchy for polynomial optimization
• Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework
• Global Optimization with Polynomials and the Problem of Moments
• Analysis of MILP Techniques for the Pooling Problem
• An Approximate Minimum Degree Ordering Algorithm
• Polynomial Programming: LP-Relaxations Also Converge
• Generalized Lagrangian Duals and Sums of Squares Relaxations of Sparse Polynomial Optimization Problems
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity