  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.)
