Skip navigation
Please use this identifier to cite or link to this item:
Title: Optimization over Nonnegative and Convex Polynomials with and without Semidefinite Programming
Authors: Hall, Georgina
Advisors: Ahmadi, Amir Ali
Contributors: Operations Research and Financial Engineering Department
Keywords: Convex polynomials
Nonnegative polynomials
Semidefinite programming
Sum of squares optimization
Subjects: Operations research
Issue Date: 2018
Publisher: Princeton, NJ : Princeton University
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. 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.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Operations Research and Financial Engineering

Files in This Item:
File Description SizeFormat 
Hall_princeton_0181D_12645.pdf5.72 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.