Workshop on semidefinite programming and its applications in control theory, combinatorial and global optimization

Friday September 27, 2002
LAAS-CNRS, Toulouse, France

Biographical sketches of the contributors with talk abstracts are given below.
Click here to go back to the main workshop page.

Miguel Anjos
Miguel F. Anjos is a Lecturer (Assistant Professor) in the Faculty of Mathematical Studies of the University of Southampton. He received his Ph.D. in 2001 from the University of Waterloo, Canada, working under the supervision of Professor Henry Wolkowicz. He previously completed a B.Sc. with First Class Honours in Computer Science at McGill University, and an M.S. in Scientific Computing and Computational Mathematics at Stanford University. More recently, he held a postdoctoral research fellowship at the Institute for Computer Science of the University of Cologne.

His research interests lie in in the application of continuous optimization techniques, primarily convex optimization, to NP-hard combinatorial optimization problems.

Title of the talk: An Improved Semidefinite Programming Relaxation for Satisfiability (SAT)

Abstract: The satisfiability (SAT) problem is a central problem in mathematical logic, computing theory, and artificial intelligence. An instance of SAT is specified by a set of boolean variables and a propositional formula in conjunctive normal form. Given such an instance, the SAT problem asks whether there is a truth assignment to the variables such that the formula is satisfied. It is well known that SAT is in general NP-complete, although several important special cases can be solved in polynomial time. We are interested in the application of SDP to satisfiability problems, and in particular in how SDP can be used to detect unsatisfiability. In this talk we introduce a new SDP relaxation for the satisfiability problem. To derive this SDP relaxation, we first formulate SAT as an optimization problem involving matrices. This formulation yields an SDP relaxation which significantly improves on the previous relaxation in the literature. The improved SDP relaxation arises from the recently introduced paradigm of ``higher liftings'' for constructing semidefinite programming relaxations of discrete optimization problems. The important characteristics of the SDP relaxation are its ability to prove that a given SAT formula is unsatisfiable independently of the lengths of the clauses in the formula, its potential to yield truth assignments satisfying the SAT instance if a feasible matrix of sufficiently low rank is computed, and the fact that it is more amenable to practical computation than previous SDPs arising from higher liftings. We present theoretical and computational results that support these claims.

Etienne de Klerk
Etienne de Klerk is an assistant professor at the Faculty of Information Technology and Systems of the Delft University of Technology in the Netherlands.

Research interests: Conic optimization, approximation algorithms for global and combinatorial optimization, interior point algorithms.

Current teaching: Nonlinear programming, Combinatorial Optimization, Randomized Algorithms

Title of the talk: Solving standard quadratic optimization problems via copositive programming.

Co-author: I.M. Bomze (University of Vienna).

Abstract: The problem of minimizing a (non-convex) quadratic function over the simplex (the standard quadratic optimization problem) has an exact convex reformulation as a copositive programming problem. In this talk we show how to approximate the optimal solution by approximating the cone of copositive matrices via systems of linear inequalities, and, more refined, linear matrix inequalities (LMI's). In particular, we show that our approach leads to a polynomial-time approximation scheme for the standard quadratic optimization problem. This is an improvement on the previous complexity result by Nesterov who showed that a 2/3-approximation is always possible.

Michal Kocvara
Michal Kocvara is currently with the Institute of Applied Mathematics, University of Erlangen, Germany, on leave from the Institute of Information Theory and Automation, Academy of Sciences of the Czech Republic, Prague. In 1991 he obtained his CSc. (Ph.D.) degree in Mathematics at the Mathematical Institute of the Czechoslovak Academy of Sciences, and in 2001 he obtained his DrSc. habilitation in Mathematics at the Charles University in Prague.

His research interests include structural optimization (material optimization of linear elastic bodies; truss optimization including single and multiple load topo or geo/topo design with displacement, stability and robustness constraints; shape optimizations of elastic bodies governed by variational inequalities), algorithms for the solution of large and sparse mathematical programs arising in structural optimization problems (these include PENNON, a code for convex and nonconvex problems of Nonlinear and Semidefinite Programming, and an iterative method for linear complementarity problems), and mathematical programs with equilibrium constraints (MPEC).

Title of the talk: PENNON - A Generalized Augmented Lagrangian Method for Semidefinite Programming.

Co-author: Michael Stingl (University of Erlangen-Nürnberg).

Abstract: We describe a generalization of the PBM method by Ben-Tal and Zibulevsky to convex semidefinite programming problems. The algorithm used is a generalized version of the Augmented Lagrangian method. We present details of this algorithm as implemented in the code PENNON. The code can also solve second-order conic programming (SOCP) problems, as well as problems with a mixture of SDP, SOCP and NLP constraints. Results of extensive numerical tests and comparison with other SDP codes are presented.

Monique Laurent
Monique Laurent received her Ph.D. at the University of Paris VII in 1986. After two years of employment as a research engineer at CNET (Centre National d'Etudes des Télécommunications), she became a researcher at CNRS (Centre National de la Recherche Scientifique). She joined first the University Paris Dauphine and, from 1992, she was a member of the computer science departement at Ecole Normale Supérieure in Paris. Since 1997, she his a researcher at CWI in Amsterdam.

Monique Laurent's research interests focus on combinatorial optimization and discrete geometry. In particular, she has worked on polyhedral theory of cuts in graphs, embeddings of metric spaces, metric aspects of lattices, matrix completions, and semidefinite programming. Part of this work has led to a coauthored book, Geometry of Cuts and Metrics, published in 1997.

Title of the talk: Semidefinite relaxations for 0/1 polytopes.

Abstract: Several methods for constructing linear and/or semidefinite relaxations of 0/1 polytopes have been proposed; in particular, the lift-and-project method (Balas, Ceria and Cornuéjols), the iterative matrix-cut method (Lovász and Schrijver), the RLT method (Sherali and Adams), and some algebraic methods based on representations of polynomials as sums of squares and the dual theory of moments (Lasserre, Parrilo, Shor). We show that the tightest relaxations are obtained when applying the algebraic construction and give a simple combinatorial interpretation in the 0/1 case. We study in detail an application to the maximum cut problem. Several results are presented, including a linear lower bound on the number of iterations needed for finding the cut polytope, and a geometric result on the set of moment matrices.

Dominikus Noll

Pierre Apkarian
Dominikus Noll is a full professor of applied mathematics at Université Paul Sabatier, Toulouse. His research interests include feedback control, medical imaging, inverse problems and nonlinear optimization.

Co-author Pierre Apkarian is a research engineer at ONERA Toulouse, and a part time professor of applied mathematics at Université Paul Sabatier. His research interest are in automatic control and nonlinear optimization.

Title of the talk: Feedback control design via nonlinear programming

Abstract: Many problems in feedback control may be cast as mathematical programs under matrix inequality constraints. The most prominent example is Hinfinty synthesis, which may be solved by semidefinite programming (SDP). In this talk we will look at more complicated cases like robust output feedback control synthesis and reduced order synthesis, which are NP-hard problems and require approaches beyond SDP. We discuss algorithms suited to solve these difficult problems. A typical test example in satellite attitude control  is presented.

Pablo Parrilo
Pablo A. Parrilo was born in Buenos Aires, Argentina. He received the Electronics Engineering degree from the University of Buenos Aires in 1994, and a PhD in Control and Dynamical Systems from the California Institute of Technology in June 2000. He held short-term visiting appointments at UC Santa Barbara, Lund Institute of Technology, and UC Berkeley. In October 2001, he joined the Automatic Control Department of the Swiss Federal Institute of Technology (ETH Zurich) as an Assistant Professor.

His research interests include robust control and identification, robustness analysis, networked systems, convex optimization and computational algebra.

Title of the talk: Sums of squares and zero dimensional ideals.

Abstract: In practice, many polynomial optimization problems have additional algebraic properties that, suitably exploited, allow for much more efficient algorithms. In this talk, we will focus on how equality constraints can be exploited within the sum of squares / semidefinite programming framework. In this case, using a quotient basis, all computations can be done in the coordinate ring, notably decreasing the computational burden. As a consequence, for zero dimensional systems, we obtain a simple constructive proof of the existence of distinguished sum of squares representations for polynomials nonnegative over semialgebraic sets. Degree bounds are directly obtained, as the cardinality of the support of the summands equals the number of points in the variety.

Jos Sturm
Jos F. Sturm completed his academic studies in Econometrics at the University of Groningen, Groningen, The Netherlands in 1993, and received the Ph.D. degree from Erasmus University, Rotterdam, The Netherlands in 1997. He has been an assistant professor at Maastricht University and a post-doc at McMaster University. He is currently an associate professor in the Department of Econometrics and Operations Research at Tilburg University, Tilburg, The Netherlands.

His research interests are in large scale optimization, cone linear programming, robust optimization and interior point methods.

Dr Sturm was awarded the Gijs de Leve Prize for the best thesis in Operations Research in The Netherlands in the years 1997-1999, and has received research grants from The Netherlands Organisation for Scientific Research (NWO).

Title of the talk: A new variant of the interior point method, for large scale and warm started linear programs.

Abstract: A new variant of the interior point method is proposed. While using a low rank update scheme, the iterates are both powerful and inexpensive to compute. The low rank updates are realized through a product form factorization. The new algorithm is particularly useful when it is initialized from a warm start.