Linear, Cone and Semidefinite Programming

Enclosing Ellipsoids and Elliptic Cylinders of Semialgebraic Sets and Their Application to Error Bounds in Polynomial Optimization

  • Masakazu Kojima
  • Makoto Yamashita
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    This paper is concerned with a class of ellipsoidal sets (ellipsoids and elliptic cylinders) in the m-dimensional Euclidean space which are determined by a freely chosen positive semidefinite matrix. All ellipsoidal sets in this class are similar to each other through a parallel transformation and a scaling around their centers by a constant factor. Based … Read more

    A sufficiently exact inexact Newton step based on reusing matrix information

  • Anders Forsgren
    • Categories Constrained Nonlinear Optimization, Linear Programming, Nonlinear Systems and Least-Squares Tags , ,

    Newton’s method is a classical method for solving a nonlinear equation $F(z)=0$. We derive inexact Newton steps that lead to an inexact Newton method, applicable near a solution. The method is based on solving for a particular $F'(z_{k’})$ during $p$ consecutive iterations $k=k’,k’+1,\dots,k’+p-1$. One such $p$-cycle requires $2^p-1$ solves with the matrix $F'(z_{k’})$. If matrix … Read more

    Copositive Programming – a Survey

  • Mirjam Duer
    • Categories Linear, Cone and Semidefinite Programming Tags

    Copositive programming is a relatively young field in mathematical optimization. It can be seen as a generalization of semidefinite programming, since it means optimizing over the cone of so called copositive matrices. Like semidefinite programming, it has proved particularly useful in combinatorial and quadratic optimization. The purpose of this survey is to introduce the field … Read more

    On convex envelopes and underestimators for bivariate functions

  • Marco Locatelli
  • Fabio Schoen
    • Categories Global Optimization, Semi-definite Programming Tags , , ,

    In this paper we discuss convex underestimators for bivariate functions. We first present a method for deriving convex envelopes over the simplest two-dimensional polytopes, i.e., triangles. Next, we propose a technique to compute the value at some point of the convex envelope over a general two-dimensional polytope, together with a supporting hyperplane of the convex … Read more

    Local superlinear convergence of polynomial-time interior-point methods for hyperbolic cone optimization problems

  • Yurii Nesterov
  • Levent Tunçel
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    In this paper, we establish the local superlinear convergence property of some polynomial-time interior-point methods for an important family of conic optimization problems. The main structural property used in our analysis is the logarithmic homogeneity of self-concordant barrier function, which must have {\em negative curvature}. We propose a new path-following predictor-corrector scheme, which work only … Read more

    A Facial Reduction Algorithm for Finding Sparse SOS Representations

  • Masakazu Muramatsu
  • Hayato Waki
    • Categories Convex Optimization, Global Optimization Theory, Semi-definite Programming Tags , , ,

    Facial reduction algorithm reduces the size of the positive semidefinite cone in SDP. The elimination method for a sparse SOS polynomial ([3]) removes unnecessary monomials for an SOS representation. In this paper, we establish a relationship between a facial reduction algorithm and the elimination method for a sparse SOS polynomial. Citation Technical Report CS-09-02, Department … Read more

    Second-Order Cone Relaxations for Binary Quadratic Polynomial Programs

  • Miguel F. Anjos
  • Bissan Ghaddar
  • Juan C. Vera
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    Several types of relaxations for binary quadratic polynomial programs can be obtained using linear, second-order cone, or semidefinite techniques. In this paper, we propose a general framework to construct conic relaxations for binary quadratic polynomial programs based on polynomial programming. Using our framework, we re-derive previous relaxation schemes and provide new ones. In particular, we … Read more

    The positive semidefinite Grothendieck problem with rank constraint

  • Jop Briet
  • Fernando Mário de Oliveira Filho
  • Frank Vallentin
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    Given a positive integer n and a positive semidefinite matrix A = (A_{ij}) of size m x m, the positive semidefinite Grothendieck problem with rank-n-constraint is (SDP_n) maximize \sum_{i=1}^m \sum_{j=1}^m A_{ij} x_i \cdot x_j, where x_1, …, x_m \in S^{n-1}. In this paper we design a polynomial time approximation algorithm for SDP_n achieving an approximation … Read more

    On the nonexistence of sum of squares certificates for the BMV conjecture

  • Kristijan Cafuta
  • Igor Klep
  • Janez Povh
    • Categories Basic Sciences Applications, Semi-definite Programming Tags , , , , ,

    The algebraic reformulation of the BMV conjecture is equivalent to a family of dimensionfree tracial inequalities involving positive semidefinite matrices. Sufficient conditions for these to hold in the form of algebraic identities involving polynomials in noncommuting variables have been given by Markus Schweighofer and the second author. Later the existence of these certificates has been … Read more

    Quadratic factorization heuristics for copositive programming

  • Immanuel M. Bomze
  • Florian Jarre
  • Franz Rendl
    • Categories (Mixed) Integer Linear Programming, Global Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    Copositive optimization problems are particular conic programs: extremize linear forms over the copositive cone subject to linear constraints. Every quadratic program with linear constraints can be formulated as a copositive program, even if some of the variables are binary. So this is an NP-hard problem class. While most methods try to approximate the copositive cone … Read more