Geometrisches Programm

Ein geometrisches Programm ist ein spezielles Problem der mathematischen Optimierung, bei dem als Ziel- und Restriktionsfunktionen eine Verallgemeinerung von Polynomen zum Einsatz kommt. Insbesondere haben Geometrische Programme zwei Formen, von denen aber nur eine zur konvexen Optimierung zählt.

Definition

Ein Optimierungsproblem der Form

$\begin{array}{ccc}\text{Minimiere }& f(x)& \\ \text{unter den Nebenbedingungen }& g_i(x)\le 1& i=1,\dots ,p\\ & h_j(x)=1& j=1,\dots q\end{array}$

heißt geometrisches Programm (in Posynomialform), wenn die $f,g_i$ Posynomialfunktionen sind und die $h_j$ Monomialfunktionen sind. Die Einschränkung $x\in {ℝ}_{++}^n:=\{x\in {ℝ}^n|x_i>0\text{ für }i=1,\dots ,n\}$ ist hierbei stets implizit vorausgesetzt.

Beispiel

Das Optimierungsproblem

$\begin{array}{ccc}\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\le 1& \\ & x_1{x}_2{x}_3=1& \end{array}$

ist ein Geometrisches Programm.

Konvexe Form

Ein Geometrisches Programm lässt sich durch elementare Substitutionen in ein konvexes Optimierungsproblem transformieren.

Dazu setzt man zuerst $x_i=e^{y_i}$ bzw. $y_i=\log x_i$. Damit wird jede Monomialfunktion

$f(x_1,\dots ,x_n)=c{x}_1^{a_1}\cdot \dots \cdot x_n^{a_n}$

transformiert zu

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

wobei $b=\log c$ und $a=(a_1,\dots ,a_n)\in {ℝ}^n$ ist. Posynomialfunktionen lassen sich analog als Summe von Exponentialfunktionen von affinen Funktionen ausdrücken. Durch Anwenden dieser Transformation und anschließendes Logarithmieren erhält man dann das Optimierungsproblem

$\begin{array}{ccc}\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)\le 0& i=1,\dots ,p\\ & {\tilde{h}}_j(y)=g_j^{T}y+b_j=0& j=1,\dots q\text{,}\end{array}$

welches Geometrisches Programm in konvexer Form genannt wird. Es ist ein konvexes Optimierungsproblem. Wenn alle Funktionen Monomialfunktionen sind, vereinfacht sich dieses Problem zu einem linearen Optimierungsproblem.

Beispiel für die konvexe Form

Transformiert man das oben angeführte Geometrische Programm in Posynomialform in die Geometrische Form, so lautet es

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

Literatur

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