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 $h:\mathbb {R} _{++}^{n}\to \mathbb {R}$ defined as

h(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^[1] 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.

Footnotes

↑ http://www.stanford.edu/~boyd/papers/opamp.html

References

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

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

This article is issued from Wikipedia - version of the 9/26/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Geometric programming

Convex form

See also

Footnotes

References

External links