Multiplicadores de lagra

ngeOptimización con restricciones
Prof. Cesar de Prada ISA-UVA prada@autom.uva.es

Indice
Restricciones Problemas con restricciones de igualdad
–

Multiplicadores de Lagrange Condiciones de Karush-Kuhn-Tucher (KKT)

Problemas generales NLP
–

Programación cuadrática QP Método de Wolfe, SLP Funciones de penalización
2
Cesar de Prada ISA-UVA

Restricciones
En la mayor parte delos problemas de toma de decisiones están presentes ligaduras entre las variables o limitaciones en las mismas Unas debidas a las ecuaciones del modelo Otras al rango permisible de unas variables Otras debidas a reglas de operación, existencias, etc. Por ello un problema de optimización a menudo se formula como:

min J (x)
x

h(x) = 0 g(x) ≤ 0

Problema de optimización no-lineal conrestricciones NLP
Cesar de Prada ISA-UVA

3

Restricciones
La presencia de restricciones limita el espacio de búsqueda pero, al mismo tiempo, dificulta el encontrar la solución óptima porque se pierden algunos de los criterios de optimalidad como que el gradiente es nulo en el óptimo

x2

x1 Región factible

Una política conducente a calcular el óptimo sin restricciones y luego limitarlo alcontorno de la región factible lleva a soluciones incorrectas

4

Cesar de Prada ISA-UVA

Restricciones de igualdad
Hay una categoría de problemas en los cuales las variables de decisión están sujetas solo a un conjunto de ecuaciones de igualdad:

min J (x)
x

min J ( x1 , x2 ,..., xn )
x

h ( x) = 0
Si es posible despejar m variables en función de las n-m restantes y sustituirlasen J, es posible transformar el problema en uno de optimización sin restricciones con n-m variables

h1 ( x1 , x2 ,..., xn ) = 0 ⎫ h2 ( x1 , x2 ,..., xn ) = 0 ⎪ ⎪ ⎬ n>m .... ⎪ hm ( x1 , x2 ,..., xn ) = 0⎪ ⎭

5

Cesar de Prada ISA-UVA

Restricciones de igualdad
min ( x1 x2 + x 2 )⎫ x2 2 ⎪ x1 , x 2 ⇒ x1 = ⎬ log x2 x1 log x2 = x2 ⎪ ⎭ ⇒ min
x2

x2 2 log x2

2 + x2

El procedimiento essimilar si partiendo de los valores de x1,x2,…,xn-m se puede evaluar J(x1,x2,…,xn) por medio de una rutina de cálculo. En ese caso se puede aplicar un algoritmo de optimización sin restricciones sobre las variables x1,x2,…,xn-m Sin embargo, en muchos casos, debido a la no-linealidad de las ecuaciones hi, no es posible aislar y despejar m variables y el procedimiento no puede emplearse, o su usoimplica el uso del método de Newton para resolver las ecuaciones en una rutina de cálculo.

6

Cesar de Prada ISA-UVA

Multiplicadores de Lagrange
Para problemas de optimización con restricciones de igualdad, el método de los multiplicadores de Lagrange proporciona condiciones necesarias que deben cumplirse en el óptimo. La idea es convertir el problema en otro sin restricciones ampliado enm variables λj (los multiplicadores de Lagrange) tal que su solución coincida en las variables x con el primitivo y cumpla las restricciones h(x) = 0

min J (x) ⎫ ⎪ x ⎬ h ( x) = 0 ⎪ ⎭

⇒

min L(x, λ ) = min J (x) + λ' h(x)
x, λ x, λ

Para todos los x que cumplan las restricciones h(x)=0 se verifica: min L(x, λ ) = min J (x)
x, λ x

Si x* es optimo para el problema original, minimizaJ(x*) y cumple h(x*) = 0, luego también tiene que ser una solución del problema de la Lagrangiana L

7

Cesar de Prada ISA-UVA

Multiplicadores de Lagrange
min L(x, λ ) = min J (x) + λ' h(x)
x, λ x, λ

L(x,λ) Lagrangiana

La solución del problema ampliado sin restricciones es:

∂L(x, λ ) = 0, ∂x x* , λ *

∂L(x, λ ) =0 ∂λ x* , λ *

⇒ h(x * ) = 0

Que puede resolverse mediante elmétodo de Newton. Si tiene solución, después hay que comprobar mediante el Hessiano de L que la solución x*,λ* corresponde verdaderamente a un mínimo de L respecto a x

8

Cesar de Prada ISA-UVA

Cualificación de las restricciones
∂J ( x * ) ∂h( x * ) + λ *' =0 ∂x ∂x h( x * ) = 0 ⎡ ∂h 1 (x) ⎢ ∂x 1 ⎢ ⎢ ∂h 2 (x) L λ m ]⎢ ∂x 1 ⎢ M ⎢ ∂h m (x) ⎢ ⎣ ∂x 1 ∂h 1 (x) ∂h 1 (x) ⎤ L ∂x 2 ∂x n ⎥ ⎥ ∂h 2...