Programación de conos de segundo orden

Problema de optimización convexa

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 , y . es la variable de optimización. es la norma euclidiana e indica transpuesta . ^[1] El "cono de segundo orden" en SOCP surge de las restricciones, que son equivalentes a requerir que la función afín se encuentre en el cono de segundo orden en . ^[1] ${\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}}$ ${\displaystyle g\in \mathbb {R} ^{p}}$ ${\displaystyle x\in \mathbb {R} ^{n}}$ ${\displaystyle \lVert x\rVert _{2}}$ ${\displaystyle ^{T}}$ ${\displaystyle (Ax+b,c^{T}x+d)}$ ${\displaystyle \mathbb {R} ^{n_{i}+1}}$

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

Cono de segundo orden

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

${\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 como cono cuadrático , cono de helado o cono de Lorentz . El cono de segundo orden estándar en es . ${\displaystyle \mathbb {R} ^{3}}$ ${\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 aplicació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 convexo.

El cono de segundo orden se puede incrustar 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 (aquí significa que es una matriz semidefinida). De manera similar, también tenemos, ${\displaystyle M\succcurlyeq 0}$ ${\displaystyle M}$

${\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}$.

Relación con otros problemas de optimización

Una jerarquía de problemas de optimización convexa. (LP: programa lineal, QP: programa cuadrático, SOCP: programa de cono de segundo orden, SDP: programa semidefinido, CP: programa de cono).

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

Los programas cuadráticos convexos cuadráticamente restringidos también pueden formularse como SOCP reformulando la función objetivo como una restricción. ^[4] La programación semidefinida subsume 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. ^[4] Sin embargo, lo inverso no es válido: hay conos semidefinidos positivos que no admiten ninguna representación de cono de segundo orden. ^{[3] De hecho, mientras que cualquier} conjunto semialgebraico convexo cerrado en el plano puede escribirse como una región factible de un SOCP, ^[8] se sabe que existen conjuntos semialgebraicos convexos que no son representables por SDP, es decir, existen conjuntos semialgebraicos convexos que no pueden escribirse como una región factible de un SDP. ^[9]

Ejemplos

Restricción cuadrática

Consideremos una restricción cuadrática convexa de la forma

${\displaystyle x^{T}Ax+b^{T}x+c\leq 0.}$

Esto es equivalente a la restricción SOCP

${\displaystyle \lVert A^{1/2}x+{\frac {1}{2}}A^{-1/2}b\rVert \leq \left({\frac {1}{4}}b^{T}A^{-1}b-c\right)^{\frac {1}{2}}}$

Programación lineal estocástica

Considere un programa lineal estocástico en forma de desigualdad

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

sujeto a

${\displaystyle \mathbb {P} (a_{i}^{T}x\leq b_{i})\geq p,\quad i=1,\dots ,m}$

donde los parámetros son vectores aleatorios gaussianos independientes con media y covarianza y . Este problema se puede expresar como SOCP ${\displaystyle a_{i}\ }$ ${\displaystyle {\bar {a}}_{i}}$ ${\displaystyle \Sigma _{i}\ }$ ${\displaystyle p\geq 0.5}$

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

sujeto a

${\displaystyle {\bar {a}}_{i}^{T}x+\Phi ^{-1}(p)\lVert \Sigma _{i}^{1/2}x\rVert _{2}\leq b_{i},\quad i=1,\dots ,m}$

donde es la función de distribución acumulativa normal inversa . ^[1] ${\displaystyle \Phi ^{-1}(\cdot )\ }$

Programación estocástica de conos de segundo orden

Nos referimos a los programas de cono de segundo orden como programas de cono de segundo orden deterministas, ya que los datos que los definen son deterministas. Los programas de cono de segundo orden estocásticos son una clase de problemas de optimización que se definen para manejar la incertidumbre en los datos que definen los programas de cono de segundo orden deterministas. ^[10]

Otros ejemplos

Hay otros ejemplos de modelado disponibles en el libro de cocina de modelado MOSEK. ^[11]

Solucionadores y lenguajes de scripting (programación)

Véase también

• Los conos de potencia son generalizaciones de conos cuadráticos a potencias distintas de 2. ^[14]

Referencias

1. Boyd, Stephen; Vandenberghe, Lieven (2004). Optimización convexa (PDF) . Cambridge University Press. ISBN 978-0-521-83378-3. Recuperado el 15 de julio de 2019 .
2. Potra, lorian A.; Wright, Stephen J. (1 de diciembre de 2000). "Métodos de puntos interiores". Revista de Matemática Computacional y Aplicada . 124 (1–2): 281–302. Código Bibliográfico :2000JCoAM.124..281P. doi :10.1016/S0377-0427(00)00433-7.
3. Fawzi, Hamza (2019). "Sobre la representación del cono semidefinido positivo utilizando el cono de segundo orden". Programación matemática . 175 (1–2): 109–118. arXiv : 1610.04901 . doi :10.1007/s10107-018-1233-0. ISSN  0025-5610. S2CID  119324071.
4. Lobo, Miguel Sousa; Vandenberghe, Lieven; Boyd, Stephen; Lebret, Hervé (1998). "Aplicaciones de la programación de conos de segundo orden". Álgebra lineal y sus aplicaciones . 284 (1–3): 193–228. doi : 10.1016/S0024-3795(98)10032-0 .
5. "Resolución de SOCP" (PDF) .
6. "Optimización de cartera" (PDF) .
7. Li, Haksun (16 de enero de 2022). Métodos numéricos con Java: para ciencia de datos, análisis e ingeniería . APress. pp. Capítulo 10. ISBN 978-1484267967.
8. Scheiderer, Claus (8 de abril de 2020). "Representación de cono de segundo orden para subconjuntos convexos del plano". arXiv : 2004.04196 [math.OC].
9. Scheiderer, Claus (2018). "Sombras espectrales". Revista SIAM de álgebra y geometría aplicadas . 2 (1): 26–44. doi : 10.1137/17M1118981 . ISSN  2470-6566.
10. Alzalg, Baha M. (1 de octubre de 2012). "Programación estocástica de conos de segundo orden: modelos de aplicaciones". Modelado matemático aplicado . 36 (10): 5122–5134. doi :10.1016/j.apm.2011.12.053. ISSN  0307-904X.
11. "Libro de recetas de modelado MOSEK - Optimización cuadrática cónica".
12. "Solucionador de programación de conos de segundo orden - MATLAB coneprog". MathWorks . 2021-03-01 . Consultado el 2021-07-15 .
13. "Algoritmo de programación de cono de segundo orden - MATLAB y Simulink". MathWorks . 2021-03-01 . Consultado el 2021-07-15 .
14. "Libro de cocina de modelado MOSEK - los conos de potencia".