Programación de conos de segundo orden

Un programa de cono de segundo orden ( SOCP ) es un problema de optimización convexa de la forma

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

sujeto a

${\displaystyle \lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i},\quad i=1,\dots ,m}$

${\displaystyle Fx=g\ }$

donde los parámetros del problema son${\displaystyle f\in \mathbb {R} ^{n},\ A_{i}\in \mathbb {R} ^{{n_{i}}\times n},\ b_{i}\in \mathbb {R} ^{n_{i}},\ c_{i}\in \mathbb {R} ^{n},\ d_{i}\in \mathbb {R} ,\ F\in \mathbb {R} ^{p\times n}}$, y${\displaystyle g\in \mathbb {R} ^{p}}$.${\displaystyle x\in \mathbb {R} ^{n}}$es la variable de optimización. ${\displaystyle \lVert x\rVert _{2}}$es la norma euclidiana y${\displaystyle ^{T}}$indica transposición . ^{[ 1 ]}

El nombre "programación de cono de segundo orden" proviene de la naturaleza de las restricciones individuales, cada una de las cuales tiene la forma:

${\displaystyle \lVert Ax+b\rVert _{2}\leq c^{T}x+d}$

Cada uno de estos define un subespacio que está acotado por una desigualdad basada en una función polinómica de segundo orden definida en la variable de optimización.${\displaystyle x}$Se puede demostrar que esto define un cono convexo , de ahí el nombre de " cono de segundo orden ". ^{[ 2 ]} Por definición de conos convexos, su intersección también puede ser un cono convexo, aunque no necesariamente uno que pueda definirse mediante una sola desigualdad de segundo orden. Véase más adelante para un análisis más detallado.

Los SOCP se pueden resolver mediante métodos de punto interior ^{[ 3 ]} y, en general, se pueden resolver de manera más eficiente que los problemas de programación semidefinida (SDP) ^{[ 4 ]} . Algunas aplicaciones de ingeniería de los SOCP incluyen el diseño de filtros , el diseño de pesos de matrices de antenas, el diseño de estructuras de celosía y la optimización de la fuerza de agarre en robótica ^{[ 5 ]} . Las aplicaciones en finanzas cuantitativas incluyen la optimización de carteras ; algunas restricciones de impacto de mercado , debido a que no son lineales, no se pueden resolver mediante programación cuadrática , pero se pueden formular como problemas SOCP ^{[ 6 ] [ 7 ] [ 8 ] .}

El cono estándar o unitario de segundo orden de dimensión${\displaystyle n+1}$se define como

${\displaystyle {\mathcal {C}}_{n+1}=\left\{{\begin{bmatrix}x\\t\end{bmatrix}}{\Bigg |}x\in \mathbb {R} ^{n},t\in \mathbb {R} ,\|x\|_{2}\leq t\right\}}$.

El cono de segundo orden también se conoce con los nombres de cono cuadrático , cono de helado ^{[ 9 ]} o cono de Lorentz . Por ejemplo, el cono estándar de segundo orden en${\displaystyle \mathbb {R} ^{3}}$es

${\displaystyle \left\{(x,y,z){\Big |}{\sqrt {x^{2}+y^{2}}}\leq z\right\}}$.

El conjunto de puntos que satisfacen una restricción de cono de segundo orden es la imagen inversa del cono unitario de segundo orden bajo una transformación afín:

${\displaystyle \lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i}\Leftrightarrow {\begin{bmatrix}A_{i}\\c_{i}^{T}\end{bmatrix}}x+{\begin{bmatrix}b_{i}\\d_{i}\end{bmatrix}}\in {\mathcal {C}}_{n_{i}+1}}$

y por lo tanto es convexa.

El cono de segundo orden puede incrustarse en el cono de las matrices semidefinidas positivas ya que

${\displaystyle ||x||\leq t\Leftrightarrow {\begin{bmatrix}tI&x\\x^{T}&t\end{bmatrix}}\succcurlyeq 0,}$

Es decir, una restricción de cono de segundo orden es equivalente a una desigualdad matricial lineal . La nomenclatura aquí puede ser confusa; aquí${\displaystyle M\succcurlyeq 0}$medio${\displaystyle M}$es una matriz semidefinida: es decir

${\displaystyle x^{T}Mx\geq 0{\text{ para todo }}x\in \mathbb {R} ^{n}}$

lo cual no es una desigualdad lineal en el sentido convencional.

De manera similar, también tenemos,

${\displaystyle \lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i}\Leftrightarrow {\begin{bmatrix}(c_{i}^{T}x+d_{i})I&A_{i}x+b_{i}\\(A_{i}x+b_{i})^{T}&c_{i}^{T}x+d_{i}\end{bmatrix}}\succcurlyeq 0}$.

Cuando${\displaystyle A_{i}=0}$para${\displaystyle i=1,\dots ,m}$, el SOCP se reduce a un programa lineal . Cuando${\displaystyle c_{i}=0}$para${\displaystyle i=1,\dots ,m}$El SOCP es equivalente a un programa lineal convexo con restricciones cuadráticas.

Los programas cuadráticos con restricciones cuadráticas convexas también pueden formularse como SOCP reformulando la función objetivo como una restricción. ^{[ 5 ]} La programación semidefinida engloba a los SOCP, ya que las restricciones de los SOCP pueden escribirse como desigualdades matriciales lineales (LMI) y pueden reformularse como una instancia de programa semidefinido. ^{[ 5 ]} Sin embargo, lo contrario no es válido: existen conos semidefinidos positivos que no admiten ninguna representación de cono de segundo orden. ^{[ 4 ]}

Cualquier conjunto semialgebraico convexo cerrado en el plano puede escribirse como una región factible de un SOCP. ^{[ 10 ]} Sin embargo, se sabe que existen conjuntos semialgebraicos convexos de dimensión superior que no son representables por SDP; es decir, existen conjuntos semialgebraicos convexos que no pueden escribirse como la región factible de un SDP (ni, con mayor razón , como la región factible de un SOCP). ^{[ 11 ]}

• Los conos de potencia son generalizaciones de los conos cuadráticos a potencias distintas de 2. ^{[ 16 ]}