Semidefinite Programming and its
Applications
(15 Dec 2005 - 31 Jan 2006)
~ Abstracts ~
A semidefinite programming approach
to tensegrity theory and realizability of graphs
Yinyu Ye, Stanford University
Recently, Connelly and Sloughter have introduced the notion of d-realizability of graphs and have, among other things, given a complete characterization of the class of 3-realizable graphs. However, their work has left open the question of finding an algorithm for realizing those graphs. In this paper, we resolve that question by showing that the semidefinite programming (SDP) approach can be used for realizing 3-realizable graphs. Specifically, we use SDP duality theory to show that given a graph G and a set of lengths on its edges, the optimal dual multipliers of a certain SDP give rise to a proper equilibrium stress for some realization of G. Using this result and the techniques in {CS04,S04}, we then obtain a polynomial approximation algorithm for realizing 3-realizable graphs. Our results also establish a previously unexplored connection between SDP and tensegrity theories and allow us to derive some interesting properties of tensegrity frameworks.
Solving polynomial matrix
inequalities in systems control design
Didier Henrion, LAAS-CNRS
With the help of simple examples, we first show how polynomial matrix inequalities (PMIs) naturally arise in standard systems control design problems (static output feedback, H2 optimal control). Second, we review currently available numerical methods to deal with these PMI problems: (local) nonlinear semidefinite programming (SDP), and (global) linear SDP, or LMI relaxations. Finally, if time permits, we describe some simple open problems related with PMIs: use of liftings in H-infinity optimal control, convexity check for PMIs, LMI formulations without liftings for convex PMIs, numerical issues related with scaling and conditioning.
Linear matrix inequality
relaxations in robust control
Carsten Scherer, Delft University of Technology
Natural formulations of nominal or robust controller analysis or synthesis problems typically require the solution of non-linear semi-definite programs. Various particular problem classes, with H-infinity control playing a role model, can be equivalently translated into convex linear matrix inequalities (LMI's) which can in turn be solved rather efficiently. If structured uncertainties enter the picture, exact convexification is in general out of reach and one has to be satisfied with approximations in terms of LMI's.
The purpose of this presentation is to illustrate why robust LMI's form a unifying framework for handling uncertainties. Moreover, we will reveal how to systematically construct convex relaxations of robust LMI problems that can be complemented by numerically verifiable tests for the absence of conservatism. Based on recent sum-of-squares representations of polynomial matrices we will finally compose relaxation families that can be shown to be asymptotically exact.
Separated continuous conic
programming: model, theory and methods
Shuzhong Zhang, The Chinese University of Hong Kong
Abstract: Separated Continuous Linear Programming has played an important role in modelling and solving queueing networks and control problems. In this talk we shall discuss a new model termed as Separated Continuous Conic Programming (SCCP), in which a certain type of conic constraints, such as Second Order Cones and the cone of positive semidefinite matrices, are used to replace the ordinary nonnegative constraints. Such models are important in solving e.g. Linear-Quadratic control problems with state constraints. We establish a symmetric duality structure for SCCP, and consequently use the duality relationships to solve the SCCP problems by conic optimization, via discretization.
(joint work with David D. Yao and Xiaoqing Wang)
An extension of sums of squares
relaxations to polynomial optimization problems over
symmetric cones
Masakazu Kojima, Tokyo Institute of Technology
Abstract: Let E and E+ be a finite dimensional real vector space and a symmetric cone embedded in E; examples of E and E+ include a pair of the N-dimensional Euclidean space and its nonnegative orthant, a pair of the N-dimensional Euclidean space and the N-dimensional second order cone, and a pair of the space of m x m real symmetric (or complex Hermitian) matrices and the cone of their positive semidefinite matrices. Sums of squares relaxations are extended to a polynomial optimization problem over E+, i.e., a minimization of a real valued polynomial a(x) in the n-dimensional real variable vector x over a compact feasible region { x : b(x) is in E+ }, where b(x) denotes an E-valued polynomial in x. It is shown under a certain moderate assumption on the E-valued polynomial b(x) that optimal values of a sequence of sums of squares relaxations of the problem, which are converted into a sequence of semidefinite programs when they are numerically solved, converge to the optimal value of the problem.
Electronic structure
calculations and semidefinite programs
Mituhiro Fukuda, Tokyo Institute of Technology
It has been a long-time dream in electronic structure theory in chemical physics/physical chemistry to compute ground state energies of atomic and molecular systems by employing a variational approach in which the two-body reduced density matrix is the unknown variable. A convex relaxation of this problem becomes an SDP and it is empirically known that its solution gives an excellent approximation to the targeting problem despite its huge computational cost. Examples of such achievement which traditional electronic structure methods cannot obtain will be shown based on numerical experiments using parallel high performance computers. The main difficult here is the cost limitation (time & memory) of using interior-point method based algorithms to seek for high accurate optimal solutions of huge-scale SDPs in a very reasonable time.
Introduction to semidefinite
programs
Masakazu Kojima, Tokyo Institute of Technology
This lecture is designed for graduate students and researchers who are not much familiar to SDPs (semidefinite programs) and/or who want to look over SDPs quickly. Assuming the basics of linear programs and linear algebra, the lecture places main emphasis on the basic theory of SDPs and primal-dual interior-point methods for SDPs. Some typical examples and applications of SDPs are also presented to show the significance of SDPs in the field of optimization.
Moments, sums of squares and
semidefinite programming
Jean B. Lasserre, LAAS-CNRS
Abstract: We will introduce the generalized problem of moments (GPM), and some of its many potential applications. When data are polynomials, we then show how the GPM can be approximated (and sometimes even solved) efficiently via semidefinite programming relaxations. On the way, we will develop some aspects of the duality between moments and sums of squares (s.o.s.), as well as the relationship between nonnegative polynomials and s.o.s.
Symmetric relaxations for
nonconvex optimization problems
Leonid Faybusovich, University of Notre Dame
We discuss several classes of nonconvex optimization problems which admit relaxations by convex optimization problems involving symmetric cones. Two types of results are considered: exact relaxations based on rank estimates and inexact relaxations quality of which is estimated based on an abstract version of famous matrix cube theorem. A variety of new results is obtained. Most of them are for problems admitting relaxations involving cones of positive semidefinite quaternion Hermitian matrices which are realized as cones of structured Hermitian matrices with complex entries. Some applications are briefly discussed.
Linear and nonlinear
semidefinite programs in structural optimization
Michal Kocvara,
University of Erlangen-Nuremberg
Several formulations of structural optimization problems based on linear and nonlinear semidefinite programming will be presented. SDP allows us to formulate and solve poblems with difficult constraints that could hardly be solved before. We will show that sometimes it is advantageous to prefer a nonlinear formulation to a linear one. All the presented formulations result in large-scale sparse (nonlinear) SDPs. In the second part of the talk we will show how these problems can be solved by our augmented Lagrangian code PENNON. Numerical examples will illustrate the talk.
Joint work with Michael Stingl.
Barrier subgradient method
Yurii Nesterov, Université catholique de Louvain
We present a new subgradient scheme for nonsmooth convex optimization problems. This scheme is based on a self-concordant barrier for the basic feasible set. It is suitable for solving problems in relative scale. We discuss some applications including fractional covering problem, maximal concurrent flow problem, semidefinite relaxations and nonlinear online optimization.
Modelling with semidefinite and
copositive matrices (Tutorial lecture 1)
Franz Rendl, University of Klagenfurt
I will recall semidefinite relaxations for the max-cut and the max-clique problem. It will turn out that completely positive matrices would give stronger approximations, but the resulting cone-lp is NP-hard to solve. Similar results are obtained for the quadratic assignment and the coloring problem.
Material related to the talk (http:///www.math.uni-klu.ac.at/or/Forschung/):
- A boundary point method to solve SDP
- Computational experience with a bundle approach for
semidefinite cutting plane relaxations of Max-Cut
- The quadratic assignment problem
Semidefinite and orthogonal
relaxations (Tutorial lecture 2)
Franz Rendl, University of Klagenfurt
The Hoffmann-Wielandt inequality is an old result related to optimizing a quadratic function over the set of orthogonal matrices. Recently, Anstreicher and Wolkowicz have established a connection of this result to semidefinite programs. We will take a closer look at this connection, and explore further results along this direction. This will allow us to get stronger bounds on the bandwidth of a graph.
Material related to the talk (http:///www.math.uni-klu.ac.at/or/Forschung/):
- A boundary point method to solve SDP
- Computational experience with a bundle approach for
semidefinite cutting plane relaxations of Max-Cut
- The quadratic assignment problem
Solving large semidefinite
programs (Tutorial lecture 3)
Franz Rendl, University of Klagenfurt
I will recall difficulties with standard methods to solve SDP. Then I will explore several possibilities to approach larger instances. These will include the classical bundle and the spectral bundle method.
Material related to the talk (http:///www.math.uni-klu.ac.at/or/Forschung/):
- A boundary point method to solve SDP
- Computational experience with a bundle approach for
semidefinite cutting plane relaxations of Max-Cut
- The quadratic assignment problem
Solving large semidefinite
programs (Tutorial lecture 4)
Franz Rendl, University of Klagenfurt
I will also present some very recent approaches to solve large scale SDPs. In particular we will take a look at the boundary point method, and also at the possibility to exploit symmetry of the input data to simplify computations.
Material related to the talk (http:///www.math.uni-klu.ac.at/or/Forschung/):
- A boundary point method to solve SDP
- Computational experience with a bundle approach for
semidefinite cutting plane relaxations of Max-Cut
- The quadratic assignment problem
Inexact path-following algorithms
for some convex quadratic SDP problems
Michael J. Todd, Cornell University
We propose a primal-dual path-following interior-point method for solving certain convex quadratic semidefinite (QSDP) problems, using a preconditioned iterative method to solve the Schur complement equation. Numerical experiments on a variety of QSDPs with matrices of dimensions up to 2000 are described.
HANSO and HIFOO: two new matlab
codes
Michael Overton, New York University
HANSO (Hybrid Algorithm for Non-Smooth Optimization) is a new Matlab code for nonsmooth, nonconvex optimization, built on the BFGS, bundle and gradient sampling algorithms.
HIFOO (H-Infinity Fixed-Order Optimization) is a new Matlab code for fixed-order control design. It is built on HANSO.
In this talk, we will discuss the scope and purpose of these codes, the algorithms underlying them, and examples of their application.
A finite branch-and-bound
algorithm for nonconvex quadratic programming via
semidefinite programming
Samuel Burer, University of Iowa
We present a branch-and-bound algorithm for nonconvex quadratic programming, which is based on solving semidefinite relaxations at each node of the enumeration tree. In contrast to existing global optimization methods, which generate an infinite number of nodes, our method is guaranteed to terminate finitely. Computational results demonstrate the effectiveness of the method, a highlight being that only a few nodes are required in practice. Furthermore, specialization to the box-constrained case yields a state-of-the-art method for globally solving this class of problems.
Joint work with D. Vandenbussche.
Complexity results for path
following algorithms for linear programming which take into
account the geometry of the central path
Renato D.C. Monteiro, Georgia Institute of Technology
In this talk, we discuss complexities of path following algorithms for linear programming which take into account the geometry of the central path. More specifically, we review old and new iteration complexities for the Mizuno-Todd-Ye predictor-corrector primal-dual algorithm. We also introduce a certain curvature of the central path whose integral along this path is directly connected with the iteration complexity of the MTY algorithm. We then present a new result stating that the (improper) integral of the curvature over the whole path is finite and its value depends only on the dimension of the problem and a certain condition number associated with the constraint matrix of the LP problem. We will also discuss open problems and directions for future research along this topic.
Problem structure in
semidefinite programs arising in control and signal
processing
Lieven Vandenberghe, University of California at Los
Angeles
General-purpose implementations of interior-point methods for semidefinite programming usually focus on exploiting sparsity and low-rank structure of the coefficient matrices. In this talk we will discuss some other types of structure that can be exploited by straightforward modifications of standard interior-point algorithms. These include problems in which the coefficient matrices can be expressed as linear combinations of a small set of rank-one matrices, problems with upper bounds on the matrix variables, and problems with symmetry constraints. The techniques will be illustrated with several applications: sum-of-squares optimization problems in signal processing, robust least-squares problems with structured uncertainty and a model calibration problem in optical lithography.
Automatic dualization
Johan Löfberg, Swiss Federal Institute of Technology
Many optimization problems gain from being interpreted and solved in either primal or dual form. For a user with a particular application, one of these forms is usually more natural for the modelling phase, but this is not always the most efficient one for computations. This talk presents an implementation in the optimization modeling tool YALMIP that allows the user to define conic optimization problems in a preferred format, and then automatically derive a YALMIP model of the dual of this problem, solve the dual, and recover original variables. Applications of this feature in sum-of-squares programming, control theory and learning theory problems will be given if time permits.
SDP approximation bounds for
quadratic optimization with applications to transmit
beamforming
Z.Q. Luo, University of Minnesota
We consider the NP-hard problem of finding a minimum norm vector in $n$-dimensional real or complex Euclidean space, subject to $m$ concave homogeneous quadratic constraints. We show that the semidefinite programming relaxation for this nonconvex quadratically constrained quadratic program (QP) provides an $O(m^2)$ approximation in the real case, and an $O(m)$ approximation in the complex case. Moreover, we show that these bounds are tight up to a constant factor. When the Hessian of each constraint function is of rank one (namely, outer products of some given so-called {\it steering} vectors) and the phase spread of the entries of these steering vectors are bounded away from $\pi/2$, we establish a certain "constant factor" approximation (depending on the phase spread but independent of $m$ and $n$) for both the SDP relaxation and a convex QP restriction of the original NP-hard problem. When the homogeneous quadratic constraints are separable and $m=n$, we show that the SDP relaxation is actually tight. All theoretical results will be illustrated through a transmit beamforming application in wireless communication.
Convex optimization techniques
for signal processing and communication
Z.Q. Luo, University of Minnesota
Description of Tutorial:
In recent years there have been major advances in the algorithms and software for convex conic optimization. These research advances are beginning to find exciting applications in digital signal processing and communications, giving powerful new modeling and computational tools to solve previously considered intractable problems. This tutorial will use various engineering examples to illustrate some of the basic concepts and algorithms in convex conic optimization that are most useful in signal processing and communication. These include the interior point algorithms for linear programming, Second Order Cone programming and Semidefinite Programming (SDP), and complexity bounds. The emphasis of this tutorial is on how to recognize and exploit convexity (sometimes hidden) in various engineering formulations, and introduce mathematical techniques for efficient solution or relaxation of nonconvex problems arising from communication system design. Theoretical foundation and general complexity analysis will be mentioned, but is not the primary focus. Various application examples will be considered, including interior point least squares algorithm, pulse shaping filter design, robust beamforming, channel equalization, transceiver design for multi-access communication and quasi-ML detection via SDP relaxation. The aim of this tutorial is to give attendees the background required to use modern convex optimization methods in their own research or engineering work.
Anticipated audience:
Researchers and practitioners involved in developing algorithms for digital signal processing applications or communications system design and implementation.
Outline:
- Introduction to basic concepts
Definitions: convexity, linear programming, SDP, SOCP, interior point methods, log-barriers, complexity bounds
Illustrating examples: channel equalization, covariance matrix approximation - Applications in digital signal processing
- interior point least squares
- pulse shaping filter design
- robust beamforming
- linear decentralized estimation in sensor networks - Applications in communication system design
- Multi-user transceiver design
- Rate allocation for multi-terminal source coding
- SDP relaxation for quasi-ML detection - Software, Matlab tools/interfaces, references
Classification problems with
heterogeneous information
Gert Lanckriet, University of California at San Diego
An important challenge for the field of machine learning is to leverage the diversity of information available in large-scale learning problems, in which different sources of information often capture different aspects of the data. Beyond classical vectorial data formats, information in the format of graphs, trees, strings and beyond have become widely available (e.g., the linked structure of webpages, amino acid sequences describing proteins). In this talk I introduce a principled computational and statistical framework to integrate data from heterogeneous information sources in a flexible and unified way. The approach is formulated within the unifying learning framework of kernel methods and applied to the specific case of classification. The resulting formulation takes the form of a semidefinite programming (SDP) problem. Applications to computational biology are presented, showing that classification performance can be enhanced by integrating diverse genome-wide information sources.
