Geometric programming

From Wikipedia, the free encyclopedia

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 \to \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.

[edit] 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 = l o g 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.