Geometric programming

From Wikipedia, the free encyclopedia

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[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.

See also

Footnotes

  1. ↑ 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

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.