semidefinite programming

Exactness of Parrilo’s conic approximations for copositive matrices and associated low order bounds for the stability number of a graph

  • Monique Laurent
  • Luis Felipe Vargas
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , , , ,

    De Klerk and Pasechnik (2002) introduced the bounds $\vartheta^{(r)}(G)$ ($r\in \mathbb{N}$) for the stability number $\alpha(G)$ of a graph $G$ and conjectured exactness at order $\alpha(G)-1$: $\vartheta^{(\alpha(G)-1)}(G)=\alpha(G)$. These bounds rely on the conic approximations $\mathcal{K}_n^{(r)}$ by Parrilo (2000) for the copositive cone $\text{COP}_n$. A difficulty in the convergence analysis of $\vartheta^{(r)}$ is the bad behaviour … Read more

    Pareto Robust Optimization on Euclidean Vector Spaces

  • Dennis Adelhütte
  • Christian Biefel
  • Martina Kuchlbauer
  • Jan Hendrik Rolfes
    • Categories Robust Optimization Tags , ,

    Pareto efficiency for robust linear programs was introduced by Iancu and Trichakis. We generalize their approach and theoretical results to robust optimization problems in Euclidean spaces with affine uncertainty. Additionally, we demonstrate the value of this approach in an exemplary manner in the area of robust semidefinite programming (SDP). In particular, we prove that computing … Read more

    SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs

  • Carlos Nohra
  • Arvind U. Raghunathan
  • Nikolaos Sahinidis
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , , ,

    We consider the global optimization of nonconvex mixed-integer quadratic programs with linear equality constraints. In particular, we present a new class of convex quadratic relaxations which are derived via quadratic cuts. To construct these quadratic cuts, we solve a separation problem involving a linear matrix inequality with a special structure that allows the use of … Read more

    Dealing with inequality constraints in large scale semidefinite relaxations for graph coloring and maximum clique problems

  • Federico Battista
  • Marianna De Santis
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , ,

    Semidefinite programs (SDPs) can be solved in polynomial time by interior point methods. However, when the dimension of the problem gets large, interior point methods become impractical both in terms of computational time and memory requirements. First order methods, such as Alternating Direction Methods of Multipliers (ADMMs), turned out to be suitable algorithms to deal … Read more

    Sequential constant rank constraint qualifications for nonlinear semidefinite programming with applications

  • Roberto Andreani
  • Gabriel Haeser
  • Héctor Ramírez
  • Leonardo M. Mito
    • Categories Constrained Nonlinear Optimization, Second-Order Cone Programming, Semi-definite Programming Tags , , ,

    We present new constraint qualification conditions for nonlinear semidefinite programming that extend some of the constant rank-type conditions from nonlinear programming. As an application of these conditions, we provide a unified global convergence proof of a class of algorithms to stationary points without assuming neither uniqueness of the Lagrange multiplier nor boundedness of the Lagrange … Read more

    Convex Hull Results on Quadratic Programs with Non-Intersecting Constraints

  • Alexander Joyce
  • Boshi Yang
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    Let F be a set defined by quadratic constraints. Understanding the structure of the closed convex hull cl(C(F)) := cl(conv{xx’ | x in F}) is crucial to solve quadratically constrained quadratic programs related to F. A set G with complicated structure can be constructed by intersecting simple sets. This paper discusses the relationship between cl(C(F)) … Read more

    Sums of Separable and Quadratic Polynomials

  • Amir Ali Ahmadi
  • Cemil Dibek
  • Georgina Hall
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization, Statistics Tags , ,

    We study separable plus quadratic (SPQ) polynomials, i.e., polynomials that are the sum of univariate polynomials in different variables and a quadratic polynomial. Motivated by the fact that nonnegative separable and nonnegative quadratic polynomials are sums of squares, we study whether nonnegative SPQ polynomials are (i) the sum of a nonnegative separable and a nonnegative … Read more

    A Strengthened Barvinok-Pataki Bound on SDP Rank

  • Haesol Im
  • Henry Wolkowicz
    • Categories Semi-definite Programming Tags , , , ,

    The Barvinok-Pataki bound provides an upper bound on the rank of extreme points of a spectrahedron. This bound depends solely on the number of affine constraints of the problem, i.e., on the algebra of the problem. Specifically, the triangular number of the rank r is upper bounded by the number of affine constraints. We revisit … Read more

    Robust Interior Point Method for Quantum Key Distribution Rate Computation

  • Hao Hu
  • Haesol Im
  • Jie Lin
  • Norbert Lutkenhaus
  • Henry Wolkowicz
    • Categories Applications - OR and Management Sciences, Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , , ,

    While the security proof method for quantum key distribution, QKD, based on the numerical key rate calculation problem, is powerful in principle, the practicality of the method is limited by computational resources and the efficiency of the underlying algorithm for convex optimization. We derive a stable reformulation of the convex nonlinear semidefinite programming, SDP, model … Read more

    Finite convergence of sum-of-squares hierarchies for the stability number of a graph

  • Monique Laurent
  • Luis Felipe Vargas
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , , , ,

    We investigate a hierarchy of semidefinite bounds $\vartheta^{(r)}(G)$ for the stability number $\alpha(G)$ of a graph $G$, based on its copositive programming formulation and introduced by de Klerk and Pasechnik [SIAM J. Optim. 12 (2002), pp.875–892], who conjectured convergence to $\alpha(G)$ in $r=\alpha(G) -1$ steps. Even the weaker conjecture claiming finite convergence is still open. … Read more