Conference Agenda

Overview and details of the sessions of this conference. Please select a date or location to show only sessions at that day or location. Please select a single session for detailed view (with abstracts and downloads if available).

 
Session Overview
Session
MS130, part 2: Polynomial optimization and its applications
Time:
Thursday, 11/Jul/2019:
10:00am - 12:00pm

Location: Unitobler, F022
104 seats, 126m^2

Presentations
10:00am - 12:00pm

Polynomial optimization and its applications

Chair(s): Timo de Wolff (Technische Universität Berlin, Germany), Simone Naldi (Université de Limoges, France), João Gouveia (Universidade de Coimbra, Portugal)

The importance of polynomial (aka semi-algebraic) optimization is highlighted by the large number of its interactions with different research domains of mathematical sciences. These include, but are not limited to, automatic control, combinatorics, and quantum information. The mini-symposium will focus on the development of methods and algorithms dedicated to the general polynomial optimization problem. Both the theoretical and more applicative viewpoints will be covered.

 

(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)

 

Moments and convex optimization for analysis and control of nonlinear partial differential equations

Milan Korda, Didier Henrion, Jean-Bernard Lasserre
CNRS-LAAS, Toulouse, France

This talk will present a convex-optimization-based framework for analysis and control of nonlinear partial differential equations. The approach uses a particular weak embedding of the nonlinear PDE, resulting in a linear equation in the space of Borel measures. This equation is then used as a constraint of an infinite-dimensional linear programming problem (LP). This LP is then approximated by the classical Lasserre hierarchy of convex, finite-dimensional, semidefinite programming problems (SDPs). In the case of analysis of uncontrolled PDEs, the solutions to these SDPs provide bounds on a specified, possibly nonlinear, functional of the solutions to the PDE; in the case of PDE control, the solutions to these SDPs provide bounds on the optimal value of a given optimal control problem as well as suboptimal feedback controllers. The entire approach is based solely on convex optimization with no reliance on spatio-temporal gridding. The approach is applicable to a very broad class of fully nonlinear PDEs with polynomial data.

 

Two-player games between polynomial optimizers and semidefinite solvers.

Victor Magron1, Mohab Safey El Din2, Jean-Bernard Lasserre1
1CNRS-LAAS, Toulouse, France, 2Sorbonne Université, Paris, France

We interpret some wrong results, due to numerical inaccuracies, already observed when solving semidefinite programming (SDP) relaxations for polynomial optimization, on a double precision floating point solver. It turns out that this behavior can be explained and justified satisfactorily by a relatively simple paradigm. In such a situation, the SDP solver - and not the user - performs some "robust optimization" without being told to do so. In other words the resulting procedure can be viewed as a "max-min" robust optimization problem with two players: the solver which maximizes on a ball of arbitrary small radius, centered at the input polynomial, and the user who minimizes over the original decision variables.

Next, we consider the problem of finding exact sums of squares (SOS) decompositions for certain classes of polynomials, while relying on arbitrary-precision SDP solvers. We provide a perturbation-compensation algorithm computing exact decompositions for polynomials lying in the interior of the SOS cone. First, the user perturbates the input polynomial to obtain an approximate SOS decomposition. Then, one obtains an exact SOS decomposition after compensating the numerical error with the perturbation terms. We prove that this algorithm runs in boolean time, which is polynomial in the degree of the input and simply exponential in the number of variables. We apply this algorithm to compute exact Polya and Putinar's representations, respectively for positive definite forms and positive polynomials over basic compact semi-algebraic sets.

 

A Generalization of SAGE Certificates for Constrained Optimization

Riley Murray, Venkat Chandrasekaran
Caltech, Los Angeles, CA, USA

We describe a generalization of the SAGE relaxation methodology for obtaining bounds on constrained signomial and polynomial optimization problems. Our approach leverages the fact that SAGE conveniently and transparently blends with convex duality, in a manner that SOS does not. Key properties of traditional SAGE relaxations (e.g. sparsity preservation) are retained by this more general approach. We illustrate the utility of this methodology with a range of examples from the global optimization literature, along with a publicly available software package.

 

On positive duality gaps in semidefinite programming

Gabor Pataki
University of North Carolina at Chapel Hill, NC, USA

We present a novel analysis of semidefinite programs (SDPs) with positive duality gaps, i.e., different optimal values in the primal and dual problems. These SDPs are considered extremely pathological, they are often unsolvable, and they also serve as models of more general pathological convex programs. We first characterize two variable SDPs with positive gaps: we transform them into a standard form which makes the positive gap easy to recognize. The transformation is very simple, as it mostly uses elementary row operations coming from Gaussian elimination.

We next show that the two variable case sheds light on larger SDPs with positive gaps: we present SDPs in any dimension in which the positive gap is certified by the same structure as in the two variable case. We analyze an important parameter, the singularity degree of the duals of our SDPs and show that it is the largest that can result in a positive gap. We complete the paper by generating a library of difficult SDPs with positive gaps (some of these SDPs have only two variables), and a computational study.