Geometric programming

A Geometric Program 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. It should be noted that in the context of geometric programming (unlike all other disciplines), a monomial is defined as a function $f:mathbb\{R\}^n\; o\; mathbb\{R\}$ with $mathrm\{dom\}\; f\; =\; mathbb\{R\}\_\{++\}^n$ defined as

:$f(x)\; =\; c\; x\_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 circuit sizing 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)\; =\; c\; x\_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.

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]