Geometric programming

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

Minimize $\ f_{0}(x)\$ subject to

$f_{i}(x)\leq 1,\quad i=1,\dots ,m$

$h_{i}(x)=1,\quad i=1,\dots ,p$

where $f_{0},\dots ,f_{m}$ are posynomials and $h_{1},\dots ,h_{p}$ are monomials.

In the context of geometric programming (unlike all other disciplines), a monomial is defined as a function $f:\mathbb {R} ^{n}\to \mathbb {R}$ with $\mathrm {dom} \ f=\mathbb {R} _{++}^{n}$ defined as

$f(x)=cx_{1}^{a_{1}}x_{2}^{a_{2}}\cdots x_{n}^{a_{n}}$

where $c>0\$ and $a_{i}\in \mathbb {R}$.

GPs have numerous application, such as components sizing in IC design 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, defining $y_{i}=\log(x_{i})$, the monomial $f(x)=cx_{1}^{a_{1}}\cdots x_{n}^{a_{n}}\mapsto e^{a^{T}y+b}$, where $b=\log(c)$. Similarly, if $f$ is the posynomial

$f(x)=\sum _{k=1}^{K}c_{k}x_{1}^{a_{1k}}\cdots x_{n}^{a_{nk}}$

then $f(x)=\sum _{k=1}^{K}e^{a_{k}^{T}y+b_{k}}$, where $a_{k}=(a_{1k},\dots ,a_{nk})$ and $b_{k}=\log(c_{k})$. After the change of variables, a posynomial becomes a sum of exponentials of affine functions.

See also

• Signomial

References

• Richard J. Duffin (1967). Geometric Programming. John Wiley and Sons. p. 278. ISBN 0-471-22370-0. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

External links

• S. Boyd, S. J. Kim, L. Vandenberghe, and A. Hassibi, A Tutorial on Geometric Programming
• S. Boyd, S. J. Kim, D. Patil, and M. Horowitz Digital Circuit Optimization via Geometric Programming