Condiciones KKT para programación cuadrática (I)

Para que sea concreto, primero considérese el ejemplo anterior. Comenzando con la forma dada en la sección anterior, sus condiciones KKT son las siguientes

Programación cuadrática (II)

para toda x, es decir, que Q es una matriz positiva semidifinida.) Se describirá uno de estos algoritmos, que es muy aceptado porque sólo emplea el método símple con una pequeña modificación. La clave de este enfoque es construir las condiciones KKT de la sección anterior y después reexpresar estas condiciones demanera conveniente que se parezca a programación lineal. Por esto, antes de describir el algoritmo, se desarrollará esta forma conveniente.

Programación cuadrática (I)

Como se indicó en la sección 14.3, el problema de programación cuadrática difiere del problema de programación lineal nada más en que la función objetivo incluye también términos xj² y xixj (i≠j). Así, si se usa la notación matricial comola que se introdujo en la sección 5.2, el problema es encontrar x para

Ejemplo Teorema de Karush-Kuhn-Tucker (KKT) (IV)

Toda vez que se encontró una solución, no se considerarán casos adicionales.

En problemas más complicados que éste puede ser difícil, si no es materialmente imposible, derivar una solución óptima directa de las condiciones KKT. De todas maneras estas condiciones proporcionan información valiosa en cuanto a la identidad de una solución óptima y también permiten verificar que una solución propuesta sea óptima.

Existen mucha aplicaciones indirectas valiosas de las condiciones KKT. Una de ellas surge en la teoría de la dualidad desarrollada par programación no lineal, que se puede poner en parelelo con la teoría de la dualidad para programación líneal presentada en el capítulo 6. En particular, para cualquier problema de maximización restringida (llámese problema primal), se pueden usar las condiciones KKT para definir un problema dual asociado, que es un problema de minización restringido. Las variables del problema dual consisten en multiplicadores de Lagrange, ui = (i = 1,2,......, m) y las variables primales xj (j = 1,2....., n). En el caso especial de que el problema primal es un problema de programación lineal, las variables xj desaparecerán del problema dual y quedará el familiar problema dual de programación líneal (en el que las variables ui, aquí corresponden a las variables yi del capítulo 6). Cuando un problema primal es un problema de programación convexa, es posible establecer relaciones entre el problema primal y el problema dual, que son muy parecidas a las de programación lineal. Por ejemplo,la propiedad dualidad fuerte de la sección 6.1, que establece que los valore óptimos de las funciones objetivo son iguales, también se cumple aquí. Más aún, los valores de las variables ui en una solución óptima para el problema dual,de nuevo se pueden interpretar como los precios sombra (véanse las secciones 4.7 y 6.2); es decir, proporcionan la tasa a la que puede aumentar el valor óptimo de la función objetivo para el problema primal, si se aumenta (ligeramente) el lado derecho de la restricción correspondiente. Como la teoría de dualidad para programación no lineal es un tema relativamente avanzado se pide al lector interesado que consulte otros libros para obtener la información.

En la sección siguiente se verá otra aplicación indirecta de la condiciones KKT.

Ejemplo Teorema de Karush-Kuhn-Tucker (KKT) (III)

Ejemplo Teorema de Karush-Kuhn-Tucker (KKT) (II)

A continuación se describen los pasos para resolver las condiciones KKT para este ejemplo específico.

Ejemplo Teorema de Karush-Kuhn-Tucker (KKT) (I)

Par ilustrar esta formulación y la aplicación de las condiciones KKT, considérese el siguiente problema de programación no lineal de dos variables.

Teorema de Karush-Kuhn-Tucker (KKT) (III) Corolario

Supóngase que f(x) es una función cóncava y que g1(x), g2(x), ......, gm(x) son funciones convexas (es decir, se trata de un problema de programación convexa) en donde todas estas funciones satisfacen las condiciones de regularidad. Entonces x* = (x1*, x2*,............xn* es una solución óptima si  y sólo si se satisfacen todas las condiciones del teorema.

Teorema de Karush-Kuhn-Tucker (KKT) (II)

En las condiciones KKT anteriores, las ui corresponden a las variables dudales de programación lineal (al final de la sección se estudia más a fondo esta correspondencia) y tienen una interpretación económica comparable. (De hecho; las ui, surgieron en la derivación matemática, como los multiplicadores de Lagrange). Las condiciones 3 y 5 sólo ayudan a asegurar la factibilidad de la solución. Las otras condiciones eliminan la mayor parte de las soluciones factibles como posibles candidatos para ser la solución óptima. Debe hacerse notar que el cumplimiento de estas condiciones no garantiza que la solución sea óptima. Cómo se resume para obtener esta garantía. Estas suposiciones se establecen formalmente en la siguiente extensión del teorema.

Teorema de Karush-Kuhn-Tucker (KKT) (I)

Condiciones de Karush-Kuhn-Tucker (KKT) para optimización restringida

La pregunta ahora es cómo reconocer una solución óptima para un problema de programación no lineal (con funciones diferenciables). Cuáles son las condiciones necesarias y (tal vez) suficientes que esa solución debe cumplir?;

En las secciones anteriores se hicieron notar estas condiciones para optimización no restringida, como se resume en los primeros dos renglones de la tabla 14.3. Al principio de la sección 14.3, también se expusieron estas condiciones para la ligera extensión de optimización no restringida cuando sólo se tienen restricciones de no negatividad. En la tabla 14.3 se muestran estas condiciones en el tercer reglón, en otra forma equivalente a la que sugiere la ampliación para optimización restringida general. Como se indica en el último renglón de la tabla, las condiciones para el caso general se llaman condiciones de Karush-Kuhn-Tucker (o condiciones KKT), porque fueron desarrolladas independientemente por Karush y por Kuhn y Tucker. Su resultado básico se expresa en el siguiente teorema.

Resumen del procedimiento de búsqueda del gradiente - Ejemplo (V)

Si se quisiera minimizar la función objetivo f(x), un cambio en el procedimiento sería moverse en la dirección opuesta al gradiente en cada iteración; en otras palabras, la regla para obtener el siguiente punto sería.

Resumen del procedimiento de búsqueda del gradiente - Ejemplo (IV)

Sin embargo, como esta situación convergente de soluciones prueba nunca alcanza su límite, en realidad el procedimiento se detendrá en algún punto  (dependiendo de ε) un poco antes de (1,1) como aproximación final de x*.

La figura 14.11 sugiere que el procedimiento de búsqueda del gradiente marca una trayectoria en zigzag hacia la solución óptima en lugar de moverse en línea recta. Tomando en cuenta este comportamiento, se han realizado algunas modificaciones que aceleran el movimiento hacia el óptimo.

Si f(x) no fuera una función cóncava, este procedimiento convergiría en un máximo local.

El único cambio en la descripción del procedimiento para este caso es que t* ahora corresponde al primer máximo local de f(x'+ t▽f(x'), conforme t aumenta su valor.

Resumen del procedimiento de búsqueda del gradiente - Ejemplo (III)

Una manera sencilla de organizar este trabajo es escribir una tabla como la que se muestra en la tabla 14.2, que resume las dos iteraciones anteriores. En cada iteración, la segunda columna muestra la solución prueba actual y la última muestra la nueva solución prueba eventual, que después se escribe abajo, en la segunda columna, para la siguiente iteración. La cuarta columna proporciona las expresiones para la xj en términos de t, que se tienen que sustituir en f(x) para dar la quinta columna.

Resumen del procedimiento de búsqueda del gradiente - Ejemplo (II)

También se puede verificar (véase el apéndice I) que f(x) es cóncava. Para comenzar el procedimiento de búsqueda del gradiente, supóngase que se elige x = (0,0) como solución prueba inicial. Como en este punto las respectivas derivadas parciales son 0 y 2, el gradiente es

Resumen del procedimiento de búsqueda del gradiente - Ejemplo (I)

Considérese el siguiente problema de dos variables

Resumen del procedimiento de búsqueda del gradiente (II)

Regla de detención

se evalúa ▽f(x') en x = x'. Se verifica si

Si es así, el proceso se detiene con la x'actual como la aproximación a una solución óptima x* deseada. De otra manera, se regresa al paso iterativo.

Resumen del procedimiento de búsqueda del gradiente

Paso inicial: se elige ε y cualquier solución prueba incial x'. Se pasa primero a la regla de detención.

Procedimiento de búsqueda del gradiente (III)

Por lo general, la parte más difícil del procedimiento de búsqueda del gradiente es encontrar t*, el valor de t que maximiza f en la dirección del gradiente, en cada iteracción. Como x y ▽f(x) tienen valores fijos para la maximización y como f(x) es cóncava, este problema se debe ver como el de maximizar una función cóncava de una sola variable t. En efecto, se puede resolver con el procedimiento de búsqueda en una dimensión de la sección 14.4 (en donde la cota inferior inicial sobre t debe ser no negativa por la restricción de t ≥ 0). De otra manera, si f e una función simple, es posible que e pueda obtener una solución analítica estableciendo la derivada con respecto a t igual a cero y depejando.

Procedimiento de búsqueda del gradiente (II)

Una anología puede ayudar a aclarar este procedimiento. Supóngase que una persona quiere subir a la cumbre de una montaña. Esta persona es miope y no puede ver la cumbre para caminar en esa dirección, pero cuando se detiene, puede ver el piso a su alrededor y determinar la dirección en la que la pendiente de la montaña es más pronunciada. La persona puede caminar en línea recta. Mientras camina, también es capaz de percibir cuándo ya no va hacia arriba (pendiente cero en esa dirección). Suponiendo que la montaña es cóncava, el individuo puede usar el procedimiento de búsqueda del gradiente para escalar hasta la cima eficientemente. Este problema tiene dos variables, en donde (x1, x2) representa las coordenadas (ignorando la altura) de la localización actual. La función f(x1, x2) da la altura de la montaña en (x1, x2). La persona comienza cada iteración en su localización actual (solución prueba actual) al determinar la dirección [en el sistema de coordenadas (x1, x2)] en la que la montaña tiene la mayor pendiente (la dirección del gradiente) en este punto. Después, comienza a caminar en otra dirección fija y continúa haciéndolo mientras sigue subiendo. Luego se detiene en una nueva localización (solución) prueba, cuando la montaña se nivela en la dirección en que camina. Estas iteraciones continúan, siguiendo una trayectoria en zig-zag hacia arriba, hasta que e alcanza una localización prueba en la que la pendiente es esencialmente cero en todas direcciones. Bajo la suposición de que la montaña [f(x1, x2)] es cóncava, en principio, la persona debe estar en la cima de la montaña.

Procedimiento de búsqueda del gradiente (I)

Pueto que el problema en cuestión no tiene restricciones, esta interpretación del gradiente sugiere que un procedimiento de búsqueda eficientes debe moverse en la dirección del gradiente hasta que (en esencia) alcance una solución óptima x*, en la que ▽f(x*) = 0. Sin embargo, no resultaría práctica cambiar x continuamente en la dirección de ▽f(x), ya que esta serie de cambios requeriría una reevaluación continua de ∂f/∂xj y del cambio de dirección de la trayectoria. Entonces, una mejora forma de hacerlo es continuar el movimiento en una dirección fija a partir de la solución prueba actual, sin detenerse, hasta que f(x) deje de aumentar. Este punto de detención sería la siguiente solución prueba, por lo que se debe volver a calcular el gradiente para determinar la nueva dirección de movimiento. Con este enfoque, cada iteración incluye cambiar la solución prueba actual x'como sigue:

Optimización no restringida de varias variables (III)

Como se supone que la función objetivo f(x) es diferenciable, posee un gradiente denotado por ▽f(x) en cada punto x. En particular, el gradiente en un punto específico x = x' es el vector cuyos elementos son las derivadas parciales respectivas evaluadas en x = x', de manera que

Optimización no restringida de varias variables (II)

En la sección 14.4 se usó el valor de la derivada ordinaria para elegir una de sólo dos direcciones posibles (aumentar x o disminuir x) para pasar de la solución prueba actual a la siguiente. La meta era alcanzar en algún momento un punto en el que la derivada fuera (esencialmente) cero. Ahora se tienen innumerables direcciones posibles hacia dónde moverse; corresponden a las tasas proporcionales posibles a las cuales las respectivas variables pueden cambiar. La meta es alcanzr eventualmente un punto en el qeu todas las derivadas parciales sean (en esencia) cero. Por tanto, la extensión del procedimiento de búsqueda en una dimensión requiere emplear los valores de las derivadas parciales para seleccionar la dirección específica en la que conviene moverse. Esta selección implica el uso del gradiente dela función objetivo, como se describirá en seguida.

Optimización no restringida de varias variables (I)

Ahora considerese el problema de maximizar una función cóncava f(x) de varias variables (o de variables múltiples), x = (x1, x2,......., xn) en la que no se tiene retricciones sobre los valores factibles. Supóngase de nuevo que la condición necesaria y suficiente para la optimalidad, dada por el sistema de ecuaciones que se obtiene al establecer las repectivas derivadas praciales iguales a cero, no e puede resolver análiticamente, por lo que debe emplearse un procedimiento de búsqueda númerico. Cómo puede extenderse el procedimiento de búsqueda en una dimensión a este problema multidimensional??.

Procedimiento de búsqueda en una dimensión - Paso inicial Ejemplo (II)

Como la segunda derivada es no positiva en todos lados, f(x) es una función cóncava, y el procedimiento de búsqueda se aplica sin problemas para encontrar su máximo global. Una rápida inspección a esta función (sin construir siquiera la gráfica de la figura 14.10) indica que f(x)es positiva para valores pequeños de x, pero es negativa para x < 0 o x > 2. Entonces, x(barra abajo) = 0 y  x(barra arriba) =2 se pueden usar como cotas iniciales, con su punto medio x' = 1, como solución prueba inicial. Sea 0.01 la tolerancia del error para x* en la regla de detención, de manera que (x(barra arriba) - x(barra abajo)) ≤ 0.02 con la x'final en el punto medio. Al aplicar el procedimiento de búsqueda en una dimensión se obtiene la sucesión de resultados que se muestranen la tabla 14.1 [Esta tabla incluye tanto los valores de la función como los de la derivada, para información del lector, en donde la derivada se evalúa en la solución prueba que se genera en la interación anterior. Obsérvese que, de hecho, el algoritmo no necesita calcular f(x') y que sólo tiene que calcular la derivada hasta el punto en que se pueda determinar su signo]. La conclusión es que

x* ≈ 0.836

0.828125 < x* < 0.84375

Procedimiento de búsqueda en una dimensión - Paso inicial Ejemplo (I)

Supóngase que la función que se quiere maximizar es

Procedimiento de búsqueda en una dimensión - Paso inicial

Se selecciona ε. Se encuentan x(barra abajo) y x(barra arriba) iniciales por inspección ( o encontrado valores respectivos de x en los cuales la derivada sea positiva y luego negativa). Se elige una solución prueba inicial.

Procedimiento de búsqueda en una dimensión (III)

Aunque existen varias reglas razonables para elegir cada nueva solución prueba, la que se usa en el siguiente procedimiento es la regla del punto medio (tradicionalmente llamada plan de búsqueda de Bolzano), que dice que se seleccione el punto medio entre la dos cotas actuales.

Resume el procedimiento de búsqueda en una dimensión.

Procedimiento de búsqueda en una dimensión (II)

La idea que fundamenta el procedimiento de búsquedaen una dimensión es muy intuitiva; se basa en el hecho de que la pendiente (derivada) esa positiva o negativa en una solución prueba, en definitiva indica si es necesario hacer esta solución más grande o más chica para moverse hacia una solución óptima. Así, si la derivada evaluada para un valor específico  de x es positiva, entonces x* debe ser más grande queesta x (véase la figura 1439), con lo que x se convierte en una cota inferior para las soluciones prueba que en adelante se tomarán  en cuenta.
Por el contrario, si la derivada es negativa, entonces x* debe ser más chica que esta x, y x se convierte en una cota superior. Una vez que se han indentificado ambas cotas, cada nueva solución prueba que se selecciona entre ellas proporciona una nueva cota más estrecha de uno de los dos tipos, cerrando la búsqueda cada vez más. Siempre y cuando se usa una regla razonable para elegir cada solución prueba en esta forma, la sucesión de soluciones prueba debe converger a x*. En la práctica, esto significa continuar la sucesión, hasta que la distancia entre las cotas sean lo suficientemente pequeña como para que la siguiente solución prueba se encuentre dentro de una tolerancia  de error de x* preespecificada.

En eguida se resume este proceso completo, usando la notación

Procedimiento de búsqueda en una dimensión (I)

Al igual que otros procedimientos de búsqueda para programación no lineal, éste trata de encontrar una serie de soluciones prueba que conduzcan hacia una solución óptima. En cada iteración, se comienza con la solución prueba actual para llevar a cabo una búsqueda sistemática, que culmina con la identificación de una nueva solución prueba mejorada (se esperaque sustancialmente mejorada)

Optimización no restringida de una variable (I)

Se comenzará por explicar cómo se pueden resolver algunos tipos de problemas como los que se acaban de describir, considerando el caso más sencillo, la optimización no restringida con una sola variable x(n=1), en donde la función diferenciable f(x) que debe maximizarse es cóncava. Así, la condición necesaria y sufiente para que una solución particularx = x* sea óptima (un máximo global) es

df/dx = 0                        en x = x*

como se bosqueja en la figura 14.9. Si en esta ecuación se puede despejar directamente x*, el problema llegó a su fin, pero si f(x) no e una función sencilla y su derivada no es una función lineal o cuadrática, tal vez sea imposible resolver la ecuación analíticamente. De ser así, el procedimiento de búsqueda en una dimensión proporcionauna forma directa de resolverlo númericamente.