Hesse's Redemption: Efficient Convex Polynomial Programming

Efficient algorithms for convex optimization, such as the ellipsoid method, require an a priori bound on the radius of a ball around the origin guaranteed to contain an optimal solution if one exists. For linear and convex quadratic programming, such solution bounds follow from classical characterizations of optimal solutions by systems of linear equations. For other programs, e.g., semidefinite ones, examples due to Khachiyan show that optimal solutions may require huge coefficients with an exponential number of bits, even if we allow approximations. Correspondingly, semidefinite programming is not even known to be in NP. The unconstrained minimization of convex polynomials of degree four and higher has remained a fundamental open problem between these two extremes: its optimal solutions do not admit a linear characterization and, at the same time, Khachiyan-type examples do not apply. We resolve this problem by developing new techniques to prove solution bounds when no linear characterizations are available. Even for programs minimizing a convex polynomial (of arbitrary degree) over a polyhedron, we prove that the existence of an optimal solution implies that an approximately optimal one with polynomial bit length also exists. These solution bounds, combined with the ellipsoid method, yield the first polynomial-time algorithm for (approximate) convex polynomial programming, settling a question posed by Nesterov (Math. Program., 2019). Before, no polynomial-time algorithm was known even for unconstrained minimization of a convex polynomial of degree four. Our results rely on a structural decomposition of any convex polynomial into a sum of a linear function and a polynomial on a linear subspace that admits a strongly convex lower bound, where the logarithm of the strong convexity parameter is polynomially bounded in the input size. A key component of our proof is a strong local-to-global property for convex polynomials: if at every point some directional second derivative vanishes, then a single directional second derivative must vanish everywhere. While Hesse erroneously claimed that this property holds for general polynomials (J. Reine Angew. Math., 1851), we show that it holds for convex ones.