Geometric programming: Difference between revisions

Revision as of 17:09, 21 November 2017

Latest revision as of 06:07, 26 August 2025

(24 intermediate revisions by 14 users not shown)

Line 1:

{{More footnotes|date=October 2011}}

A '''geometric program''' ('''GP''') is an [[optimization (mathematics)|optimization]] problem of the form

:<math>

: Minimize <math>\ f_0(x)\ </math> subject to

\begin{array}{ll}

:: <math>f_i(x) \leq 1, \quad i = 1,\dots,m</math>

\mbox{minimize} & f_0(x) \\

:: <math>h_i(x) = 1,\quad i = 1,\dots,p</math>

::\mbox{subject to} & <math>f_i(x) \leq 1, \quad i = 1, \dotsldots, m</math>\\

:where <math>f_0,\dots,f_m</math> are [[posynomials]] and <math>h_1,\dots,h_p</math> are monomials.

::& <math>h_ig_i(x) = 1, \quad i = 1, \dotsldots, p</math>,

\end{array}

</math>

where <math>f_0,\dots,f_m</math> are [[posynomials]] and <math>g_1,\dots,g_p</math> are monomials. In the context of geometric programming (unlike allstandard other disciplinesmathematics), a monomial is a function from <math>h:\mathbb{R}_{++}^n</math> \to <math>\mathbb{R}</math> defined as

:<math>h(x) =\mapsto c x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n} </math>

In the context of geometric programming (unlike all other disciplines), a monomial is a function <math>h:\mathbb{R}_{++}^n \to \mathbb{R}</math> defined as

where <math> c > 0 \ </math> and <math>a_i \in \mathbb{R} </math>. A posynomial is any sum of monomials.<ref name="duffin">{{cite book

:<math>h(x) = c x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n} </math>

| author = Richard J. Duffin

|author2=Elmor L. Peterson |author3=Clarence Zener

| title = Geometric Programming

| publisher = John Wiley and Sons

| year = 1967

| pages = 278

| isbn = 0-471-22370-0

*}}</ref><ref name="tutorial">S. Boyd, S. J. Kim, L. Vandenberghe, and A. Hassibi,. ''[httphttps://wwwweb.stanford.edu/~boyd/papers/gp_tutorial.html A Tutorial on Geometric Programming].'' Retrieved 20 October 2019.</ref>

Geometric programming is

where <math> c > 0 \ </math> and <math>a_i \in \mathbb{R} </math>.

closely related to [[convex optimization]]: any GP can be made convex by means of a change of variables.<ref name="tutorial"/> GPs have numerous applications, including component sizing in [[Integrated circuit|IC]] design,<ref>M. Hershenson, S. Boyd, and T. Lee. ''[https://web.stanford.edu/~boyd/papers/opamp.html Optimal Design of a CMOS Op-amp via Geometric Programming].'' Retrieved 8 January 2019.</ref><ref>S. Boyd, S. J. Kim, D. Patil, and M. Horowitz. ''[https://web.stanford.edu/~boyd/papers/gp_digital_ckt.html Digital Circuit Optimization via Geometric Programming].'' Retrieved 20 October 2019.</ref> aircraft design,<ref>W. Hoburg and P. Abbeel. ''[https://people.eecs.berkeley.edu/~pabbeel/papers/2014-AIAA-GP-aircraft-design.pdf Geometric programming for aircraft design optimization].'' AIAA Journal 52.11 (2014): 2414-2426.</ref> [[maximum likelihood estimation]] for [[logistic regression]] in [[statistics]], and parameter tuning of positive [[Linear dynamical system|linear systems]] in [[control theory]].<ref>{{Cite journal|last1=Ogura|first1=Masaki|last2=Kishida|first2=Masako|last3=Lam|first3=James|date=2020|title=Geometric Programming for Optimal Positive Linear Systems|journal=IEEE Transactions on Automatic Control|volume=65|issue=11|pages=4648–4663|doi=10.1109/TAC.2019.2960697|issn=0018-9286|arxiv=1904.12976|bibcode=2020ITAC...65.4648O |s2cid=140222942 }}</ref>

GPs have numerous applications, such as component sizing in [[Integrated circuit|IC]] design<ref>http://www.stanford.edu/~boyd/papers/opamp.html</ref> and parameter estimation via [[logistic regression]] in [[statistics]]. The [[maximum likelihood]] estimator in logistic regression is a GP.

==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, definingafter performing the change of variables <math>y_i = \log(x_i)</math> and taking the log of the objective and constraint functions, the monomialfunctions <math>f(x)f_i</math>, =i.e., cthe x_1^{a_1}posynomials, \cdotsare x_n^{a_n}transformed \mapsto e^{a^Tinto y[[LogSumExp|log-sum-exp]] functions, which are convex, and the functions +b}<math>g_i</math>, wherei.e., the monomials, become [[affine transformation|affine]]. Hence, this transformation transforms every GP into an equivalent convex program.<math>bref name="tutorial"/> In fact, this \log-log transformation can be used to convert a larger class of problems, known as [[log-log convex programming]] (cLLCP), into an equivalent convex form.</mathref name="dgp">A. Agrawal, S. Diamond, and S. Boyd. ''[https://arxiv.org/abs/1812.04074 Disciplined Geometric Programming.]'' Retrieved 8 January 2019.</ref>

Similarly, if <math>f</math> is the [[posynomial]]

:<math> f(x) = \sum_{k=1}^K c_k x_1^{a_{1k}} \cdots x_n^{a_{nk}} </math>

then <math>f(x) = \sum_{k=1}^K e^{a_k^T y + b_k}</math>, where <math>a_k = (a_{1k},\dots,a_{nk} )</math> and <math>b_k = \log(c_k) </math>. After the change of variables, a posynomial becomes a sum of exponentials of affine functions.

==Software==

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

* [https://www.mosek.com/ MOSEK] is a commercial solver capable of solving geometric programs as well as other non-linear optimization problems.

* [http://cvxopt.org/ CVXOPT] is an open-source solver for convex optimization problems.

* [https://github.com/hoburgconvexengineering/gpkit 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 [https://github.com/hoburgconvexengineering/gpkit-modelsgplibrary here].

*[https://web.stanford.edu/~boyd/ggplab/ GGPLAB] is a MATLAB toolbox for specifying and solving geometric programs (GPs) and generalized geometric programs (GGPs).

* [https://www.cvxpy.org/tutorial/dgp/index.html CVXPY] is a Python-embedded modeling language for specifying and solving convex optimization problems, including GPs, GGPs, and LLCPs.<ref name="dgp"/>

==See also==

*[[Signomial]]

*[[Clarence Zener]]

==FootnotesReferences==

{{reflist}}

[[Category:MathematicalConvex optimization]]

==References==

*{{cite book

| author = Richard J. Duffin

|author2=Elmor L. Peterson |author3=Clarence Zener

| title = Geometric Programming

| publisher = John Wiley and Sons

| year = 1967

| pages = 278

| isbn = 0-471-22370-0

}}

==External links==

* S. Boyd, S. J. Kim, L. Vandenberghe, and A. Hassibi, [http://www.stanford.edu/~boyd/gp_tutorial.html A Tutorial on Geometric Programming]

* S. Boyd, S. J. Kim, D. Patil, and M. Horowitz [http://www.stanford.edu/~boyd/gp_digital_ckt.html Digital Circuit Optimization via Geometric Programming]

[[Category:Mathematical optimization]]