Optimizacion convexa

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

Definición

Forma abstracta

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

• El función objetiva, que es una función convexa real de n variables, f:D⊆ ⊆ Rn→ → R{displaystyle f:{mathcal Subseteq mathbb {R};
• El factible, que es un subconjunto convexo C⊆ ⊆ Rn{displaystyle Csubseteq mathbb {R} {fn}.

El objetivo del problema es encontrar algunos xAlternativa Alternativa ▪ ▪ C{displaystyle mathbf {x^{ast}in C} alcanzando

inf{}f()x):x▪ ▪ C}{displaystyle inf {x}mathbf {x}.

En general, existen tres opciones respecto a la existencia de una solución:

• Si tal punto x* existe, se conoce como un punto óptimo o solución; el conjunto de todos los puntos óptimos se llama el set óptimo; y el problema se llama solvable.
• Si f{displaystyle f} está sin límites por debajo C{displaystyle C}, o el infimum no se alcanza, entonces se dice que el problema de optimización sin límites.
• Si no, C{displaystyle C} es el conjunto vacío, entonces se dice que el problema infeasible.

Forma estándar

Un problema de optimización convexa está en forma estándar si se escribe como

minimizarxf()x)subject togi()x)≤ ≤ 0,i=1,... ... ,mhi()x)=0,i=1,... ... ,p,{displaystyle {begin{aligned} âunderset {mathbf {x} {fnMimize} {fnMitbf {x}fnMitbf {x}\fnMittsm\\\\\fnMitbf {x}fnMitbf {fnMitsm\\\\\fnMinMinMicrosoft} {cH00f}fnMinMit}fnMicrosoft,f}fnMicrosoft,fnMicrosoft,fnMinMicrosoft,f}fnMicrosoft,fnMinMicrosoft,fnMinMinMicrosoft,fnMinMinMinMinMinMinMinMinMinMicrosoft,fnMicrosoft,fnMicrosoft,f}f}fnMinMinMinMinMinMinMicrosoft,fnMinMicrosoft,f}f}fnMin

donde:

• x▪ ▪ Rn{displaystyle mathbf {x} in mathbb {R} {fn} es el vector de variables de optimización;
• Función objetiva f:D⊆ ⊆ Rn→ → R{displaystyle f:{mathcal Subseteq mathbb {R} es una función convexa;
• Funciones restrictivas de la desigualdad gi:Rn→ → R{displaystyle "Mathbb" {R} ^{n}to mathbb {R}, i=1,... ... ,m{displaystyle i=1,ldotsm}, son funciones convexas;
• Funciones restrictivas de la igualdad hi:Rn→ → R{displaystyle "Mathbb" {R} ^{n}to mathbb {R}, i=1,... ... ,p{displaystyle i=1,ldotsp}, son transformaciones afines, es decir, de la forma: hi()x)=ai⋅ ⋅ x− − bi{fnMicrosoft Sans Serif} cdot mathbf {x} - ¿Qué?, donde ai{displaystyle mathbf {a_{i} es un vector y bi{displaystyle B_{i} es un cuero cabelludo.

El conjunto viable C{displaystyle C} del problema de optimización consiste en todos los puntos x▪ ▪ D{displaystyle mathbf {x} {mathcal {}}} satisfaciendo la desigualdad y las limitaciones de igualdad. Este set es convexo porque D{displaystyle {fnMithcal}} es convex, los conjuntos de subnivel de funciones convex son convex, los conjuntos de affine son convex, y la intersección de conjuntos convex es convex.

Muchos problemas de optimización se pueden formular equivalentemente en esta forma estándar. Por ejemplo, el problema de maximizar una función concave f{displaystyle f} puede ser re-formulado equivalentemente como el problema de minimizar la función convex − − f{displaystyle - f). El problema de maximizar una función de concave sobre un conjunto convexo se llama comúnmente un problema de optimización convexa.

Forma de epígrafe (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 programa con un objetivo general se puede transformar en un programa con un objetivo lineal agregando una sola variable t y una sola restricción, de la siguiente manera:

minimizarx,ttsubject tof()x)− − t≤ ≤ 0gi()x)≤ ≤ 0,i=1,... ... ,mhi()x)=0,i=1,... ... ,p,{fnMinisterio {fnMinisterio}} {fnMinisterio {fnMinisterio}}} {\fnMimize}} {fnMinisterio {fnMinisterio {fnMinisterio}} {fnMinisterio {fnMinMincipio}f}fnMinMinMinMinMinMinMinMinMinunciof}fnMinMinMinMinMinMinMinMinMinMinunciof}f}fnMinMinMinMinMinMinMinMinunciof}f}f}fnMinMinMinMinMinunciofnMinunció*

Forma cónica

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

minimizarxcTxsubject tox▪ ▪ ()b+L)∩ ∩ K{displaystyle {begin{aligned} âunderset {mathbf {x} {fnMimize}} {fnMimize}}} {T}x\\\fnMicrosoft Sans Serif} {subject to} > {fnMicrosoft Sans Serif}}

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

Eliminar restricciones de igualdad lineal

Es posible convertir un programa convexo en forma estándar en un programa convexo sin restricciones de igualdad. Denota las restricciones de igualdad h_i(x)=0 como Ax=b , donde A tiene n columnas. Si Ax=b no es factible, entonces, por supuesto, el problema original no es factible. De lo contrario, tiene alguna solución x₀ y el conjunto de todas las soluciones se puede presentar como: Fz+x ₀, donde z está en R^k, k=n -rank(A) y F es una matriz n-por-k. Sustituyendo x = Fz+x₀ en el problema original se obtiene:

minimizarxf()Fz+x0)subject togi()Fz+x0)≤ ≤ 0,i=1,... ... ,m{begin{aligned} {mathbf {x} {m} {m}} {mf}} {m}} {mcH}}}mf {m}mf}f}f}f}f}f}f}f}f}f}f}f} +mathbf {x} ¿Por qué?

donde las variables son z. Tenga en cuenta que hay rango(A) menos variables. Esto significa que, en principio, se puede restringir la atención a problemas de optimización convexos sin restricciones de igualdad. En la práctica, sin embargo, a menudo se prefiere conservar las restricciones de igualdad, ya que podrían hacer que algunos algoritmos sean más eficientes y también hacer que el problema sea más fácil de entender y analizar.

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:

• Los problemas de programación lineal son los programas convexos más simples. En LP, las funciones objetivas y restrictivas son lineales.
• La programación cuadrática es la más próxima. En QP, las limitaciones son lineales, pero el objetivo puede ser una función cuadrática convexa.
• La programación de cono de segundo orden es más general.
• La programación semidefinita es más general.
• La optimización conica es aún más general - ver la figura a la derecha,

Otros casos especiales incluyen;

• Menos cuadrados
• Minimización cuadrática con limitaciones cuadráticas convexas
• Programación geométrica
• Maximización de la entropía con limitaciones apropiadas.

Propiedades

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

• todo mínimo local es un mínimo mundial;
• el ajuste óptimo es convexo;
• si la función objetiva es estrictamente estricta convex, entonces el problema tiene al máximo un punto óptimo.

Estos resultados son utilizados por la teoría de la 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 de separación y el teorema de Farkas. lema.

Algoritmos

Problemas sin restricciones y con restricciones de igualdad

Los programas convexos más fáciles de resolver son los problemas sin restricciones o los problemas que sólo tienen restricciones de igualdad. Como todas las restricciones de igualdad son lineales, pueden eliminarse con álgebra lineal e integrarse en el objetivo, convirtiendo así un problema de igualdad restringida 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 el objetivo es cuadrático. Para estos problemas, las condiciones KKT (que son necesarias para la optimización) son todas lineales, por lo que pueden resolverse analíticamente.

Para problemas sin restricciones (o con restricciones de igualdad) con un objetivo convexo general que es dos veces diferenciable, se puede utilizar el método de Newton. Puede verse 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 de un tamaño de paso apropiado 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 de descenso más pronunciado).

Problemas generales

Los problemas más difíciles son los que tienen limitaciones de desigualdad. Una manera común de resolverlos es reducirlos a problemas sin restricciones añadiendo una función de barrera, haciendo cumplir las limitaciones de desigualdad, a la función objetiva. Tales métodos se denominan métodos de puntos interiores. Tienen que ser inicializados mediante la búsqueda de un punto interior viable utilizando los llamados fase I métodos, que encuentran un punto factible o muestran que no existen. Los métodos de fase I consisten generalmente 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 se pueden resolver mediante los siguientes métodos contemporáneos:

• Métodos de unión (Wolfe, Lemaréchal, Kiwiel) y
• Métodos de proyección (Polyak),
• Métodos de interior, que hacen uso de funciones de barrera autoconcordantes y funciones de barrera autoregular.
• Métodos de planificación de corte
• Método Ellipsoide
• Método de subgrado
• Dual subgradients and the drift-plus-penalty method

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 primarias.

Multiplicadores de Lagrange

Considere un problema de minimización convexa dado en forma estándar por una función de coste f()x){displaystyle f(x)} y limitaciones de la desigualdad gi()x)≤ ≤ 0{displaystyle g_{i}(x)leq 0} para 1≤ ≤ i≤ ≤ m{displaystyle 1leq ileq m}. Entonces el dominio X{displaystyle {fnMitcal}} es:

X={}x▪ ▪ XSilenciog1()x),... ... ,gm()x)≤ ≤ 0}.{displaystyle {Mathcal {X}=left{xin Xvert g_{1}(x),ldotsg_{m}(x)leq 0right}

La función lagrangiana para el problema es

L()x,λ λ 0,λ λ 1,... ... ,λ λ m)=λ λ 0f()x)+λ λ 1g1()x)+⋯ ⋯ +λ λ mgm()x).{displaystyle L(x,lambda _{0},lambda _{1},ldotslambda _{m})=lambda _{0}f(x)+lambda _{1}g_{1}(x)+cdots +lambda _{m}g_{m}(x). }

Para cada punto x{displaystyle x} dentro X{displaystyle X} que minimiza f{displaystyle f} sobre X{displaystyle X}, hay números reales λ λ 0,λ λ 1,... ... ,λ λ m,{displaystyle lambda _{0},lambda _{1},ldotslambda _{m} llamados multiplicadores Lagrange, que satisfacen estas condiciones simultáneamente:

1. x{displaystyle x} minimizar L()Sí.,λ λ 0,λ λ 1,... ... ,λ λ m){displaystyle L(y,lambda _{0},lambda _{1},ldotslambda - Sí. por todas partes Sí.▪ ▪ X,{displaystyle yin X,}
2. λ λ 0,λ λ 1,... ... ,λ λ m≥ ≥ 0,{displaystyle lambda _{0},lambda _{1},ldotslambda ¿Qué? con al menos uno 0,}" xmlns="http://www.w3.org/1998/Math/MathML">λ λ k■0,{displaystyle lambda _{k} título0,}0,}" aria-hidden="true" class="mwe-math-fallback-image-inline mw-invert" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5d2415e1d4e77a55ce34d475258fa89acde11f03" style="vertical-align: -0.671ex; width:7.352ex; height:2.509ex;"/>
3. λ λ 1g1()x)=⋯ ⋯ =λ λ mgm()x)=0{displaystyle lambda ¿Por qué? (esclavitud completa).

Si existe un "punto estrictamente factible", es decir, un punto z{displaystyle z} satisfacción

<math alttext="{displaystyle g_{1}(z),ldotsg_{m}(z)g1()z),... ... ,gm()z)c)0,{displaystyle g_{1}(z),ldotsg_{m}(z) obtenidos0,}<img alt="{displaystyle g_{1}(z),ldotsg_{m}(z)

entonces la declaración anterior puede fortalecerse para exigir que λ λ 0=1{displaystyle lambda ¿Qué?.

Por el contrario, si algunos x{displaystyle x} dentro X{displaystyle X} satisfies (1)–(3) para escalares λ λ 0,... ... ,λ λ m{displaystyle lambda _{0},ldotslambda ¿Qué? con λ λ 0=1{displaystyle lambda ¿Qué? entonces x{displaystyle x} es seguro minimizar f{displaystyle f} sobre X{displaystyle X}.

Software

Hay un gran ecosistema de software para la optimización convexa. Este ecosistema tiene dos categorías principales: Solvers en una mano y herramientas de modelado (o interfacesPor otro lado.

Los Solvers implementan los algoritmos mismos y generalmente están escritos en C. Requieren que los usuarios especifiquen problemas de optimización en formatos muy específicos que pueden no ser naturales desde una perspectiva de modelado. Las herramientas de modelado son piezas separadas de software que permiten al usuario especificar una optimización en la sintaxis de nivel superior. Gestionan todas las transformaciones desde y hacia el modelo de alto nivel del usuario y el formato de entrada/salida del solucionador.

La tabla siguiente muestra una mezcla de herramientas de modelado (como CVXPY y Convex.jl) y solvers (como CVXOPT y MOSEK). Esta tabla no es exhaustiva.

Aplicaciones

La optimización convexa se puede utilizar para modelar problemas en una amplia gama de disciplinas, como sistemas de control automático, estimación y procesamiento de señales, comunicaciones y redes, diseño de circuitos electrónicos, análisis y modelado de datos, finanzas, estadística (diseño experimental óptimo) y optimización estructural, donde el concepto de aproximación ha demostrado ser eficiente. La optimización convexa se puede utilizar para modelar problemas en los siguientes campos:

• Optimización de cartera.
• Análisis de riesgo peor.
• Publicidad óptima.
• Variaciones de regresión estadística (incluida la regularización y regresión cuantitativa).
• Ajuste modelo (principalmente clasificación multiclase).
• Optimización de generación de electricidad.
• Optimización combinada.
• Modelo no probabilístico de incertidumbre.
• Localización mediante señales inalámbricas

Extensiones

Las extensiones de la optimización convexa incluyen la optimización de funciones biconvexas, pseudoconvexas y cuasiconvexas. Las extensiones de la teoría del análisis convexo y los métodos iterativos para resolver aproximadamente problemas de minimización no convexos ocurren en el campo de la convexidad generalizada, también conocido como análisis convexo abstracto.