Optimization over Nonnegative and Convex Polynomials With and Without Semidefinite Programming

Abstract

The problem of optimizing over the cone of nonnegative polynomials is a fundamental problem in computational mathematics, with applications to polynomial optimization, control, machine learning, game theory, and combinatorics, among others. A number of breakthrough papers in the early 2000s showed that this problem, long thought to be out of reach, could be tackled by using sum of squares programming. This technique however has proved to be expensive for large-scale problems, as it involves solving large semidefinite programs (SDPs). In the first part of this thesis, we present two methods for approximately solving large-scale sum of squares programs that dispense altogether with semidefinite programming and only involve solving a sequence of linear or second order cone programs generated in an adaptive fashion. We then focus on the problem of finding tight lower bounds on polynomial optimization problems (POPs), a fundamental task in this area that is most commonly handled through the use of SDP-based sum of squares hierarchies (e.g., due to Lasserre and Parrilo). In contrast to previous approaches, we provide the first theoretical framework for constructing converging hierarchies of lower bounds on POPs whose computation simply requires the ability to multiply certain fixed polynomials together and to check nonnegativity of the coefficients of their product. In the second part of this thesis, we focus on the theory and applications of the problem of optimizing over convex polynomials, a subcase of the problem of optimizing over nonnegative polynomials. (See manuscript for the rest of the abstract.)

PhD Thesis (Department of Operations Research and Financial Engineering, Princeton University)

References in corpus (12)

• Symmetry groups, semidefinite programs, and sums of squares
• Approximation of the joint spectral radius using sum of squares
• On the Convergence of Bound Optimization Algorithms
• Fast ADMM for Semidefinite Programs with Chordal Sparsity
• Sorting out typicality with the inverse moment matrix SOS polynomial
• Exploiting chordal structure in polynomial ideals: a Gröbner bases approach
• Algebraic Relaxations and Hardness Results in Polynomial Optimization and Lyapunov Analysis
• QSDPNAL: A two-phase augmented Lagrangian method for convex quadratic semidefinite programming
• An elementary recursive bound for effective Positivstellensatz and Hilbert 17-th problem
• A note on QUBO instances defined on Chimera graphs
• Approximation of smooth functions using Bernstein polynomials in multiple variables
• SOS-Convex Lyapunov Functions and Stability of Difference Inclusions

Cited by in corpus (8)

• Shape-constrained Symbolic Regression -- Improving Extrapolation with Prior Knowledge
• Decomposed Structured Subsets for Semidefinite and Sum-of-Squares Optimization
• A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
• Handling Hard Affine SDP Shape Constraints in RKHSs
• Using Shape Constraints for Improving Symbolic Regression Models
• Engineering and Business Applications of Sum of Squares Polynomials
• Hard Shape-Constrained Kernel Machines
• A Fine-Grained Variant of the Hierarchy of Lasserre