Signomial and polynomial optimization via relative entropy and partial dualization
- PDF / 699,167 Bytes
- 39 Pages / 439.37 x 666.142 pts Page_size
- 48 Downloads / 215 Views
Signomial and polynomial optimization via relative entropy and partial dualization Riley Murray1 · Venkat Chandrasekaran1 · Adam Wierman1 Received: 21 July 2019 / Accepted: 11 August 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract We describe a generalization of the Sums-of-AM/GM-Exponential (SAGE) methodology for relative entropy relaxations of constrained signomial and polynomial optimization problems. Our approach leverages the fact that SAGE certificates conveniently and transparently blend with convex duality, in a way which enables partial dualization of certain structured constraints. This more general approach retains key properties of ordinary SAGE relaxations (e.g. sparsity preservation), and inspires a projective method of solution recovery which respects partial dualization. We illustrate the utility of our methodology with a range of examples from the global optimization literature, along with a publicly available software package. Keywords Global optimization · Exponential cone programs · SAGE certificates · SOS certificates · Signomial programming
1 Introduction m A signomial is a function x → i=1 ci exp(α i · x) for real scalars ci and row vectors α i in R1×n . Signomial optimization and signomial programming are challenging problems with applications in chemical engineering [1], aeronautics [2], circuit design [3], and communications network optimization [4]. Signomials are sometimes thought of as generalized polynomials over the positive orthant Rn++ ; by a change of variables m α yi = exp xi one arrives at “geometric form” signomials y → i=1 ci nj=1 y j i j . Despite this aesthetic similarity, signomials and polynomials have many significant
B
Riley Murray [email protected] Venkat Chandrasekaran [email protected] Adam Wierman [email protected]
1
California Institute of Technology, Pasadena, CA 91125, USA
123
R. Murray et al.
differences. Where polynomials are generated by a countably infinite basis, signomials require an uncountably infinite basis. Where polynomials are closed under composition, signomials are not. Where polynomials and exponential-form signomials are defined on all of Rn , geometric-form signomials are only defined on Rn++ . For many years these abstract differences between signomials and polynomials have coincided with algorithmic disparities. Contemporary methods for signomial programming use some combination of local linearization, penalty functions, sequential geometric programming, and branch-and-bound [5–11]—ideas which precede the advent of modern convex optimization. By contrast, the study of polynomial optimization has been substantially influenced by semidefinite programming, specifically through Sums-of-Squares (SOS) certificates of polynomial nonnegativity [12–14]. In recent work, Chandrasekaran and Shah proposed Sums-of-AM/GM-Exponentials or “SAGE” decompositions, which use relative entropy programming to certify signomial nonnegativity [15]. The authors of the present article have
Data Loading...
