Geometric programming

A geometric program (GP) is an optimization problem of the form

minimize ${\displaystyle \ f_{0}(x)\ }$ subject to

${\displaystyle f_{i}(x)\leq 1,\quad i=1,\dots ,m}$

${\displaystyle h_{i}(x)=1,\quad i=1,\dots ,p}$

where ${\displaystyle f_{0},\dots ,f_{m}}$ are polynomials and ${\displaystyle h_{1},\dots ,h_{p}}$ are monomials. In the context of geometric programming (unlike all other disciplines), a monomial is defined as a function ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ with ${\displaystyle \mathrm {dom} \ f=\mathbb {R} _{++}^{n}}$ defined as

${\displaystyle f(x)=cx_{1}^{a_{1}}x_{2}^{a_{2}}\cdots x_{n}^{a_{n}}}$

where ${\displaystyle c>0\ }$ and ${\displaystyle 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 ${\displaystyle y_{i}=\log(x_{i})}$ , the monomial ${\displaystyle f(x)=cx_{1}^{a_{1}}\cdots x_{n}^{a_{n}}\mapsto e^{a^{T}y+b}}$ , where ${\displaystyle b=\log(c)}$ . Similarly, if ${\displaystyle f}$  is the posynomial

${\displaystyle f(x)=\sum _{k=1}^{K}c_{k}x_{1}^{a_{1k}}\cdots x_{n}^{a_{nk}}}$ 

then ${\displaystyle f(x)=\sum _{k=1}^{K}e^{a_{k}^{T}y+b_{k}}}$ , where ${\displaystyle a_{k}=(a_{1k},\dots ,a_{nk})}$  and ${\displaystyle 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, A Tutorial on Geometric Programming

• S. Boyd, S. J. Kim, D. Patil, and M. Horowitz Digital Circuit Optimization via Geometric Programming