CaltechTHESIS
  A Caltech Library Service

Applications of Convex Analysis to Signomial and Polynomial Nonnegativity Problems

Citation

Murray, Riley John (2021) Applications of Convex Analysis to Signomial and Polynomial Nonnegativity Problems. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/vn9x-xj10. https://resolver.caltech.edu/CaltechTHESIS:05202021-194439071

Abstract

Here is a question that is easy to state, but often hard to answer:

Is this function nonnegative on this set?

When faced with such a question, one often makes appeals to known inequalities. One crafts arguments that are sufficient to establish the nonnegativity of the function, rather than determining the function's precise range of values. This thesis studies sufficient conditions for nonnegativity of signomials and polynomials. Conceptually, signomials may be viewed as generalized polynomials that feature arbitrary real exponents, but with variables restricted to the positive orthant.

Our methods leverage efficient algorithms for a type of convex optimization known as relative entropy programming (REP). By virtue of this integration with REP, our methods can help answer questions like the following:

Is there some function, in this particular space of functions, that is nonnegative on this set?

The ability to answer such questions is extremely useful in applied mathematics. Alternative approaches in this same vein (e.g., methods for polynomials based on semidefinite programming) have been used successfully as convex relaxation frameworks for nonconvex optimization, as mechanisms for analyzing dynamical systems, and even as tools for solving nonlinear partial differential equations.

This thesis builds from the sums of arithmetic-geometric exponentials or SAGE approach to signomial nonnegativity. The term "exponential" appears in the SAGE acronym because SAGE parameterizes signomials in terms of exponential functions.

Our first round of contributions concern the original SAGE approach. We employ basic techniques in convex analysis and convex geometry to derive structural results for spaces of SAGE signomials and exactness results for SAGE-based REP relaxations of nonconvex signomial optimization problems. We frame our analysis primarily in terms of the coefficients of a signomial's basis expansion rather than in terms of signomials themselves. The effect of this framing is that our results for signomials readily transfer to polynomials. In particular, we are led to define a new concept of SAGE polynomials. For sparse polynomials, this method offers an exponential efficiency improvement relative to certificates of nonnegativity obtained through semidefinite programming.

We go on to create the conditional SAGE methodology for exploiting convex substructure in constrained signomial nonnegativity problems. The basic insight here is that since the standard relative entropy representation of SAGE signomials is obtained by a suitable application of convex duality, we are free to add additional convex constraints into the duality argument. In the course of explaining this idea we provide some illustrative examples in signomial optimization and analysis of chemical dynamics.

The majority of this thesis is dedicated to exploring fundamental questions surrounding conditional SAGE signomials. We approach these questions through analysis frameworks of sublinear circuits and signomial rings. These sublinear circuits generalize simplicial circuits of affine-linear matroids, and lead to rich modes of analysis for sets that are simultaneously convex in the usual sense and convex under a logarithmic transformation. The concept of signomial rings lets us develop a powerful signomial Positivstellensatz and an elementary signomial moment theory. The Positivstellensatz provides for an effective hierarchy of REP relaxations for approaching the value of a nonconvex signomial minimization problem from below, as well as a first-of-its-kind hierarchy for approaching the same value from above.

In parallel with our mathematical work, we have developed the sageopt python package. Sageopt drives all the examples and experiments used throughout this thesis, and has been used by engineers to solve high-degree polynomial optimization problems at scales unattainable by alternative methods. We conclude this thesis with an explanation of how our theoretical results affected sageopt's design.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:signomials; exponential sums; generalized polynomials; sparse polynomials; fewnomials; sums of arithmetic-geometric exponentials (SAGE); positive signomials; positive polynomials; sums of nonnegative circuit polynomials (SONC); sums of squares (SOS); arithmetic-geometric-mean inequality; global optimization; Positivstellensatz; convex relaxations; lower bounds; relative entropy programming; exponential cone programming; convex programming; semidefinite programming; multiplicative convexity; sublinear circuits; signomial rings; moment problems; Lasserre's second hierarchy; upper bounds
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computing and Mathematical Sciences
Awards:Amori Doctoral Prize in Computing and Mathematical Sciences
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Chandrasekaran, Venkat (co-advisor)
  • Wierman, Adam C. (co-advisor)
Thesis Committee:
  • Tropp, Joel A. (chair)
  • Low, Steven H.
  • Chandrasekaran, Venkat
  • Wierman, Adam C.
Defense Date:13 May 2021
Funders:
Funding AgencyGrant Number
NSF Graduate Research FellowshipUNSPECIFIED
NSFCCF-1350590
NSFCCF-1637598
Air Force Office of Scientific Research (AFOSR)A9550-16-1-0210
Record Number:CaltechTHESIS:05202021-194439071
Persistent URL:https://resolver.caltech.edu/CaltechTHESIS:05202021-194439071
DOI:10.7907/vn9x-xj10
Related URLs:
URLURL TypeDescription
https://doi.org/10.1007/s10208-021-09497-wDOIArticle adapted for ch. 3
https://doi.org/10.1007/s12532-020-00193-4DOIArticle adapted for ch. 4, 7, 8
https://arxiv.org/abs/2006.06811arXivArticle adapted for ch. 5
ORCID:
AuthorORCID
Murray, Riley John0000-0003-1461-6458
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:14169
Collection:CaltechTHESIS
Deposited By: Riley Murray
Deposited On:02 Jun 2021 23:58
Last Modified:09 Jun 2021 16:16

Thesis Files

[img] PDF - Final Version
See Usage Policy.

1MB

Repository Staff Only: item control page