El punto minimax de la función lagrangiana es otro concepto relacionado con la solución de un problema de optimización. Si bien su definición no le hace útil a la hora de la resolución directa del problema, sí constituye un paso intermedio muy importante en la obtención del problema dual, que estudiaremos más adelante. En esta sección definimos dicho punto y estudiamos su relación con otro concepto, el punto de silla de la lagrangiana.
La relación del punto minimax con la solución del problema de programación no lineal se obtiene de forma inmediata sin mas que tener en cuenta que:
Min L (x, ë ) = f (x) − Max ët [g(x) − b]R m+R m+
Si gi (x) – bi ≤ 0, entonces ëi [gi(x) – bi] ≤ 0, luego
Max ëi ( gi (x) − bi ) = 0R m+ (se alcanza en ë = 0). Por tanto, si x ∈ X, Min L (x, ë ) = f (x) .R m+ Si gi (x) – bi > 0, entonces Sup ëi [gi(x) – bi] = ∞, por lo que en este caso no se alcanza el R m+ mínimo de la Lagrangiana.
Por tanto,
Max Min L (x, ë ) = Max f (x) D R m+ X
Así pues, si (x0, ë0) es un punto minimax, x0 es una solución óptima del problema original.
Pasamos ahora a dar los teoremas que relacionan los conceptos de punto de silla de L y punto minimax. Veremos que dicha relación es casi una equivalencia, en el sentido de que todo punto minimax es punto de silla, y todo punto de silla es un punto minimax considerado sobre conjuntos mas restringidos.
Como hemos expuesto anteriormente, para obtener el teorema recíproco es necesario restringir los conjuntos de definición del punto minimax. Previamente, hemos visto que la primera parte de la igualdad debe ser de la forma
Definimos, por tanto,
N = {ë ∈ R m + / ∃ Max ( f ( x ) − ët [g(x) − b ])}, N ⊂ R m +
Entonces, la segunda parte de la igualdad se debe expresar como sigue:
Min Max L (x, ë )
Por tanto, el punto minimax que buscamos ahora es de la forma:
Para el problema de mínimo, el punto minimax toma la forma:
tomando además la función lagrangiana correspondiente a este problema. Con esta definición, los teoremas 16 y 17 serían válidos de forma análoga para esta formulación.
4.1.- Dualidad en Programación Matemática.
El concepto de dualidad nace estrechamente ligado al de punto minimax que se desarrolló en la sección anterior. Así, dado nuestro problema original, recordemos la definición de punto minimax: se trata de un par (x0, ë0) que verifica:
L (x0 , ë0 ) = Max Min L (x, ë ) = Min Max L (x, ë ) ,
donde
L(x, ë) = f(x) – ët[g(x)
L(x, ë) = f(x) – ët[g(x)
que es, precisamente, el problema de partida, que llamaremos a partir de ahora Problema
Primal (PP).
Por otro lado, el segundo término de la igualdad del punto minimax se puede expresar como:
Min
N
õ (ë ),
tomando además la función lagrangiana correspondiente a este problema. Con esta definición, los teoremas 16 y 17 serían válidos de forma análoga para esta formulación.
4.1.- Dualidad en Programación Matemática.
El concepto de dualidad nace estrechamente ligado al de punto minimax que se desarrolló en la sección anterior. Así, dado nuestro problema original, recordemos la definición de punto minimax: se trata de un par (x0, ë0) que verifica:
L (x0 , ë0 ) = Max Min L (x, ë ) = Min Max L (x, ë ) ,
L(x, ë) = f(x) – ët[g(x)
que es, precisamente, el problema de partida, que llamaremos a partir de ahora Problema
Primal (PP).
Por otro lado, el segundo término de la igualdad del punto minimax se puede expresar como:
MinNõ (ë ),
donde
N = {ë ∈ Rm + / ∃ Max{f (x) − ët [g(x) − b]}}.
A este problema le llamaremos Problema Dual (PD).
Pues bien, la dualidad consiste en que se dé o no la igualdad entre los valores óptimos de las soluciones de estos dos problemas (lo que sucede si existe el punto minimax). Los siguientes teoremas establecen bajo qué condiciones se tiene esta dualidad.
Como consecuencia de este teorema, podemos afirmar que siempre se da la relación:
Max µ (x) ≥ Min õ (ë ) ,es decir, que el valor óptimo del problema primal es siempre menor o igual que el del dual. La pregunta que surge es cuándo se da la igualdad. En el caso en que no se dé, es decir, si la solución del primal es estrictamente menor que la del dual, se dice que se produce un gap de dualidad. El siguiente teorema afirma que, bajo condiciones de convexidad y si se da una cualificación de restricciones, entonces se verifica la igualdad:
Por lo tanto, bajo estas condiciones, los valores óptimos de los problemas primal y dual coinciden. La utilidad de este concepto consiste en que, en algunos problemas, dada su estructura y la forma específica que toma el problema dual, puede ser más sencillo resolver este último, y obtener, a partir del él, la solución del primal.
Por último, señalemos que, si el problema original se formula para mínimo, tendremos que tomar la correspondiente función de Lagrange, es decir,
L(x, ë) = f(x) + ët[g(x) – b].
y las funciones primal y dual toman ahora las formas:
Nuevamente, el problema primal coincide con el problema de mínimo de partida, y se da el teorema de dualidad débil en cualquier caso, y el de dualidad fuerte si suponemos que la función f es convexa en lugar de ser cóncava.
Solución de Programación no Lineal con una Variable
Aquí explicaremos cómo resolver el PNL:
máx (o mín) (4)
sujeto a
(Si , la región factible para el PNL (4) es y si , la región factible para (4) es ).
Para encontrar la solución óptima para (4), buscamos todos los máximos (o mínimos) locales.
Un punto que es un máximo local o un mínimo local para (4) se llama un extremo local.
Entonces la solución óptima para (4) es el máximo (o mínimo) local con el mayor (o menor) valor de
Naturalmente, si , (4) no puede tener una solución óptima (ver la figura)
Existen tres tipos de puntos para los cuales (4) puede tener un máximo o mínimo local (estos puntos a veces se llaman extremos candidato).
Caso 1. Los puntos en los cuales y (llamado punto estacionario de )
No hay comentarios:
Publicar un comentario