Programació geomètrica

Un programa geomètric és un problema d'optimització de la forma^[1]

Minimitzar ${\displaystyle \ f_{0}(x)\ }$ tal que

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

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

on ${\displaystyle f_{0},\dots ,F_{m}}$ són posinomis i ${\displaystyle h_{1},\dots ,h_{p}}$ són monomis. Cal subratllar que en parlar de programació geomètrica (al contrari que en altres disciplines), un monomi es defineix com una funció ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ amb ${\displaystyle \mathrm {dg} \ f=\mathbb {R} _{++}^{n}}$ definit com

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

on ${\displaystyle c>0\ }$ i ${\displaystyle a_{i}\in \mathbb {R} }$.

Té múltiples aplicacions, com el dimensionament de circuits i l'estimació paramètrica via regressió logística en estadística.

Els programa geomètrics no són per regla general problemes d'optimització convexa, però poden transformar-se en ells mitjançant un canvi de variables i una transformació de les funcions objectiu i de restricció. Definint ${\displaystyle y_{i}=\log {x_{i}}}$, el monomi ${\displaystyle f(x)=cx_{1}^{a_{1}}\cdots x_{n}^{a_{n}}\mapsto i^{a^{T}i+b}}$, on ${\displaystyle b=log{c}}$. De la mateixa manera, si ${\displaystyle f}$ és el posinomi

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

llavors ${\displaystyle f(x)=\sum _{k=1}^{K}i^{a_{k}^{T}i+b_{k}}}$, on ${\displaystyle a_{k}=(a_{1k},\dots ,a_{nk})}$ i ${\displaystyle b_{k}=\log {c_{k}}}$. Després del canvi de variables, el posinomi es converteix en una suma d'exponencials de funcions afins.

• S. Boyd, S. J. Kim, L. Vandenberghe, and A. Hassibi - Optimization and Engineering, 8(1):67-127, 2007., A Tutorial on Geometric Programming
• S. Boyd, S. J. Kim, D. Patil, and M. Horowitz Digital Circuit Optimization via Geometric Programming
• Stephen P. Boyd, Seung-Jean Kim, Dinesh D. Patil, Mark A. Horowitz, Optimització de circuits via programació geomètrica.