Calificación de restricciones de Mangasarian-Fromovitz

La calificación de restricciones Mangasarian-Fromovitz (abreviada MF) es una condición importante para los criterios necesarios de optimalidad aplicados en optimización no lineal. Es una condición para la regularidad de un punto factible. Si la calificación de restricciones MF se cumple en un punto $\overline{x}$, que además es mínimo local, las condiciones de Karush-Kuhn-Tucker también se cumplen en este punto. Aplicando la calificación de restricciones MF, es sencillo determinar si un punto dado es óptimo o no.

Lleva el nombre de Olvi Mangasarian y Stanley Fromovitz.

Definición

Dado un problema de optimización de la forma:

$\underset{x\in X}{\min }f(x)$

con

$X=\{x\in {ℝ}^n|g_i(x)\le 0,h_j(x)=0\}$

y donde todas las funciones son continuamente diferenciables . Entonces un punto factible $\overline{x}\in X$ del problema de optimización con restricciones la calificación MF si se cumplen las dos condiciones siguientes:

1. Los gradientes de las restricciones de igualdad $h_j(x)$ linealmente independientes en el punto $\overline{x}$ .
2. Existe un vector $d\in {ℝ}^n$ tal que $\mathrm{\nabla }{h}_j(\overline{x}{)}^{T}d=0$ y $\mathrm{\nabla }{g}_i(\overline{x}{)}^{T}d<0$, si $g_i(\overline{x})=0$.

Ejemplo

Consideremos la restricción de igualdad $h(x)=x_1^2+x_2^2-1=0$ y la restricción de desigualdad $g(x)=x_2\le 0$ . El conjunto descrito por estas restricciones es el borde del círculo unitario, restringido a la mitad inferior del sistema de coordenadas. Examinamos si el punto $\overline{x}=(1,0)$ cumple la calificación MF. Los gradientes de las funciones de restricción son $\mathrm{\nabla }g(\overline{x})=(0,1),\mathrm{\nabla }h(\overline{x})=(2,0)$, y la desigualdad está activa en $\overline{x}$.

Como solo hay una restricción de igualdad, la independencia lineal se sigue directamente. Además, cada vector de la forma $(0,t)$ es ortogonal al gradiente de la restricción de la ecuación. Por otro lado, si $t<0$, entonces $\mathrm{\nabla }{g}_i(\overline{x}{)}^T(0,t)<0$. Por ejemplo, el vector $d=(0,-1)$ cumple con todas las condiciones de la calificación de restricciones MF.

Condiciones de Abadie sin MF

Consideremos las funciones $g_1(x)=-x_1,g_2(x)=-x_1^2-x_2,g_3(x)=-x_1^2+x_2$ y el siguiente conjunto factible descrito por ellas:

$X=\{x\in {ℝ}^2|g_i(x)\le 0,i=1,2,3\}$ .

Este conjunto es el área encerrada entre una parábola positiva y negativa, limitada al lado derecho del sistema de coordenadas. Ahora examinamos el conjunto $X$ para ver si las condiciones de Abadie y las de MF se cumplen en el punto $\overline{x}=(0,0)$.

Todas las desigualdades están activas en este punto y los gradientes de las restricciones de desigualdad son $\mathrm{\nabla }{g}_1(\overline{x})=(-1,0{)}^T,\mathrm{\nabla }{g}_2(\overline{x})=(0,-1{)}^T,\mathrm{\nabla }{g}_3(\overline{x})=(0,1{)}^T$ . Las condiciones MF no pueden cumplirse, de lo contrario se tendría $d_2>0$ y $d_2<0$. Sin embargo, las condiciones de Abadie sí se cumplen, ya que tanto el cono tangente como el cono tangente linealizado corresponden a la semirrecta $(0,\lambda )$ con $\lambda \ge 0$.

Comparación con otras calificaciones de restricciones

Entre las otras calificaciones de restricción, la calificación de restricciones Mangasarian-Fromovitz es un compromiso entre generalidad y facilidad de manipulación. Es más difícil de usar, pero más general que la calificación de independencia lineal, y más fácil de usar que las condiciones de Abadie, pero menos general. Entre estas calificaciones de restricciones se cumple la siguiente cadena de implicancias:

$\text{IL}⟹\text{MF}⟹\text{Abadie}$ .

Sin embargo, las recíprocas no se cumplen.

Bibliografía

• C. Geiger, C. Kanzow: Theorie und Numerik restringierter Optimierungsaufgaben. Springer, 2002. ISBN 3-540-42790-2. http://books.google.de/books?id=spmzFyso_b8C