Programación no lineal

Pontificia Universidad Católica Escuela de Ingeniería Departamento de Ingeniería Industrial y de Sistemas

Clase 9 • Programaci´n No Lineal o
ICS 1102 • Optimizaci´n o Profesor : Claudio Seebach

Apuntes de Clases • Optimizaci´n • Claudio Seebach o

No Lineal • 1

Programaci´n No Lineal o

1. Optimizaci´n de una funci´n sin restricciones o o (a) Condiciones Necesarias y Suficientes paraextremos (b) M´todos de b´squeda de soluciones e u i. M´todo de Newton e ii. M´todo del Gradiente o de Cauchy e 2. Optimizaci´n de una funci´n con restricciones o o (a) Caso 1: Problema Unidimensional (b) Caso 2: Restricciones de igualdad i. Caso general con restricciones de igualdad ii. Interpretaci´n de los multiplicadores de Lagrange o 3. Restricciones de desigualdad

Apuntes de Clases •Optimizaci´n • Claudio Seebach o

No Lineal • 2

Optimizaci´n de una funci´n sin restricciones o o

P) • f (x) funci´n diferenciable o

min f (x) x ∈ Rn

• x = (x1, x2, ..., xn) es m´ ınimo local si: f (x) ≤ f (x + h) ∀h = (h1, h2, ..., hn) tal que |hj | es suficientemente peque˜o para todo j. n • x es un m´ ınimo local si el valor de f (x) en cada punto del entorno o vecindad de x no esmenor a f (x).

Apuntes de Clases • Optimizaci´n • Claudio Seebach o

No Lineal • 3

Condiciones Necesarias y suficientes para extremos
¯ Teorema 1 (Condici´n necesaria de 1er orden). Si x ∈ Rn es un o → − punto m´nimo local de f (x), entonces debe cumplirse que f (¯) = 0 , ı x es decir, ¯ ∂f (¯1, x2, ..., xn) x ¯ =0 ∀i = 1, ..., n. ∂xi • Esta condici´n es necesaria, pero no suficiente para unm´ o ınimo • Tambi´n la satisfacen otros puntos extremos: e – M´ximos a – Puntos de inflexi´n o

¯ ⇒ Para que x sea un punto m´ ınimo, debe cumplirse una segunda condici´n necesaria. o

Apuntes de Clases • Optimizaci´n • Claudio Seebach o

No Lineal • 4

Condiciones Necesarias para Extremos
¯ Teorema 2 (Condici´n necesaria de 2do orden) Si x ∈ Rn es un punto o m´nimo local de f (x), y f(x) es dos veces diferenciable, entonces debe ı → − cumplirse que f (¯) = 0 (1er orden) y que la matriz Hessiana D2f (¯) x x do sea semidefinida positiva (2 orden).

Apuntes de Clases • Optimizaci´n • Claudio Seebach o

No Lineal • 5

Condiciones Suficientes para Extremos

¯ x Teorema 3 (Condici´n suficiente de 2do orden) Si x verifica: f (¯) = o → − 2 ¯ 0 y D f (¯) es definida positiva,entonces x es un punto m´nimo local x ı estricto de f (¯). x

Mínimo local estricto

Apuntes de Clases • Optimizaci´n • Claudio Seebach o

No Lineal • 6

Derivaci´n Condiciones de Segundo Orden o

¯ • La expansi´n de Taylor de la funci´n objetivo en torno al punto x es: o o ¯ f (x) = f (¯) + (x − x) f (¯) + x x ¯ ¯ (x − x)D2f (¯)(x − x)T x + R2(¯) x 2

¯ ¿qu´ condici´n debe satisfacer x paraser punto m´ e o ınimo local? ¯ • En la vecindad de x, R2(¯) es un orden de magnitud m´s peque˜o x a n do que el t´rmino de 2 orden ⇒ podemos ignorarlo para un an´lisis de e a optimalidad local. • En un punto m´ ınimo, el gradiente de la funci´n en el punto debe ser o nulo.

Apuntes de Clases • Optimizaci´n • Claudio Seebach o

No Lineal • 7

Derivaci´n Condiciones de Segundo Orden o
•Para que f (¯) sea menor a la funci´n objetivo evaluada en cualquier x x o ¯ en la vecindad de x, debe suceder que ¯ ¯ (x − x)D2f (¯)(x − x)T x f (¯) ≤ f (x) = f (¯) + x x + R2(x). 2 • Es decir: ¯ ¯ (x − x)D2f (¯)(x − x)T x (∆x)D2f (¯)(∆x)T x = ≥0 2 2 • Esto equivale a que la matriz D2f (¯) sea semidefinida positiva: x ∆xD2f (¯)∆xT ≥ 0, x x ∆xD2f (¯)∆xT > 0, ∀∆x • Si es definida positiva esto se cumpleestrictamente: ∀∆x

Apuntes de Clases • Optimizaci´n • Claudio Seebach o

No Lineal • 8

Ejemplo de Problema No Lineal Irrestricto

Ejemplo 1 Considere el problema P ) min −2x1x2 − 2x2 + x2 + 2x2 1 2 s.a. (x1, x2) ∈ R2
0 0.5 1 4 1.5 2

2

0

0

0.5

1

1.5

2

Apuntes de Clases • Optimizaci´n • Claudio Seebach o

No Lineal • 9

Ejemplo de Problema No Lineal...