copositive programming

Solving Nonconvex Optimization Problems using Outer Approximations of the Set-Copositive Cone

  • Kurt M. Anstreicher
  • MarkusGabl
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Global Optimization Theory Tags , ,

    We consider the solution of nonconvex quadratic optimization problems using an outer approximation of the set-copositive cone that is iteratively strengthened with conic constraints and cutting planes. Our methodology utilizes an MILP-based oracle for a generalization of the copositive cone that considers additional linear equality constraints. In numerical testing we evaluate our algorithm on a … Read more

    Approximation hierarchies for copositive cone over symmetric cone and their comparison

  • Mitsuhiro Nishijima
  • Kazuhide Nakata
    • Categories Cone Programming, Convex Optimization, Global Optimization Theory Tags , , , ,

    We first provide an inner-approximation hierarchy described by a sum-of-squares (SOS) constraint for the copositive (COP) cone over a general symmetric cone. The hierarchy is a generalization of that proposed by Parrilo (2000) for the usual COP cone (over a nonnegative orthant). We also discuss its dual. Second, we characterize the COP cone over a … Read more

    A copositive framework for analysis of hybrid Ising-classical algorithms

  • David E. Bernal Neira
  • Robin Brown
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Cutting Plane Approaches Tags , , , , ,

    Recent years have seen significant advances in quantum/quantum-inspired technologies capable of approximately searching for the ground state of Ising spin Hamiltonians. The promise of leveraging such technologies to accelerate the solution of difficult optimization problems has spurred an increased interest in exploring methods to integrate Ising problems as part of their solution process, with existing … 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

    Copositive Duality for Discrete Energy Markets

  • Cheng Guo
  • Merve Bodur
  • Joshua Taylor
    • Categories Applications - OR and Management Sciences Tags , , , ,

    Optimization problems with discrete decisions are nonconvex and thus lack strong duality, which limits the usefulness of tools such as shadow prices. It was shown in Burer (2009) that mixed-binary quadratic programs can be written as completely positive programs, which are convex. Completely positive reformulations of discrete optimization problems therefore have strong duality if a … Read more

    A Modified Simplex Partition Algorithm to Test Copositivity

  • Mohammadreza Safi
  • Seyed Saeed Nabavi
  • Richard J. Caron
    • Categories Global Optimization Theory Tags , , , ,

    A real symmetric matrix $A$ is copositive if $x^\top Ax\geq 0$ for all $x\geq 0$. As $A$ is copositive if and only if it is copositive on the standard simplex, algorithms to determine copositivity, such as those in Sponsel et al. (J Glob Optim 52:537–551, 2012) and Tanaka and Yoshise (Pac J Optim 11:101–120, 2015) … Read more

    Testing Copositivity via Mixed-Integer Linear Programming

  • Kurt M. Anstreicher
    • Categories (Mixed) Integer Linear Programming, Global Optimization Theory Tags , ,

    We describe a simple method to test if a given matrix is copositive by solving a single mixed-integer linear programming (MILP) problem. This methodology requires no special coding to implement and takes advantage of the computational power of modern MILP solvers. Numerical experiments demonstrate that the method is robust and efficient. Citation Dept. of Business … Read more

    On Standard Quadratic Programs with Exact and Inexact Doubly Nonnegative Relaxations

  • Y. Gorkem Gokmen
  • E. Alper Yildirim
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , ,

    The problem of minimizing a (nonconvex) quadratic form over the unit simplex, referred to as a standard quadratic program, admits an exact convex conic formulation over the computationally intractable cone of completely positive matrices. Replacing the intractable cone in this formulation by the larger but tractable cone of doubly nonnegative matrices, i.e., the cone of … Read more

    Gaddum’s test for symmetric cones

  • Michael Orlitzky
    • Categories Complementarity and Variational Inequalities, Game Theory, Linear, Cone and Semidefinite Programming Tags , , , ,

    A real symmetric matrix “A” is copositive if the inner product if Ax and x is nonnegative for all x in the nonnegative orthant. Copositive programming has attracted a lot of attention since Burer showed that hard nonconvex problems can be formulated as completely-positive programs. Alas, the power of copositive programming is offset by its … Read more

    Generating irreducible copositive matrices using the stable set problem

  • Reinier de Zeeuw
  • Peter J.C. Dickinson
    • Categories Convex Optimization, Graphs and Matroids, Linear, Cone and Semidefinite Programming Tags , , , ,

    In this paper it is considered how graphs can be used to generate copositive matrices, and necessary and sufficient conditions are given for these generated matrices to then be irreducible with respect to the set of positive semidefinite plus nonnegative matrices. This is done through combining the well known copositive formulation of the stable set … Read more