La optimización convexa es un subcampo de la optimización matemática que estudia el problema de minimizar funciones convexas sobre conjuntos convexos (o, equivalentemente, maximizar funciones cóncavas sobre conjuntos convexos). Muchas clases de problemas de optimización convexa admiten algoritmos de tiempo polinomial, mientras que la optimización matemática es, en general, NP-difícil.

Definición Un problema de optimización convexa se define mediante dos ingredientes:

La función objetivo, que es una función convexa de n variables que toma valores reales, ; El conjunto factible, que es un subconjunto convexo .

El objetivo del problema es encontrar algún punto donde se alcance el menor valor de la función objetivo en el conjunto :

.

En general, existen tres situaciones posibles:

Si existe un punto donde se alcance el valor ínfimo de , a este punto se le denomina punto óptimo o solución, y el problema se denomina resoluble (tiene solución). El conjunto de todos los puntos óptimos se denomina conjunto óptimo (conjunto de soluciones). Si es no acotada inferiormente en , o si no se alcanza el ínfimo, entonces se dice que el problema de optimización es no acotado. Si es el conjunto vacío, entonces se dice que el problema es no factible: no existe .

Forma estándar Un problema de optimización convexa está en forma estándar cuando se escribe como:

donde:

es el vector de variables de optimización; La función objetivo es una función convexa (en particular el dominio se asume convexo); Las funciones de restricciones de desigualdad , , son funciones convexas; Las funciones de restricciones de igualdad , , son funciones afines. Es decir, funciones de la forma: , donde es un vector y es un escalar.

El conjunto factible del problema de optimización consta de todos los puntos que satisfacen las restricciones de desigualdad e igualdad. Este conjunto es convexo porque: es convexo, los conjuntos de nivel de funciones convexas son convexos, los conjuntos afines son convexos y la intersección de conjuntos convexos es convexa.

Muchos problemas de optimización pueden formularse en esta forma estándar. Por ejemplo, el problema de maximizar una función cóncava puede reformularse de forma equivalente como el problema de minimizar la función convexa . Debido a esto, el problema de maximizar una función cóncava sobre un conjunto convexo se denomina comúnmente problema de optimización convexa.

Forma epigráfica (forma estándar con objetivo lineal) En la forma estándar es posible asumir, sin pérdida de generalidad, que la función objetivo f es una función lineal. Esto se debe a que cualquier problema convexo en su forma estándar puede transformarse de forma equivalente en un problema convexo con función objetivo lineal, agregando una variable t y una restricción, como sigue:

Forma cónica Todo programa convexo puede presentarse en forma cónica, lo que significa minimizar una función objetivo lineal sobre la intersección de un plano afín y un cono convexo:

donde K es un cono convexo cerrado y puntiagudo, L es un subespacio lineal de Rn, y b es un vector en Rn. Un problema lineal en forma estándar es el caso especial en el que K es el ortante no negativo de Rn.

Eliminación de restricciones de igualdad lineal Es posible convertir un problema convexo en forma estándar a un problema convexo sin restricciones de igualdad. Denotemos las restricciones de igualdad hi ( x )=0 como Ax = b, donde A es una matriz de n columnas. Si Ax = b es no factible, entonces, por supuesto, el problema original es no factible. De lo contrario, tiene alguna solución x0, y el conjunto de todas las soluciones se puede escribir como: Fz + x0, donde z está en Rk, k = n -rango(A), y F es una matriz n × k. Sustituyendo x = Fz + x 0 en el problema original se obtiene:donde las variables son z. Nótese que hay rango( A ) menos variables. Esto significa que, en principio, se puede limitar la atención a problemas de optimización convexa sin restricciones de igualdad. Sin embargo, en la práctica, suele preferirse mantener las restricciones de igualdad, ya que pueden hacer que algunos algoritmos sean más eficientes y también facilitan la comprensión y el análisis del problema.

Casos especiales Las siguientes clases de problemas son todos problemas de optimización convexa, o pueden reducirse a problemas de optimización convexa mediante transformaciones simples: miniaturadeimagen|Jerarquía de problemas de optimización convexa. (LP: programación lineal, QP: programación cuadrática, SOCP: programa de cono de segundo orden, SDP: programación semidefinida, CP: optimización cónica).

Los problemas de programación lineal son los problemas convexos más simples. En la programación lineal, tanto la función objetivo como las funciones de restricción son lineales. La programación cuadrática es la siguiente más sencilla. En la programación cuadrática, todas las restricciones son lineales, pero la función objetivo puede ser una función cuadrática convexa. La programación de conos de segundo orden es más general. La programación semidefinida es más general. La optimización cónica es aún más general; véase la figura de la derecha.

Otros casos especiales incluyen:

Mínimos cuadrados. Minimización cuadrática con restricciones cuadráticas convexas. Programación geométrica. Maximización de la entropía con las restricciones adecuadas.

Propiedades Las siguientes son propiedades útiles de los problemas de optimización convexa:

Todo punto que sea un mínimo local es también un mínimo global; El conjunto de soluciones es convexo; Si la función objetivo es estrictamente convexa, entonces el problema tiene como máximo un punto óptimo.

Estos resultados son utilizados por la teoría de minimización convexa junto con nociones geométricas del análisis funcional (en espacios de Hilbert) como el teorema de proyección de Hilbert, el teorema del hiperplano separador y el lema de Farkas.

Algoritmos

Problemas sin restricciones y problemas con restricciones de igualdad Los problemas convexos más fáciles de resolver son los problemas sin restricciones, o aquellos con solo restricciones de igualdad. Dado que las restricciones de igualdad son todas lineales, se pueden eliminar mediante álgebra lineal e integrar en la función objetivo, transformando así un problema con restricciones de igualdad en uno sin restricciones.

En la clase de problemas sin restricciones (o con restricciones de igualdad), los más simples son aquellos en los que la función objetivo es cuadrática. Para estos problemas, las condiciones de KKT (que son necesarias para la optimalidad) son todas lineales, por lo que pueden resolverse analíticamente.

Para problemas sin restricciones (o con restricciones de igualdad) con una función objetivo convexa general que es dos veces diferenciable, se puede utilizar el método de Newton. Se puede ver como una reducción de un problema convexo general sin restricciones a una secuencia de problemas cuadráticos. El método de Newton se puede combinar con la búsqueda lineal para obtener un tamaño de paso adecuado, y se puede demostrar matemáticamente que converge rápidamente.

Otros algoritmos eficientes para la minimización sin restricciones son el descenso de gradiente (un caso especial del descenso más pronunciado).

Problemas generales Los problemas más complejos son aquellos con restricciones de desigualdad. Una forma común de resolverlos es reducirlos a problemas sin restricciones añadiendo una función barrera, que impone las restricciones de desigualdad a la función objetivo. Estos métodos se denominan métodos de punto interior. Deben inicializarse encontrando un punto interior factible mediante los llamados métodos de fase I, que o bien encuentran un punto factible o bien demuestran que no existe ninguno. Los métodos de fase I generalmente consisten en reducir la búsqueda en cuestión a un problema de optimización convexa más simple.

Los problemas de optimización convexa también pueden resolverse mediante los siguientes métodos contemporáneos:

Métodos de agrupamiento (Wolfe, Lemaréchal, Kiwiel), Métodos de proyección de subgradiente (Polyak), Métodos de punto interior, que utilizan funciones de barrera autoconcordantes y funciones de barrera autorregulares. Métodos de planos de corte. Método elipsoidal. Método de subgradiente. Subgradientes duales y el método de deriva más penalización.

Los métodos de subgradiente se pueden implementar de forma sencilla y, por lo tanto, se utilizan ampliamente. Los métodos de subgradiente dual son métodos de subgradiente aplicados a un problema dual. El método de deriva más penalización es similar al método de subgradiente dual, pero toma un promedio temporal de las variables primales.

Multiplicadores de Lagrange Consideremos un problema de minimización convexa dado en forma estándar por una función objetivo y restricciones de desigualdad , para . Entonces el dominio es:

La función lagrangiana para el problema es

Para cada punto en que minimiza en , existen números reales denominados multiplicadores de Lagrange, que satisfacen simultáneamente estas condiciones:

minimiza el lagrangiano con respecto a con al menos uno positivo (complementariedad).

Si existe un punto "estrictamente factible", es decir, un punto que cumple:

entonces la afirmación anterior puede reforzarse para exigir que .

Recíprocamente, si existe en que satisface las condiciones (1), (2) y (3) para ciertos escalares , con , entonces minimiza sobre .

Software Existe un amplio ecosistema de software para la optimización convexa. Este ecosistema se divide en dos categorías principales: por un lado, los solucionadores y, por otro, las herramientas de modelado del problema (o interfaces).

Los solucionadores implementan los algoritmos de búsqueda de soluciones y suelen estar escritos en C. Requieren que los usuarios especifiquen los problemas de optimización en formatos muy específicos, que pueden no ser naturales desde una perspectiva de modelado. Las herramientas de modelado son programas independientes que permiten al usuario especificar un problema de optimización con una sintaxis de alto nivel. Gestionan todas las transformaciones desde y hacia el modelo de alto nivel del usuario y el formato de entrada/salida del solucionador.

A continuación se presentan dos tablas. La primera muestra herramientas de modelado (como CVXPY y JuMP.jl) y la segunda, solucionadores (como SCS y MOSEK). Estas tablas no son exhaustivas. + Programa Idioma Descripción ¿Software libre ? Ref. CVX MATLAB Interfaz compatible con los solucionadores SeDuMi y SDPT3; diseñada para expresar únicamente problemas de optimización convexa.! CVXPY Python! Convexo.jl Julia Programación convexa disciplinada, compatible con numerosos solucionadores.! CVXR R! GAMS Sistema de modelado para problemas de programación lineal, no lineal, lineal/no lineal de enteros mixtos y de cono de segundo orden.! GloptiPoly MATLAB, Octave Sistema de modelado para la optimización polinómica.! JuMP.jl Julia Admite numerosos solucionadores. También admite optimización entera y no lineal, así como cierta optimización no convexa.! ROME Sistema de modelado para optimización robusta. Admite optimización robusta distribucional y conjuntos de incertidumbre .! SOSTOOLS Sistema de modelado para optimización polinómica. Utiliza SDPT3 y SeDuMi. Requiere Symbolic Computation Toolbox.! SparsePOP Sistema de modelado para optimización polinómica. Utiliza los solucionadores SDPA o SeDuMi.! YALMIP MATLAB, Octave Se integra con los solucionadores CPLEX, GUROBI, MOSEK, SDPT3, SEDUMI, CSDP, SDPA y PENNON; también admite optimización entera y no lineal, así como cierta optimización no convexa. Permite realizar optimización robusta con incertidumbre en las restricciones LP/SOCP/SDP.!