variados

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

Indice
Restricciones
Problemas con restricciones de igualdad
–

Multiplicadores de Lagrange

Problemas generales NLP
–

Condiciones de Karush-Kuhn-Tucher (KKT)

Programación cuadrática QP
Método de Wolfe, SLP
Funciones de penalización
2

Cesar de Prada ISA-UVA

Restricciones
En la mayorparte de los 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

3

Problema de optimizaciónno-lineal
con restricciones NLP
Cesar de Prada ISA-UVA

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

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

Región factible

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)

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

h ( x) = 0

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

x

5

Si es posible despejar m
variables en función de las n-m
restantes y sustituirlas en J, es
posible transformar el problema
en uno de optimización sin
restricciones con n-m variables

x

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 ⎪
⎭

⇒ minx2

x2
2
log x2

2
+ x2

El procedimiento es similar 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 mvariables y el
procedimiento no puede emplearse, o su uso implica 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 ideaes convertir el
problema en otro sin restricciones ampliado en m 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, minimiza J(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 el mé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

⎡ ∂J ( x)
⎢ ∂x
⎣ 1...