semidefinite programming

Optimized Dimensionality Reduction for Moment-based Distributionally Robust Optimization

  • ShiyiJiang
  • Jianqiang Cheng
  • Kai Pan
  • Z.J. Max Shen
    • Categories Optimization in Data Science, Robust Optimization, Semi-definite Programming Tags , , , ,

    Moment-based distributionally robust optimization (DRO) provides an optimization framework to integrate statistical information with traditional optimization approaches. Under this framework, one assumes that the underlying joint distribution of random parameters runs in a distributional ambiguity set constructed by moment information and makes decisions against the worst-case distribution within the set. Although most moment-based DRO problems … Read more

    Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator

  • Yu Hin (Gary) Au
  • Levent Tunçel
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Semi-definite Programming Tags , , , ,

    We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász-Schrijver SDP operator \( \text{LS}_+\), with a particular focus on a search for relatively small graphs with high \( \text{LS}_+\)-rank (the least number of iterations of the \( \text{LS}_+\) operator on the fractional stable set polytope to compute the … Read more

    Semidefinite approximations for bicliques and biindependent pairs

  • Monique Laurent
  • Sven Polak
  • Luis Felipe Vargas
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , , , , ,

    We investigate some graph parameters dealing with biindependent pairs $(A,B)$ in a bipartite graph $G=(V_1\cup V_2,E)$, i.e., pairs $(A,B)$ where $A\subseteq V_1$, $B\subseteq V_2$ and $A\cup B$ is independent. These parameters also allow to study bicliques in general graphs. When maximizing the cardinality $|A\cup B|$ one finds the stability number $\alpha(G)$, well-known to be polynomial-time … Read more

    On solving the MAX-SAT using sum of squares

  • Lennart Sinjorgo
  • Renata Sotirov
    • Categories 0-1 Programming, Branch and Cut Algorithms, Semi-definite Programming Tags , , , ,

    We consider semidefinite programming (SDP) approaches for solving the maximum satisfiabilityproblem (MAX-SAT) and the weighted partial MAX-SAT. It is widely known that SDP is well-suitedto approximate the (MAX-)2-SAT. Our work shows the potential of SDP also for other satisfiabilityproblems, by being competitive with some of the best solvers in the yearly MAX-SAT competition.Our solver combines … Read more

    Polynomial argmin for recovery and approximation of multivariate discontinuous functions

  • Didier Henrion
  • Milan Korda
  • Jean-Bernard Lasserre
    • Categories Basic Sciences Applications, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    We propose to approximate a (possibly discontinuous) multivariate function f(x) on a compact set by the partial minimizer arg min_y p(x,y) of an appropriate polynomial p whose construction can be cast in a univariate sum of squares (SOS) framework, resulting in a highly structured convex semidefinite program. In a number of non-trivial cases (e.g. when … Read more

    A Note on Semidefinite Representable Reformulations for Two Variants of the Trust-Region Subproblem

  • Sarah Kelly
  • Yuyuan Ouyang
  • Boshi Yang
    • Categories Cone Programming, Semi-definite Programming Tags , , ,

    Motivated by encouraging numerical results in the literature, in this note we consider two specific variants of the trust-region subproblem and provide exact semidefinite representable reformulations. The first is over the intersection of two balls; the second is over the intersection of a ball and a special second-order conic representable set. Different from the technique … Read more

    Linear optimization over homogeneous matrix cones

  • Levent Tunçel
  • Lieven Vandenberghe
    • Categories Cone Programming, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    A convex cone is homogeneous if its automorphism group acts transitively on the interior of the cone, i.e., for every pair of points in the interior of the cone, there exists a cone automorphism that maps one point to the other. Cones that are homogeneous and self-dual are called symmetric. The symmetric cones include the … Read more

    A Strengthened SDP Relaxation for Quadratic Optimization Over the Stiefel Manifold

  • Samuel Burer
  • Kyungchan Park
    • Categories Global Optimization, Quadratic Programming, Semi-definite Programming Tags , ,

    We study semidefinite programming (SDP) relaxations for the NP-hard problem of globally optimizing a quadratic function over the Stiefel manifold. We introduce a strengthened relaxation based on two recent ideas in the literature: (i) a tailored SDP for objectives with a block-diagonal Hessian; (ii) and the use of the Kronecker matrix product to construct SDP relaxations. Using synthetic instances on … Read more

    The exact worst-case convergence rate of the alternating direction method of multipliers

  • Moslem Zamani
  • Hadi Abbaszadehpeivasti
  • Etienne de Klerk
    • Categories Convex Optimization Tags , , ,

    Recently, semidefinite programming performance estimation has been employed as a strong tool for the worst-case performance analysis of first order methods. In this paper, we derive new non-ergodic convergence rates for the alternating direction method of multipliers (ADMM) by using performance estimation. We give some examples which show the exactness of the given bounds. We … Read more

    Partitioning through projections: strong SDP bounds for large graph partition problems

  • Frank de Meijer
  • Renata Sotirov
  • Angelika Wiegele
  • Shudian Zhao
    • Categories Semi-definite Programming Tags , , , ,

    The graph partition problem (GPP) aims at clustering the vertex set of a graph into a fixed number of disjoint subsets of given sizes such that the sum of weights of edges joining different sets is minimized. This paper investigates the quality of doubly nonnegative (DNN) relaxations, i.e., relaxations having matrix variables that are both … Read more