Semi-definite Programming

Distributionally robust expectation inequalities for structured distributions

  • Paul J. Goulart
  • Bart Paul Gerard Van Parys
  • Manfred Morari
    • Categories Convex Optimization, Semi-definite Programming, Stochastic Programming Tags , , ,

    Quantifying the risk of unfortunate events occurring, despite limited distributional information, is a basic problem underlying many practical questions. Indeed, quantifying constraint violation probabilities in distributionally robust programming or judging the risk of financial positions can both be seen to involve risk quantification, notwithstanding distributional ambiguity. In this work we discuss worst-case probability and conditional … Read more

    Quantum and classical coin-flipping protocols based on bit-commitment and their point games

  • Ashwin Nayak
  • Jamie Sikora
  • Levent Tunçel
    • Categories Linear Programming, Second-Order Cone Programming, Semi-definite Programming Tags , , , ,

    We focus on a family of quantum coin-flipping protocols based on quantum bit-commitment. We discuss how the semidefinite programming formulations of cheating strategies can be reduced to optimizing a linear combination of fidelity functions over a polytope. These turn out to be much simpler semidefinite programs which can be modelled using second-order cone programming problems. … Read more

    Lower Bounds on Complexity of Lyapunov Functions for Switched Linear Systems

  • Amir Ali Ahmadi
  • Raphaël Jungers
    • Categories Convex Optimization, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , ,

    We show that for any positive integer $d$, there are families of switched linear systems—in fixed dimension and defined by two matrices only—that are stable under arbitrary switching but do not admit (i) a polynomial Lyapunov function of degree $\leq d$, or (ii) a polytopic Lyapunov function with $\leq d$ facets, or (iii) a piecewise … Read more

    New bounds for the max-hBccut and chromatic number of a graph

  • Renata Sotirov
  • Edwin van Dam
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , , , , , ,

    We consider several semidefinite programming relaxations for the max-$k$-cut problem, with increasing complexity. The optimal solution of the weakest presented semidefinite programming relaxation has a closed form expression that includes the largest Laplacian eigenvalue of the graph under consideration. This is the first known eigenvalue bound for the max-$k$-cut when $k>2$ that is applicable to … Read more

    Exact solutions to Super Resolution on semi-algebraic domains in higher dimensions

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

    We investigate the multi-dimensional Super Resolution problem on closed semi-algebraic domains for various sampling schemes such as Fourier or moments. We present a new semidefinite programming (SDP) formulation of the l1-minimization in the space of Radon measures in the multi-dimensional frame on semi-algebraic sets. While standard approaches have focused on SDP relaxations of the dual … Read more

    New Semidefinite Programming Relaxations for the Linear Ordering and the Traveling Salesman Problem

  • Philipp Hungerländer
    • Categories Approximation Algorithms, Production and Logistics, Semi-definite Programming

    In 2004 Newman suggested a semidefinite programming relaxation for the Linear Ordering Problem (LOP) that is related to the semidefinite program used in the Goemans-Williamson algorithm to approximate the Max Cut problem. Her model is based on the observation that linear orderings can be fully described by a series of cuts. Newman shows that her … Read more

    A Semidefinite Opimization Approach to the Target Visitation Problem

  • Philipp Hungerländer
    • Categories Production and Logistics, Semi-definite Programming

    We propose an exact algorithm for the Target Visitation Problem (TVP). The (TVP) is a composition of the Linear Ordering Problem and the Traveling Salesman Problem. It has several military and non-military applications, where two important, often competing factors are the overall distance traveled (e.g. by an unmanned aerial vehicle) and the visiting sequence of … Read more

    Constrained trace-optimization of polynomials in freely noncommuting variables

  • Igor Klep
  • Janez Povh
    • Categories Basic Sciences Applications, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , , , , , , , ,

    The study of matrix inequalities in a dimension-free setting is in the realm of free real algebraic geometry (RAG). In this paper we investigate constrained trace and eigenvalue optimization of noncommutative polynomials. We present Lasserre’s relaxation scheme for trace optimization based on semidefinite programming (SDP) and demonstrate its convergence properties. Finite convergence of this relaxation … Read more

    Mathematical Programming Models Based on Hub Covers in Graph Query Processing

  • Ş. İlker Birbil
  • Kerem Bülbül
  • Belma Yelbay
    • Categories 0-1 Programming, Applications - Science and Engineering, Semi-definite Programming Tags , , , ,

    The use of graph databases for social networks, images, web links, pathways and so on, has been increasing at a fast pace and promotes the need for efficient graph query processing on such databases. In this study, we discuss graph query processing — referred to as graph matching — and an inherent optimization problem known … Read more

    Convergence analysis for Lasserre’s measure–based hierarchy of upper bounds for polynomial optimization

  • Etienne de Klerk
  • Monique Laurent
  • Zhao Sun
    • Categories Global Optimization Theory, Semi-definite Programming Tags

    We consider the problem of minimizing a continuous function f over a compact set K. We analyze a hierarchy of upper bounds proposed by Lasserre in [SIAM J. Optim. 21(3) (2011), pp. 864-􀀀885], obtained by searching for an optimal probability density function h on K which is a sum of squares of polynomials, so that … Read more