Semi-definite Programming

Global optimality in minimum compliance topology optimization of frames and shells by moment-sum-of-squares hierarchy

  • Didier Henrion
  • Martin Kružík
  • Marek Tyburec
  • Jan Zeman
    • Categories Civil and Environmental Engineering, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , , , ,

    The design of minimum-compliance bending-resistant structures with continuous cross-section parameters is a challenging task because of its inherent non-convexity. Our contribution develops a strategy that facilitates computing all guaranteed globally optimal solutions for frame and shell structures under multiple load cases and self-weight. To this purpose, we exploit the fact that the stiffness matrix is … Read more

    Stokes, Gibbs and volume computation of semi-algebraic sets

  • Didier Henrion
  • Jean-Bernard Lasserre
  • Matteo Tacchi
    • Categories Infinite Dimensional Optimization, Semi-definite Programming Tags , ,

    We consider the problem of computing the Lebesgue volume of compact basic semi-algebraic sets. In full generality, it can be approximated as closely as desired by a converging hierarchy of upper bounds obtained by applying the Moment-SOS (sums of squares) methodology to a certain infinite-dimensional linear program (LP). At each step one solves a semidefinite … Read more

    SDP-based bounds for the Quadratic Cycle Cover Problem via cutting plane augmented Lagrangian methods and reinforcement learning

  • Frank de Meijer
  • Renata Sotirov
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , , , ,

    We study the Quadratic Cycle Cover Problem (QCCP), which aims to find a node-disjoint cycle cover in a directed graph with minimum interaction cost between successive arcs. We derive several semidefinite programming (SDP) relaxations and use facial reduction to make these strictly feasible. We investigate a nontrivial relationship between the transformation matrix used in the … Read more

    Exact SDP relaxations of quadratically constrained quadratic programs with forest structures

  • Godai Azuma
  • Mituhiro Fukuda
  • Sunyoung Kim
  • Makoto Yamashita
    • Categories Global Optimization, Semi-definite Programming Tags , , ,

    We study the exactness of the semidefinite programming (SDP) relaxation of quadratically constrained quadratic programs (QCQPs). With the aggregate sparsity matrix from the data matrices of a QCQP with $n$ variables, the rank and positive semidefiniteness of the matrix are examined. We prove that if the rank of the aggregate sparsity matrix is not less … Read more

    Dual optimal design and the Christoffel-Darboux polynomial

  • Yohann De Castro
  • Didier Henrion
  • Jean-Bernard Lasserre
  • Fabrice Gamboa
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , , ,

    The purpose of this short note is to show that the Christoffel-Darboux polynomial, useful in approximation theory and data science, arises naturally when deriving the dual to the problem of semi-algebraic D-optimal experimental design in statistics. It uses only elementary notions of convex analysis. Article Download View Dual optimal design and the Christoffel-Darboux polynomial

    Learning Dynamical Systems with Side Information

  • Amir Ali Ahmadi
  • Bachir El Khadir
    • Categories Convex Optimization, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , ,

    We present a mathematical and computational framework for the problem of learning a dynamical system from noisy observations of a few trajectories and subject to side information. Side information is any knowledge we might have about the dynamical system we would like to learn besides trajectory data. It is typically inferred from domain-specific knowledge or … Read more

    Matchings, hypergraphs, association schemes, and semidefinite optimization

  • Yu Hin (Gary) Au
  • Levent Tunçel
  • Nathan Lindzey
    • Categories Polyhedra, Semi-definite Programming Tags , , , ,

    We utilize association schemes to analyze the quality of semidefinite programming (SDP) based convex relaxations of integral packing and covering polyhedra determined by matchings in hypergraphs. As a by-product of our approach, we obtain bounds on the clique and stability numbers of some regular graphs reminiscent of classical bounds by Delsarte and Hoffman. We determine … Read more

    Complexity Aspects of Local Minima and Related Notions

  • Amir Ali Ahmadi
  • Jeffrey Zhang
    • Categories Global Optimization Theory, Nonlinear Optimization, Semi-definite Programming Tags , , , , ,

    We consider the notions of (i) critical points, (ii) second-order points, (iii) local minima, and (iv) strict local minima for multivariate polynomials. For each type of point, and as a function of the degree of the polynomial, we study the complexity of deciding (1) if a given point is of that type, and (2) if … Read more

    On the weak second-order optimality condition for nonlinear semidefinite and second-order cone programming

  • Ellen H. Fukuda
  • Gabriel Haeser
  • Leonardo M. Mito
    • Categories Linear, Cone and Semidefinite Programming, Second-Order Cone Programming, Semi-definite Programming Tags , ,

    Second-order necessary optimality conditions for nonlinear conic programming problems that depend on a single Lagrange multiplier are usually built under nondegeneracy and strict complementarity. In this paper we establish a condition of such type for two classes of nonlinear conic problems, namely semidefinite and second-order cone programming, assuming Robinson’s constraint qualification and a generalized form … Read more

    Necessary and sufficient conditions for rank-one generated cones

  • C.J. Argue
  • Fatma Kılınç-Karzan
  • Alex L. Wang
    • Categories Quadratic Programming, Semi-definite Programming

    A closed convex conic subset $\cS$ of the positive semidefinite (PSD) cone is rank-one generated (ROG) if all of its extreme rays are generated by rank-one matrices. The ROG property of $\cS$ is closely related to the exactness of SDP relaxations of nonconvex quadratically constrained quadratic programs (QCQPs) related to $\cS$. We consider the case … Read more