January 16 - 20, 2007
Extending the work of de Klerk, Warners and van Maaren, we propose new
semidefinite programming (SDP) relaxations for the satisfiability (SAT)
problem. The SDP relaxations are partial liftings motivated by the
Lasserre hierarchy of SDP relaxations for 0-1 optimization problems.
Theoretical and computational results show that these relaxations have a
number of favourable properties, particularly as a means to prove that a
given SAT formula is unsatisfiable, and that this approach compares
favourably with existing techniques for SAT.
By a noncommutative multidimensional linear system we mean a linear
discrete-time input/state/output system with evolution along a
finitely generated free semigroup. A formal Z-transform of the
input-output map results in a transfer function equal to a
formal power series in noncommuting indeterminates with operator (or
matrix) coefficients. If one imposes energy-balance inequalities and
additional structure to the system equations, the resulting transfer
function is a formal power series with the additional structure of
interest for analyzing the robust control problem for a plant with
linear-fractional-modeled time-varying structured uncertainty.
The Bounded Real Lemma for such systems is closely connected with work
of Paganini on the robust control of such systems. An abelianization
of the system equations leads to systems with evolution along a
multidimensional integer lattice with transfer function equal to a
linear-fractional expression in several commuting variables of
Givon-Roesser, Fornasini-Marchesini or other structured types. Connections
with the automata theory of Schuetzenberger, Fliess, Eilenberg and others
from the 1960s will also be discussed. This talk reports on joint
work of the speaker with Tanit Malakorn (Naresuan University,
Thailand) and Gilbert Groenewald (North West University, South Africa).
We consider the problem of computing the maximum absolute value of a real
multivariate polynomial on the unit sphere. We identify a class of polynomials for which
the problem admits a randomized polynomial time approximation algorithm consisting in computing the maximum absolute value of the restriction of the polynomial onto a
random subspace of logarithmic dimension and scaling the result.
The characteristic feature of polynomials admitting such an algorithm is that they are
"focused": the ratio of their maximum absolute value and the L^{2} norm is large.
We present a complete derivation of coprime factorizations for a class of
multi-dimensional systems containing linear parameter-varying and uncertain
systems. A generalization of coprime factors model reduction using a balanced
truncation approach is then given, with error bounds
on the factorized mapping in the l2-induced norm. The proposed reduction
method is thus applicable to linear parameter-varying and uncertain systems
that do not satisfy the usual l2-induced stability constraint
required by the standard non-factored truncation methods.
We address the problem of evaluating the expected optimal objective
value of a discrete optimization problem under uncertainty in the objective
coefficients. The probabilistic model we consider prescribes limited marginal
distributional information for the objective coefficients in the form of
moments. We show that for a fairly general class of marginal information,
a tight upper (lower) bound on the expected optimal objective value of
a discrete maximization (minimization) problem can be computed in
polynomial time if the corresponding deterministic discrete
optimization problem is solvable
in polynomial time. We provide an efficiently solvable semidefinite
programming formulation to compute this tight bound.
We use the insights from this analysis to:
a) understand the
percistency of a decision variable, i.e.,
the probability that
it is part of an optimal solution;
for instance, in project scheduling, when the task activity times are
random, the challenge is to determine a set of critical activities
that will potentially lie on the longest path;
b) to analyze the
asymptotic behavior of a general class of combinatorial problems that includes
the linear assignment, spanning tree and traveling salesman problems, under
knowledge of complete marginal distributions, with and without
independence. We calculate the limiting constants exactly.
(joint work with Karthik Natarajan and Chung Piaw Teo)
The world around us often seems terribly complex, chaotic and difficult to understand. We encounter this every day: in the weather, social networks, sophisticated machinery, the internet. Frequently this complexity arises from the interaction of widely diverse scales in time and space. For example, the weather can turn in minutes, while the climate persists for many many years. Can math and science help us to make sense of all this complexity, or is it a study doomed from the start? Illustrating with many examples, Professor Budd will show that all is not lost. He will explain how simple properties often emerge from seemingly very complex systems, and how we can use these properties to gain understanding.
Read More...
Joint work with Y.S. Hung.
The problem of computing the solution of systems of polynomial equalities and inequalities is considered. First, it is shown that the solutions of these systems can be found by looking for vectors with polynomial structure in linear spaces obtained via a convex LMI optimization. Then, it is shown that an upper bound to the dimension of the linear spaces where the sought solutions are looked for can be imposed in a non-conservative way by imposing suitable linear matricial constraints. This allows one to obtain the linear spaces with the smallest dimension, which is important because the solutions can be extracted only if the dimension of the linear spaces is smaller than a certain threshold. Moreover, the proposed approach allows one to improve the numerical accuracy of the extraction mechanism.
We describe how a symbolic computer algebra tool (NCAlgebra) that can handle symbolic matrix (noncommutative) products is used to numerically solve systems and control problems. Our current focus is on semidefinite programs arising from control theory, where matrix variables appear naturally. Our tools keep matrix variables aggregated at all steps of a primal-dual interior-point algorithm. Symbolic matrix expressions are automatically generated and used on iterative numerical procedures for the determination of search directions, showing promising results.
Consider the following Problem: Given an m-by-n real matrix
A and a positive integer k, find the m-by-n matrix with rank k
that is closest to A. (I use the Frobenius inner product.)
I shall present a rank-preserving differential equation (d.e.)
in the space of m-by-n real matrices which solves this
problem. In particular, I shall show that if X(t) is a solution
of this d.e. then the distance between X(t) and A decreases;
in other words, this distance function is a Lyapunov function
for the d.e. I shall also show that (generically) this d.e. converges
to a unique stable equilibrium point. This point is the
solution of the given problem.
The graphical model formalism allows to describe multivariate probability distributions using a graph where random
variables are represented by nodes, and the absence of an edge corresponds to conditional independence. While this
formalism is very general, the corresponding maximum-likelihood problem is often challenging numerically. In addition,
one often needs to obtain a graph that is sparse, in order to enhance interpretability of the result. In this talk, we examine
the problem where log-likelihood function is penalized by an l-one norm term to encourage sparsity, in two special
cases,first for Gaussian then for Boolean variables. In the Gaussian case, we discuss first-order methods and a block-
coordinate descent algorithm. For Boolean random variables, the problem is NP-hard, due to an exponential number of
terms in the log-likelihood function. We discuss two approximations, one based on Wainwright and Jordan's log-
determinant approximation (2005), and another based on lifting and rank relaxation.
Joint work with Mazen Farhood.
We present an application of semidefinite programming techniques to the regulation of vehicle trajectories in the vicinity of obstacles. We design control laws, together with Lyapunov functions that guarantee closed-loop stability and performance of the vehicle's regulation loop. These control laws are easy to implement and automatically "relax the system's gains" when away from the obstacles, while tightening them when obstacle proximity is detected.
The calculation of eigenvalues for stiff elliptic linear
partial differential equations (LPDEs) can be plagued with
significant inaccuracies depending on the "estimation" methods
used (i.e. variational, finite differencing, asymptotic
analysis, perturbative, Galerkin, etc.). A preferred approach
is to be able to generate tight, converging lower and upper
bounds to the eigenvalues, thereby removing any uncertainties
in the reliability of the generated results. Twenty years ago
one such method was developed by Handy, Bessis, and co-workers
[1-3]. This general approach is referred to as the Eigenvalue
Moment Method (EMM) and involves a Semidefinite Programming
formalism coupled with a Linear Programming based “Cutting
Algorithm.” It makes use of well known nonnegativity properties
of Sturm-Liouville type systems combined with important
theorems from the classic Moment Problem. The EMM procedure has
been used to solve a variety of LPDEs on various support spaces
(i.e. unbounded, semi-bounded, bounded, periodic, discrete).
Equivalent gradient search variational reformulations,
exploiting higher levels of convexity, have also been developed
leading to the Volcano Function representation [4]. It is also
possible to extend EMM to certain non-hermitian systems of
importance in forefront areas in mathematical physics. Here
too, the EMM approach can yield converging lower and upper
bounds to the real and imaginary parts of the complex
eigenvalues (or other physical parameters) [5]. More recently
EMM was broadened (exploiting certain quasi-convexity
properties and the generalized eigenvlaue problem) in order to
convexify a multi-extrema plagued procedure in mathematical
physics [6]. We outline the important EMM results achieved over
the last two decades.
1. C. R. Handy and D. Bessis, "Rapidly Convergent Lower Bounds
for the Schrodinger Equation Ground State Energy," Phys. Rev.
Lett. 55, 931 (1985).
2. C. R. Handy, D. Bessis, and T. R. Morley, "Generating
Quantum Energy Bounds by the Moment Method: A Linear
Programming Approach," Phys. Rev. A 37, 4557 (1988).
3. C. R. Handy, D. Bessis, G. Sigismondi, and T. D. Morley,
"Rapidly Converging Bounds for the Ground State Energy of
Hydrogenic Atoms in Superstrong Magnetic Fields," Phys. Rev.
Lett. 60, 253 (1988).
4. C. R. Handy, K. Appiah, and D. Bessis "Moment-Problem
Formulation of a Minimax Quantization Procedure", Phys. Rev. A
50, 988 (1994).
5. C. R. Handy, "Generating Converging Bounds to the (Complex)
Discrete States of the P^{2} + iX^{3} + iaX Hamiltonian," J. Phys.
A: Math. Gen. 34, 5065 (2001).
6. C. R. Handy “(Quasi)-convexification of Barta’s
(multi-extrema) bounding theorem," J. Phys. A: Math. Gen.
39, 3425 (2006)
Given a graph with node weights, the convex hull of the incidence
vectors of all cuts satisfying a weight restricition on each side
is called the bisection cut polytope. We study the facial structure
of this polytope which shows up in many graph partitioning problems
with applications in VLSI-design or frequency assignment. We give
necessary and in some cases sufficient conditions for the knapsack
tree inequalities introduced in Ferreira et al. 1996 to be
facet-defining. We extend these inequalities to a richer class by
exploiting that each cut intersects each cycle in an even number of
edges. Furthermore, we present a new class of inequalities that are
based on non-connected substructures yielding non-linear right-hand
sides. We show that the supporting hyperplanes of the convex
envelope of this non-linear function correspond to the faces of the
so-called cluster weight polytope, for which we give a complete
description under certain conditions. Finally, we incorporate
cutting planes algorithms based on the presened inequalities in a
branch-and-cut framework and discuss their interaction with the
linear and semidefinite relaxation.
Joint work by Jean-Bernard Lasserre, Johan Löfberg, Christophe Prieur and Emmanuel Trélat.
The new release 3.0 of the Matlab package GloptiPoly is introduced
through an application to a class of nonlinear optimal control problems
for which the data (differential equations, state and control constraints,
cost) are multivariate polynomials. GloptiPoly 3.0 is aimed at solving
generalized moment problems. It allows to manipulate several measures and define linear decision problems on their moments. The problems can then be solved numerically with any semidefinite programming solver interfaced with YALMIP.
We discuss some progress on a long-standing conjecture in
mathematical physics due to Bessis, Moussa, and Villani (1975). The
statement is enticingly simple (thanks to a reformulation by Elliot Lieb
and Robert Seiringer): For every positive integer m and every pair of
positive semidefinite matrices A and B, the polynomial
p(t) = Tr[(A+tB)^{m}]
has nonnegative coefficients. Our approach allows for several reductions
to this difficult conjecture. For instance, it would be enough to show
that a nonzero (matrix) coefficient (A+tB)^{m} has at least 1 positive
eigenvalue. Additionally, if the conjecture is true for infinitely many
m, then it is true for all m. Finally, two challenges to the SOS
community are proposed: Prove the conjecture in dimension 3 for m = 6
(known) and m = 7 (unknown).
Joint work with Jesus A. de Loera (University of California, Davis).
Transportation polytopes are well-known objects in operations reseach and mathematical programming. These polytopes have very quick
tests for feasiblity, coordinates of a vertex can be quickly determined, and they have nice embedding properties: every polytope can
be viewed as a certain kind of transportation polytope. Using the notion of chamber complex, Gale diagrams, and the theory of secondary
polytopes we are able to exhaustively and systematically enumerate all combinatorial types of nondegenerate transportation polytopes of
small sizes. These generic polytopes (those of maximal dimension whose vertices are simple) will have the largest graph diameters and
vertex counts in their class. Using our exhaustive lists, we give results on some of the conjectures of Yemelichev, Kovalev, and
Kratsov. In particular, this poster focuses on questions related to the 1-skeleton graph of these polyhedra. The study of
1-skeleta of these polytopes are fundamental in attempting to consider the complexity of the simplex method of linear programming.
SparesPOP is MATLAB implementation of a sparse semidefinite programming (SDP)
relaxation method proposed for polynomial optimization problems (POPs)
in the recent paper by Waki, Kim, Kojima and Muramatsu. The sparse SDP relaxation
is based on "a hierarchy of LMI relaxations of increasing dimensions"
by Lasserre, and exploits a sparsity structure of polynomials in POPs.
The efficiency of SparsePOP to compute bounds for optimal values of POPs
is increased and larger scale POPs can be handled. Numerical results are shown
to illustrate the perfomance of SparsePOP.
A polynomial optimization problem (POP) is a problem of minimizing a polynomial
objective function subject to polynomial equalities and inequalities. It is getting
popular to apply the sum of squares (SOS) relaxation to compute global minimum
solutions of a POP. The SOS relaxation problem is reduced to a semidefinite
programming problem (SDP), which we can solve by applying the primal-dual interior-point
method. In this process, exploiting sparsity is essential in solving a large-scale POP. We present
"correlative sparsity," a certain structured sparsity of a POP which is characterized
as a sparse Cholesky factorization of an aggregated sparsity pattern matrix of the POP.
With this correlative sparsity, we can apply the sparse SOS relaxation to a large-scale POP, and
we can solve the resulting SDP efficiently by the primal-dual interior-point method.
We also discuss some applications.
Approximation of positive polynomials by sums of squares has important
applications to polynomial optimisation. In this talk, I will survey
the main recent results achieved on that topic:
I will consider positive (respectively, non-negative) polynomials on
compact (respectively, unbounded) semi-algebraic sets. I will discuss
representations in the associated preorderings (respectively, linear
representations in the associated quadratic module). The
representation often depends on
the dimension of the semi-algebraic set; I will present stronger results
in the low dimensional case. I will also highlight special representations
when the positive polynomials under consideration are sparse (that is,
satisfy some separation and overlap conditions on the variables appearing
in the monomials).
We provide a sufficient condition on a class of
compact basic semialgebraic sets K for their convex hull
to have a lifted semidefinite representation (SDr). This lifted
SDr
is explicitly expressed in terms of the polynomials that define
K.
Examples are provided. For convex and compact basic
semi-algebraic sets
K defined by concave polynomials,
we also provide an explicit lifted SDr when the nonnegative
Lagrangian
L_{f} associated with
K and any linear polynomial f, is a sum of squares. We then
provide an approximate lifted SDr in the general convex case.
By this we mean that for every fixed a>0, there is a convex set
K_{r} in
sandwich between K and K+aB
(where B is the unit ball), with an explicit lifted SDr in
terms of the
polynomials that define K.
For a special class of convex sets K, we also provide the
explicit
dependence of r with respect to a.
Given an ODE model for a biological system, the forward problem consists of
determining its solution behavior. However, many biological questions are of
the inverse type: what are the possible dynamics that can arise out of the
model? how is the control mechanism encoded in the topology of the regulatory
network?
We propose inverse dynamical analysis as a methodology for addressing various
questions that arise in studying biological systems, from the initial
modelling to the proposal of new experiments. In addition, once a
satisfactory model has been developed, the method can be used to design
various bifurcation phenotypes that exhibit certain dynamical properties. To
summarize, the proposed methodology consists of the following two inverse
analyses:
- inverse eigenvalue analysis, to probe and characterize parameter
combinations leading to changes in the qualitative dynamics;
- inverse bifurcation analysis, to identify and design mechanisms that can
give rise to a set of bifurcation phenotypes.
In our work, we use sparsity-promoting regularization functional to 'sparsely'
map dynamical behaviors to parameter sets. In combination with hierarchical
identification strategies, the underlying mechanisms can be elucidated. We
demonstrate some applications, from exploring possible evolutionary scenarios
to analyzing influential interactions in a cell phase transition model.
Many ideas from convex analysis and
real algebraic geometry extend canonically to the
operator space setting giving rise to the notions of
matrix (non-commutative) convex sets and functions.
These notions also model matrix inequalities
which are scalable in the sense that they do not
explicitly depend upon the size of the matrices
involved.
This talk will survey matrix convexity emphasizing the
rigid nature of convexity in the non-commutative semi-algebraic
setting. It may aslo include a discussion of
characterizing factorizations of a non-commutative polynomial
in terms of the signature of its Hessian.
Read More...
SDP's duality theory has been somewhat less well studied than its algorithmic aspects. Strong
duality, — expected in linear programming fails in many cases, and the variety of how
things can go wrong is bewildering: one can have nonattainment in either one of the primal
and the dual problems, attainment on both sides, but a finite duality gap, etc.
The main result we present in this talk is a surprisingly simple, exact,
"excluded minor" type characterization of all semidefinite systems that have a badly behaved
dual for some objective function.
The characterization is based on some new, fundamental results in convex analysis on the closedness of the linear image of a closed convex cone. In particular, our result is a necessary
condition for the closedness of the linear image
— as opposed to the usual sufficient conditions, such as the existence
of a Slater-point, or polyhedrality. Our conditions are
necessary and sufficient, when the cone belongs to a large class,
called nice cones.
We discuss algorithms for optimizing polynomials on
semialgebraic sets using representation theorems from real algebraic
geometry for positive polynomials. In the case of compact semialgebraic
sets, the method of Lasserre generates a sequence of SDP relaxations
which converge to the solution, however this method does not always
work in the non-compact case. We will discuss work of Demmel, Nie,
and Sturmfels in the global case and joint work with Demmel and Nie
in the case of non-compact semialgebraic sets.
We consider a distributed optimization problem whereby two nodes S1 and S2 wish to jointly minimize a common convex quadratic cost function f(x1; x2), subject to separate local constraints on x1 and x2, respectively. Suppose that node S1 has control of variable x1 only and node S2 has control of variable x2 only. The two nodes locally update their respective variables and periodically exchange their values over a noisy channel. Previous studies of this problem have mainly focused on the convergence issue and the analysis of convergence rate. In this work, we focus on the communication energy and study its impact on convergence. In particular, we consider a class of distributed stochastic gradient type algorithms implemented using certain linear analog messaging schemes. We study the minimum amount of communication energy required for the two nodes to compute an epsilon-minimizer of f(x1; x2) in the mean square sense. Our analysis shows that the communication energy must grow at least at the rate of (1/epsilon). We also derive specific designs, which attain this minimum energy bound, and provide simulation results that confirm our theoretical analysis. Extension to the multiple node case is described.
Joint work with J.-B. Lasserre and M. Laurent.
For an ideal
given by a set of generators, h_1...h_m in R[x] a new
semidefinite
characterization of its real radical ideal I(V_R(I))is
presented,
provided it is zero-dimensional (even if I is not). Moreover
we propose
an algorithm using numerical linear algebra and semidefinite
optimization techniques, to compute all (finitely many)
points of the
real variety V_R=V(I) subset R^n as well as generators of
the real
radical ideal. The latter are obtained in the form of border
or Gröbner
bases. The algorithm is based on moment relaxations and, in
contrast to other existing methods, it exploits the real algebraic nature
of the
problem right from the beginning and avoids the computation
of complex components.
Global optimization of polynomial functions under polynomial constraints will be related to general algorithmic problems in real algebraic geometry and the current existing complexity results discussed.
The results in the special case of quadratic polynomials will be described.
Main reference for the talk: S. Basu, R. Pollack, M.-F. Roy: Algorithms in real algebraic geometry, Springer, second edition (2006)
We discuss complexity aspects of Lasserre's sequence
of SDP relaxations of a given
polynomial optimization problem. As a special example where a
lot is known, we
consider the MAXCUT problem. The following topics should be
covered:
- the moment problem and convergence to unique minimizers,
- speed of convergence to the optimal value,
- Scheiderers result on stability and the moment problem,
- the approximability result of Goemans and Williamson for
MAXCUT, and
- the inapproximability result of Khot, Kindler, Mossel and
O'Donnell for MAXCUT.
Semidefinite programs (SDPs) with a BLOCK-ANGULAR structure occur
routinely in practice. In some cases, it is also possible to exploit the
SPARSITY and SYMMETRY in an unstructured SDP,
and preprocess it into an equivalent SDP with a block-angular structure.
We present a PARALLEL CONIC INTERIOR POINT DECOMPOSITION approach to
solve block-angular SDPs. Our aim is to solve such a SDP in an iterative
fashion between a master problem (a quadratic conic program); and
decomposed and distributed subproblems (smaller SDPs) in a parallel
computing environment. We present our computational results with the
algorithm on several test instances; our computations were performed on
the distributed HENRY2 cluster at North Carolina State University.
Given a semidefinite program, specified by matrices
with rational entries, each coordinate of its optimal solution
is
an algebraic number. We study the degree of the minimal
polynomials
of these algebraic numbers. Geometrically, this degree counts
the
critical points attained by a linear functional on a fixed rank
locus in a linear space of symmetric matrices. We determine
this degree
using methods from complex algebraic geometry, such as
projective duality,
determinantal varieties, and their Chern classes. This is a
joint paper with
Jiawang Nie and Kristian Ranestad, posted at
rxiv.org/abs/math.OC/0611562.
The problem of computing bounds on the region-of-attraction for systems
with polynomial vector fields is considered. Invariant subsets of the
region-of-attraction are characterized as sublevel sets of Lyapunov
functions. Finite dimensional polynomial parameterizations for Lyapunov
functions are used. A methodology utilizing information from simulations
to generate Lyapunov function candidates satisfying necessary conditions
for bilinear constraints is proposed. The suitability of Lyapunov function
candidates are assessed solving linear sum-of-squares optimization
problems. Qualified candidates are used to compute invariant subsets of
the region-of-attraction and to initialize various bilinear search
strategies for further optimization. We illustrate the method on several
small examples from the literature and a controlled aircraft dynamics
problem.
I will discuss the characterization of convex sets in
^{m}
which can be represented by Linear Matrix Inequalities, i.e., as feasible
sets of semidefinite programmes. There is a simple necessary condition,
called rigid convexity, which has been shown to be sufficient for sets in
the plane and is conjectured to be sufficient (in a somewhat weakened
sense) for any m.
This should be contrasted with the situation for matrix convex sets that
will feature in the talk of Scott McCullough, where all the available
evidence suggests that any matrix convex set with noncommutative algebraic
boundary admits an LMI representation.
This is a joint work with Bill Helton.
The problem of recovering the sparsity pattern of an unknown signal arises in various domains, including graphical model selection, signal denoising, constructive approximation, compressive sensing, and subset selection in regression. The standard optimization-theoretic formulation of sparsity recovery involves l_0-constraints, and typically leads to computationally intractable optimization problems. This difficulty motivates the development and analysis of approximate methods; in particular, a great deal of work over the past decade has focused on the use of convex l_1-relaxations for sparsity recovery.
In this work, we analyze the performance of l_1-constrained quadratic programming for recovering an unknown signal in p dimensions with at most s non-zero entries based on a set of n noisy observations. Of interest is the number of observations n that are required, as a function of the model dimension p and sparsity index s, for exact sparsity recovery. We analyze this question in the high-dimensional setting, in which both the model dimension p and number of observations n tend to infinity. Our main result is to establish, for a broad class of Gaussian measurement ensembles, precise threshold results on the required growth rate for successful recovery using the computationally tractable l_1 relaxation.
We study Semidefinite Programming, SDP, relaxations for Sensor Network
Localization, SNL, with anchors and with noisy distance information. The
main point of the paper is to view SNL as a (nearest) Euclidean Distance
Matrix, EDM, completion problem and to show the advantages for using
this latter, well studied model. We first show that the current popular
SDP relaxation is equivalent to known relaxations in the literature for
EDM completions. The existence of anchors in the problem is not special.
The set of anchors simply corresponds to a given fixed clique for the
graph of the EDM problem. We next propose a method of projection when a
large clique or a dense subgraph is identified in the underlying graph.
This projection reduces the size, and improves the stability, of the
relaxation.
In addition, viewing the problem as an EDM completion problem yields
better low rank approximations for the low dimensional realizations.
And, the projection/reduction procedure can be repeated for other given
cliques of sensors or for sets of sensors, where many distances are
known. Thus, further size reduction can be obtained.
Optimality/duality conditions and a primal-dual interior-exterior path
following algorithm are derived for the SDP relaxations We discuss the
relative stability and strength of two formulations and the
corresponding algorithms that are used. In particular, we show that the
quadratic formulation arising from the SDP relaxation is better
conditioned than the linearized form, that is used in the literature and
that arises from applying a Schur complement.