Linear, Cone and Semidefinite Programming

Tight-and-cheap conic relaxation for the AC optimal power flow problem

  • Miguel F. Anjos
  • Christian Bingane
  • Sébastien Le Digabel
    • Categories Applications - Science and Engineering, Nonlinear Optimization, Semi-definite Programming Tags , , ,

    The classical alternating current optimal power flow problem is highly nonconvex and generally hard to solve. Convex relaxations, in particular semidefinite, second-order cone, convex quadratic, and linear relaxations, have recently attracted significant interest. The semidefinite relaxation is the strongest among them and is exact for many cases. However, the computational efficiency for solving large-scale semidefinite … Read more

    Sum of squares certificates for stability of planar, homogeneous, and switched systems

  • Amir Ali Ahmadi
  • Pablo A. Parrilo
    • Categories Control Applications, Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , ,

    We show that existence of a global polynomial Lyapunov function for a homogeneous polynomial vector field or a planar polynomial vector field (under a mild condition) implies existence of a polynomial Lyapunov function that is a sum of squares (sos) and that the negative of its derivative is also a sum of squares. This result … Read more

    Maximum-Entropy Sampling and the Boolean Quadric Polytope

  • Kurt M. Anstreicher
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming, Statistics Tags , ,

    We consider a bound for the maximum-entropy sampling problem (MESP) that is based on solving a max-det problem over a relaxation of the Boolean Quadric Polytope (BQP). This approach to MESP was first suggested by Christoph Helmberg over 15 years ago, but has apparently never been further elaborated or computationally investigated. We find that the … Read more

    A projection algorithm based on KKT conditions for convex quadratic semidefinite programming with nonnegative constraints

  • Jianchao Bai
  • Chang Xiaokai
  • Liu Sanyang
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    The dual form of convex quadratic semidefinite programming (CQSDP) problem, with nonnegative constraints, is a 4-block separable convex optimization problem. It is known that,the directly extended 4-block alternating direction method of multipliers (ADMM4d) is very efficient to solve the dual, but its convergence is not guaranteed. In this paper, we reformulate the dual as a … Read more

    Long-Step Path-Following Algorithm for Solving Symmetric Programming Problems with Nonlinear Objective Functions

  • Leonid Faybusovich
  • Cunlu Zhou
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    We describe a long-step path-following algorithm for a class of symmetric programming problems with nonlinear convex objective functions. The complexity estimates similar to the case of a linear-quadratic objective function are established. The results of numerical experiments for the class of optimization problems involving quantum entropy are presented. Citation Preprint, University of Notre Dame, December … Read more

    On the local stability of semidefinite relaxations

  • Sameer Agarwal
  • Diego Cifuentes
  • Pablo A. Parrilo
  • Rekha R. Thomas
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , ,

    In this paper we consider a parametric family of polynomial optimization problems over algebraic sets. Although these problems are typically nonconvex, tractable convex relaxations via semidefinite programming (SDP) have been proposed. Often times in applications there is a natural value of the parameters for which the relaxation will solve the problem exactly. We study conditions … Read more

    Network-based Approximate Linear Programming for Discrete Optimization

  • Andre Augusto Cire
  • Selvaprabu Nadarajah
    • Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming, Linear Programming Tags , ,

    We develop a new class of approximate linear programs (ALPs) that project the high-dimensional value function of dynamic programs onto a class of basis functions, each defined as a network that represents aggregrations over the state space. The resulting ALP is a minimum-cost flow problem over an extended variable space that synchronizes flows across multiple … Read more

    Amenable cones: error bounds without constraint qualifications

  • Bruno F. Lourenço
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We provide a framework for obtaining error bounds for linear conic problems without assuming constraint qualifications or regularity conditions. The key aspects of our approach are the notions of amenable cones and facial residual functions. For amenable cones, it is shown that error bounds can be expressed as a composition of facial residual functions. The … Read more

    On the Convergence Rate of the Halpern-Iteration

  • Felix Lieder
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    In this work, we give a tight estimate of the rate of convergence for the Halpern-Iteration for approximating a fixed point of a nonexpansive mapping in a Hilbert space. Specifically, we prove that the norm of the residuals is upper bounded by the distance of the initial iterate to the closest fixed point divided by … Read more

    Set-Completely-Positive Representations and Cuts for the Max-Cut Polytope and the Unit Modulus Lifting

  • Florian Jarre
  • Ya-Feng Liu
  • Felix Lieder
  • Cheng Lu
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    This paper considers a generalization of the “max-cut-polytope” $\conv\{\ xx^T\mid x\in\real^n, \ \ |x_k| = 1 \ \hbox{for} \ 1\le k\le n\}$ in the space of real symmetric $n\times n$-matrices with all-ones-diagonal to a complex “unit modulus lifting” $\conv\{xx\HH\mid x\in\complex^n, \ \ |x_k| = 1 \ \hbox{for} \ 1\le k\le n\}$ in the space of … Read more