Optimización Clásica - us

Optimización Clásica

Yolanda Hinojosa

Contenido

• Optimización no lineal sin restricciones. Condicionesnecesarias y suficientes de óptimo

• Optimización no lineal con restricciones de igualdad.Condiciones necesarias de óptimo

• Análisis de sensibilidad. Interpretación de losmultiplicadores de Lagrange

• Aplicaciones

Ejemplo

En una planta industrial funcionan dos procesos productivos entre los que espreciso repartir un único input. Sean x e y las cantidades de dicho inputasignadas a cada uno de ambos procesos. Se estima que el beneficio totalobtenido por la planta viene dado por la funciónB(x, y) = 200 − (x − 5)2 − (y − 5)2 u.m.

1. ¿Qué cantidad de input, repartido entre x e y maximiza el beneficio?.Hállese dicho beneficio.

2. Si se impone que el consumo de input debe ser exactamente de 6unidades, ¿Qué cantidades de x e y necesitaremos ahora paramaximizar el beneficio?

3. Estúdiese el apartado anterior en el caso general de que nos imponganun consumo de k unidades. Hágase la interpretación económica de losresultados.

4. Si en el caso k=6, le ofrecen a la planta adquirir una unidad nueva deinput por 7 u. m. ¿Debe la planta adquirirla o no?

Extremos de funciones de varias variables

Objetivo: Encontrar de entre todas las soluciones factibles aquellas para las que lafunción objetivo es óptima (óptimos)

Máximo

0 2

4 6

8 10 0

2

4

6

8

10

160

180

200

0 2

4 6

8 10

Curvas de nivel

0 2 4 6 8 10

0

2

4

6

8

10

Extremos de funciones de varias variables

Condición necesaria de 1er orden de óptimo local: Sea f : D ⊆ Rn → R diferenciable

en x∗ ∈ int(D). Si x∗ es un óptimo local de f entonces ∇f(x∗) = 0.

A los puntos que anulan el gradiente se les llama puntos críticos o estacionarios.

Los puntos críticos pueden ser máximos, mínimos o puntos de silla.

x∗ es un punto de silla de f si es un punto crítico y ∀B(x∗, r) ⊆ D

∃ x1, x2 ∈ B(x∗, r) tales que f(x1) > f(x∗) y f(x2) < f(x∗).

Ejemplo: (0, 0) es un punto de silla de la función f(x, y) = x2 − y2

Punto de Silla

- 10 - 5

0 5

10 - 10

- 5

0

5

10

- 100 - 50 0

50 100

- 10 - 5

0 5

10

Curvas de nivel

-10 -5 0 5 10

-10

-5

0

5

10

Condiciones de Optimalidad Global

1 Dada f : S ⊆ Rn → R una función convexa definida en un conjunto convexoS ⊆ Rn se verifica que:

• Si x∗ ∈ S es un mínimo local de f , entonces x∗ es un mínimo global.• El conjunto de todos los mínimos de f es un conjunto convexo.

(Si f es cóncava se obtiene un resultado análogo para máximos).

2 Si f : S ⊆ Rn → R es una función convexa y diferenciable en int(S) entoncestodos los puntos críticos de f (en caso de que existan) son mínimos globales.

3 Si f : S ⊆ Rn → R es una función cóncava y diferenciable en int(S) entoncestodos los puntos críticos de f (en caso de que existan) son máximos globales.

Nota: Los puntos críticos son puntos interiores del dominio de definición . En algunoscasos para buscar los máximos y mínimos de una función se hace necesariocomprobar qué ocurre en los puntos de la frontera que pertenezcan al dominio de lafunción (en caso de que existan).

Ejemplos: Estudiar la existencia de máximos y mínimos de las funcionesf (x) =

√x, f (x, y) =

√x + y.

Extremos de funciones de varias variables

Condiciones de 2 o orden

Hipótesis: Sea f : D ⊆ Rn → R, dos veces diferenciable con continuidad en un punto

crítico, x∗ ∈ int(D). Por tanto:

(Fórmula de Taylor) f(x∗ + h) = f(x∗) + ∇f(x∗)h +1

2htHf(x∗)h + R(x∗, h)

Si denotamos por q(h) = ht Hf(x∗) h ∀h ∈ Rn la forma cuadrática asociada al

hessiano en x∗, se tiene que: signo(f(x∗ + h) − f(x∗)) = signo(q)

Condición suficiente de 2o orden:

Si q es definida positiva, entonces x∗ es un mínimo relativo estricto.

Si q es definida negativa, entonces x∗ es un máximo relativo estricto.

Si q es indefinida, entonces x∗ es un punto de silla.

Nota: Si q es semidefinida positiva, entonces x∗ es un mínimo ó un punto de silla.Si q es semidefinida negativa, entonces x∗ es un máximo ó un punto de silla.

Ejemplo inicial: 1. max B(x, y) = 200 − (x − 5)2 − (y − 5)2

Metodos Numéricos para el cálculo de óptimos

Dado el problema: minx∈Rn f (x) se dice que d ∈ Rn es una dirección dedescenso de la función f en un punto x ∈ Rn si:

f (x + λd) < f (x) ∀λ ∈ R arbitrariamente pequeño

1 Algoritmo:

• Paso 0. Determinar un punto inicial x0.

• Paso k. Dado xk y una dirección de descensodk, calcular la longitud de paso λk, p.ej.,como solución de minλ f (xk + λdk).

• Paso k + 1. Considerar xk+1 = xk + λkdk.

• Criterios de parada:

• ||∇f (xk)|| < ε.• |f (xk+1)− f (xk)| < ε.• |xk+1 − xk| < ε.

Extremos bajo restricciones de igualdad

Sean f, gi : D ⊆ Rn → R, bi ∈ R, (i = 1, . . . , m < n). El problema es:

Optimizar f(x)

s.a. g1(x) = b1

g2(x) = b2...

gm(x) = bm

9>>>>>>>>>=>>>>>>>>>;Óptimo condicionado

0 2

4 6

8 10 0

2

4

6

8 10

160

180

200

0 2

4 6

8 10

Resolución:

1a forma: Si es posible, despejar m variables en función de las n − m restantes.

Ejemplo inicial: 2.max B(x, y) = 200 − (x − 5)2 − (y − 5)2

s. a. x + y = 6

Nota: Esto no siempre es posible y además no permite realizar un estudio postoptimal.

2a forma: Método de los multiplicadores de Lagrange.

Extremos bajo restricciones de igualdad

Condiciones de 1 er ordenf : R

2 → R

0 2 4 6 8 10 0

2

4

6

8

10

g

f ∇

∇

Si x∗ es un óptimo local condicionado y ∇g1(x∗), . . . ,∇gm(x∗) son linealmenteindependientes (condiciones de regularidad), entonces existen λ1, . . . , λm ∈ R,denominados multiplicadores de Lagrange , tales que

∇f(x∗) = λ1∇g1(x∗) + · · · + λm∇gm(x∗)

Extremos bajo restricciones de igualdad

Función de Lagrange: L(x, λ) = f(x) + λ1 (b1 − g1(x)) + · · · + λm (bm − gm(x)).

A λ1, . . . , λm ∈ R, se les llama multiplicadores de Lagrange

Propiedades:

Si x es un punto factible del problema condicionado entonces L(x, λ) = f(x).

∇L(x, λ) =

0BBBBBB�

∇f(x) − λ1∇g1(x) − · · · − λm∇gm(x)

b1 − g1(x)

...

bm − gm(x)

1CCCCCCA.

Por tanto, si ∇L(x, λ) = 0 entonces, x es un punto factible del problemacondicionado y además ∇f(x) = λ1∇g1(x) + · · · + λm∇gm(x).

Teorema de los multiplicadores de Lagrange (Condición necesaria de 1er orden):Sean f, gi : D ⊆ R

n → R de clase C1 en int(D) (i = 1, . . . , m < n).Si x∗ ∈ int(D) es un óptimo local condicionado y ∇g1(x∗), . . . ,∇gm(x∗) sonlinealmente independientes, entonces existe λ∗ = (λ∗

1, . . . , λ∗m) tal que (x∗, λ∗) es un

punto crítico de la función de Lagrange (∇L(x∗, λ∗) = 0)

Condiciones de Optimalidad Global bajo restricciones deigualdad

Sean f , gi : D ⊆ Rn → R, bi ∈ R, ( i = 1, . . . ,m < n) funciones C1 en int(D). Dado elsiguiente problema :

Optimizar f (x)s.a. g1(x) = b1

g2(x) = b2...

gm(x) = bm

(I)

se verifica que:

1 Supongamos que (I) es un problema de minimización. Si f es una funciónconvexa en D y las funciones gi ∀i = 1, . . . ,m son funciones lineales, entoncescualquier punto que satisfaga las condiciones necesarias de primer orden(∇L(x, λ) = 0) es un mínimo global de (I).

2 Supongamos que (I) es un problema de maximización. Si f es una funcióncóncava en D y las funciones gi ∀i = 1, . . . ,m son funciones lineales, entoncescualquier punto que satisfaga las condiciones necesarias de primer orden(∇L(x, λ) = 0) es un máximo global de (I).

3 Teorema de Weierstrass: Si f : Rn → R es una función continua y la regiónfactible es un conjunto cerrado y acotado, entonces f tiene un mínimo y unmáximo global.

Interpretación de los multiplicadores de Lagrange

¿Cómo varía el valor óptimo de la función objetivo al incrementar en una unidad eltérmino independiente de las restricciones (cantidad de recurso)?

Sea x∗ una solución óptima del problema condicionado, λ∗ = (λ∗1, · · · , λ∗

m) el

conjunto de multiplicadores asociados y sea f∗ = f(x∗) el valor óptimo de la funciónobjetivo. Estos valores dependen del vector de recursos o términos independientes delas restricciones b = (b1, · · · , bm): x∗ = x∗(b), f∗ = f∗(b) = f(x∗(b)).Se verifica que:

∂f(x∗(b))

∂bi

= λ∗i

∀ 1 ≤ i ≤ m

A λ∗i

se le conoce con el nombre de precio sombra o precio marginal y representala cantidad que estaríamos dispuestos a pagar por una unidad más de recurso.

Ejemplo inicial:

Apartado 3.max B(x, y) = 200 − (x − 5)2 − (y − 5)2

s.a. x + y = k

Punto óptimo: (x∗, y∗, λ∗) = (k

2,k

2, 10 − k)

Apartado 4. k = 6, coste de la unidad adicional de input= 7 u.m.