His research interests lie in in the application of continuous optimization techniques, primarily convex optimization, to NP-hard combinatorial optimization problems.
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.
Research interests: Conic optimization, approximation algorithms for global and combinatorial optimization, interior point algorithms.
Current teaching: Nonlinear programming, Combinatorial Optimization, Randomized Algorithms
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.
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).
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'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.
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.
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.
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.
His research interests include robust control and identification, robustness analysis, networked systems, convex optimization and computational algebra.
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.
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).
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.