Dual Certificates of Primal Cone Membership

Abstract. We discuss optimization problems over convex cones in which membership is difficult to verify directly. In the standard theory of duality, vectors in the dual cone [Formula: see text] are associated with separating hyperplanes and interpreted as certificates of nonmembership in the primal cone [Formula: see text]. Complementing this perspective, we develop easily verifiable certificates of membership in [Formula: see text] given by vectors in [Formula: see text]. Assuming that [Formula: see text] admits an efficiently computable logarithmically homogeneous self-concordant barrier, every vector in the interior of [Formula: see text] is associated with a full-dimensional cone of efficiently verifiable membership certificates. Consequently, rigorous certificates can be computed using numerical methods, including interior-point algorithms. The proposed framework is particularly well suited to optimization over low-dimensional linear images of higher-dimensional cones: We argue that these problems can be solved by optimizing directly over the (low-dimensional) dual cone, circumventing the customary lifting that introduces a large number of auxiliary variables. As an application, we derive a novel closed-form formula for computing exact primal feasible solutions from suitable dual feasible solutions; as the dual solutions approach optimality, the computed primal solutions do so as well. To illustrate the generality of our approach, we show that the new certification scheme is applicable to virtually every tractable subcone of nonnegative polynomials commonly used in polynomial optimization (such as sums of squares, SONC, SAGE, and SDSOS, among others), facilitating the computation of rigorous nonnegativity certificates using numerical algorithms.