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

Journal article (2020)

Authors

Ahmadreza Marandi Eindhoven University of Technology

E. de Klerk Tilburg University, Discrete Mathematics and Optimization -

Joachim Dahl MOSEK ApS

Research Group

Discrete Mathematics and Optimization () (TU Delft)

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

To reference this document use:

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

More Info

expand_more

Published Date

2020

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

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.

Files

1_s2.0_S0166218X17305954_main.... (pdf)

(pdf | 0.515 Mb)

Download not available