<span class=strong>IMA Reception and Poster Session</span>

Tuesday, January 16, 2007 - 4:00pm - 6:30pm
Lind 400
  • Obstacle-sensitive Gain scheduling Using Semidefinite Programming
    Eric Feron (Georgia Institute of Technology)
    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.
  • Distributed Optimization in an Energy-constrained Network
    Seid Alireza Razavi Majomard (University of Minnesota, Twin Cities)
    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.
  • Application of Semidefinite Programming to Eigenvalue Problems for Elliptic Linear Partial Differential Equations
    Carlos Handy (Texas Southern University)
    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)
  • SparsePOP and Numerical Results
    Sunyoung Kim (Ewha Women's University)
    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.
  • Semidefinite Characterization and Computation of Real Radical Ideals
    Philipp Rostalski (Eidgenössische TH Zürich-Hönggerberg)
    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
    characterization of its real radical ideal I(V_R(I))is
    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.
  • Recent Progress in Applying Semidefinite Optimization to the Satisfiability Problem
    Miguel Anjos (University of Waterloo)
    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.
  • SeDuMi: A Package for Conic Optimization
    Yuriy Zinchenko (McMaster University)
    No Abstract
  • A PARALLEL Conic Interior Point Decomposition Approach for BLOCK ANGULAR Semidefinite Programs
    Kartik Sivaramakrishnan (North Carolina State University)
    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.
    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.
  • Solving Polynomial Systems via LMIs
    Graziano Chesi (University of Hong Kong)
    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.
  • Numerical Optimization Assisted by Noncommutative Symbolic Algebra
    Mauricio de Oliveira (University of California, San Diego)
    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.
  • Inverse Dynamical Analysis of Gene Networks Using Sparsity-promoting Regularization
    James Lu (Johann Radon Institute for Computational and Applied Mathematics )
    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

    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

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

  • Graphs of Transportation Polytopes
    Edward Kim (University of California)
    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.
  • Experiments with Linear and Semidefinite Relaxations for Solving the Minimum Graph Bisection Problem
    Christoph Helmberg (Technische Universität Chemnitz-Zwickau)
    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.
  • Sensor Network Localization, Euclidean Distance Matrix Completions, and Graph Realization
    Henry Wolkowicz (University of Waterloo)
    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

    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.
  • Stability Region Analysis Using Simulations and Sum-of-Squares Programming
    Ufuk Topcu (University of California, Berkeley)
    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
  • Computing the Best Low Rank Approximation of a Matrix
    Kenneth Driessel (Iowa State University)
    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.
  • An Exact Characterization of Bad Semidefinite Programs
    Gabor Pataki (University of North Carolina, Chapel Hill)
    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.
  • Advances on the BMV Trace Conjecture
    Christopher Hillar (Texas A & M University)
    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).