Formulación estándar del problema

OPTIMIZACIÓN CON RESTRICCIONES DE IGUALDAD

⎧opt f ( x ) ⎨ ⎩ g i ( x ) = 0 i = 1,2,..., m ♦ Se considerarán problemas en los que el

número de restricciones sea menor que el número de variables de decisión ♦ Si el número de restricciones supera al de variables, puede ocurrir que el problema sea infactible (ninguna solución factible) ♦ Una restricción de la forma g(x)=b es equivalente a g(x)-b=0

♦ Localización de óptimos de

funciones sujetas a restricciones en forma de igualdad ♦ Técnica de los multiplicadores de Lagrange

Método de eliminación de variables

♦ El método de eliminación de variables no

♦ Convertir un problema con n variables y m

resulta operativo cuando el problema tiene muchas restricciones o las restricciones son complejas

restricciones en un problema con n-m variables sin restricciones Ejemplo:

⎧opt x 2 + y 2 ⎨ ⎩x + y −1 = 0

♦ Se utilizará un método alternativo que

y = 1− x

Tiene un mínimo en el punto (x,y)=(1/2,1-1/2)=(1/2,1/2)

opt x 2 + (1 − x) 2

Tiene un mínimo en el punto x=1/2

Deducción gráfica de las condiciones necesarias de optimalidad de primer orden Ejemplo:

⎧opt x 2 + y 2 ⎨ ⎩x + y −1 = 0 f ( x, y ) = x 2 + y 2 g ( x, y ) = x + y − 1 El problema no tiene máximo y tiene un mínimo en el punto (x,y)=(1/2,1/2)

1

además proporciona más información sobre el problema (método de los multiplicadores de Lagrange)

Gradiente de la función objetivo:

1

0.75

f ( x, y ) = x 2 + y 2 ⎛ 2x ⎞ ∇f ( x, y ) = ⎜⎜ ⎟⎟ ⎝2y⎠

0.25

Gradiente de la función de restricción: g ( x, y ) = x + y − 1

0.5

⎛ 1⎞ ∇g ( x, y ) = ⎜⎜ ⎟⎟ ⎝ 1⎠

0

(1/2,1/2)

0.5

-0.5

-0.25

0.25

0.5

0.75

1

-0.25

-0.5

-0.5

⎛ 1⎞ ∇f (1 / 2,1 / 2) = ⎜⎜ ⎟⎟ ⎝ 1⎠

-1 -1

-0.5

0

0.5

1

⎛1⎞ ∇g (1 / 2,1 / 2) = ⎜⎜ ⎟⎟ ⎝1⎠

Se observa una relación de proporcionalidad entre los dos vectores

∇f (1 / 2,1 / 2) + λ∇g (1 / 2,1 / 2) = 0

1

Teorema de los multiplicadores de Lagrange ⎧opt f ( x) Sea x* un óptimo local del ⎨ problema ⎩ g i ( x) = 0 i = 1,2,..., m Si los vectores gradientes

condición de regularidad o cualificación

∇g1 ( x*),..., ∇g m ( x*) son linealmente independientes, entonces:

El teorema de Lagrange establece una condición necesaria de optimalidad (bajo las condiciones de regularidad) Todos los óptimos que verifiquen las condiciones de regularidad establecidas tienen asociados los correspondientes multiplicadores

Existen λ1, λ2,..., λm números reales tales que:

∇f ( x*) + λ1∇g1 ( x*) + ... + λm ∇g m ( x*) = 0 Los números λ1, λ2,..., λm se conocen como multiplicadores de Lagrange, variables duales o precios sombra

Puntos estacionarios ♦ Se llaman puntos estacionarios del problema

a las soluciones del siguiente sistema de ecuaciones: ⎧∇f ( x ) + λ1∇g1 ( x ) + ... + λm ∇g m ( x ) = 0 ⎪ g ( x) = 0 ⎪ 1 ⎨ ⎪.......... ..... ⎪⎩ g m ( x ) = 0

Sistema de n+m ecuaciones con n+m incógnitas

Siempre que se cumplan las condiciones de regularidad del teorema de Lagrange, todo punto óptimo es estacionario

Ejemplo de problema en el que no se verifican la condiciones de regularidad ⎛ 2x ⎞ ∇f ( x, y ) = ⎜⎜ ⎟⎟ ⎧⎪min x 2 + y 2 ⎝2y⎠

⎨ ⎪⎩( x − 1) 3 − y 2 = 0

⎛ 2( x − 1) 2 ⎞ ⎟ ∇g ( x, y ) = ⎜⎜ ⎟ ⎝ − 2y ⎠

Puntos estacionarios: ⎧2 x + λ 2( x − 1) 2 = 0 ⎪ ⎨ 2 y + λ ( −2 y ) = 0 ⎪( x − 1) 3 − y 2 = 0 ⎩

Este sistema no tiene solución

¿Significa esto que el problema no tiene ningún mínimo?

Función lagrangiana

1

El problema alcanza un mínimo en el punto (1,0)

0.5

0

-0.5

♦ Función de n+m variables (las n variables de

decisión y los m multiplicadores), definida de la siguiente manera: L( x, λ ) = f ( x) + λ1 g1 ( x) + λ2 g 2 ( x) + ... + λm g m ( x)

-1 -1

-0.5

0

0.5

1

1.5

2

⎛ 2( x − 1) 2 ⎞ ⎛0⎞ ⎟ ⇒ ∇g (1,0) = ⎜⎜ ⎟⎟ ∇g ( x, y ) = ⎜⎜ ⎟ ⎝0⎠ ⎝ − 2y ⎠

♦ Los puntos estacionarios son los puntos

críticos de la función Lagrangiana

No se verifica la condición de regularidad: el conjunto de vectores gradientes de las restricciones no es un conjunto de vectores linealmente independientes en el óptimo

2

Bajo las condiciones de regularidad exigidas, todo óptimo de un problema con restricciones de igualdad es un punto estacionario No todo punto estacionario es óptimo, puede ser también un punto de silla El Teorema de Lagrange establece condiciones necesarias de optimalidad pero no suficientes, salvo en un caso.... EL CASO DE LOS PROBLEMAS CONVEXOS

Condiciones suficientes de optimalidad (caso general) ⎧opt f ( x ) ⎨ ⎩ g i ( x) = 0 i = 1,2,..., m

Dado (x*,λ*) un punto estacionario del problema

Se define: M ( x*) = { p ∈ R n ∇g i ( x*) o p = 0 i = 1,2,..., m}

H x L ( x*, λ *) = Hf ( x*) + λ1* Hg1 ( x*) + ... + λ*m Hg m ( x*) Si se verifica: p H x L( x*, λ*)p > 0 ∀p ∈ M ( x*), p ≠ 0 entonces x* es un mínimo local estricto del problema T

Si se verifica: pT H x L( x*, λ*)p < 0 ∀p ∈ M ( x*), p ≠ 0 entonces x* es un máximo local estricto del problema

Problemas convexos con restricciones de igualdad ⎧min f ( x) ⎨ ⎩ g i ( x ) = 0 i = 1,2,..., m

con f(x) función convexa y gi(x) funciones lineales

Todo punto estacionario es mínimo global

Todo punto estacionario es máximo global

⎧max f ( x ) ⎨ ⎩ g i ( x ) = 0 i = 1,2,..., m

con f(x) función cóncava y gi(x) funciones lineales

H x L( x*, λ *) = Hf ( x*) + λ1* Hg1 ( x*) + ... + λ*m Hg m ( x*) es la matriz hessiana de la función lagrangiana pero restringida a las variables x

{

}

M ( x*) = p ∈ R n ∇g i ( x*) o p = 0 i = 1,2,..., m

representa el espacio asociado al hiperplano tangente a la región factible en el punto x* Ejemplo:

⎧opt x + y ⎨ 2 2 ⎩x + y − 2 = 0

tiene dos puntos estacionarios: • el punto (1,1) con λ = -1/2 y • el punto (-1,-1) con λ = 1/2

⎫⎪ ⎧⎪ ⎛p ⎞ M (1,1) = ⎨( p1 , p2 ) ∇g (1,1)⎜⎜ 1 ⎟⎟ = 2 p1 + 2 p2 = 0⎬ = {( p,− p) p ∈ R} ⎪⎩ ⎪⎭ ⎝ p2 ⎠

Aplicación práctica de las condiciones suficientes ♦ Si HxL(x*,λ*) es definida positiva entonces el

punto corresponde a un mínimo local

punto estacionario (1,1)

Por la propia definición de matriz definida positiva pT HxL(x*,λ*) p>0 para cualquier vector p

♦ Si HxL(x*,λ*) es definida negativa entonces

el punto corresponde a un máximo local Región factible x2+y2=2

M (1,1) = {( p,− p ) p ∈ R}

Por la propia definición de matriz definida negativa pT HxL(x*,λ*) p 0, el valor óptimo del problema disminuye al aumentar

bk .

Si λk = 0 no se dispone de información suficiente para predecir la variación del valor óptimo.

4

Los multiplicadores actúan como un sistema de precios Si una restricción representa disponibilidad de materia prima: Materia prima gastada = Materia prima disponible El multiplicador asociado a la restricción indicará el precio máximo a pagar por una unidad adicional de materia prima

Aproximación de los valores óptimos de problemas modificados ⎧opt f ( x) ⎪ g (x) = b 1 ⎪ 1 ⎪⎪.......... ..... P≡⎨ ⎪ g k ( x) = bk ⎪.......... ..... ⎪ ⎩⎪ g m ( x) = bm − λk =

⎧opt f (x) ⎪ g ( x) = b 1 ⎪ 1 ⎪⎪.......... ..... P∆ ≡ ⎨ ⎪ g k ( x) = bk + ∆ ⎪.......... ..... ⎪ ⎩⎪ g m ( x) = bm

∂VOpt VOpt ( P∆ ) − VOpt ( P ) ≈ ∂bk ∆

VOpt ( P∆ ) ≈ VOpt ( P ) − λk ∆

⇒

Se realiza una modificación en el término de la derecha de una restricción

La aproximación será más fiable cuanto menor sea el incremento aplicado a la restricción

5