Optimización cónica

Subcampo de optimización convexa

La optimización cónica es un subcampo de la optimización convexa que estudia problemas que consisten en minimizar una función convexa sobre la intersección de un subespacio afín y un cono convexo .

La clase de problemas de optimización cónica incluye algunas de las clases más conocidas de problemas de optimización convexa, a saber, la programación lineal y semidefinida .

Definición

Dado un espacio vectorial real X , una función convexa y de valor real

${\displaystyle f:C\to \mathbb {R} }$

definido en un cono convexo y un subespacio afín definido por un conjunto de restricciones afines , un problema de optimización cónica es encontrar el punto en el que el número es más pequeño. ${\displaystyle C\subset X}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle h_{i}(x)=0\ }$ ${\displaystyle x}$ ${\displaystyle C\cap {\mathcal {H}}}$ ${\displaystyle f(x)}$

Entre los ejemplos de se incluyen el ortante positivo , las matrices semidefinidas positivas y el cono de segundo orden . A menudo es una función lineal, en cuyo caso el problema de optimización cónica se reduce a un programa lineal , un programa semidefinido y un programa de cono de segundo orden , respectivamente. ${\displaystyle C}$ ${\displaystyle \mathbb {R} _{+}^{n}=\left\{x\in \mathbb {R} ^{n}:\,x\geq \mathbf {0} \right\}}$ ${\displaystyle \mathbb {S} _{+}^{n}}$ ${\displaystyle \left\{(x,t)\in \mathbb {R} ^{n}\times \mathbb {R} :\lVert x\rVert \leq t\right\}}$ ${\displaystyle f\ }$

Dualidad

Ciertos casos especiales de problemas de optimización cónica tienen notables expresiones en forma cerrada de sus problemas duales.

LP cónico

El dual del programa lineal cónico

minimizar ${\displaystyle c^{T}x\ }$

sujeto a ${\displaystyle Ax=b,x\in C\ }$

es

maximizar ${\displaystyle b^{T}y\ }$

sujeto a ${\displaystyle A^{T}y+s=c,s\in C^{*}\ }$

donde denota el cono dual de . ${\displaystyle C^{*}}$ ${\displaystyle C\ }$

Si bien la dualidad débil se cumple en la programación lineal cónica, la dualidad fuerte no necesariamente se cumple. ^[1]

Programa Semidefinido

El dual de un programa semidefinido en forma de desigualdad

minimizar ${\displaystyle c^{T}x\ }$

sujeto a ${\displaystyle x_{1}F_{1}+\cdots +x_{n}F_{n}+G\leq 0}$

viene dado por

maximizar ${\displaystyle \mathrm {tr} \ (GZ)\ }$

sujeto a ${\displaystyle \mathrm {tr} \ (F_{i}Z)+c_{i}=0,\quad i=1,\dots ,n}$

${\displaystyle Z\geq 0}$

Referencias

1. "Dualidad en programación cónica" (PDF) .

Enlaces externos

• Boyd, Stephen P.; Vandenberghe, Lieven (2004). Optimización convexa (PDF) . Cambridge University Press. ISBN 978-0-521-83378-3. Recuperado el 15 de octubre de 2011 .
• Software MOSEK capaz de resolver problemas de optimización cónica.