Geometric programming

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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} 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 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[edit]

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.

See also[edit]

Footnotes[edit]

References[edit]

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

External links[edit]