Geometrical program

A geometrical program is a special problem of mathematical optimization in which a generalization of polynomials is used as target and restriction functions . In particular, geometric programs have two forms, but only one of them counts for convex optimization .

definition

A shape optimization problem

${\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g_{i}(x)\leq 1&i=1,\dots ,p\\&h_{j}(x)=1&j=1,\dots q\end{aligned}}}$

is called a geometric program (in posynomial form) if the are posynomial functions and the monomial functions are. The restriction is always implicit here. ${\displaystyle f,g_{i}}$ ${\displaystyle h_{j}}$ ${\displaystyle x\in \mathbb {R} _{++}^{n}:=\{x\in \mathbb {R} ^{n}\,|\,x_{i}>0{\text{ für }}i=1,\dots ,n\}}$

example

The optimization problem

${\displaystyle {\begin{aligned}{\text{Minimiere }}&x_{1}^{1/2}x_{2}^{2}+x_{2}^{-4/3}x_{3}^{8}&\\{\text{unter den Nebenbedingungen }}&x_{1}^{-1}x_{2}^{5}x_{3}^{5/7}+x_{3}\leq 1&\\&x_{1}x_{2}x_{3}=1&\end{aligned}}}$

is a geometric program.

Convex shape

A geometric program can be transformed into a convex optimization problem by means of elementary substitutions .

To do this, first set or . This makes every monomial function ${\displaystyle x_{i}=e^{y_{i}}}$ ${\displaystyle y_{i}=\log x_{i}}$

${\displaystyle f(x_{1},\dots ,x_{n})=cx_{1}^{a_{1}}\cdot \dots \cdot x_{n}^{a_{n}}}$

transformed to

${\displaystyle {\tilde {f}}(x)=e^{a^{T}x+b}}$,

where and is. Posynomial functions can be expressed analogously as the sum of exponential functions of affine functions. The optimization problem is then obtained by applying this transformation and then taking the logarithm ${\displaystyle b=\log c}$ ${\displaystyle a=(a_{1},\dots ,a_{n})\in \mathbb {R} ^{n}}$

${\displaystyle {\begin{aligned}{\text{Minimiere }}&{\tilde {f}}(y)=\log \left(\sum _{k=1}^{N}e^{a_{k}^{T}y+b_{k}}\right)&\\{\text{unter den Nebenbedingungen }}&{\tilde {g}}_{i}(y)=\log \left(\sum _{k=1}^{N_{i}}e^{a_{i,k}^{T}y+b_{i,k}}\right)\leq 0&i=1,\dots ,p\\&{\tilde {h}}_{j}(y)=g_{j}^{T}y+b_{j}=0&j=1,\dots q{\text{,}}\end{aligned}}}$

which is called a geometric program in convex form . It's a convex optimization problem. When all functions are monomial, this problem simplifies to a linear optimization problem .

Example of the convex shape

If one transforms the above geometric program in posynomial form into the geometric form, it reads

${\displaystyle {\begin{aligned}{\text{Minimiere }}&\log \left(\exp {[(1/2,2,0)\cdot y]}+\exp {[(0,-4/3,8)\cdot y]}\right)&\\{\text{unter den Nebenbedingungen }}&\log \left(\exp {[(-1,5,5/7)\cdot y]}+\exp {[(0,0,1)\cdot y]}\right)\leq 0&\\&(1,1,1)\cdot y=0&\end{aligned}}}$.

literature

• Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3 . ( online )