Linear, Cone and Semidefinite Programming

Perturbation analysis of nonlinear semidefinite programming under Jacobian uniqueness conditions

  • Ziran Yin
  • Liwei Zhang
    • Categories Semi-definite Programming

    We consider the stability of a class of parameterized nonlinear semidefinite programming problems whose objective function and constraint mapping all have second partial derivatives only with respect to the decision variable which are jointly continuous. We show that when the Karush-Kuhn-Tucker (KKT) condition, the constraint nondegeneracy condition, the strict complementary condition and the second order … Read more

    Exploiting sparsity for the min k-partition problem

  • Hassan L. Hijazi
  • Guanglei Wang
    • Categories 0-1 Programming, Semi-definite Programming Tags , , ,

    The minimum k-partition problem is a challenging combinatorial problem with a diverse set of applications ranging from telecommunications to sports scheduling. It generalizes the max-cut problem and has been extensively studied since the late sixties. Strong integer formulations proposed in the literature suffer from a prohibitive number of valid inequalities and integer variables. In this … Read more

    On the effectiveness of primal and dual heuristics for the transportation problem

  • Jonas Schwinn
  • Ralf Werner
    • Categories Linear Programming, Optimization Software Benchmark

    The transportation problem is one of the most popular problems in linear programming. Over the course of time a multitude of exact solution methods and heuristics have been proposed. Due to substantial progress of exact solvers since the mid of the last century, the interest in heuristics for the transportation problem over the last few … Read more

    Lower bounds on matrix factorization ranks via noncommutative polynomial optimization

  • David de Laat
  • Monique Laurent
  • Sander Gribling
    • Categories Semi-definite Programming Tags ,

    We use techniques from (tracial noncommutative) polynomial optimization to formulate hierarchies of semidefinite programming lower bounds on matrix factorization ranks. In particular, we consider the nonnegative rank, the positive semidefinite rank, and their symmetric analogues: the completely positive rank and the completely positive semidefinite rank. We study the convergence properties of our hierarchies, compare them … Read more

    Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization

  • David de Laat
  • Monique Laurent
  • Sander Gribling
    • Categories Semi-definite Programming Tags , ,

    In this paper we study bipartite quantum correlations using techniques from tracial polynomial optimization. We construct a hierarchy of semidefinite programming lower bounds on the minimal entanglement dimension of a bipartite correlation. This hierarchy converges to a new parameter: the minimal average entanglement dimension, which measures the amount of entanglement needed to reproduce a quantum … Read more

    A Data-Driven Distributionally Robust Bound on the Expected Optimal Value of Uncertain Mixed 0-1 Linear Programming

  • Samuel Burer
  • Guanglin Xu
    • Categories Robust Optimization, Semi-definite Programming, Stochastic Programming

    This paper studies the expected optimal value of a mixed 0-1 programming problem with uncertain objective coefficients following a joint distribution. We assume that the true distribution is not known exactly, but a set of independent samples can be observed. Using the Wasserstein metric, we construct an ambiguity set centered at the empirical distribution from … Read more

    Membership testing for Bernoulli and tail-dependence matrices

  • Daniel Krause
  • Jonas Schwinn
  • Ralf Werner
  • Matthias Scherer
    • Categories Finance and Economics, Linear Programming, Statistics Tags , , ,

    Testing a given matrix for membership in the family of Bernoulli matrices is a longstanding problem, the many applications of Bernoulli vectors in computer science, finance, medicine, and operations research emphasize its practical relevance. A novel approach towards this problem was taken by [Fiebig et al., 2017] for lowdimensional settings d

    On Solving the Quadratic Shortest Path Problem

  • Hao Hu
  • Renata Sotirov
    • Categories Semi-definite Programming Tags , , ,

    The quadratic shortest path problem is the problem of finding a path in a directed graph such that the sum of interaction costs over all pairs of arcs on the path is minimized. We derive several semidefinite programming relaxations for the quadratic shortest path problem with a matrix variable of order $m+1$, where $m$ is … Read more

    Equivalences and Differences in Conic Relaxations of Combinatorial Quadratic Optimization Problems

  • Naoki Ito
  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
  • Akiko Takeda
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , , ,

    Various conic relaxations of quadratic optimization problems in nonnega- tive variables for combinatorial optimization problems, such as the binary integer quadratic problem, quadratic assignment problem (QAP), and maximum stable set problem have been proposed over the years. The binary and complementarity conditions of the combi- natorial optimization problems can be expressed in several ways, each … Read more

    Self-concordant inclusions: A unified framework for path-following generalized Newton-type algorithms

  • Shu Lu
  • Tianxiao Sun
  • Quoc Tran-Dinh
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming

    We study a class of monotone inclusions called “self-concordant inclusion” which covers three fundamental convex optimization formulations as special cases. We develop a new generalized Newton-type framework to solve this inclusion. Our framework subsumes three schemes: full-step, damped-step and path-following methods as specific instances, while allows one to use inexact computation to form generalized Newton … Read more