domingo, 27 de octubre de 2019

3.4.2 MAXIMOS Y MINIMOS

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 (x, ë ) = (x) − Max ë[g(x) − b]R m+R m+ 
Si g(x) – b≤ 0, entonces ë[gi(x) – bi] ≤ 0, luego 
 Max ëg(x) − b) = 0R m+ (se alcanza en ë = 0). Por tanto, si ∈ XMin L (x, ë ) = (x) .R m+ Si g(x) – b> 0, entonces Sup ë[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 (xD        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 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, 
= {ë ∈ R m +  / ∃ Max x ) − ë[g(x) − b ])},  ⊂ R m + 
Entonces, la segunda parte de la igualdad se debe expresar como sigue: 
Min Max (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: 
 (x0 , ë0 ) = Max Min (x, ë ) = Min Max (x, ë ) , 
donde 
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   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 
 
= {ë ∈ R+ / ∃ Max{(x) − ë[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 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 )

 
 

3.4.1 PUNTOS DE INFLEXIÓN

Puntos estacionarios.
 Procedemos entonces, tras haber establecido ciertos conceptos básicos en la sección anterior, a resolver el problema
 Maximizarsujeta a :(x)g(x) ≤ b(PRD)
donde suponemos que se dan condiciones de diferenciabilidad sobre y que el conjunto es abierto. En esta situación, tenemos aseguradas ciertas condiciones de diferenciabilidad sobre la función de Lagrange L. Empezaremos definiendo el concepto de punto estacionario de Kuhn-Tucker a partir de L. Tras ello, estudiaremos su relación con las soluciones del problema (PRD). Como veremos, serán necesarias condiciones de convexidad en los teoremas de suficiencia, y no así en los de necesariedad (donde, eso sí, hará falta incluir cualificaciones de restricciones).
Así pues, definimos
supuesto que x0 es un punto factible:
Una  vez  definido  este  concepto,  veamos  seguidamente  los  teoremas  que  lo relacionan con las soluciones del problema (PRD). Empezaremos dando el teorema de condiciones necesarias, es decir, el teorema en el que se establecen qué condiciones necesariamente deben verificar los óptimos de (PRD).
Como se observa, gracias a la formulación de punto estacionario de Kuhn-Tucker (4), este teorema afirma que, si se verifica la cualificación de restricciones de independencia lineal en x0, entonces necesariamente todo óptimo local del problema es un punto estacionario   de   Kuhn-Tucker.   Existe   otro   concepto   de   punto   estacionario   (punto estacionario de Fritz-John) más general que el de Kuhn-Tucker, que no necesita de la cualificación de restricciones para que se establezca esta condición necesaria.
 Este  teorema  admite  exactamente  la  misma  formulación  para  el  problema  de mínimo,  teniendo  simplemente  en  cuenta  las  definiciones  de  punto  estacionario  para mínimo. Así, por ejemplo, la condición quedaría:
() + ∑ ëig() = .00iI
 Pasamos ahora a dar el teorema de condiciones suficientes, es decir, el teorema que afirma  bajo  qué  condiciones  un  punto  estacionario  de  Kuhn-Tucker  es  máximo  del problema. Ya se ha comentado que hace falta en este caso exigir condiciones de convexidad
sobre las funciones del problema. Realmente, basta con unas suposiciones un poco más suaves que la convexidad global, si bien aquí no vamos a especificarlas:
24 sobre las funciones del problema. Realmente, basta con unas suposiciones un poco más suaves que la convexidad global, si bien aquí no vamos a especificarlas
 Este teorema admite una formulación similar para el problema de mínimo, con las correspondientes definiciones de los puntos estacionarios, y suponiendo que la función sea convexa.
 Si observamos con detenimiento las condiciones de punto estacionario que hemos desarrollado  en  esta  sección,  podremos  ver  su analogía con el caso en el que existan restricciones de igualdad. En concreto, desde un punto de vista intuitivo, el proceso se podría interpretar de la siguiente forma: en primer lugar, se identifican las restricciones activas en el punto en cuestión. Posteriormente, se toman las condiciones de primer orden para problemas con restricciones de igualdad, teniendo en cuenta sólo las mencionadas restricciones activas (que, en el punto bajo estudio, se pueden considerar de igualdad). Finalmente, se añade la condición adicional de no negatividad sobre los multiplicadores óptimos, que, según vimos previamente, garantizan que la función objetivo no mejora al moverse hacia el interior relativo de las restricciones activas.


3.4 OPTIMIZACION CLASICA

Optimización clásica

La teoría de optimización clásica o programación matemática está constituida por un conjunto de resultados y métodos analíticos y numéricos enfocados a encontrar e identificar al mejor candidato de entre una colección de alternativas, sin tener que enumerar y evaluar explícitamente todas esas alternativas. Un problema de optimización es, en general, un problema de decisión.

Con el fin de ilustrar de forma adecuada la estructura y composición de un problema de optimización, introduciremos a continuación un sencillo ejemplo.

Ejemplo 1(Construcción de una caja con volumen máximo) Supongamos que queremos determinar las dimensiones de una caja rectangular de forma que contenga el mayor volumen posible, pero utilizando para ello una cantidad fija de material. El problema en forma abstracta se podría plantear en los siguientes términos Maximizar Volumen de la caja sujeto a Área lateral fija Con el fin de resolver este problema habrá que modelizarlo matemáticamente, es decir tendremos que expresarlo en términos matemáticos.

El primer paso para modelizar un problema de optimización es identificar y definir las variables que están implicadas en dicho problema, en este caso y puesto que estamos tratando de determinar el tamaño de una caja rectangular, la opción más clara es considerar como variables sus tres dimensiones rectangulares usuales (ancho, largo, alto) y que representamos con x, y, z. Con estas variables, la función para la que tenemos que encontrar el mejor valor será el volumen de la caja que puede expresarse como V (x, y, z) = xyz.

 A continuación debemos tener en cuenta las limitaciones existentes sobre el material. Como este material se utiliza para construir las paredes de la caja, necesitaremos considerar el área lateral de la misma, y si la caja tiene tapa, dicha área será A (x, y, z)= 2(xy + yz + zx).

Por último, teniendo en cuenta que las dimensiones de la caja no pueden ser negativas el problema puede expresarse matemáticamente como Maximizar xyz sujeto a 2 (xy + yz + zx) = A x, y, z ≥ 0.

 Fundamentos de Optimización 


En este ejemplo se distinguen tres elementos fundamentales: las variables del problema, una función de esas variables y un conjunto de relaciones que deben cumplir las variables del problema. Estos elementos se repetirán en todos los problemas de optimización y se definen formalmente a continuación:


1.- Variables de decisión: El primer elemento clave en la formulación de problemas de optimización es la selección de las variables independientes que sean adecuadas para caracterizar los posibles diseños candidatos y las condiciones de funcionamiento del sistema. Como variables independientes se suelen elegir aquellas que tienen un impacto significativo sobre la función objetivo.

Representaremos las variables independientes se representarán mediante vectores columna de Rn x = x1  . . .  + xn o vectores fila xt= (x1,...,xn) Aunque para los casos n = 1, 2 y 3 se emplearán las notaciones usuales de x, (x, y) y (x, y, z) respectivamente.

2.- Restricciones: Una vez determinadas las variables independientes, el siguiente paso es establecer, mediante ecuaciones o inecuaciones las relaciones existentes entre las variables de decisión. Estas relaciones son debidas, entre otras razones, a limitaciones en el sistema, a leyes naturales o a limitaciones tecnológicas y son las llamadas restricciones del sistema. Podemos distinguir dos tipos de restricciones:

(a) Restricciones de igualdad: Son ecuaciones entre las variables de la forma h (x) = h (x1,....xn)=0 donde g : A ⊆ Rn → R es una función real de variables reales definida sobre un conjunto A de números reales.

(b) Restricciones de desigualdad: Son inecuaciones entre las variables de la forma g (x) = g(x1,....xn) ≤ 0 donde A : C ⊆ Rn → R es una función real de variables reales definida sobre un conjunto A de números reales.

Observación: Solamente se han considerado restricciones de dos tipos: restricciones de igualdad del forma h (x1,....xn)=0 y restricciones de desigualdad de la forma g(x1,....xn) ≤ 0, debido a que siempre es posible, mediante una simple transformación, expresar el problema en términos de esta clase de restricciones.

Función objetivo: Finalmente, el último ingrediente de un problema de optimización es la función objetivo, también llamado índice de rendimiento o criterio de elección. Este es el elemento utilizado para decidir los valores adecuados de las variables de decisión que resuelven el problema de optimización. La función objetivo permite determinar los mejores valores para las variables de decisión. Independientemente del criterio seleccionado, dentro del contexto de la optimización matemática el adjetivo “mejor” siempre indica los valores de las variables de decisión que producen el mínimo o máximo valor (según el criterio utilizado) de la función objetivo elegida. Algunos de estos criterios pueden ser por ejemplo de tipo económico (coste total, beneficio), de tipo tecnológico (energía mínima, máxima capacidad de carga, máxima tasa de producción) o de tipo temporal (tiempo de producción mínimo) entre otros.

Puntos de Inflexión

Se define un punto de inflexión como el punto en que la función pasa de ser convexa a cóncava o de cóncava a convexa.

En la siguiente gráfica podemos ver que cuando x = 0, la gráfica pasa de ser cóncava a ser convexa, por lo que podemos decir que el punto de inflexión esta en X = 0.


Una característica de los puntos de inflexión es que son los puntos donde la función derivada tiene máximos y mínimos. Si nos fijamos, cuando nos acercamos a un punto de inflexión la función cada vez crece más (o decrece menos), pero al sobrepasar el punto de inflexión la función empieza a crecer menos (o decrecer menos). Esto significa que justamente donde haya un punto de inflexión la derivada tendrá un máximo o un mínimo. Consecuentemente encontraremos los puntos de inflexión buscando ceros de la segunda derivada.

Vamos a ilustrar el proceso con un ejemplo para así dar una explicación simple y clara:

Consideraremos la función F(x) = x³ - 3x  (es la función representada en la anterior gráfica).

Sabemos ya calcular los máximos y los mínimos de la función f(x)  usando la primera derivada. La expresión de ésta es 3x² - 3  y justamente encontramos máximos y mínimos respectivamente en x = -14  y x = 1 .  Si representamos la gráfica de la derivada queda:

Observamos que justamente donde la derivada tiene un mínimo es donde la función tiene el punto de inflexión.

Para saber qué punto es vamos a derivar la función derivada e igualarla a cero: F´´(x) = 6x=0 = x = 0/6 = 0, y por tanto la función original en x = 0  tiene un punto de inflexión.

Máximos y Mínimos

Loas máximos y mínimos de una función son los valores más grandes o más pequeños de ésta, ya sea en una región o en todo el dominio.

Los máximos y mínimos en una función f son los valores más grandes (máximos) o más pequeños (mínimos) que toma la función, ya sea en una región (extremos relativos) o en todo su dominio (extremos absolutos).


A continuación tenemos un vídeo acerca de lo que es optimización clásica