Un programa de cono de segundo orden ( SOCP ) es un problema de optimización convexa de la forma
- minimizar
- sujeto a
donde están los parámetros del problema , y . es la variable de optimización. es la norma euclidiana yindica transposición . [1] El "cono de segundo orden" en SOCP surge de las restricciones, que son equivalentes a requerir la función afín reposar en el cono de segundo orden en . [1]
Los SOCP pueden resolverse mediante métodos de puntos interiores [2] y, en general, pueden resolverse 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 del peso de la matriz de antenas, el diseño de truss y la optimización de la fuerza de agarre en robótica. [4]
Cono de segundo orden
El cono de dimensión estándar o unitario de segundo orden Se define como
.
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 en es , que parece un helado.
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 un mapeo afín:
y por tanto es convexo.
El cono de segundo orden se puede incrustar en el cono de las matrices semidefinidas positivas ya que
es decir, una restricción de cono de segundo orden es equivalente a una desigualdad de matriz lineal (aquí medio es matriz semidefinida). Del mismo modo, también tenemos,
.
Relación con otros problemas de optimización
Cuándo por , el SOCP se reduce a un programa lineal . Cuándo por , el SOCP es equivalente a un programa lineal convexo restringido cuadráticamente.
Los programas cuadráticos convexos con restricciones cuadráticas también se pueden formular como SOCP reformulando la función objetivo como una restricción. [4] La programación semidefinida subsume los SOCP ya que las restricciones del SOCP se pueden escribir como desigualdades de matriz lineal (LMI) y se pueden reformular como una instancia de programa semidefinito. [4] Lo contrario, sin embargo, no es válido: hay conos positivos semidefinidos 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, [5] se sabe que existen conjuntos semialgebraicos convexos que no son representables por los SDP, es decir, existen conjuntos semialgebraicos convexos que no se pueden escribir como una región factible de un SDP. [6]
Ejemplos de
Restricción cuadrática
Considere una restricción cuadrática de la forma
Esto es equivalente a la restricción SOC
Programación lineal estocástica
Considere un programa lineal estocástico en forma de desigualdad
- minimizar
- sujeto a
donde los parámetros son vectores aleatorios gaussianos independientes con media y covarianza y . Este problema se puede expresar como el SOCP
- minimizar
- sujeto a
dónde es la función de distribución acumulativa normal inversa . [1]
Programación estocástica de cono de segundo orden
Nos referimos a los programas de conos de segundo orden como programas de conos deterministas de segundo orden, 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 programas de cono de segundo orden deterministas.
Solucionadores y lenguajes de scripting (programación)
Nombre | Licencia | Breve información |
---|---|---|
AMPL | comercial | Un lenguaje de modelado algebraico con soporte SOCP |
Artelys Knitro | comercial | |
CPLEX | comercial | |
FICO Xpress | comercial | |
Gurobi | comercial | algoritmo de barrera SOCP paralelo |
MOSEK | comercial | algoritmo de punto interior paralelo |
Biblioteca numérica NAG | comercial | Biblioteca numérica de uso general con solucionador SOCP |
Referencias
- ^ a b c Boyd, Stephen; Vandenberghe, Lieven (2004). Optimización convexa (PDF) . Prensa de la Universidad de Cambridge. ISBN 978-0-521-83378-3. Consultado el 15 de julio de 2019 .
- ^ Potra, lorian A .; Wright, Stephen J. (1 de diciembre de 2000). "Métodos de punto interior" . 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 .
- ^ a b Fawzi, Hamza (2019). "Sobre la representación del cono semidefinito 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 .
- ^ a b c 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 .
- ^ Scheiderer, Claus (8 de abril de 2020). "Representación de cono de segundo orden para subconjuntos convexos del plano". arXiv : 2004.04196 [ math.OC ].
- ^ Scheiderer, Claus (2018). "Sombras espectrales" . Revista SIAM de Álgebra Aplicada y Geometría . 2 (1): 26–44. doi : 10.1137 / 17M1118981 . ISSN 2470-6566 .