copositive programming

Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone

  • Monique Laurent
  • Teresa Piovesan
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , ,

    We investigate the completely positive semidefinite cone $\mathcal{CS}_+^n$, a new matrix cone consisting of all $n\times n$ matrices that admit a Gram representation by positive semidefinite matrices (of any size). In particular we study relationships between this cone and the completely positive and doubly nonnegative cones, and between its dual cone and trace positive non-commutative … Read more

    New lower bounds and asymptotics for the cp-rank

  • Immanuel M. Bomze
  • Werner Schachinger
  • Reinhard Ullrich
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    Let $p_n$ denote the largest possible cp-rank of an $n\times n$ completely positive matrix. This matrix parameter has its significance both in theory and applications, as it sheds light on the geometry and structure of the solution set of hard optimization problems in their completely positive formulation. Known bounds for $p_n$ are $s_n=\binom{n+1}2-4$, the current … Read more

    Copositivity-based approximations for mixed-integer fractional quadratic optimization

  • Paula Alexandra Amaral
  • Immanuel M. Bomze
    • Categories Constrained Nonlinear Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    We propose a copositive reformulation of the mixed-integer fractional quadratic problem (MIFQP) under general linear constraints. This problem class arises naturally in many applications, e.g., for optimizing communication or social networks, or studying game theory problems arising from genetics. It includes several APX-hard subclasses: the maximum cut problem, the $k$-densest subgraph problem and several of … Read more

    An LP-based Algorithm to Test Copositivity

  • Akihiro Tanaka
  • Akiko Yoshise
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    A symmetric matrix is called copositive if it generates a quadratic form taking no negative values over the nonnegative orthant, and the linear optimization problem over the set of copositive matrices is called the copositive programming problem. Recently, many studies have been done on the copositive programming problem (see, for example, \cite{aDUR10, aBOMZE12}). Among others, … Read more

    From seven to eleven: completely positive matrices with high cp-rank

  • Immanuel M. Bomze
  • Werner Schachinger
  • Reinhard Ullrich
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    We study $n\times n$ completely positive matrices $M$ on the boundary of the completely positive cone, namely those orthogonal to a copositive matrix $S$ which generates a quadratic form with finitely many zeroes in the standard simplex. Constructing particular instances of $S$, we are able to construct counterexamples to the famous Drew-Johnson-Loewy conjecture (1994) for … Read more

    EXPLOITING SYMMETRY IN COPOSITIVE PROGRAMS VIA SEMIDEFINITE HIERARCHIES

  • Cristian Dobre
  • Juan C. Vera
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    Copositive programming is a relative young field which has evolved into a highly active research area in mathematical optimization. An important line of research is to use semidefinite programming to approximate conic programming over the copositive cone. Two major drawbacks of this approach are the rapid growth in size of the resulting semidefinite programs, and … Read more

    Completely Positive Reformulations for Polynomial Optimization

  • Javier F. Peña
  • Juan C. Vera
  • Luis F. Zuluaga
    • Categories Convex Optimization, Global Optimization Theory Tags , , ,

    Polynomial optimization encompasses a very rich class of problems in which both the objective and constraints can be written in terms of polynomials on the decision variables. There is a well stablished body of research on quadratic polynomial optimization problems based on reformulations of the original problem as a conic program over the cone of … Read more

    Analysis of Copositive Optimization Based Linear Programming Bounds on Standard Quadratic Optimization

  • Gizem Sagol
  • E. Alper Yildirim
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , ,

    The problem of minimizing a quadratic form over the unit simplex, referred to as a standard quadratic optimization problem, admits an exact reformulation as a linear optimization problem over the convex cone of completely positive matrices. This computationally intractable cone can be approximated from the inside and from the outside by two sequences of nested … Read more

    Extension of Completely Positive Cone Relaxation to Polynomial Optimization

  • Naohiko Arima
  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    We propose the moment cone relaxation for a class of polynomial optimization problems (POPs) to extend the results on the completely positive cone programming relaxation for the quadratic optimization (QOP) model by Arima, Kim and Kojima. The moment cone relaxation is constructed to take advantage of sparsity of the POPs, so that efficient numerical methods … Read more

    Erratum to: On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets” [Optim. Letters, 2012]

  • Peter J.C. Dickinson
  • Gabriele Eichfelder
  • Janez Povh
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    In this paper, an erratum is provided to the article “\emph{On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets}”, published in Optim.\ Letters, 2012. Due to precise observation of the first author, it has been found that the proof of Lemma 9 has a nontrivial gap, and consequently the main result (Theorem … Read more