Método Símplex Modificado (II)

Como se analizó en la sección 4.6, tal solución básica factible inicial se encuentra casi directamente. En el caso sencillo (poco probable) de que e^T ≤ 0 y b ≥ 0, las varibles básicas inciiales son los elementos de y y v (se multiplica por -1 todo el primer conjunto de ecuaciones), de manera que la solución deseada es x =0, u =0, y = -e^T, v = b. De otra manera, es necesario revisar el problema introducieno una variable artificial en cada una de las ecuaciones en donde cj > 0 (se agrega la variable a la izquierda) o bi < 0 ( se resta la variable a la izquierda y después se multiplican los dos lados por -1), con el fin de usar estas variables artificiales (que se denotan por z1, z2, etc) como varibles básicas iniciales para el problema revisado. (Nótese que esta selección de variables básicas iniciales satisface la restricción de complementariedad, ya que como variables básicas x = 0 y u = 0 de manera automática)

Método Símplex Modificado (I)

El método símplex modificado explota el hecho importante de que, con excepción de la restricción de complementariedad, las condiciones KKT expresadas en la forma conveniente que se acaba de obtener, no son otra cosa que condiciones de programación lineal. Lo que es más la restricción de complementariedad sencillamente implica que no es permisible que las dos variables complementarias de un par dado sean variables básicas (las únicas variables > 0) al considerar soluciones básicas factibles (no generadas). Por tanto,  el problema se reduce a encontrar una solución inicial básica factible para cualquier problema de programación lineal con estas restricción, sujeta a la restricción adicional sobre la identidad de las variables básicas. (Esta solución inicial básica factible puede ser la única solución factible en este caso.).

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

Como se supone que la función objetivo del problema original es cóncava y como las funciones de restricción son lineales y, por tanto, convexas, se puede aplicar el colorario del teorema de la sección 14.6. Así, x es óptima si y sólo si existen valores de y, y y v talse que los cuatro vectores juntos satisfagan todas estas condiciones. Así pues, el problema original se reduce al problema equivalente de encontrar una solución factible para estas restricciones.

Es interesante observar que este problema equivalente es un ejemplo del problema de complementariedad lineal introducido en la sección 14.3 (véase el problema 13), y que una restricción clave para este problema de complementariedad lineal es su restricción de complementariedad.

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

En cualquier problema de programación cuadrática, sus condiciones KKT se pueden reducir a la misma forma conveniente que contiene sólo restricciones de programación lineal y una restricción de complementariedad. En notación matricial, esta forma general es

en donde los elementos del vector columna u son las ui de la sección anterior y lo elementos de los vectores columna y y v son variables de holgura.

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

Después de multiplicar las ecuaciones de las condiciones 1a y 1b por (-1) para obtener lados derechos no negativos, se obtiene la forma deseada para el conjunto completo de condiciones.

Esta forma e en espcial conveniente ya que excepto por la restricción de complementariedad, estas condiciones son restricciones de programación lineal.

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

Para cada uno de estos tres pares, (x1, y1), (x2, y2), (u1, v1), las dos variables se llaman variables complementarias, porque sólo una de las dos puede ser diferente de cero. Como se requiere que las seis variables sean no negativas, estas nuevas formas de las condiciones 2a, 2b y 4 se pueden combinar en una restricción.

xiy1 + x2y2 + u1v1 = 0

llamada restricción de complementariedad

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

Para poder reexpresar estas condiciones en una forma más conveniente, se mueven las constantes de las condiciones 1a, 1b y 3 al lado derecho y después se introducen variables de holgura no negativas (denotadas por y1, y2 y v1 respectivamente) para convertir estas desigualdades a ecuaciones.