Dual certificates of primal cone membership

We discuss easily verifiable cone membership certificates, that is, certificates proving relations of the form \( b\in K \) for convex cones \(K\) that consist of vectors in the dual cone \(K^*\). Vectors in the dual cone are usually associated with separating hyperplanes, and so they are interpreted as certificates of non-membership in the standard … Read more

PDCS: A Primal-Dual Large-Scale Conic Programming Solver with GPU Enhancements

In this paper, we introduce the Primal-Dual Conic Programming Solver (PDCS), a large-scale conic programming solver with GPU enhancements. Problems that PDCS currently supports include linear programs, second-order cone programs, convex quadratic programs, and exponential cone programs. PDCS achieves scalability to large-scale problems by leveraging sparse matrix-vector multiplication as its core computational operation, which is … Read more

Facial approach for constructing stationary points for mathematical programs with cone complementarity constraints

This paper studies stationary points in mathematical programs with cone complementarity constraints (CMPCC). We begin by reviewing various formulations of CMPCC and revisiting definitions for Bouligand, proximal strong, regular strong, Wachsmuth’s strong, L-strong, weak, as well as Mordukhovich and Clarke stationary points, establishing a comprehensive framework for CMPCC. Building on key principles related to cone … Read more

The uniqueness of Lyapunov rank among symmetric cones

The Lyapunov rank of a cone is the dimension of the Lie algebra of its automorphism group. It is invariant under linear isomorphism and in general not unique—two or more non-isomorphic cones can share the same Lyapunov rank. It is therefore not possible in general to identify cones using Lyapunov rank. But suppose we look … Read more

Interior-point algorithms with full Newton steps for nonsymmetric convex conic optimization

We design and analyze primal-dual, feasible interior-point algorithms (IPAs) employing full Newton steps to solve convex optimization problems in standard conic form. Unlike most nonsymmetric cone programming methods, the algorithms presented in this paper require only a logarithmically homogeneous self-concordant barrier (LHSCB) of the primal cone, but compute feasible and \(\varepsilon\)-optimal solutions to both the … Read more

Proximity results in convex mixed-integer programming

We study proximity (resp. integrality gap), that is, the distance (resp. difference) between the optimal solutions (resp. optimal values) of convex integer programs (IP) and the optimal solutions (resp. optimal values) of their continuous relaxations. We show that these values can be upper bounded in terms of the recession cone of the feasible region of … Read more

Faces of homogeneous cones and applications to homogeneous chordality

A convex cone K is said to be homogeneous if its group of automorphisms acts transitively on its relative interior. Important examples of homogeneous cones include symmetric cones and cones of positive semidefinite (PSD) matrices that follow a sparsity pattern given by a homogeneous chordal graph. Our goal in this paper is to elucidate the … Read more

Jordan and isometric cone automorphisms in Euclidean Jordan algebras

Every symmetric cone K arises as the cone of squares in a Euclidean Jordan algebra V. As V is a real inner-product space, we may denote by Isom(V) its group of isometries. The groups JAut(V) of its Jordan-algebra automorphisms and Aut(K) of the linear cone automorphisms are then related. For certain inner products, JAut(V) = … Read more

Generator Subadditive Functions for Mixed-Integer Programs

For equality-constrained linear mixed-integer programs (MIP) defined by rational data, it is known that the subadditive dual is a strong dual and that there exists an optimal solution of a particular form, termed generator subadditive function. Motivated by these results, we explore the connection between Lagrangian duality, subadditive duality and generator subadditive functions for general … Read more

Exact SDP relaxations for a class of quadratic programs with finite and infinite quadratic constraints

We investigate exact semidefinite programming (SDP) relaxations for the problem of minimizing a nonconvex quadratic objective function over a feasible region defined by both finitely and infinitely many nonconvex quadratic inequality constraints (semi-infinite QCQPs). Specifically, we present two sufficient conditions on the feasible region under which the QCQP, with any quadratic objective function over the … Read more