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. On the theoretical side, we show that the problem of testing whether a cubic polynomial is convex over a box is NP-hard. We also study norms generated by convex forms and provide an SDP hierarchy for optimizing over them. On the application side, we study a problem of interest to robotics and motion planning, which involves modeling complex environments with simpler representations. We also study two applications in machine learning: the first is multivariate monotone regression, which is motivated by some applications in pricing; the second concerns a specific subclass of optimization problems called difference of convex (DC) programs, which appear naturally in machine learning problems.