Programacion lineal

CAP´ ITULO 2 ´ PROGRAMACION NO LINEAL

Programaci´n No Lineal o

in34a - Optimizaci´n o

Cap´ ıtulo 2: Programaci´n No Lineal o
m´ (´ m´x)f (x) ın o a s.a. x ∈ S ⊆ Rn No existe un m´todo que permita resolver cualquier problema de programaci´n no e o lineal. Los m´todos existentes s´lo resuelven algunos tipos de problemas. Veremos e o conceptos y herramientas que proveen el marco te´ricopara la resoluci´n de problemas o o con ciertas condiciones. Conceptos B´sicos a 1. Conjuntos Convexos: Dados los vectores x1, x2, . . . , xk ∈ Rn se dice que el vector y es una combinaci´n o lineal convexa de x1, x2, . . . , xk si:
k k

y=
i=1

αixi, con αi ≥ 0,
i=1

αi = 1

Programaci´n No Lineal o

1

in34a - Optimizaci´n o

Conceptos B´sicos a
Definici´n: o Un conjunto S ⊆ Rnse dice convexo si el segmento de recta que une 2 puntos cualesquiera de S est´ totalmente contenido en S. O sea, ∀x1; x2 ∈ S se tiene que: a λx1 + (1 − λ)x2 ∈ S, ∀λ ∈ [0, 1] Esto corresponde a una combinaci´n lineal convexa de x1, x2 o Ej:

Programaci´n No Lineal o

2

in34a - Optimizaci´n o

Conceptos B´sicos a
Teorema: Sean S1, S2, . . . , Sp conjuntos convexos. Entonces S = oObservaci´n: Por convenci´n el conjunto φ es convexo. o Ej: El conjunto S = {(x1, x2)/x1 − 3x2 ≤ 6, x1 + 2x2 ≥ 4, 2x1 − 2x2 ≥ −6} es convexo (es la intersecci´n de los 3 semiespacios definidos por las respectivas desigualdades o lineales).
n i=1 Si

tambi´n es convexo. e

Programaci´n No Lineal o

3

in34a - Optimizaci´n o

Conceptos B´sicos a
2. Funciones Convexas: Definici´n: o Sea f : S ⊆Rn −→ R una funci´n escalar, donde S es un conjunto convexo no o vac´ f se dice convexa en S si: ıo. f (λx1 + (1 − λ)x2) ≤ λf (x1) + (1 − λ)f (x2), ∀x1, x2 ∈ S, ∀λ ∈ [0, 1] Interpretaci´n Geom´trica: o e Una funci´n es convexa cuando su interpolaci´n lineal f entre 2 puntos no subestio o ma el valor de la funci´n. o

Programaci´n No Lineal o

4

in34a - Optimizaci´n o

Conceptos B´sicos aDefinici´n: o La funci´n f es estrictamente convexa en S si la desigualdad anterior es estricta o para todo x1 = x2 ∈ S y ∀λ ∈ (0, 1). Ej:

Estrictamente Convexa: f (x, y) = x4 + y 2 Convexa: f (x) = sx
Programaci´n No Lineal o 5

in34a - Optimizaci´n o

Conceptos B´sicos a
Teorema: Sea la funci´n f ∈ C 1. Entonces f es convexa en el conjunto convexo S sii: o f (y) ≥ f (x) + f (x)T (y −x), ∀x, y ∈ S

Interpretaci´n Geom´trica: o e Dado un cierto valor de x, la funci´n f (y) = f (x) + f (x)T (y − x) corresponde a o la aproximaci´n lineal de f basada en la derivada direccional de f en x. o El teorema establece que esta aproximaci´n lineal nunca supera el valor de una o funci´n convexa. o

Programaci´n No Lineal o

6

in34a - Optimizaci´n o

Conceptos B´sicos a
Ej: f (x)= (x − 3)2 + 2 f (y) = (x − 3)2 + 2 + 2(x − 3)(y − x) f (y) = −x2 + 2xy − 6y + 11 + y 2 − y 2 f (y) = −(x − y)2 + (y − 3)2 + 2 ⇒ f (y) ≤ (y − 3)2 + 2 = f (y), ∀x, y ∴ f convexa por el teorema Teorema: Sea f ∈ C 2 y sea S ⊆ Rn un conjunto convexo, abierto y no vac´ ıo. Entonces f es convexa si y s´lo si Hf (x) es semidefinida positiva en todo S. o Recordemos como se calcula la matriz hessiana: Seaf (x, y) ∈ C 2, la matriz hessiana Hf (x, y) viene dada por:   
∂ 2f ∂x2 ∂ 2f ∂y∂x ∂ 2f ∂x∂y ∂ 2f ∂y 2



Programaci´n No Lineal o

7

in34a - Optimizaci´n o

Conceptos B´sicos a
Teorema: Sea f ∈ C 2 ⇒
∂ 2f ∂x∂y ∂ 2f ∂y∂x , ∀x, y.

=

Corolario: f ∈ C 2 ⇒ Hf (x) es sim´trica. e

Programaci´n No Lineal o

8

in34a - Optimizaci´n o

Repaso de Matrices DefinidasPositivas
Definici´n: o Sea A ∈ Rn×n una matriz sim´trica. Se dice que A es definida positiva si la forma e cuadr´tica xT Ax es positiva para todo vector x diferente al vector nulo, es decir, si a xT Ax > 0, ∀x = 0. Definici´n: o A es semidefinida positiva si xT Ax ≥ 0, ∀x = 0. Definici´n: o A es definida negativa si xT Ax < 0, ∀x = 0 Definici´n: o A es semidefinida negativa si xT Ax ≤ 0, ∀x = 0 Observaci´n:...