Linear, Cone and Semidefinite 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

    First order optimality conditions for mathematical programs with second-order cone complementarity constraints

  • Jane J. Ye
  • Jinchuan Zhou
    • Categories Complementarity and Variational Inequalities, Nonsmooth Optimization, Second-Order Cone Programming Tags , , , , ,

    In this paper we consider a mathematical program with second-order cone complementarity constraints (SOCMPCC). The SOCMPCC generalizes the mathematical program with complementarity constraints (MPCC) in replacing the set of nonnegative reals by a second-order cone. We show that if the SOCMPCC is considered as an optimization problem with convex cone constraints, then Robinson’s constraint qualification … Read more

    Some Applications of Polynomial Optimization in Operations Research and Real-Time Decision Making

  • Amir Ali Ahmadi
  • Anirudha Majumdar
    • Categories Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We demonstrate applications of algebraic techniques that optimize and certify polynomial inequalities to problems of interest in the operations research and transportation engineering communities. Three problems are considered: (i) wireless coverage of targeted geographical regions with guaranteed signal quality and minimum transmission power, (ii) computing real-time certificates of collision avoidance for a simple model of … 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

    Extended Formulations for Independence Polytopes of Regular Matroids

  • Volker Kaibel
  • Jon Lee
  • Matthias Walter
  • Stefan Weltge
    • Categories Linear Programming, Polyhedra Tags , , ,

    We show that the independence polytope of every regular matroid has an extended formulation of size quadratic in the size of its ground set. This generalizes a similar statement for (co-)graphic matroids, which is a simple consequence of Martin’s extended formulation for the spanning-tree polytope. In our construction, we make use of Seymour’s decomposition theorem … 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

    A strong polynomial gradient algorithm in Linear Programming

  • Peter A. Bruijs
    • Categories Convex Optimization, Linear Programming

    It has been an open question whether the Linear Programming (LP) problem can be solved in strong polynomial time. The simplex algorithm does not offer a polynomial bound, and polynomial algorithms by Khachiyan and Karmarkar don’t have the strong characteristic. The curious fact that non-linear algorithms would be needed to deliver the strongest complexity result … 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