semidefinite programming

A Polynomial-Time Affine-Scaling Method for Semidefinite and Hyperbolic Programming

  • James Renegar
  • Mutiara Sondjaja
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    We develop a natural variant of Dikin’s affine-scaling method, first for semidefinite programming and then for hyperbolic programming in general. We match the best complexity bounds known for interior-point methods. All previous polynomial-time affine-scaling algorithms have been for conic optimization problems in which the underlying cone is symmetric. Hyperbolicity cones, however, need not be symmetric. … Read more

    Inexactness of SDP Relaxation and Valid Inequalities for Optimal Power Flow

  • Santanu S. Dey
  • Burak Kocuk
  • Xu Andy Sun
    • Categories Global Optimization Tags , , ,

    It has been recently proven that the semidefinite programming (SDP) relaxation of the optimal power flow problem over radial networks is exact under technical conditions such as not including generation lower bounds or allowing load over-satisfaction. In this paper, we investigate the situation where generation lower bounds are present. We show that even for a … Read more

    Efficient First-Order Methods for Linear Programming and Semidefinite Programming

  • James Renegar
    • Categories Linear Programming, Semi-definite Programming Tags , , ,

    We present a simple transformation of any linear program or semidefinite program into an equivalent convex optimization problem whose only constraints are linear equations. The objective function is defined on the whole space, making virtually all subgradient methods be immediately applicable. We observe, moreover, that the objective function is naturally “smoothed,” thereby allowing most first-order … Read more

    A Gentle, Geometric Introduction to Copositive Optimization

  • Samuel Burer
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    This paper illustrates the fundamental connection between nonconvex quadratic optimization and copositive optimization—a connection that allows the reformulation of nonconvex quadratic problems as convex ones in a unified way. We intend the paper for readers new to the area, and hence the exposition is largely self-contained. We focus on examples having just a few variables … Read more

    Sensitivity analysis of semidefinite programs without strong duality

  • Yuen-Lam Cheung
  • Henry Wolkowicz
    • Categories Semi-definite Programming Tags , , ,

    Suppose that we are given a feasible conic program with a finite optimal value and with strong duality failing. It is known that there are small perturbations of the problem data that lead to relatively big changes in the optimal value. We quantify the notion of big change in the case of a semidefinite program … Read more

    Coordinate shadows of semi-definite and Euclidean distance matrices

  • Dmitriy Drusvyatskiy
  • Gabor Pataki
  • Henry Wolkowicz
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , , ,

    We consider the projected semi-definite and Euclidean distance cones onto a subset of the matrix entries. These two sets are precisely the input data defining feasible semi-definite and Euclidean distance completion problems. We characterize when these sets are closed, and use the boundary structure of these two sets to elucidate the Krislock-Wolkowicz facial reduction algorithm. … Read more

    Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques

  • Florian Jarre
  • Felix Lieder
  • Fatameh Bani Asadi Rad
    • Categories 0-1 Programming, Combinatorial Optimization Tags , , , , , ,

    A reformulation of quadratically constrained binary programs as duals of set-copositive linear optimization problems is derived using either \(\{0,1\}\)-formulations or \(\{-1,1\}\)-formulations. The latter representation allows an extension of the randomization technique by Goemans and Williamson. An application to the max-clique problem shows that the max-clique problem is equivalent to a linear program over the max-cut … Read more

    A search for quantum coin-flipping protocols using optimization techniques

  • Ashwin Nayak
  • Jamie Sikora
  • Levent Tunçel
    • Categories Global Optimization Applications, Linear, Cone and Semidefinite Programming, Optimization Software Design Principles Tags , ,

    Coin-flipping is a cryptographic task in which two physically separated, mistrustful parties wish to generate a fair coin-flip by communicating with each other. Chailloux and Kerenidis (2009) designed quantum protocols that guarantee coin-flips with near optimal bias away from uniform, even when one party deviates arbitrarily from the protocol. The probability of any outcome in … Read more

    Lagrangian-Conic Relaxations, Part II: Applications to Polynomial Optimization Problems

  • Naohiko Arima
  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
    • Categories Convex Optimization, Semi-definite Programming Tags , , , ,

    We present the moment cone (MC) relaxation and a hierarchy of sparse Lagrangian-SDP relaxations of polynomial optimization problems (POPs) using the unified framework established in Part I. The MC relaxation is derived for a POP of minimizing a polynomial subject to a nonconvex cone constraint and polynomial equality constraints. It is an extension of the … Read more

    A Comprehensive Analysis of Polyhedral Lift-and-Project Methods

  • Yu Hin (Gary) Au
  • Levent Tunçel
    • Categories Combinatorial Optimization, Integer Programming, Linear, Cone and Semidefinite Programming Tags , , , , ,

    We consider lift-and-project methods for combinatorial optimization problems and focus mostly on those lift-and-project methods which generate polyhedral relaxations of the convex hull of integer solutions. We introduce many new variants of Sherali–Adams and Bienstock–Zuckerberg operators. These new operators fill the spectrum of polyhedral lift-and-project operators in a way which makes all of them more … Read more