Polynomial Optimization I

WD-05: Polynomial Optimization I
Stream: Polynomial Optimization
Room: Pontryagin
Chair(s): Marek Tyburec

Sparse moment-sum-of-squares relaxations for nonlinear dynamical systems with guaranteed convergence
Corbinian Schlosser, Milan Korda
We present a sparse moment-sum-of-squares approach for sparse dynamical systems that can be applied to the problems: region of attraction, maximum positively invariant set and global attractor. We prove a decomposition of these sets provided that the vector field and constraint set posses certain structure. We combine these decompositions with existing methods that are based on infinite-dimensional linear programming. In case of sparse polynomial dynamics, we show that these methods admit a sparse sum-of-squares (SOS) approximation with guaranteed convergence.

Polynomial optimization applied to set computation
Benoît Legat, Raphaël M. Jungers
The search for a set satisfying given properties is commonly narrowed down to polytopes or ellipsoids. However, in high dimension, the size of the representation of feasible polytopes might not be practical and the restriction to ellipsoids might be too conservative. In this talk, we explore the computation of sets defined by polynomial functions. For convex sets, we discuss the choice to parametrize the search in terms of the gauge or support function of the set depending on the properties that the set should satisfy.

Exploiting constant trace property in large-scale polynomial optimization
Ngoc Hoang Anh Mai, Jean Bernard Lasserre, Victor Magron
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. The efficiency and scalability of our framework are illustrated on second-order moment relaxations for various randomly generated QCQPs. This is joint work with Lasserre, Magron and Wang.

Theme: Overlay by Kaira