Principios Fundamentales de Optimización Restringida: Teoremas de Lagrange y Kuhn-Tucker

Definiciones de Extremos Relativos Condicionados

Sea $\mathbf{a}$ un punto de la región factible ($\mathbf{a} \in S$). En este punto $\mathbf{a}$:

• $f$ tiene un máximo relativo condicionado por $\phi(\mathbf{x}) = 0$ si existe un entorno $U$ de $\mathbf{a}$ tal que $f(\mathbf{a}) \ge f(\mathbf{x})$, $\forall \mathbf{x} \in U \cap S$.
• $f$ tiene un máximo relativo estricto condicionado por $\phi(\mathbf{x}) = 0$ si existe un entorno reducido $U^*$ de $\mathbf{a}$ tal que $f(\mathbf{a}) > f(\mathbf{x})$, $\forall \mathbf{x} \in U^* \cap S$.
• $f$ tiene un mínimo relativo condicionado por $\phi(\mathbf{x}) = 0$ si existe un entorno $U$ de $\mathbf{a}$ tal que $f(\mathbf{a}) \le f(\mathbf{x})$, $\forall \mathbf{x} \in U \cap S$.
• $f$ tiene un mínimo relativo estricto condicionado por $\phi(\mathbf{x}) = 0$ si existe un entorno reducido $U^*$ de $\mathbf{a}$ tal que $f(\mathbf{a}) < f(\mathbf{x})$, $\forall \mathbf{x} \in U^* \cap S$.

Función Lagrangiana

Sean $f : C \to \mathbb{R}$ y $\phi : C \to \mathbb{R}^q$ dos funciones definidas en un subconjunto abierto $C \subseteq \mathbb{R}^n$ ($q < n$).

Se llama función lagrangiana asociada al problema $(\ast)$ a la función:

$$L (\mathbf{x}; \lambda_1, \ldots, \lambda_q) = f (\mathbf{x}) - \lambda_1\phi_1(\mathbf{x}) - \cdots - \lambda_q\phi_q(\mathbf{x})$$

donde $\phi_1, \ldots, \phi_q$ son las componentes de $\phi$, y $\lambda_1, \ldots, \lambda_q \in \mathbb{R}$ son los llamados multiplicadores de Lagrange.

Teorema (Condición Necesaria de Lagrange)

Sean $f : C \to \mathbb{R}$ y $\phi : C \to \mathbb{R}^q$ dos funciones de clase $C^1$ en un abierto $C \subseteq \mathbb{R}^n$ ($q < n$).

Si $\mathbf{a} \in C$ es un extremo relativo de $f$ condicionado por $\phi(\mathbf{x}) = 0$, y se cumple $\text{rango}(d\phi(\mathbf{a})) = q$, entonces existen multiplicadores de Lagrange $\lambda_1, \ldots, \lambda_q \in \mathbb{R}$ tales que la diferencial de la función lagrangiana $L$ en $(\mathbf{a}; \mathbf{\lambda})$ es $0$.

Es decir:

$$\frac{\partial f}{\partial x_i}(\mathbf{a}) - \lambda_1 \frac{\partial \phi_1}{\partial x_i}(\mathbf{a}) - \cdots - \lambda_q \frac{\partial \phi_q}{\partial x_i} (\mathbf{a}) = 0, \quad i = 1, \ldots, n.$$

La hipótesis $\text{rango}(d\phi(\mathbf{a})) = q$ es la llamada condición de regularidad. Si una solución del problema no la cumple, no tiene por qué verificar la condición necesaria de Lagrange.

Condición Suficiente de Extremo Local Condicionado

Si no nos encontramos en conjuntos factibles compactos, podemos intentar aplicar esta condición.

Sean $f : C \to \mathbb{R}$ y $\phi : C \to \mathbb{R}^q$ funciones de clase $C^2$ en $C \subseteq \mathbb{R}^n$ abierto ($q < n$). Sea $\mathbf{a} \in C$ con $\phi(\mathbf{a}) = 0$ y $\text{rango}(d\phi(\mathbf{a})) = q$.

Si existen multiplicadores de Lagrange $\lambda_1, \ldots, \lambda_q \in \mathbb{R}$ tales que $dL(\mathbf{a}; \mathbf{\lambda}) = 0$, y $Q_0 = [d^2L_{\mathbf{x}} (\mathbf{a}; \mathbf{\lambda})]|_V$ es la forma cuadrática definida al restringir $d^2L_{\mathbf{x}} (\mathbf{a}; \mathbf{\lambda})$ (con respecto a las variables $x_1, \ldots, x_n$) a $V = \{\mathbf{x} \in \mathbb{R}^n : d\phi(\mathbf{a})(\mathbf{x}) = 0\} = \text{ker}(d\phi(\mathbf{a}))$:

• Si $Q_0$ es definida positiva, entonces $\mathbf{a}$ es un mínimo relativo de $f$ condicionado por $\phi(\mathbf{x}) = 0$.
• Si $Q_0$ es definida negativa, entonces $\mathbf{a}$ es un máximo relativo de $f$ condicionado por $\phi(\mathbf{x}) = 0$.
• Si $Q_0$ es indefinida, entonces $\mathbf{a}$ no es un extremo relativo de $f$ condicionado por $\phi(\mathbf{x}) = 0$.

El Método de Kuhn-Tucker

Sea $f : C \to \mathbb{R}$, $C \subseteq \mathbb{R}^n$ abierto. Sea $\phi : C \to \mathbb{R}^q$, y sea $S$ el conjunto de los puntos de $C$ que cumplen las restricciones de desigualdad:

$$S = \{\mathbf{x} \in C : \phi(\mathbf{x}) \le 0\} = \{\mathbf{x} \in C : \phi_1(\mathbf{x}) \le 0, \ldots, \phi_q(\mathbf{x}) \le 0\}$$

donde $\phi_1, \ldots, \phi_q$ son las componentes de $\phi$. La restricción $i$-ésima se satura en $\mathbf{a} \in S$ cuando $\phi_i(\mathbf{a}) = 0$.

Condiciones Necesarias de Kuhn y Tucker para Mínimo

Sean $f : C \to \mathbb{R}$ y $\phi : C \to \mathbb{R}^q$ definidas en un subconjunto abierto $C \subseteq \mathbb{R}^n$. Sea $\mathbf{a} \in S = \{\mathbf{x} \in C : \phi(\mathbf{x}) \le 0\}$, de forma que $r$ restricciones se saturan en $\mathbf{a}$.

Si $f$ y $\phi$ son funciones de clase $C^1$ en $C$, y $\mathbf{a}$ es un mínimo relativo de $f$ condicionado por $\phi(\mathbf{x}) \le 0$ tal que el rango de la matriz formada por las $r$ filas de $d\phi(\mathbf{a})$ correspondientes a las $r$ componentes que se saturan en $\mathbf{a}$ es $r$ (el máximo posible), entonces existen $\lambda_1, \ldots, \lambda_q \in \mathbb{R}$ tales que:

Condiciones Suficientes de Kuhn y Tucker para Mínimo

Consideremos funciones $f : C \to \mathbb{R}$ y $\phi : C \to \mathbb{R}^q$ de clase $C^2$ definidas en un subconjunto abierto $C \subseteq \mathbb{R}^n$.

Si $\mathbf{a} \in S = \{\mathbf{x} \in C : \phi(\mathbf{x}) \le 0\}$ es una solución factible que cumple la condición de regularidad y las condiciones necesarias de Kuhn-Tucker para mínimo, y $Q'' = [d^2L_{\mathbf{x}} (\mathbf{a}; \mathbf{\lambda})]|_V'$ es la forma cuadrática definida por la restricción de $d^2L_{\mathbf{x}} (\mathbf{a}; \mathbf{\lambda})$ (con respecto a las variables $x_1, \ldots, x_n$) al subespacio:

$$V' = \{\mathbf{x} \in \mathbb{R}^n : d\phi_j(\mathbf{a})(\mathbf{x}) = 0, \text{ para todo } j \in J\}$$

donde $J = \{j : j = 1, \ldots, q, \phi_j(\mathbf{a}) = 0, \lambda_j > 0\}$.

Entonces, si $V' \ne \emptyset$ y $Q''$ es definida positiva, $\mathbf{a}$ es un mínimo relativo estricto de $f$ condicionado por $\phi(\mathbf{x}) \le 0$.