Geometric programming

A geometric program (GP) is an optimization problem of the form

{\begin{array}{ll}{\mbox{minimize}}&f_{0}(x)\\{\mbox{subject to}}&f_{i}(x)\leq 1,\quad i=1,\ldots ,m\\&g_{i}(x)=1,\quad i=1,\ldots ,p,\end{array}}

where $f_{0},\dots ,f_{m}$ are posynomials and $g_{1},\dots ,g_{p}$ are monomials. In the context of geometric programming (unlike standard mathematics), a monomial is a function from ${\mathbb {R}}_{{++}}^{n}$ to $\mathbb {R}$ defined as

x\mapsto cx_{1}^{a_{1}}x_{2}^{a_{2}}\cdots x_{n}^{a_{n}}

where $c>0\$ and $a_{i}\in {\mathbb {R}}$ . A posynomial is any sum of monomials.^[1]^[2]

Geometric programming is closely related to convex optimization: any GP can be made convex by means of a change of variables.^[2] GPs have numerous applications, including component sizing in IC design,^[3]^[4] aircraft design,^[5] maximum likelihood estimation for logistic regression in statistics, and parameter tuning of positive linear systems in control theory.^[6]

Convex form

Geometric programs are not in general convex optimization problems, but they can be transformed to convex problems by a change of variables and a transformation of the objective and constraint functions. In particular, after performing the change of variables $y_{i}=\log(x_{i})$ and taking the log of the objective and constraint functions, the functions $f_{i}$ , i.e., the posynomials, are transformed into log-sum-exp functions, which are convex, and the functions $g_{i}$ , i.e., the monomials, become affine. Hence, this transformation transforms every GP into an equivalent convex program.^[2] In fact, this log-log transformation can be used to convert a larger class of problems, known as log-log convex programming (LLCP), into an equivalent convex form.^[7]

Software

Several software packages exist to assist with formulating and solving geometric programs.

MOSEK is a commercial solver capable of solving geometric programs as well as other non-linear optimization problems.
CVXOPT is an open-source solver for convex optimization problems.
GPkit is a Python package for cleanly defining and manipulating geometric programming models. There are a number of example GP models written with this package here.
GGPLAB is a MATLAB toolbox for specifying and solving geometric programs (GPs) and generalized geometric programs (GGPs).
CVXPY is a Python-embedded modeling language for specifying and solving convex optimization problems, including GPs, GGPs, and LLCPs. ^[7]

References

^ Richard J. Duffin; Elmor L. Peterson; Clarence Zener (1967). Geometric Programming. John Wiley and Sons. p. 278. ISBN 0-471-22370-0.
^ ^a ^b ^c S. Boyd, S. J. Kim, L. Vandenberghe, and A. Hassibi. A Tutorial on Geometric Programming. Retrieved 20 October 2019.
^ M. Hershenson, S. Boyd, and T. Lee. Optimal Design of a CMOS Op-amp via Geometric Programming. Retrieved 8 January 2019.
^ S. Boyd, S. J. Kim, D. Patil, and M. Horowitz. Digital Circuit Optimization via Geometric Programming. Retrieved 20 October 2019.
^ W. Hoburg and P. Abbeel. Geometric programming for aircraft design optimization. AIAA Journal 52.11 (2014): 2414-2426.
^ Ogura, Masaki; Kishida, Masako; Lam, James (2020). "Geometric Programming for Optimal Positive Linear Systems". IEEE Transactions on Automatic Control. 65 (11): 4648–4663. arXiv:1904.12976. doi:10.1109/TAC.2019.2960697. ISSN 0018-9286.
^ ^a ^b A. Agrawal, S. Diamond, and S. Boyd. Disciplined Geometric Programming. Retrieved 8 January 2019.

[duffin-1] Richard J. Duffin; Elmor L. Peterson; Clarence Zener (1967). Geometric Programming. John Wiley and Sons. p. 278. ISBN 0-471-22370-0.

[tutorial-2] S. Boyd, S. J. Kim, L. Vandenberghe, and A. Hassibi. A Tutorial on Geometric Programming. Retrieved 20 October 2019.

[3] M. Hershenson, S. Boyd, and T. Lee. Optimal Design of a CMOS Op-amp via Geometric Programming. Retrieved 8 January 2019.

[4] S. Boyd, S. J. Kim, D. Patil, and M. Horowitz. Digital Circuit Optimization via Geometric Programming. Retrieved 20 October 2019.

[5] W. Hoburg and P. Abbeel. Geometric programming for aircraft design optimization. AIAA Journal 52.11 (2014): 2414-2426.

[6] Ogura, Masaki; Kishida, Masako; Lam, James (2020). "Geometric Programming for Optimal Positive Linear Systems". IEEE Transactions on Automatic Control. 65 (11): 4648–4663. arXiv:1904.12976. doi:10.1109/TAC.2019.2960697. ISSN 0018-9286.

[dgp-7] A. Agrawal, S. Diamond, and S. Boyd. Disciplined Geometric Programming. Retrieved 8 January 2019.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Geometric programming

Convex form

Software

See also

References