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 4: Polynomial optimization and its applications
Time:
Saturday, 13/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)

 

Tighter bounds through rank-one convexification

Tillmann Weisser1, Sidhant Misra2, Hassan Hijzai2
1Los Alamos National Lab, NM, USA, 2Los Alamos National Laboratory, Los Alamos, NM, USA

To be completed.In classical polynomial optimization, point evaluation is relaxed to integration with respect to a measure. By optimizing over a measure instead of points, the search for the global optimum becomes a linear problem on a measure, and thanks to results from real algebraic geometry, a conic program on moments. The most common approach of this kind is the Lasserre (or SDP) hierarchy where linear constraints on the moments are combined with positive semi-definite constraints on the moment matrix. In case bounds on the optimization variables of the original problem are known, we propose to strengthen the SDP hierarchy by adding non-linear moment constraints that are derived from necessary condition on the moment matrix to be rank-one. Though non-linear, the additional constraints do not change the convex character of the relaxation. Hence, local non-linear solvers are able to solve the tightened relaxation to optimality.

 

Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs

Yuzixuan Zhu, Pataki Gabor, Tran-Dinh Quoc
University of North Carolina at Chapel Hill, NC, USA

We introduce Sieve-SDP, a simple algorithm to preprocess semidefinite programs (SDPs). Sieve-SDP belongs to the class of facial reduction algorithms. It inspects the constraints of the problem, deletes redundant rows and columns, and reduces the size of the variable matrix. It often detects infeasibility. It does not rely on any optimization solver: the only subroutine it needs is Cholesky factorization, hence it can be implemented in a few lines of code in machine precision. We present extensive computational results on more than seven hundred SDPs from the literature.

We conclude that Sieve-SDP is very fast: preprocessing by Sieve-SDP takes, on average, less than one percent of the time that it takes for a commercial solver to solve an SDP. Preprocessing by Sieve-SDP significantly improves accuracy and reduces the solution time.

 

Phaseless rank

António Goucha1, João Gouveia2
1Universidade de Coimbra, 2Universidade de Coimbra, Portugal

The phaseless rank of a nonnegative matrix M is defined to be the least k for which there exists a complex rank-k matrix N such that |N|=M, entrywise speaking. In optimization terms, it is the solution to the rank minimization of a matrix under complete phase uncertainty on the entries.

This concept has a strong connection not only with amoebas, since computing the phaseless rank amounts to solving the amoeba membership problem for the varieties of matrices with restricted rank, but also with positive semidefinite matrix factorizations, as the phaseless rank can be used to derive bounds on the psd rank.

In 1966, Camion and Hoffman proved a landmark characterization of what can be seen as the set of singular square matrices with respect to phaseless rank. In this talk we will revisit and extend these results, and show how they can be used to derive some new examples in both amoeba theory and psd factorizations.

 

Log-concave polynomials, entropy, and approximate counting

Cynthia Vinzant1, Nima Anari2, Kuikui Liu3, Shayan Oveis Gharan3
1North Carolina State University, NC, USA, 2Stanford University, CA, USA, 3University of Washington, Seattle, WA, USA

A polynomial is called completely log-concave if it is log-concave as a function on the nonnegative orthant and its directional derivatives have the same property. This class of polynomials includes homogeneous stable polynomials and the basis generating polynomials of matroids. I will introduce some of the basic properties of these polynomials and discuss a concave program that based on entropy maximization that can approximate the size of its support. An important application will be approximating the number of bases of a matroid. This is joint work with Nima Anari, Kuikui Liu, and Shayan Oveis Gharan.