Linear, Cone and Semidefinite Programming

Worst-case convergence analysis of gradient and Newton methods through semidefinite programming performance estimation

  • Etienne de Klerk
  • François Glineur
  • Adrien B. Taylor
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    We provide new tools for worst-case performance analysis of the gradient (or steepest descent) method of Cauchy for smooth strongly convex functions, and Newton’s method for self-concordant functions. The analysis uses semidefinite programming performance estimation, as pioneered by Drori en Teboulle [Mathematical Programming, 145(1-2):451–482, 2014], and extends recent performance estimation results for the method of … Read more

    Perturbation analysis of a class of conic programming problems under Jacobian uniqueness conditions

  • Ziran Yin
  • Liwei Zhang
    • Categories Linear, Cone and Semidefinite Programming, Second-Order Cone Programming, Semi-definite Programming

    We consider the stability of a class of parameterized conic programming problems which are more general than the C2-smooth parameterization. We show that when the Karush-Kuhn-Tucker (KKT) condition, the constraint nondegeneracy condition, the strict complementary condition and the second order sucient condition (named as Jacobian uniqueness conditions here) are satis ed at a feasible point of … Read more

    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