Clase 06

Métodos de Penalización y de Barrera

Nuevo problema:

$$\begin{array}{rl} \min & f(x) \\ s.a: & g_i(x) \leq 0 \quad i\in \mathcal{I}\\ & h_j(x) = 0 \quad j\in\mathcal{E} \end{array}$$

Con $f,g,h\in C^1(\Omega)$. Consideraremos $\Omega$ al conjunto de puntos factibles, es decir: $$\Omega = \{x\in \mathbb{R}^n \colon g_i(x) \leq 0 \; \forall i\in \mathcal{I}, h_j(x) = 0\; \forall j\in\mathcal{E}\}$$

Método de Penalización

Motivación: minimizar $f$ sobre $\mathbb{R}^n$, aplicándole una penalización a los puntos que no están en $\Omega$

Si podemos conseguir una función $P:\mathbb{R}^n\rightarrow\mathbb{R}$ tal que:

  • $P$ es continua
  • $P(x)\geq0 \; \forall x\in\mathbb{R}^n$
  • $P(x) = 0 \Leftrightarrow x\in\Omega$

Entonces podemos minimizar $f(x)+cP(x)$ con $c\in\mathbb{R}$ utilizando técnicas de optimización irrestricta.

Función de penalización cuadrática

Si tenemos el siguiente problema: $$\begin{array}{rl} \min & f(x) \\ s.a: & g_i(x) \leq 0 \quad i\in \mathcal{I}\\ & h_j(x) = 0 \quad j\in\mathcal{E} \end{array}$$

Definimos la función de penalización cuadrática como: $$Q(x,c) = f(x) + c\sum_{j\in\mathcal{E}} h_j^2(x) + c\sum_{i\in\mathcal{I}}g^+_i(x)^2$$

Donde $c$ es el parámetro de penalización y $g_i^+ = \max\{0, g_i(x)\}$. Si hacemos $c\rightarrow\infty$, la violación de las restricciones será castigada con mayor severidad.

Idea: considerar una secuencia $\{c_k\}$ tal que $c_k\xrightarrow{k\rightarrow\infty}\infty$ y utilizar métodos de optimización irrestricta para encontrar el minimizador $x_k$ de $Q(x,c_k)$ para cada $k$.

Observación: si sólo tenemos restricciones dadas por igualdad, $Q(x,c)$ sigue siendo $C^1$ (pues $f, h_j$ lo son) y se pueden utilizar los métodos que habíamos visto para optimización irrestricta. En cambio, si hay restricciones dadas por desigualdad, $\nabla Q(x,\mu)$ podría no ser continua, por lo que los métodos podrían no comportarse de la forma esperada.

Lema: Sea $x_k$ mínimo de $Q(x,c_k)$, vale lo siguiente:

  • $Q(x_k, c_k) \leq Q(x_{k+1}, c_{k+1})$
  • $P(x_k) \geq P(x_k+1)$
  • $f(x_k) \leq f(x_{k+1})$

Teorema: sea $\{x_k\}_{k\in\mathbb{N}}$ la sucesión de puntos obtenidos con el método de penalidad, entonces cualquier punto límite de la misma es solución del problema $\underset{x\in\Omega}{min} f(x)$

Teorema: sean $g^+(x)=(g_1^+(x),\dots,g_{|I|}^+(x))^T$, $\{x_k\}_k$ la sucesión generada por el método de penalidad, se define $\lambda_k = c_kg^+(x_k)$. Si $x_k\rightarrow x^*$ con $x^*$ solución al problema y punto regular, luego $\lambda_k\rightarrow \lambda$ siendo $\lambda$ es vector con los multiplicadores de Lagrange del problema con restricciones.

Ejemplo: $$\begin{array}{rl}\min & f(x)= -(x-4)^2 + 4 \\ s.a: & x \leq 5 \qquad (\Rightarrow g_1(x) = x-5) \\ & x \geq 3 \qquad (\Rightarrow g_2(x) = 3-x) \\ \end{array}$$

$$\Rightarrow Q(x,c) = f(x) + cg_1^+(x) + cg_2^+(x)$$

Penalizacion.png

Implementación

Dadas $f, h_j, g_i,\; x_0\in \mathbb{R}^n,\; c_0\in\mathbb{R},\; \alpha\in\mathbb{R}_{>1},\; \varepsilon, k_{MAX}$
REPETIR Mientras $\lVert x^k - x^{k+1}\rVert > \varepsilon$ y $k<k_{MAX}$:
     Definir $Q(x,c_k)$
     $x^{k+1}=$ mínimo de $Q(x,c_{k})$ utilizando opt. irrestricta (punto inicial: $x_k$)
     Si $x^{k+1}\in\Omega$:
         PARAR
     Si no:
         $c_{k+1} = \alpha c_k$
         $k = k + 1$

Valores iniciales estándar podrían ser: $c=1.5,\; \varepsilon=10^{-3},\; \alpha=2$. Una buena idea es tomar $x_0\in\Omega^c$.

Observaciones

Chequear si $x^{k+1}\in\Omega$ significa chequear si es cierto que $g_i(x^{k+1}) \leq 0 \;\forall i$ y si $h_j(x^{k+1}) = 0 \;\forall j$.
Computacionalmente, hay que tener cuidado cuando uno compara la igualdad de floats, y esto es importante al momento de chequear si $h_j(x) = 0$. En vez de escribir h(x) == 0 utilizamos la función np.isclose de numpy y escribimos np.isclose(h(x), 0). La función np.isclose devuelve True si los float están cerca y False en caso contrario. Veamos cómo funciona:

In [1]:
import numpy as np

print(0.1 + 0.1 + 0.1)
print(0.1 + 0.1 + 0.1 == 0.3)
print(np.isclose(0.1 + 0.1 + 0.1, 0.3))

0.30000000000000004
False
True

Aumentar $c_k$ demasiado rápido puede traer como consecuencia inestabilidad numérica y divergencia de los métodos de optimización, por eso no comenzamos con un c muy grande, sino que comenzamos con uno pequeño y lo aumentamos gradualmente.

Se pueden aplicar modificaciones al Método de Penalidad presentado: por ejemplo, ajustar el crecimiento de $c_k$ acorde a cuán caro fue encontrar el óptimo de $Q(x,c_k)$: si fue fácil, aumentamos mucho el parámetro de penalidad (x10); de lo contrario, lo aumentamos más moderadamente (x1.5)

Método de Barrera

Motivación: acercarnos a los puntos de la frontera de $\Omega$ desde su interior.

Aplicables a problemas con restricciones dadas por desigualdades, ya que, en particular, es necesario que $\Omega^o \neq \emptyset$. En general, es necesario poder aproximarse a cualquier punto de $\partial\Omega$ desde $\Omega^o$.

Si conseguimos una función $B$ tal que:

  • $B$ es continua
  • $B(x)\geq 0$
  • $B(x)\rightarrow \infty$ cuando $x$ se acerca a $\partial\Omega$

Entonces podemos resolver el problema $\underset{x\in\Omega^o}{\min}\; f(x)+\mu B(x)$ con herramientas de optimización irrestricta, tomando como punto inicial $x_0\in\Omega^o$. A medida que $\mu\rightarrow 0$, permitiremos que se consideren puntos más cercanos a $\partial\Omega$

Las funciones de Barrera más comunes son $B(x)=\displaystyle\sum_i -\dfrac{1}{g_i(x)}$ y $B(x)=\displaystyle\sum_i log(-g_i(x))$. De esta manera, el problema se convierte en minimizar la siguiente función: $$R(x,\mu) = f(x) + \mu B(x)$$

Se pueden probar resultados análogos a los del Método de Penalización, en particular:

Teorema: cualquier punto límite de una sucesión $\{x_k\}_k$ generada con el Método de Barrera es solución del problema con restricciones dadas por desigualdades.

Ejemplo: $$\begin{array}{rl}\min & f(x)= -(x-4)^2 + 4 \\ s.a: & x \leq 5 \qquad (\Rightarrow g_1(x) = x-5) \\ & x \geq 3 \qquad (\Rightarrow g_2(x) = 3-x) \\ \end{array}$$

$$\Rightarrow R(x,\mu) = f(x) - \mu\frac{1}{g_1(x)} - \mu\frac{1}{g_2(x)}$$

Barrera.png

Implementación

Análoga a la del Método de Penalidad

Dadas $f, g_i,\; x_0\in \Omega^o,\; \mu_0\in\mathbb{R},\; \alpha\in\mathbb{R}_{<1},\; \varepsilon, k_{MAX}$
REPETIR Mientras $\lVert x^k - x^{k+1}\rVert > \varepsilon$ y $k<k_{MAX}$:
     Definir $R(x,\mu_k)$
     $x^{k+1}=$ mínimo de $R(x,\mu_{k})$ utilizando opt. irrestricta (punto inicial: $x_k$)
     $\mu_{k+1} = \alpha \mu_k$
     $k = k + 1$

Valores iniciales estándar podrían ser: $\mu=1,\; \varepsilon=10^{-3},\; \alpha=0.5$. Se debe tomar $x_0\in\Omega^o$.

Ejercicios

  1. Implementar las funciones metodo_penalidad y metodo_barrera. Como input deben tomar: f la función a minimizar, x0 el punto inicial, G una tupla con funciones que definen las restricciones por desigualdad, H una tupla con las restricciones de igualdad (sólo para Método de Penalidad), alpha el factor de cambio de los paramétros de penalidad/barrera, $\varepsilon$ la tolerancia y k_max el número máximo de iteraciones. Sugerencia: utilizar Método del Gradiente para efectuar la optimización irrestricta y usar lambdapara definir $Q$ o $R$ en cada iteración.

  2. El siguiente problema busca hallar el punto de una esfera más cercano a un plano: $$\begin{array}{rl} \min & f(x) = \frac{1}{10}(x_2+x_3-3)^2 \\ \text{s.a:} & x_1^2 + x_2^2 + x_3^2 \leq 1 \end{array}$$ Utilizar el Método de Barrera y el Método de Penalidad que resuelvan este problema. Solución: $\left(0, \frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}\right)$

  3. Resolver el siguiente problema utilizando el Método de Penalidad: $$\begin{array}{rl} \min & f(x) = x_1 + x_2 \\ \text{s.a:} & x_1^2 + x_2^2 = 2 \\ & x_1 \geq 0 \end{array}$$ Solución: $\left(0, -\sqrt{2}\right)$