CaltechAUTHORS
  A Caltech Library Service

Relative Entropy Relaxations for Signomial Optimization

Chandrasekaran, Venkat and Shah, Parikshit (2016) Relative Entropy Relaxations for Signomial Optimization. SIAM Journal on Optimization, 26 (2). pp. 1147-1173. ISSN 1052-6234. http://resolver.caltech.edu/CaltechAUTHORS:20161017-134459797

[img] PDF - Published Version
See Usage Policy.

351Kb
[img] PDF - Submitted Version
See Usage Policy.

347Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20161017-134459797

Abstract

Signomial programs (SPs) are optimization problems specified in terms of signomials, which are weighted sums of exponentials composed with linear functionals of a decision variable. SPs are nonconvex optimization problems in general, and families of NP-hard problems can be reduced to SPs. In this paper we describe a hierarchy of convex relaxations to obtain successively tighter lower bounds of the optimal value of SPs. This sequence of lower bounds is computed by solving increasingly larger-sized relative entropy optimization problems, which are convex programs specified in terms of linear and relative entropy functions. Our approach relies crucially on the observation that the relative entropy function, by virtue of its joint convexity with respect to both arguments, provides a convex parametrization of certain sets of globally nonnegative signomials with efficiently computable nonnegativity certificates via the arithmetic-geometric-mean inequality. By appealing to representation theorems from real algebraic geometry, we show that our sequences of lower bounds converge to the global optima for broad classes of SPs. Finally, we also demonstrate the effectiveness of our methods via numerical experiments.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1137/140988978DOIArticle
http://epubs.siam.org/doi/10.1137/140988978PublisherArticle
https://arxiv.org/abs/1409.7640arXivDiscussion Paper
Additional Information:© 2016 SIAM. Received by the editors September 26, 2014; accepted for publication (in revised form) September 15, 2015; published electronically May 12, 2016. This work was supported in part by the following grants: National Science Foundation Career award CCF-1350590 and Air Force Office of Scientific Research grant FA9550-14-1-0098.
Funders:
Funding AgencyGrant Number
NSFCCF-1350590
Air Force Office of Scientific Research (AFOSR)FA9550-14-1-0098
Subject Keywords:arithmetic-geometric-mean inequality, convex optimization, geometric programming, global optimization, real algebraic geometry
Classification Code:AMS subject classifications. 90C25, 90C26
Record Number:CaltechAUTHORS:20161017-134459797
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20161017-134459797
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71183
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:17 Oct 2016 20:52
Last Modified:14 Jun 2017 17:04

Repository Staff Only: item control page