semidefinite programming

Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization

  • Etienne de Klerk
  • Monique Laurent
  • Roxana Hess
    • Categories Semi-definite Programming Tags , , , , ,

    We consider the problem of minimizing a given $n$-variate polynomial $f$ over the hypercube $[-1,1]^n$. An idea introduced by Lasserre, is to find a probability distribution on $[-1,1]^n$ with polynomial density function $h$ (of given degree $r$) that minimizes the expectation $\int_{[-1,1]^n} f(x)h(x)d\mu(x)$, where $d\mu(x)$ is a fixed, finite Borel measure supported on $[-1,1]^n$. It … Read more

    A coordinate ascent method for solving semidefinite relaxations of non-convex quadratic integer programs

  • Christoph Buchheim
  • Maribel Montenegro
  • Angelika Wiegele
    • Categories Integer Programming, Semi-definite Programming Tags , ,

    We present a coordinate ascent method for a class of semidefinite programming problems that arise in non-convex quadratic integer optimization. These semidefinite programs are characterized by a small total number of active constraints and by low-rank constraint matrices. We exploit this special structure by solving the dual problem, using a barrier method in combination with … Read more

    Exact Solution Methods for the hBcitem Quadratic Knapsack Problem

  • Lucas Létocart
  • Angelika Wiegele
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

    The purpose of this paper is to solve the 0-1 k-item quadratic knapsack problem (kQKP), a problem of maximizing a quadratic function subject to two linear constraints.We propose an exact method based on semide nite optimization. The semide nite relaxation used in our approach includes simple rank one constraints, which can be handled efficiently by interior point … Read more

    Solving rank-constrained semidefinite programs in exact arithmetic

  • Simone Naldi
    • Categories Semi-definite Programming Tags , , , , , , , ,

    We consider the problem of minimizing a linear function over an affine section of the cone of positive semidefinite matrices, with the additional constraint that the feasible matrix has prescribed rank. When the rank constraint is active, this is a non-convex optimization problem, otherwise it is a semidefinite program. Both find numerous applications especially in … Read more

    The min-cut and vertex separator problem

  • Franz Rendl
  • Renata Sotirov
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    We consider graph three-partitions with the objective of minimizing the number of edges between the first two partition sets while keeping the size of the third block small. We review most of the existing relaxations for this min-cut problem and focus on a new class of semidefinite relaxations, based on matrices of order $2n$ which … Read more

    Quadratic Programs with Hollows

  • Kurt M. Anstreicher
  • Samuel Burer
  • Boshi Yang
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    Let $\F$ be a quadratically constrained, possibly nonconvex, bounded set, and let $\E_1, \ldots, \E_l$ denote ellipsoids contained in $\F$ with non-intersecting interiors. We prove that minimizing an arbitrary quadratic $q(\cdot)$ over $\G := \F \setminus \cup_{k=1}^\ell \myint(\E_k)$ is no more difficult than minimizing $q(\cdot)$ over $\F$ in the following sense: if a given semidefinite-programming … Read more

    Semi-infinite programming using high-degree polynomial interpolants and semidefinite programming

  • Dávid Papp
    • Categories Semi-definite Programming, Semi-infinite Programming, Statistics Tags , , , ,

    In a common formulation of semi-infinite programs, the infinite constraint set is a requirement that a function parametrized by the decision variables is nonnegative over an interval. If this function is sufficiently closely approximable by a polynomial or a rational function, then the semi-infinite program can be reformulated as an equivalent semidefinite program. Solving this … Read more

    Strengthening the SDP Relaxation of AC Power Flows with Convex Envelopes, Bound Tightening, and Lifted Nonlinear Cuts

  • Carleton Coffrin
  • Hassan L. Hijazi
  • Pascal Van Hentenryck
    • Categories Applications - OR and Management Sciences, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , ,

    This paper considers state-of-the-art convex relaxations for the AC power flow equations and introduces new valid cuts based on convex envelopes and lifted nonlinear constraints. These valid linear inequalities strengthen existing semidefinite and quadratic programming relaxations and dominate existing cuts proposed in the litterature. Together with model intersections and bound tightening, the new linear cuts … Read more

    On the Lovasz Theta Function and Some Variants

  • Laura Galli
  • Adam N. Letchford
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , ,

    The Lovasz theta function of a graph is a well-known upper bound on the stability number. It can be computed efficiently by solving a semidefinite program (SDP). Actually, one can solve either of two SDPs, one due to Lovasz and the other to Groetschel et al. The former SDP is often thought to be preferable … Read more

    New Formulation and Strong MISOCP Relaxations for AC Optimal Transmission Switching Problem

  • Santanu S. Dey
  • Burak Kocuk
  • Xu Andy Sun
    • Categories Applications - Science and Engineering, Global Optimization, Integer Programming Tags , , , , ,

    As the modern transmission control and relay technologies evolve, transmission line switching has become an important option in power system operators’ toolkits to reduce operational cost and improve system reliability. Most recent research has relied on the DC approximation of the power flow model in the optimal transmission switching problem. However, it is known that … Read more