Cone Programming

A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization

  • Chuan He
  • Zhaosong Lu
    • Categories Cone Programming, Nonlinear Optimization Tags , , , , , ,

    \(\) In this paper we consider finding an approximate second-order stationary point (SOSP) of general nonconvex conic optimization that minimizes a twice differentiable function subject to nonlinear equality constraints and also a convex conic constraint. In particular, we propose a Newton-conjugate gradient (Newton-CG) based barrier-augmented Lagrangian method for finding an approximate SOSP of this problem. … Read more

    A Note on Semidefinite Representable Reformulations for Two Variants of the Trust-Region Subproblem

  • Sarah Kelly
  • Yuyuan Ouyang
  • Boshi Yang
    • Categories Cone Programming, Semi-definite Programming Tags , , ,

    Motivated by encouraging numerical results in the literature, in this note we consider two specific variants of the trust-region subproblem and provide exact semidefinite representable reformulations. The first is over the intersection of two balls; the second is over the intersection of a ball and a special second-order conic representable set. Different from the technique … 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

    Linear optimization over homogeneous matrix cones

  • Levent Tunçel
  • Lieven Vandenberghe
    • Categories Cone Programming, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    A convex cone is homogeneous if its automorphism group acts transitively on the interior of the cone, i.e., for every pair of points in the interior of the cone, there exists a cone automorphism that maps one point to the other. Cones that are homogeneous and self-dual are called symmetric. The symmetric cones include the … Read more

    Weighted Geometric Mean, Minimum Mediated Set, and Optimal Second-Order Cone Representation

  • Jie Wang
    • Categories Cone Programming, Convex Optimization, Second-Order Cone Programming Tags , , , ,

    We study optimal second-order cone representations for weighted geometric means, which turns out to be closely related to minimum mediated sets. Several lower bounds and upper bounds on the size of optimal second-order cone representations are proved. In the case of bivariate weighted geometric means (equivalently, one dimensional mediated sets), we are able to prove … Read more

    Superadditive duality and convex hulls for mixed-integer conic optimization

  • Akshay Gupte
  • Temitayo Ajayi
  • Amin Khademi
  • Andrew J. Schaefer
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Cutting Plane Approaches Tags , , ,

    We present an infinite family of linear valid inequalities for a mixed-integer conic program, and prove that these inequalities describe the convex hull of the feasible set when this set is bounded and described by integral data. The main element of our proof is to establish a new strong superadditive dual for mixed-integer conic programming … 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

    Automorphisms of rank-one generated hyperbolicity cones and their derivative relaxations

  • Masaru Ito
  • Bruno F. Lourenço
    • Categories Cone Programming, Linear, Cone and Semidefinite Programming Tags , ,

    A hyperbolicity cone is said to be rank-one generated (ROG) if all its extreme rays have rank one, where the rank is computed with respect the underlying hyperbolic polynomial. This is a natural class of hyperbolicity cones which are strictly more general than the ROG spectrahedral cones. In this work, we present a study of … Read more

    On duality theory of conic linear problems

  • Alexander Shapiro
    • Categories Cone Programming, Convex Optimization, Infinite Dimensional Optimization

    In this paper we discuss duality theory of optimization problems with a linear objective function and subject to linear constraints with cone inclusions, referred to as conic linear problems. We formulate the Lagrangian dual of a conic linear problem and survey some results based on the conjugate duality approach where the questions of “no duality … Read more