HOME    »    SCIENTIFIC RESOURCES    »    Volumes
Abstracts and Talk Materials
Optimization and Control
January 16-20, 2007

Miguel F. Anjos (University of Waterloo)

Recent progress in applying semidefinite optimization to the satisfiability problem
December 31, 1969

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.

Joseph A. Ball (Virginia Polytechnic Institute and State University)

Conservative structured noncommutative multidimensional linear systems: realization theory and bounded real lemma
January 17, 2007

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).

Alexander Barvinok (University of Michigan)

Optimization of polynomials on the unit sphere
January 16, 2007

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 L2 norm is large.

Carolyn Beck (University of Illinois at Urbana-Champaign)

Coprime factorizations and reduction of linear parameter-varying systems
January 17, 2007

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.

Dimitris Bertsimas (Massachusetts Institute of Technology)

Discrete optimization under moment uncertainty: complexity, persistency and asymptotics
January 19, 2007

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)

Christopher J. Budd (University of Bath)

Math matters - IMA public lecture: Making sense of a complex world
January 18, 2007

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.


Graziano Chesi (University of Hong Kong)

Solving polynomial systems via LMIs
December 31, 1969

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.

Mauricio de Oliveira (University of California, San Diego)

Numerical optimization assisted by noncommutative symbolic algebra
December 31, 1969

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.

Kenneth R. Driessel (Iowa State University)

Computing the best low rank approximation of a matrix
December 31, 1969

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.

Laurent El Ghaoui (University of California, Berkeley)

Estimation of sparse graphical models
January 19, 2007

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.

Eric Feron (Georgia Institute of Technology)

Obstacle-sensitive gain scheduling using semidefinite programming
December 31, 1969

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.

Carlos R. Handy (Texas Southern University)

Application of semidefinite programming to eigenvalue problems for elliptic linear partial differential equations
December 31, 1969

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 P2 + iX3 + 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)

Christoph Helmberg (Technische Universität Chemnitz-Zwickau)

Experiments with linear and semidefinite relaxations for solving the minimum graph bisection problem
December 31, 1969

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.

Didier Henrion (Centre National de la Recherche Scientifique (CNRS))

Polynomial optimal control with GloptiPoly 3.0
January 18, 2007

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.

Christopher Hillar (University of California, Berkeley)

Advances on the BMV trace conjecture
December 31, 1969

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).

Edward D. Kim (University of California)

Graphs of transportation polytopes
December 31, 1969

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.

Sunyoung Kim (Ewha Women's University)

SparsePOP and numerical results
December 31, 1969

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.

Masakazu Kojima (Tokyo Institute of Technology)

Sparsity in polynomial optimization
January 20, 2007

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.

Salma Kuhlmann (University of Saskatchewan)

Approximation of positive polynomials by sums of squares
January 20, 2007

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).

Jean Bernard Lasserre Fatal error: Call to a member function getVisitorOrganization() on a non-object in /srv/web/IMA-Propel/build/classes/discovery3/Person.php on line 78