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 drealizability of graphs and have,
among other things, given a complete characterization of the
class of 3realizable 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 3realizable
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 3realizable
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.
« Back...
Solving polynomial matrix
inequalities in systems control design
Didier Henrion, LAASCNRS
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 Hinfinity optimal control,
convexity check for PMIs, LMI formulations without liftings
for convex PMIs, numerical issues related with scaling and
conditioning.
« Back...
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 nonlinear semidefinite programs. Various
particular problem classes, with Hinfinity 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
sumofsquares representations of polynomial matrices we
will finally compose relaxation families that can be shown
to be asymptotically exact.
« Back...
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.
LinearQuadratic 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)
« Back...
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 Ndimensional Euclidean space
and its nonnegative orthant, a pair of the Ndimensional
Euclidean space and the Ndimensional 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
ndimensional real variable vector x over a compact feasible
region { x : b(x) is in E+ }, where b(x) denotes an Evalued
polynomial in x. It is shown under a certain moderate
assumption on the Evalued 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.
« Back...
Electronic structure
calculations and semidefinite programs
Mituhiro Fukuda, Tokyo Institute of Technology
It has been a longtime 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 twobody
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 interiorpoint method
based algorithms to seek for high accurate optimal solutions
of hugescale SDPs in a very reasonable time.
« Back...
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 primaldual interiorpoint methods for SDPs. Some
typical examples and applications of SDPs are also presented
to show the significance of SDPs in the field of
optimization.
« Back...
Moments, sums of squares and
semidefinite programming
Jean B. Lasserre, LAASCNRS
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.
« Back...
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.
« Back...
Linear and nonlinear
semidefinite programs in structural optimization
Michal Kocvara,
University of ErlangenNuremberg
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 largescale 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.
« Back...
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
selfconcordant 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.
« Back...
Modelling with semidefinite and
copositive matrices (Tutorial lecture 1)
Franz Rendl, University of Klagenfurt
I will recall semidefinite relaxations for the maxcut
and the maxclique problem. It will turn out that completely
positive matrices would give stronger approximations, but
the resulting conelp is NPhard to solve. Similar results
are obtained for the quadratic assignment and the coloring
problem.
Material related to the talk (http:///www.math.uniklu.ac.at/or/Forschung/):
 A boundary point method to solve SDP
 Computational experience with a bundle approach for
semidefinite cutting plane relaxations of MaxCut
 The quadratic assignment problem
« Back...
Semidefinite and orthogonal
relaxations (Tutorial lecture 2)
Franz Rendl, University of Klagenfurt
The HoffmannWielandt 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.uniklu.ac.at/or/Forschung/):
 A boundary point method to solve SDP
 Computational experience with a bundle approach for
semidefinite cutting plane relaxations of MaxCut
 The quadratic assignment problem
« Back...
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.uniklu.ac.at/or/Forschung/):
 A boundary point method to solve SDP
 Computational experience with a bundle approach for
semidefinite cutting plane relaxations of MaxCut
 The quadratic assignment problem
« Back...
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.uniklu.ac.at/or/Forschung/):
 A boundary point method to solve SDP
 Computational experience with a bundle approach for
semidefinite cutting plane relaxations of MaxCut
 The quadratic assignment problem
« Back...
Inexact pathfollowing algorithms
for some convex quadratic SDP problems
Michael J. Todd, Cornell University
We propose a primaldual pathfollowing interiorpoint
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.
« Back...
HANSO and HIFOO: two new matlab
codes
Michael Overton, New York University
HANSO (Hybrid Algorithm for NonSmooth Optimization) is a
new Matlab code for nonsmooth, nonconvex optimization, built
on the BFGS, bundle and gradient sampling algorithms.
HIFOO (HInfinity FixedOrder Optimization) is a new
Matlab code for fixedorder 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.
« Back...
A finite branchandbound
algorithm for nonconvex quadratic programming via
semidefinite programming
Samuel Burer, University of Iowa
We present a branchandbound 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 boxconstrained case
yields a stateoftheart method for globally solving this
class of problems.
Joint work with D. Vandenbussche.
« Back...
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
MizunoToddYe predictorcorrector primaldual 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.
« Back...
Problem structure in
semidefinite programs arising in control and signal
processing
Lieven Vandenberghe, University of California at Los
Angeles
Generalpurpose implementations of interiorpoint methods
for semidefinite programming usually focus on exploiting
sparsity and lowrank 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 interiorpoint algorithms. These include problems
in which the coefficient matrices can be expressed as linear
combinations of a small set of rankone matrices, problems
with upper bounds on the matrix variables, and problems with
symmetry constraints. The techniques will be illustrated
with several applications: sumofsquares optimization
problems in signal processing, robust leastsquares problems
with structured uncertainty and a model calibration problem
in optical lithography.
« Back...
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
sumofsquares programming, control theory and learning
theory problems will be given if time permits.
« Back...
SDP approximation bounds for
quadratic optimization with applications to transmit
beamforming
Z.Q. Luo, University of Minnesota
We consider the NPhard 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 socalled {\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 NPhard 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.
« Back...
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 multiaccess communication and
quasiML 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, logbarriers, 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
 Multiuser transceiver design
 Rate allocation for multiterminal source coding
 SDP relaxation for quasiML detection
 Software, Matlab tools/interfaces, references
« Back...
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
largescale 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
genomewide information sources.
« Back...
