Karush-Kuhn-Tucker en una dimensión infinita

Question

¿Se aplica el teorema de Karush-Kuhn-Tucker sobre las suficientes condiciones para la optimización de un programa convexo en una dimensión contable?

Para precisiones, véase la definición 4.1.1 y el teorema 4.1.4 de este curso . ¿Se extiende el teorema a un número infinito (pero discreto) de variables y restricciones asociadas? Si es así, ¿tiene una referencia?

Answer 1

Sí, Bachir, Fabre y Tapia-García extender el teorema de Karush-Kuhn-Tucker bajo hipótesis suaves, para un número infinito de variables.

Doy a continuación una versión más débil de la generalización de Karush-Kuh-Tucker en una dimensión infinita:

Deje que $X \subset\mathbb {R}^{ \mathbb {N}}$ ser un subconjunto convexo no vacío de $ \mathbb {R}^{ \mathbb {N}}$ y dejar $x^{*} \in Int \left (X \right )$ . Deje que $f,g_{1},g_{2},...,g_{m}:X \rightarrow\mathbb {R}$ ser funciones convexas continua en $x^{*}$ y diferenciable de un período a otro en $x^{*}$ es decir. de tal manera que las funciones $f_{n,x^{*}} \left (x_{n} \right ):=f \left ((x_1^{*},...,x_{n-1}^*,x_n,x_{n+1}^*,...) \right )$ y $g_{j,n,x^{*}} \left (x_{n} \right ):=g_{j} \left ((x_1^{*},...,x_{n-1}^*,x_n,x_{n+1}^*,...) \right )$ son diferenciable en $x_{n}$ para todos $n \in\mathbb {N}$ y $j \in\left\ { 1,2,...,m \right\ }$ .

(Condición de calificación) Supongamos que para todos $k \in\mathbb {N}^{*}$ y para todos $x \in X$ , $$x^{*}+P^{k} \left (x-x^{*} \right )= \left (x_{1},...,x_{k},x_{k+1}^{*},x_{k+2}^{*},... \right ) \in X$$ Si existe $ \left ( \lambda_ {j}^{*} \right )_{j} \in\left ( \mathbb {R}_{+} \right )^{ \mathbb {N}}$ de tal manera que

$$ \lambda_ {j}^{*}g_{j} \left (x^{*} \right ) =0,\: \forall j \in\left\ { 1,2,...,m \right\ } \quad \quad \quad \quad \quad (1)$$ $$f_{n,x^{*}}^{ \prime } \left (x_{n}^{*} \right )+ \sum_ {j=1}^{m} \lambda_ {j}^{*}g_{j,n,x^{*}}^{ \prime } \left (x_{n}^{*} \right )=0,\: \forall n \in\mathbb {N} \quad \quad (2)$$

Entonces $x^{*}$ es una solución óptima en $ \Gamma := \left\ { \left (x_{i} \right )_{i} \in X\,:\,g_{1} \left (x \right ) \leq0 ,...,g_{m} \left (x \right ) \leq0\right\ } :$

$$f \left (x^{*} \right )= \underset {x \in\Gamma }{ \inf }f \left (x \right )$$

Además, si $x^{*}$ es una solución óptima en $ \Gamma $ y si la condición de Slater $Int \left ( \Gamma\right ) \neq\emptyset $ es verificado, entonces existe una única $ \left ( \lambda_ {j}^{*} \right )_{j} \in\left ( \mathbb {R}_{+} \right )^{ \mathbb {N}}$ que verifican las condiciones (Karush-Kuhn-Tucker) (1) y (2).

El número de restricciones tiene que ser finito, pero las restricciones simples, como las restricciones de no negatividad, pueden ser sustituidas por una restricción equivalente en el dominio de las variables. Por ejemplo, en lugar de las restricciones $ \forall n \in \mathbb {N},\;x_n \geq 0$ en el dominio $ \mathbb {R}^{ \mathbb {N}}$ uno puede tomar $X=( \mathbb {R}_+)^{ \mathbb {N}}$ y el teorema se aplica.

Nótese que el resultado (de la suficiencia) es fácil de probar cuando se asume además que el Lagrangiano convexo $ \mathcal L(x, \lambda )=f(x)+ \sum_ {j=1}^m \lambda_j g_j(x)$ es diferenciable de Gateaux, con un derivado de Gateaux igual a 0 en $u=(x^*, \lambda ^*)$ .

De hecho, una función $h: V \rightarrow \mathbb {R} $ convexo y Gateaux diferenciables en $V$ verifica $h(v)-h(u) \geq h^ \prime (u; v-u), \forall u,v \in V$ donde $h^ \prime (u; v)$ es el derivado direccional de $h$ en $u$ en la dirección $v$ . (Se puede ver eso en la definición de convexidad: $h(u)+ \theta \left ( h(v) -h(u) \right ) \geq h \left (u+ \theta (v-u) \right )$ ; restándole $h(u)$ dividiendo por $ \theta $ y tomando el límite cuando $ \theta \rightarrow 0^+$ ; ver este para más detalles). Aplicando esa desigualdad al Lagrangiano en $u$ prueba que el Lagrangiano admite un mínimo de $u$ que resuelve el programa de minimización: $ f(x^*) =L(x^*, \lambda ^*) \leq f(x)+ \sum_ {j=1}^m \lambda_j g_j(x) \leq f(x), \; \forall x \in \Gamma $ .

Sin embargo, en general, no es fácil probar que el derivado de Gateaux de una serie convexa (como un Lagragiano infinito) (existe y) es igual a 0 en algún momento $u$ a menos que se utilice el resultado (Propuesta 3 en Bachir, Fabre y Tapia-García ) que el derivado de Gateaux es, por lo tanto, igual a la suma de los derivados de cada término de la serie.