Polynomial Optimisation: workshop and summer school
Monday 15th July 2013 to Friday 19th 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, socalled 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 easytocheck 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, socalled 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 easytocheck 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, socalled 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 easytocheck 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 facetdescription of polyhedra have been crucial in the success of branchandbound 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 algebraiccombinatorial geometry in optimization appears even greater.
In the past 5 years advances in algebraicgeometric algorithms have been used to prove unexpected new results on the computation of nonlinear 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 nonlinear 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 SIAMMOS. 
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 facetdescription of polyhedra have been crucial in the success of branchandbound 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 algebraiccombinatorial geometry in optimization appears even greater.
In the past 5 years advances in algebraicgeometric algorithms have been used to prove unexpected new results on the computation of nonlinear 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 nonlinear 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 SIAMMOS. 
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 facetdescription of polyhedra have been crucial in the success of branchandbound 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 algebraiccombinatorial geometry in optimization appears even greater.
In the past 5 years advances in algebraicgeometric algorithms have been used to prove unexpected new results on the computation of nonlinear 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 nonlinear 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 SIAMMOS. 
INI 1  
17:00 to 18:00  Welcome wine reception 
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 
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 HigherOrder Semidefinite Relaxations for MaxCut
The basic semidefinite relaxation for maxcut underlying the GoemansWilliamson hyperplane rounding procedure can be tightened in different ways. A straightforward approach is to add facetdefining 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 
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 nspace defined by X_1^{2d}+\dots+X_n^{2d}

INI 1  
15:30 to 16:00  Afternoon Tea  
16:00 to 16:30 
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 
Gap Inequalities for the MaxCut 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 righthand side of a gap inequality, for a given lefthand side, is NPhard. 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 (nonconvex MixedInteger 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 
09:30 to 10:00 
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 BenTal. A second consequence is the real radical duality theory for semidefinite programming.

INI 1  
10:00 to 10:30 
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 NPhard. 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 
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 zerodimensional. 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 
Scaling relationship between the copositive cone and a hierarchy of semidefinite approximations
Several NPcomplete 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 coNPcomplete 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 
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 NPhard. 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 
Cutting Planes for FirstLevel RLT Relaxations of Mixed 01 Programs
The ReformulationLinearization 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 firstlevel relaxation, based on optimally weakening valid inequalities for the secondlevel relaxation. These cutting planes can be applied to any pure or mixed 01 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 exponentiallylarge 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 
The ATruncated KMoment Problem
Let A be a finite subset of N^n, and K be a compact semialgebraic set. An Atms is a vector y indexed by elements in A. The ATruncated KMoment Problem (ATKMP) studies whether a given Atms y admits a Kmeasure
(i.e., a Borel measure supported in K) or not. We propose a numerical algorithm for solving ATKMPs. 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 Kmeasures and R[x]_A is Kfull, we can get a certificate for the nonexistence of representing measures. If y admits a Kmeasure, 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 ATKMP. 
INI 1  
15:00 to 15:30 
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 semialgebraic 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 semialgebraic
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 
09:30 to 10:00 
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 sumsofsquaresrelaxation 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 
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 branchandbound 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 
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 wellknown 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 FermatWeber 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 nonconvex 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 entangledassisted graph parameters
Graph parameters as the independence and the chromatic number are related to classical (zeroerror) communication problems. It is known that allowing the presence of entanglement, one of quantum mechanics most peculiar feature, might increase the efficiency of the (zeroerror) 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 nonnegative 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,jth 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 
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 nontrivial 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 
The width of 5dimensional prismatoids
Santos' construction of counterexamples 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 5dimensional prismatoids, obtaining the following results:
 There are 5prismatoids of width six with only 25 vertices, versus the 48 vertices in Santos' original construction. This leads to nonHirsch polytopes of dimension 20, rather than the original dimension 43.  There are 5prismatoids with n vertices and width Omega(\sqrt{n}) for arbitrarily large n. Hence, the width of 5prismatoids 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 
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 CelisDennisTapia problem
We study the socalled CelisDennisTapia (CDT) problem to minimize a nonconvex quadratic function over the intersection of two ellipsoids.
Contrasting with the wellstudied 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, nonconvex optimization, optimality condition, polynomial optimization, trust region problem Cospeaker: Michael Overton, Courant Institute of Math.~Sciences, New York University, U.S.A. 
INI 1  
16:30 to 17:00  Optimising polynomials over the simplex  INI 1  
17:00  End of Workshop  INI 1 