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

None, None; None, None; None, None

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

Journal Article (2020)

Author(s)

Ahmadreza Marandi (Eindhoven University of Technology)

Etienne de Klerk (TU Delft - Electrical Engineering, Mathematics and Computer Science, Tilburg University)

Joachim Dahl (MOSEK ApS)

Research Group

Discrete Mathematics and Optimization

Polynomial optimization Pooling problem Discrete-time optimal control Chordal sparsity structure Semi-definite programming Sparse sum-of-squares hierarchy

DOI related publication

https://doi.org/10.1016/j.dam.2017.12.015 Final published version

To reference this document use

https://resolver.tudelft.nl/uuid:d246fa4d-0253-4835-8ec7-35ca55dcd142

More Info

expand_more

Publication Year

2020

Language

English

Research Group

Discrete Mathematics and Optimization

Journal title

Discrete Applied Mathematics

Volume number

275

Pages (from-to)

95-110

Downloads counter

205

Abstract

The sparse bounded degree sum-of-squares (sparse-BSOS) hierarchy of Weisser et al. (2017) constructs a sequence of lower bounds for a sparse polynomial optimization problem. Under some assumptions, it is proved by the authors that the sequence converges to the optimal value. In this paper, we modify the hierarchy to deal with problems containing equality constraints directly, without eliminating or replacing them by two inequalities. We also evaluate the sparse-BSOS hierarchy on a well-known bilinear programming problem, called the pooling problem, as well as a discrete-time optimal control problem.