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 non-convex 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.
We introduce and study conic geometric programs (CGPs), which are convex optimization problems that unify geometric programs (GPs) and conic optimization problems such as semidefinite programs (SDPs). A CGP consists of a linear objective function tha
t is to be minimized subject to affine constraints, convex conic constraints, and upper bound constraints on sums of exponential and affine functions. The conic constraints are the central feature of conic programs such as SDPs, while upper bounds on combined exponential/affine functions are generalizations of the types of constraints found in GPs. The dual of a CGP involves the maximization of the negative relative entropy between two nonnegative vectors jointly, subject to affine and conic constraints on the two vectors. Although CGPs contain GPs and SDPs as special instances, computing global optima of CGPs is not much harder than solving GPs and SDPs. More broadly, the CGP framework facilitates a range of new applications that fall outside the scope of SDPs and GPs. Specifically, we demonstrate the utility of CGPs in providing solutions to problems such as permanent maximization, hitting-time estimation in dynamical systems, the computation of the capacity of channels transmitting quantum information, and robust optimization formulations of GPs.
