Linear, Cone and Semidefinite Programming

How to generate weakly infeasible semidefinite programs via Lasserre’s relaxations for polynomial optimization

  • Hayato Waki
    • Categories Convex Optimization, Semi-definite Programming Tags , ,

    Examples of weakly infeasible semidefinite programs are useful to test whether semidefinite solvers can detect infeasibility. However, finding non trivial such examples is notoriously difficult. This note shows how to use Lasserre’s semidefinite programming relaxations for polynomial optimization in order to generate examples of weakly infeasible semidefinite programs. Such examples could be used to test … Read more

    On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets

  • Gabriele Eichfelder
  • Janez Povh
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , ,

    In the paper we prove that any nonconvex quadratic problem over some set $K\subset \mathbb{R}^n$ with additional linear and binary constraints can be rewritten as linear problem over the cone, dual to the cone of K-semidefinite matrices. We show that when K is defined by one quadratic constraint or by one concave quadratic constraint and … Read more

    Implementing the simplex method as a cutting-plane method

  • Krisztian Eretnek
  • Csaba I. Fábián
  • Olga Papp
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We show that the simplex method can be interpreted as a cutting-plane method, assumed that a special pricing rule is used. This approach is motivated by the recent success of the cutting-plane method in the solution of special stochastic programming problems. We compare the classic Dantzig pricing rule and the rule that derives from the … Read more

    Robust solutions of optimization problems affected by uncertain probabilities

  • Aharon Ben-Tal
  • Dick den Hertog
  • Anja De Waegenaere
  • Bertrand Melenberg
  • Gijs Rennen
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , ,

    In this paper we focus on robust linear optimization problems with uncertainty regions defined by phi-divergences (for example, chi-squared, Hellinger, Kullback-Leibler). We show how uncertainty regions based on phi-divergences arise in a natural way as confidence sets if the uncertain parameters contain elements of a probability vector. Such problems frequently occur in, for example, optimization … Read more

    A lower bound on the optimal self-concordance parameter of convex cones

  • Roland Hildebrand
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    Let $K \subset \mathbb R^n$ be a regular convex cone, let $e_1,\dots,e_n \in \partial K$ be linearly independent points on the boundary of a compact affine section of the cone, and let $x^* \in K^o$ be a point in the relative interior of this section. For $k = 1,\dots,n$, let $l_k$ be the line through … Read more

    Computing the Grothendieck constant of some graph classes

  • Monique Laurent
  • Antonios Varvitsiotis
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

    Given a graph $G=([n],E)$ and $w\in\R^E$, consider the integer program ${\max}_{x\in \{\pm 1\}^n} \sum_{ij \in E} w_{ij}x_ix_j$ and its canonical semidefinite programming relaxation ${\max} \sum_{ij \in E} w_{ij}v_i^Tv_j$, where the maximum is taken over all unit vectors $v_i\in\R^n$. The integrality gap of this relaxation is known as the Grothendieck constant $\ka(G)$ of $G$. We present … Read more

    Copositive optimization – recent developments and applications

  • Immanuel M. Bomze
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming, Quadratic Programming

    Due to its versatility, copositive optimization receives increasing interest in the Operational Research community, and is a rapidly expanding and fertile field of research. It is a special case of conic optimization, which consists of minimizing a linear function over a cone subject to linear constraints. The diversity of copositive formulations in different domains of … Read more

    Think co(mpletely )positive ! Matrix properties, examples and a clustered bibliography on copositive optimization

  • Immanuel M. Bomze
  • Werner Schachinger
  • Gabriele Uchida
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Linear, Cone and Semidefinite Programming

    Copositive optimization is a quickly expanding scientific research domain with wide-spread applications ranging from global nonconvex problems in engineering to NP-hard combinatorial optimization. It falls into the category of conic programming (optimizing a linear functional over a convex cone subject to linear constraints), namely the cone of all completely positive symmetric nxn matrices, and its … Read more

    On semidefinite programming bounds for graph bandwidth

  • Etienne de Klerk
  • Marianna Eisenberg-Nagy
  • Renata Sotirov
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    We propose two new lower bounds on graph bandwidth and cyclic bandwidth based on semidefinite programming (SDP) relaxations of the quadratic assignment problem. We compare the new bounds with two other SDP bounds in [A. Blum, G. Konjevod, R. Ravi, and S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoretical Computer Science, … Read more

    Exact Approaches to Multi-Level Vertical Orderings

  • Markus Chimani
  • Philipp Hungerländer
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , ,

    We present a semide nite programming (SDP) approach for the problem of ordering vertices of a layered graph such that the edges of the graph are drawn as vertical as possible. This Multi-Level Vertical Ordering (MLVO) problem is a quadratic ordering problem and conceptually related to the well-studied problem of Multi-Level Crossing Minimization (MLCM). In contrast … Read more