skip to content
 

Timetable (POPW01)

Polynomial Optimisation: workshop and summer school

Monday 15th July 2013 to Friday 19th July 2013

Monday 15th July 2013
08:45 to 09:15 Registration
09:15 to 09:30 Summer School: Welcome from Adam Letchfor (Organiser) & John Toland (INI Director) INI 1
09:30 to 10:15 T Netzer (Universität Leipzig)
Semidefinite Programming and its Feasible Sets I
In this lecture series I will first give a brief introduction to semidefinite programming and some of its applications. I will then focus on the class of feasible sets for such problems, so-called spectrahedra, and their linear projections. These sets are generalizations of polyhedra. Although there exists an exact definition, we so far do not have a satisfactory and easy-to-check characterization for them. The methods used in finding such characterizations come from convexity theory, optimization, algebra, algebraic geometry and functional analysis. This makes the area an exciting field of research, with many recent results, and many interesting results still to come.
INI 1
10:15 to 11:00 T Netzer (Universität Leipzig)
Semidefinite Programming and its Feasible Sets II
In this lecture series I will first give a brief introduction to semidefinite programming and some of its applications. I will then focus on the class of feasible sets for such problems, so-called spectrahedra, and their linear projections. These sets are generalizations of polyhedra. Although there exists an exact definition, we so far do not have a satisfactory and easy-to-check characterization for them. The methods used in finding such characterizations come from convexity theory, optimization, algebra, algebraic geometry and functional analysis. This makes the area an exciting field of research, with many recent results, and many interesting results still to come.
INI 1
11:00 to 11:30 Morning Coffee
11:30 to 12:30 T Netzer (Universität Leipzig)
Semidefinite Programming and its Feasible Sets III
In this lecture series I will first give a brief introduction to semidefinite programming and some of its applications. I will then focus on the class of feasible sets for such problems, so-called spectrahedra, and their linear projections. These sets are generalizations of polyhedra. Although there exists an exact definition, we so far do not have a satisfactory and easy-to-check characterization for them. The methods used in finding such characterizations come from convexity theory, optimization, algebra, algebraic geometry and functional analysis. This makes the area an exciting field of research, with many recent results, and many interesting results still to come.
INI 1
12:30 to 13:30 Lunch at Wolfson Court
14:00 to 14:45 J De Loera (University of California, Davis)
Algebraic and Geometric Ideas in Discrete Optimisation I
It is common knowledge that the understanding of the combinatorial geometry of convex bodies has helped speed up algorithms in discrete optimization. For example, cutting planes and facet-description of polyhedra have been crucial in the success of branch-and-bound algorithms for mixed integer linear programming. Another example, is how the ellipsoid method can be used to prove polynomiality results in combinatorial optimization. For the future, the importance of algebraic-combinatorial geometry in optimization appears even greater.

In the past 5 years advances in algebraic-geometric algorithms have been used to prove unexpected new results on the computation of non-linear integer programs. These lectures will introduce the audience to new techniques. I will describe several algorithms and explain why we can now prove theorems that were beyond our reach before, mostly about integer optimization with non-linear objectives. I will also describe attempts to turn these two algorithms into practical computation, not just in theoretical results.

This a nice story collecting results by various authors and now contained in our monograph recently published by SIAM-MOS.

INI 1
14:45 to 15:30 J De Loera (University of California, Davis)
Algebraic and Geometric Ideas in Discrete Optimisation II
It is common knowledge that the understanding of the combinatorial geometry of convex bodies has helped speed up algorithms in discrete optimization. For example, cutting planes and facet-description of polyhedra have been crucial in the success of branch-and-bound algorithms for mixed integer linear programming. Another example, is how the ellipsoid method can be used to prove polynomiality results in combinatorial optimization. For the future, the importance of algebraic-combinatorial geometry in optimization appears even greater.

In the past 5 years advances in algebraic-geometric algorithms have been used to prove unexpected new results on the computation of non-linear integer programs. These lectures will introduce the audience to new techniques. I will describe several algorithms and explain why we can now prove theorems that were beyond our reach before, mostly about integer optimization with non-linear objectives. I will also describe attempts to turn these two algorithms into practical computation, not just in theoretical results.

This a nice story collecting results by various authors and now contained in our monograph recently published by SIAM-MOS.

INI 1
15:30 to 16:00 Afternoon Tea
16:00 to 17:00 J De Loera (University of California, Davis)
Algebraic and Geometric Ideas in Discrete Optimisation III
It is common knowledge that the understanding of the combinatorial geometry of convex bodies has helped speed up algorithms in discrete optimization. For example, cutting planes and facet-description of polyhedra have been crucial in the success of branch-and-bound algorithms for mixed integer linear programming. Another example, is how the ellipsoid method can be used to prove polynomiality results in combinatorial optimization. For the future, the importance of algebraic-combinatorial geometry in optimization appears even greater.

In the past 5 years advances in algebraic-geometric algorithms have been used to prove unexpected new results on the computation of non-linear integer programs. These lectures will introduce the audience to new techniques. I will describe several algorithms and explain why we can now prove theorems that were beyond our reach before, mostly about integer optimization with non-linear objectives. I will also describe attempts to turn these two algorithms into practical computation, not just in theoretical results.

This a nice story collecting results by various authors and now contained in our monograph recently published by SIAM-MOS.

INI 1
17:00 to 18:00 Welcome wine reception
Tuesday 16th July 2013
09:30 to 10:15 E Candes (Stanford University)
Convex Programming in Data Science I
INI 1
10:15 to 11:00 E Candes (Stanford University)
Convex Programming in Data Science II
INI 1
11:00 to 11:30 Morning Coffee
11:30 to 12:30 E Candes (Stanford University)
Convex Programming in Data Science III
INI 1
12:30 to 13:30 Lunch at Wolfson Court
14:00 to 14:45 B Sturmfels (University of California, Berkeley)
Convex Algebraic Geometry I
Lecture 1: Introduction to Convex Algebraic Geometry Lecture 2: The Convex Hull of a Space Curve Lecture 3: Maximum Likelihood for Matrices with Rank Constraints
INI 1
14:45 to 15:30 B Sturmfels (University of California, Berkeley)
Convex Algebraic Geometry II
Lecture 1: Introduction to Convex Algebraic Geometry Lecture 2: The Convex Hull of a Space Curve Lecture 3: Maximum Likelihood for Matrices with Rank Constraints
INI 1
15:30 to 16:00 Afternoon Tea
16:00 to 17:00 B Sturmfels (University of California, Berkeley)
Convex Algebraic Geometry III
Lecture 1: Introduction to Convex Algebraic Geometry Lecture 2: The Convex Hull of a Space Curve Lecture 3: Maximum Likelihood for Matrices with Rank Constraints
INI 1
Wednesday 17th July 2013
09:30 to 10:30 M Kocvara (University of Birmingham)
Nonlinear Semidefinite Optimization I
INI 1
10:30 to 11:00 Morning Coffee
11:00 to 12:00 M Kocvara (University of Birmingham)
Nonlinear Semidefinite Optimization II
INI 1
12:00 End of Summer School/Start of Workshop
12:30 to 13:30 Lunch at Wolfson Court
14:00 to 14:30 Workshop: Welcome and introduction INI 1
14:30 to 15:00 MF Anjos (École Polytechnique de Montréal)
Towards Efficient Higher-Order Semidefinite Relaxations for Max-Cut
The basic semidefinite relaxation for max-cut underlying the Goemans-Williamson hyperplane rounding procedure can be tightened in different ways. A straightforward approach is to add facet-defining inequalities for the metric polytope, or more generally valid inequalities for the convex hull of incidence vectors of cuts, known as the cut polytope. Other approaches are hierarchical and build a sequence of relaxations that increasingly better approximate the cut polytope but at an increasingly greater computational cost. A natural systematic hierarchy was introduced by Lasserre. The first step in this hierarchy corresponds to the basic semidefinite relaxation which optimizes over the set of correlation matrices. The second step is a relaxation with a matrix of order $n^2$, and so on.

We start with the basic semidefinite relaxation intersected with the metric polytope, and propose to iteratively refine this relaxation using semidefiniteness and/or linear constraints derived from selected submatrices of the Lasserre matrix of order $n^2$. We present theoretical insights as well as computational results.

INI 1
15:00 to 15:30 MA Marshall (University of Saskatchewan)
Computing lower bounds for a polynomial using geometric programming
We present a new algorithm for computing a new lower bound for a polynomial f in R}[X] by geometric programming. This bound is typically not as good as the lower bound obtained using Lasserre's algorithm but, on the other hand, the algorithm takes full advantage of sparsity of coefficients and it works in cases where the degree and/or number of variables is large, cases where Lasserre's algorithm breaks down. There is also variant of the algorithm which computes a lower bound for f on the semialgebraic set in real n-space defined by X_1^{2d}+\dots+X_n^{2d}
INI 1
15:30 to 16:00 Afternoon Tea
16:00 to 16:30 PJC Dickinson (University of Groningen)
A new convex reformulation and approximation hierarchy for polynomial optimisation
In this talk we will look at how any polynomial minimisation problem with a bounded feasible set can be reformulated into a conic maximisation problem with a single variable. By reformulated we mean that the optimal values of these problems are equal. The difficulty of the original problem goes into a cone of homogeneous polynomials which are nonnegative over a certain subset of the nonnegative orthant. We shall consider a new hierarchy of inner approximations to this cone. These approximations can be used to produce linear optimisation problems, whose optimal values provide a monotonically increasing sequence of lower bounds to the optimal value of the original problem. Using a new positivstellensatz, we shall show that this sequence of lower bounds in fact converges to the optimal value of the original problem.
INI 1
16:30 to 17:00 L Galli (Università di Pisa)
Gap Inequalities for the Max-Cut Problem
Laurent & Poljak introduced an interesting class of valid inequalities for the cut polytope, called gap inequalities. The gap inequalities are remarkably general, including several other important classes of inequalities (including some known to define facets) as special cases. Unfortunately, however, computing the right-hand side of a gap inequality, for a given left-hand side, is NP-hard. This suggests that it would be difficult to use gap inequalities as cutting planes. Perhaps for this reason, the inequalities have received little attention from researchers.

In this talk, we present some recent progress on the gap inequalities. In particular:

1. We show how to define gap inequalities for a much more general class of problems (non-convex Mixed-Integer Quadratic Programs).

2. We prove several results concerned with the computational complexity of various problems related to gap inequalities.

3. We present the first ever finite separation algorithm for the gap inequalities.

4. We present some computational results obtained when using gap inequalities as cutting planes.

INI 1
19:30 to 22:00 Conference Dinner at Emmanuel College
Thursday 18th July 2013
09:30 to 10:00 I Klep (University of Auckland)
Linear Matrix Inequalities meet Positivstellensätze
Let L be a linear pencil, and consider its linear matrix inequality (LMI) L(x)>0. In this talk we describe a natural relaxation of an LMI, based on substituting matrices X for the variables x. With this relaxation, we prove that a ``perfect'' convex Positivstellensatz: a noncommutative polynomial p is positive semidefinite on the matricial LMI domain L(X)>0 if and only if it has a weighted sum of squares representation with optimal degree bounds. We shall also give two corollaries of this theorem. First, we present an LMI domination theorem, whose special case is the SDP relaxation of the matrix cube problem due to Nemirovskii and Ben-Tal. A second consequence is the real radical duality theory for semidefinite programming.
INI 1
10:00 to 10:30 D de Laat (Technische Universiteit Delft)
A semidefinite programming hierarchy for geometric packing problems
Geometric packing problems can be modeled as maximum independent set problems in infinite graphs. Computing the independence number is NP-hard. To get a chain of improving upper bounds for finite graphs one can formulate the problem as a polynomial optimization problem and then use the Lasserre hierarchy. We generalize this hierarchy to infinite graphs using conic optimization over cones of positive kernels and measures of positive type. For finite graphs it is known that the hierarchy attains the independence number after finitely many steps. We show that this is also true for the generalized hierarchy if the infinite graph corresponds to a packing problem. Based on joint work with Frank Vallentin.
INI 1
10:30 to 11:00 M Abril-Bucero (INRIA Sophia Antipolis)
Global polynomial optimization with Moment Matrices and Border Basis
Optimization appears in many areas of Scientific Computing, since the solution of a problem can often be described as the minimum of an optimization problem. We describe a new method to compute the global minimum of a real polynomial function and the ideal defining the points which minimize this polynomial function, assuming that the minimizer ideal is zero-dimensional. Our method is a generalization of Lasserre relaxation method and stops in a finite number of steps. The proposed algorithm combines Border Basis, Moment Matrices and Semidefinite Programming.In the case where the minimum is reached at a finite number of points, it provides a border basis of the minimizer ideal.
INI 1
11:00 to 11:30 Morning Coffee
11:30 to 12:00 L Gijben (Rijksuniversiteit Groningen)
Scaling relationship between the copositive cone and a hierarchy of semidefinite approximations
Several NP-complete problems can be turned into convex problems by formulating them as optimization problems over the copositive cone. Unfortunately checking membership in the copositive cone is a co-NP-complete problem in itself. To deal with this problem, several approximation schemes have been developed. One of them is a hierarchy of cones introduced by P. Parrilo, membership of which can be checked via semidefinite programming. In some sense this hierarchy forms a bridge between the semidefinite cone and the copositive cone. Starting off from the cone of semidefinite plus nonnegative matrices, the sets in the hierarchy grow ever closer to the copositive cone. We know that for matrices of order n 4. In particular a surprising result is found for the case n = 5, establishing a direct link between coposit ive programming and semidefinite programming for problems of that order.
INI 1
12:00 to 12:30 A Ahmadi (IBM Thomas J. Watson Research Center)
Optimization over Polynomials for Analysis of Polynomial Vector Fields
We present complexity results and semidefinite programming (SDP) based algorithms for stability analysis of polynomial differential equations. We show that deciding asymptotic stability of homogeneous cubic vector fields is strongly NP-hard. We then settle some of the converse questions on existence of polynomial and sum of squares Lyapunov functions.
INI 1
12:30 to 13:30 Lunch at Wolfson Court
14:00 to 14:30 K Kaparis (Lancaster University)
Cutting Planes for First-Level RLT Relaxations of Mixed 0-1 Programs
The Reformulation-Linearization Technique (RLT), due to Sherali and Adams, is used to construct hierarchies of linear programming relaxations of various optimisation problems. We present a method for generating cutting planes in the space of the first-level relaxation, based on optimally weakening valid inequalities for the second-level relaxation. These cutting planes can be applied to any pure or mixed 0-1 program with a linear or quadratic objective function, and any mixture of linear, quadratic and convex constraint functions. In fact, our method results in several exponentially-large families of cutting planes. We show that the separation problem associated with each family can be solved efficiently, under mild conditions. We also present some encouraging computational results, obtained by applying the cutting planes to the quadratic knapsack and quadratic assignment problems.
INI 1
14:30 to 15:00 J Nie (University of California, San Diego)
The A-Truncated K-Moment Problem
Let A be a finite subset of N^n, and K be a compact semialgebraic set. An A-tms is a vector y indexed by elements in A. The A-Truncated K-Moment Problem (A-TKMP) studies whether a given A-tms y admits a K-measure

(i.e., a Borel measure supported in K) or not. We propose a numerical algorithm for solving A-TKMPs. It is based on finding a flat extension of y by solving a hierarchy of semidefinite relaxations, whose objective R is generated in a certain randomized way. If y admits no K-measures and R[x]_A is K-full, we can get a certificate for the nonexistence of representing measures. If y admits a K-measure, then for almost all generated R, we prove

that: i) we can asymptotically get a flat extension of y; ii) under a general condition that is almost sufficient and necessary, we can get a flat

extension of y. The complete positive matrix decomposition and sum of even powers of linear forms decomposition problems can be solved as an A-TKMP.

INI 1
15:00 to 15:30 M Infusino (University of Reading)
Concrete conditions for realizability of moment functions via quadratic modules
In this talk, we intend to give a brief introduction to the realizability problem presenting a new approach based on its deep connection to the moment theory. This is not only the key idea which allowed us to get interesting results about the full realizability problem, but it is also the base for a new research direction which links the realizability problem to polynomial optimization theory. The realizability problem naturally arises from applications dealing with systems consisting of a huge number of components. The investigation of such systems is greatly facilitated if the attention is restricted to selected physical parameters (usually correlation functions) which encode the relevant structure of the system. The realizability problem exactly addresses the question whether a given candidate correlation function actually represents the correlation function of some random distribution. We will present necessary and sufficient conditions for the realizability of an infinite sequence of moments given by generalized functions on a closed semi-algebraic subset of the space of distributions. Our approach is based on the interpretation of the realizability problem as an infinite dimensional moment problem and it exploits the quadratic module generated by the polynomials defining the semi-algebraic set in question. This result determines realizability conditions which can be more easily verified than the Haviland type conditions developed by A. Lenard. Moreover, it completely characterizes the support of the realizing process giving a solution of the full realizability problem for Radon measures. 1
INI 1
15:30 to 17:00 Afternoon Tea and Poster Session
Friday 19th July 2013
09:30 to 10:00 D Plaumann (Universität Konstanz)
Hyperbolic polynomials, interlacers and sums of squares
A real polynomial is hyperbolic if it defines a hypersurface consisting of maximally nested ovaloids. These polynomials appear in many areas of mathematics, including convex optimisation, combinatorics and differential equations. We investigate the relation between a hyperbolic polynomial and the set of polynomials that interlace it. This set of interlacers is a convex cone, which we realize as a linear slice of the cone of nonnegative polynomials. We combine this with a sums-of-squares-relaxation to approximate a hyperbolicity cone explicitly by the projection of a spectrahdedron. A multiaffine example coming from the Vámos matroid shows that this relaxation is not always exact.
INI 1
10:00 to 10:30 R Hauser (University of Oxford)
Likelihood Maximization on Phylogenic Trees
The problem of inferring the phylogenic tree of $n$ extant species from their genome is treated via mainly two approaches, the maximum parsimony and the maximum likelihood approach. While the latter is thought to produce more meaningful results, it is harder to solve computationally. We show that under a molecular clock assumption, the maximum likelihood model has a natural formulation that can be approached via branch-and-bound and polynomial optimization. Using this approach, we produce a counterexample to a conjecture relating to the reconstruction of an ancestral genome under the maximum parsimony and maximum likelihood approaches.
INI 1
10:30 to 11:00 A El Haj Ben Ali (Universidad de Sevilla)
Revisiting several problems and algorithms in Continuous Location with l_p norms
This work addresses the general continuous single facility location problems in finite dimension spaces under possibly diferent l_p norms, p>=1, in the demand points. We analyze the dificulty of this family of problems and revisit convergence properties of some well-known algorithms. The ultimate goal is to provide a common approach to solve the family of continuous l_p ordered median location problems in dimension d (including of course the l_p minisum or Fermat-Weber location problem for any p>=1). We prove that this approach has a polynomial worst case complexity for monotone lambda weights and can be also applied to constrained and even non-convex problems.
INI 1
11:00 to 11:30 Morning Coffee
11:30 to 12:00 T Piovesan (Centrum voor Wiskunde en Informatica (CWI))
A conic approach to entangled-assisted graph parameters
Graph parameters as the independence and the chromatic number are related to classical (zero-error) communication problems. It is known that allowing the presence of entanglement, one of quantum mechanics most peculiar feature, might increase the efficiency of the (zero-error) communication. However there are still many open problem, for example the maximal possible separation between classical and quantum communication, computational complexity and approximation of the quantum variant of the graph parameters etc. We propose a new framework for studying the quantum parameters, introducing a cone that lies between the completely positive and the double non-negative one. We say that a matrix X is in this cone if there exists a set of positive semidefinite matrices {A_i} such that the i,j-th entry of X is equal to the inner product between A_i and A_j. Testing membership of the dual cone is equivalent to determine whether a particular polynomial is trace positive over all the real symmetric matrices of any dimension. This problem is therefore related to a special case of the Connes’ embedding conjecture. This conic approach allow us to prove better bounds for the quantum variant of the graph parameters, to have a more unified framework and hopefully to build approximation hierarchies.
INI 1
12:00 to 12:30 R Weismantel (ETH Zürich)
Integer quadratic minimization over polyhedra in dimension two
This talk deals with algorithms and complexity results about the minimization of convex functions over integer points in convex regions. This topic is quite novel and today only few non-trivial algorithmic methods exist that can cope with problems of this generality. We survey current state of art, both when the number of integer variables is constant and variable. We discuss results about the speed of convergence of oracle algorithms that iteratively solve special integer subproblems with a constant approximation factor. Despite the generality of the underlying setting we show how to detect efficiently w.r.t. our oracle assumptions feasible solutions whose objective function value is close to the optimal value. We also show how to prove that such proximity results are best possible up to a polynomial factor.
INI 1
12:30 to 13:30 Lunch at Wolfson Court
14:00 to 14:30 B Matschke (Technische Universität Berlin)
The width of 5-dimensional prismatoids
Santos' construction of counter-examples to the Hirsch Conjecture (2012) is based on the existence of prismatoids of dimension d of width greater than d. Santos, Stephen and Thomas (2012) have shown that this cannot occur in dimension less than 5. Motivated by this we here study the width of 5-dimensional prismatoids, obtaining the following results:

- There are 5-prismatoids of width six with only 25 vertices, versus the 48 vertices in Santos' original construction. This leads to non-Hirsch polytopes of dimension 20, rather than the original dimension 43.

- There are 5-prismatoids with n vertices and width Omega(\sqrt{n}) for arbitrarily large n. Hence, the width of 5-prismatoids is unbounded.

This is joint work with Francisco Santos and Christophe Weibel.

INI 1
14:30 to 15:00 M Lotz (University of Manchester)
The Geometry of Phase Transitions in Convex Optimization
Recent empirical research indicates that many convex optimization problems with random constraints exhibit a phase transition as the number of constraints increases. For example, this phenomenon emerges in the l1 minimization method for identifying a sparse vector from random linear samples. Indeed, this approach succeeds with high probability when the number of samples exceeds a threshold that depends on the sparsity level; otherwise, it fails with high probability.

We present the first rigorous analysis that explains why phase transitions are ubiquitous in random convex optimization problems. We also describe tools for making reliable predictions about the quantitative aspects of the transition, including the location and the width of the transition region. These techniques apply to regularized linear inverse problems with random measurements, to demixing problems under a random incoherence model, and also to cone programs with random affine constraints.

These applications depend on foundational research in conic geometry. A new summary parameter, called the statistical dimension, canonically extends the dimension of a linear subspace to the class of convex cones. The main result demonstrates that the sequence of conic intrinsic volumes of a convex cone concentrates sharply near the statistical dimension. This fact leads to an approximate version of the conic kinematic formula that gives bounds on the probability that a randomly oriented cone shares a ray with a fixed cone.

This is joint work with D. Amelunxen, M. McCoy and J. Tropp.

INI 1
15:00 to 15:30 RZ Robinson (University of Washington)
Positive Semidefinite Rank of Polytopes
We define the positive semidefinite (psd) rank of a polytope P to be the size of the smallest cone of psd matrices that admits a lift of P. This can be thought of as a measure on how well semidefinite programming may be used to optimize over P. We will present an overview of the subject, several recent results, and some open problems.
INI 1
15:30 to 16:00 Afternoon Tea
16:00 to 16:30 I Bomze (Universität Wien)
Narrowing the difficulty gap for the Celis-Dennis-Tapia problem
We study the so-called Celis-Dennis-Tapia (CDT) problem to minimize a non-convex quadratic function over the intersection of two ellipsoids. Contrasting with the well-studied trust region problem where the feasible set is just one ellipsoid, the CDT problem seems to be not yet fully understood. Our main objective in this paper is to narrow the difficulty gap defined by curvature of the Lagrangian. We propose seemingly novel sufficient and necessary conditions for local and global optimality, and hint at algorithmic possibilities to exploit these.

Key words: Copositive matrices, non-convex optimization, optimality condition, polynomial optimization, trust region problem

Co-speaker: Michael Overton, Courant Institute of Math.~Sciences, New York University, U.S.A.

INI 1
16:30 to 17:00 E De Klerk (Nanyang Technological University)
Optimising polynomials over the simplex
INI 1
17:00 End of Workshop INI 1
University of Cambridge Research Councils UK
    Clay Mathematics Institute The Leverhulme Trust London Mathematical Society Microsoft Research NM Rothschild and Sons