Pensemos primero en un problema con restricciones dadas por desigualdades: $$\begin{array}{rl} \min & f(x) \\ \text{s.a:} & g(x)\leq 0 \end{array}$$ Donde $g(x) = (g_1(x),\dots, g_m(x))$ y $g(x)\leq 0$ significa $g_j(x)\leq 0\;\forall j=1,\dots,m$
Las condiciones necesarias para este problema son:
$$\begin{array}{rl} \nabla f(x) + \mu ^T \nabla g(x) & =0 \\ g(x) &\leq 0 \\ \mu ^T g(x) & = 0 \\ \mu &\geq 0 \end{array}$$Esas condiciones se pueden expresar en términos del conjunto de condiciones activas. Definimos $W$ el conjunto de condiciones activas como $W_x=\{j\colon g_j(x)=0\}$. Las condiciones quedan escritas como:
$$\begin{array}{rl} \nabla f(x) + \displaystyle\sum_{j \in W}\mu_j \nabla g_j(x) & =0 \\ g_j(x) &= 0 \quad j\in W\\ g_j(x) &< 0 \quad j\not\in W \\ \mu_j & \geq 0 \quad j\in W\\ \mu_j &= 0 \quad j\not\in W \end{array}$$Las primeras dos condiciones son idénticas a las necesarias para el problema con restricciones dadas por igualdad. La tercera condición garantiza que las restricciones inactivas se satisfacen. Las últimas dos condiciones, que involucrana los multiplicadores de Lagrange, garantizan que toda restricción activa debería estar activa.
En estas ideas se basan los métodos de conjuntos activos, los cuales constan, de manera muy general, de dos pasos:
Gradiente Proyectado es un método de conjuntos activos.
Aplicaremos el método de Gradiente Proyectado a problemas de optimización con restricciones lineales :
$$\begin{array}{rl} \min & f(x) \\ \text{s.a:} & a_j^Tx \leq b_j \qquad i\in J_1 \\ & a_j^Tx = b_j \qquad j\in J_2 \end{array}$$La idea de este método está motivada por el Método del Gradiente para problemas sin restricciones.
Comenzamos tomando un punto inicial factible $x_0$. Para encontrarlo, puede llevarse a cabo la Fase I (que vimos en Investigación Operativa!) o elegirlo manualmente.
En nuestro punto inicial $x_0$ tendremos un conjunto de $q$ condiciones activas que satisfacen $a_i^Tx = b_i$ y algunas restricciones inactivas $a_i^Tx < b_i$. Comenzamos tomando $W=\{j\colon a_j^T x = b_j\}$ y consideramos la matriz $A_w$ que tiene como filas a las $a_j$ tales que $j\in W$.
$A_w$ es de $q\times n$ de rango $q<n$.
Ahora buscamos $d$ una dirección de descenso, i.e., que satisfaga $\nabla f(x_0)d<0$. Pero además queremos que $a_j^Td=0 \;\forall j\in W$ para que las restricciones activas sigan siéndolo
$\Rightarrow$ quiero que $ d\in <a_j>_{j\in W}^\perp$
Sean $M=<a_j>_{j\in W}^\perp$ y $N=<a_j>_{j\in W}$, cualquier vector se puede escribir como suma de vectores de esos espacios complementarios. En particular: $$-\nabla f(x_0) = d + A_w^T\mu \quad d\in M,\; \mu\in\mathbb{R}^q$$
Podemos despejar $\mu$ a partir del requerimiento de que $A_wd=0$: $$0 = A_wd=-A_w\nabla f(x_0)-(A_wA_w^T)\mu\;\Rightarrow\; \mu = -(A_wA_w^T)^{-1}A_w\nabla f(x_0)$$
Volviendo a la igualdad anterior: $$\begin{array}{}-\nabla f(x_0) = d + A_w^T\mu \\ \Rightarrow d = -\nabla f(x_0) -A_w^T(-(A_wA_w^T)^{-1}A_w\nabla f(x_0)) \\ \Rightarrow d = -(I-A_w^T(A_wA_w^T)^{-1}A_w)\nabla f(x_0) \end{array}$$
Llamaremos $P=I-A_w^T(A_wA_w^T)^{-1}A_w$ el proyector sobre $<a_j>_{j\in W}^\perp$. Es sencillo ver que si $d\neq 0$ entonces es dirección de desenso. Dado que $\nabla f(x_0)+d$ es ortogonal a $d$: $$\nabla f(x_0)^T d = (\nabla f(x_0)^T + d^T - d^T)d=-\lVert d\rVert ^2$$
Entonces, si $d\neq 0$, ya tenemos la dirección de descenso. Lo siguiente sería buscar la longitud del paso:
1)Busco $t_1=\max\{t\colon x_0+td\in\Omega\}$
2)Busco $t_2=\min\{f(x+td)\colon 0\leq t\leq t_1\}$
Veamos qué ocurre si $d=0$:
$$0=d=\nabla f(x_0)+A_w^T\mu = \nabla f(x_0)+\displaystyle\sum_{j\in W} \mu_j\nabla g_j(x_0) \quad \text{pues }a_j^T=\nabla g_j(x_0)$$Entonces, $\mu$ es el vector con los multiplicadores de Lagrange. Si $\mu\geq 0$, listo, hallamos un óptimo. Si no, sacamos de $W$ el $j$ tal que $\mu_j$ es el más negativo y volvemos a comenzar.
¿Qué podríamos hacer si querríamos usar gradiente proyectado pero no todas las restricciones son lineales?
Combinación de Método de Barrera y Método de Gradiente Proyectado: podemos incluir a las restricciones no lineales en la función de penalidad y usar gradiente proyectado para optimizar $Q(x,c)$
Implementación de Gradiente Proyectado para problemas con restricciones lineales
Dados: $f,\; A,\; b,\;x_0 \text{ punto inicial factible},\; \varepsilon,\; k_{MAX}$
$calcular\_w = True$
REPETIR Mientras $\lVert x_{k+1} - x_k\rVert > \varepsilon$ y $k < k_{MAX}$:
Si $calcular\_w$:
Definir $W$ (usando $A$)
Calcular $A_w$ y $P$
Calcular $d_k=-P\nabla f(x_0)$
Si $d_k\neq 0$:
Hallar $t_1 = \max\{t\colon x_k+td_k\in\Omega\}$
Hallar $t_2 = \min\{f(x_k+td_k)\colon 0\leq t\leq t_1\}$ (usar Armijo, Sección Áurea, etc.)
$x_{k+1} = x_k + t_2d_k$
$k = k+1$
$calcular\_w = True$
Si no:
Calcular $\mu = -(A_wA_w^T)^{-1}A_w\nabla f(x_0)$
Si $\mu \geq 0$:
PARAR
Si no:
Sacar $j$ de $W$, con $j$ tal que $\mu_j = \min \mu$
$k = k+1$
$calcular\_w = False$