Programación no lineal

Tema 12. Optimización con restricciones de  desigualdad
1. El problema básico de programación no lineal 1.1 Geometría del problema básico de programación no lineal 1.2 Condiciones necesarias de Kuhn y Tucker para el     problema básico 1.3 Restricciones de no negatividad. Condiciones de Kuhn y  Tucker  2. El problema general de programación no lineal  2.1 Formulación estándar del problema 2.2Programas cóncavos  2.3 Condiciones de Kuhn y Tucker y

El problema básico de programación no lineal

Max f( M f(x, y) ) s.a: g(x, y) ≤ b
f(x, f(x y) y g(x y) de clase C1 g(x,

[P]

Maximización: Restricción del tipo

≤

Condiciones necesarias (Kuhn- Tucker) (esquema de l d ( d la demostración) t ió ) Transformamos el problema P en un problema de Lagrange añadiendo una variabledenominada de holgura Máx. f(x, ) Má f( y) s.a g(x, y) ≤b Máx. f(x, y) s.a g(x, y) + u2 = b

⎡b − u2 − g(x, y)⎤ L(x, y, u, λ ) = f(x, y) + λ ⎣ ⎦
Por el teorema de Lagrange, si (x*, y*, u*) es solución local del problema y y si ∇g( x*,y*,u*) ≠ ( 0,0,0) ( (condición de regularidad) g ) existen λ * y u* tales que

∇L(x*, y*, u*, λ *) = (0, 0, 0, 0)

Sistema de condiciones necesarias:
∂f(x,y)∂g(x,y) −λ =0 ∂x ∂x ∂f( ) f(x,y) ∂g(x,y) ( ) −λ =0 ∂y ∂y −2 λ u = 0 ↔ λ u = 0 b − u2 − g(x,y) = 0 ↔ g(x,y) + u2 = b

Si eliminamos la variable de holgura obtenemos:
∂f(x y) f(x,y) ∂g(x,y) g(x y) −λ =0 ∂x ∂x ∂f(x,y) ∂g(x,y) −λ =0 ∂y ∂y g(x,y) ≤ b λ [b − g(x,y)] = 0

Signo del multiplicador Supuesto q b p p que puede variar

df(x*,y*) λ* = db

Si (x* y*) resuelve P p ( y) para λ * y b aumenta( (disminuye), y ), entonces

λ* O bien ( * y*) sigue siendo solución y entonces λ* bi (x* *) i i d l ió O bien el objetivo aumenta (disminuye) y entonces

=0 λ* > 0

Concluimos:

λ* ≥ 0

Signo del multiplicador

g(x, y) ≤ b

(x*, y*)

f(x, y) = k

g(x, y) = b Figura 2

Signo del multiplicador

g(x, y) ≤ b
(x*, y*) f(x, y) = k

Figura 3

g(x, y) = b

Teorema deKuhn-Tucker. Sea el problema P Máx. f(x, y) con f y g de clase C1 s.a: g(x, y)≤ b

L(x, y, λ ) = f(x, y) + λ [b − g(x, y)]
Si (x*, y*) es solución de P y si se cumple la regularidad, existe un λ * único de modo que:
∂f( * *) f(x*,y*) ∂g(x*,y*) ( * *) −λ* =0 ∂x ∂x ∂f(x* y*) f(x*,y*) ∂g(x* y*) g(x*,y*) −λ* =0 ∂y ∂y g(x y*) g(x*,y ) ≤ b λ * [b − g(x*,y*)] = 0 λ* ≥ 0

Condición de regularidad ode cualificación de g las restricciones. C1 C j Conjunto f ibl convexo y existe un punto que cumple factible i l todas las restricciones con desigualdad estricta (Slater). C2 Todas las restricciones son lineales

El problema con restricciones de no negatividad. p g Condiciones necesarias (Kuhn –Tucker). (esquema de la demostración) 1. Escribimos el problema en forma estándar

Max f ( x, y )⎫ Max f ( x, y ) ⎪ s.a g ( x, y ) ≤ b ⎪ s.a g ( x, y ) ≤ b ⎬⇔ −x ≤ 0 x≥0 ⎪ ⎪ y≥0 −y ≤ 0 ⎭

2. Añadimos variables de holgura

Max f ( x, y ) s.a g ( x, y ) + u 2 = b − x + v2 = 0 − y + w2 = 0
3. D fi i Definimos la función lagrangiana l f ió l i

L(x, y, u, λ, μ, δ) = f(x, y) + λ ⎡b − u2 − g(x, y)⎤ + μ[x − v 2 ] + δ[y − w 2 ] ⎣ ⎦

4. Calculamos el gradiente de la lagrangiana y loigualamos al
vector nulo: t l

L(x, y, u, λ, μ, δ) = f(x, y) + λ ⎡b − u2 − g(x, y)⎤ + μ[x − v 2 ] + δ[y − w 2 ] ⎣ ⎦

∂f(x,y) ∂g(x,y) −λ +μ =0 ∂x ∂x ∂f(x,y) ∂g(x,y) −λ +δ=0 ∂y ∂y b − u2 − g(x,y) = 0 ↔ g(x,y) + u2 = b x − v 2 = 0 ↔ −x + v 2 = 0 y − w 2 = 0 ↔ −y + w 2 = 0 −2 λ u = 0 −2μv = 0 −2δw = 0

5. Por último, eliminamos las variables de holgura, como en el caso anterior, anterior y obtenemoslas siguientes condiciones necesarias

∂f(x,y) ∂g(x,y) −λ ≤0 ∂x ∂x ∂f(x,y) ∂g(x,y) −λ ≤0 ∂y ∂y g(x,y) ≤ b x ≥ 0;y ≥ 0 λ≥0 λ [b − g(x,y)] = 0 g( ,y) ∂g(x,y) ⎤ ⎡ ∂f(x,y) x⎢ −λ ⎥=0 ∂x ⎦ ⎣ ∂x ⎡ ∂f(x,y) ∂g(x,y) ⎤ y⎢ −λ ⎥=0 ∂y ⎦ ⎣ ∂y

5. Condiciones suficientes

Estudiaremos sólo problemas de programación cóncava: Maximización de una función cóncava en un conjunto factible convexo más una...