Fundamentos de Programación con Restricciones: Kuhn-Tucker y Multiplicadores de Lagrange

Programación con Restricciones de Desigualdad: Condiciones de Karush-Kuhn-Tucker (KKT)

El problema se define para minimizar f(x) sujeto a g(x) ≤ 0, considerando todas las restricciones excepto la de no negatividad. En la función Lagrangiana (L), no se modifican los signos de los multiplicadores (λ) ni se altera el término independiente.

Tipo 1: 4 Condiciones Básicas

• 1. ∇_xL = 0
• 2. g_i ≤ 0
• 3. g_i · λ_i = 0
• 4. λ_i ≥ 0

Tipo 2: 6 Condiciones (Incluyendo No Negatividad)

Se diferencia por la inclusión de la condición de no negatividad (condición 6):

• 1. ∇_xL ≥ 0
• 2. x_i · ∇_xL = 0
• 3. g_i ≤ 0
• 4. λ_i · g_i = 0
• 5. λ ≥ 0
• 6. x ≥ 0

Verificación de Optimalidad

Podemos asegurar que los puntos de KKT son óptimos si la función objetivo y las restricciones son convexas. Para confirmar que son óptimos, los gradientes de las restricciones saturadas deben ser linealmente independientes.

Pasos para la comprobación:

1. Identificación: Obtener los puntos candidatos.
2. Convexidad: Comprobar si la función es convexa derivando respecto a las variables (no respecto a los λ) y calculando la matriz Hessiana. Si la Hessiana es definida positiva (DP), la función es convexa; si es definida negativa (DN), no se puede continuar bajo este criterio.
3. Saturación: Evaluar si g_i(x, y) = 0. Si se satura, se debe verificar si es un mínimo calculando el gradiente en el punto.
4. Independencia Lineal: Construir una matriz con las derivadas parciales de las restricciones saturadas. Si el resultado es distinto de cero, las restricciones son linealmente independientes, confirmando que es un mínimo de f(x, y).

Optimización con Restricciones de Igualdad: Multiplicadores de Lagrange

• Planteamiento de la función Lagrangiana (L).
• Cálculo de derivadas parciales igualadas a cero para obtener los puntos críticos.
• Dado que la función objetivo y las restricciones son diferenciables, no existen otros puntos estacionarios.

Consideraciones Técnicas

• Número de restricciones: Si hay una restricción, se usa el gradiente; si hay más de una, se utiliza la matriz Jacobiana.
• Hessiana: Se calculan las derivadas parciales de segundo orden. Si es DP, es un mínimo; si es DN, es un máximo.
• Matriz Indefinida: Si la diagonal principal es cero, se utiliza el parámetro -a para resolver la matriz y determinar si es DP, DN o indefinida.

Nota: Si no hay restricción, se trata de un punto silla. Si existe restricción, es obligatorio realizar el gradiente de la función.

Regla de multiplicación de matrices: Al multiplicar, el resultado de la fila por columna será la fila por la columna de la matriz resultante.