Matematica

Métodos Clásicos de Optimización para Problemas No-Lineales sin Restricciones
Dr. Gonzalo Hernández Oliva
UChile - Departamento de Ingeniería Matemática 07 de Mayo 2006

Abstract En este apunte veremos una breve descripción de la teoría y métodos que se utilizan para enfrentar problemas de optimización no-lineales sin restrcciones. La no presencia de restricciones puede ser vista en uncomienzo como una grave limitación, sin embargo, la razón del porque dedicamos tiempo a resolver este tipo de problemas desde el punto de vista de la optimización, es que existe toda una metodología que permite tratar problemas de optimización no-lineales con restriccciones como problemas de optimización no-lineales sin restricciones: Los Métodos de Penalización.

1

Introducción

Nos interesaresolver el problema siguiente: Dada f : Rn → R, campo escalar 2 veces diferenciable con continuidad, encontrar x ∈ Rn , solución de:
x∈Rn

min f (x)

(POSR)

Encontrar una solución de este problema corresponde a encontrar un punto x que satisface: f (x) ≤ f (x) ∀x ∈ Rn Este punto x se denomina mínimo global de f sobre Rn . Desde un punto de vista práctico, encontrar el mínimo o máximo globalde una función no-lineal cualquiera es un problema abierto en matemáticas. Los métodos existentes sólo obtienen mínimo locales.

1

Definición 0: Un punto x es un mínimo local de f en Rn si existe r > 0 talque: f (x) ≤ f (x) para kx − xk ≤ r

El mínimo global de f será el mínimo local de menor valor de la función objetivo.

Figura 1. Mínimos locales de una función de 2 variables

Desdeun punto de vista teórico, las condiciones más generales para que x sea mínimo local de f son las siguientes: Teorema 1: Un punto x es mínimo local de f si se verifican las siguientes condiciones: 1) x es un punto estacionario de f ⎢ ⎢ → − ∇f (x) = 0 ⇐⇒ ⎢ ⎢ ⎣ ⎡
∂ 2 f (x) ∂x2 1 ∂ 2 f (x) ∂x1 ∂x2

⎡

∂f (x) ∂x1 ∂f (x) ∂x2

. . .

⎤

∂f (x) ∂xn

2) La matriz hessiana ∇2 f (x) de f en x esdefinida positiva: ⎢ ⎢ ⎢ ∇2 f (x) = ⎢ ⎢ ⎣
∂ 2 f (x) ∂x1 ∂x2 ∂ 2 f (x) ∂x2 2

⎥ ⎢ ⎥ ⎢ ⎥=⎢ ⎥ ⎣ ⎦

⎡

0 0 . . . 0

⎤ ⎥ ⎥ ⎥ ⎦ ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦

··· ··· .. . ···

∂ 2 f (x) ∂x1 ∂xn ∂ 2 f (x) ∂x2 ∂xn

. . .
∂ 2 f (x) ∂x1 ∂xn

. . .

. . .
∂ 2 f (x) ∂x2 n

∂ 2 f (x) ∂x2 ∂xn

2

Dem: Se demuestra mediante la aproximación de Taylor de 2◦ Orden de la función f en torno a x.¥Entonces, para obtener el mínimo local se debe resolver un sistema de ecuaciones no lineales, en general complejo. Surge de esta forma la necesidad de aplicar métodos numéricos. Consideraremos métodos numéricos llamados de descenso, que pueden ser clasificados en 3 grupos: ⎧ ⎪ ⎪ ⎪ ⎪ Primer Orden ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ Métodos Descenso ⎪ Segundo Orden ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ Cuasi-Newton ⎧ ⎨ Método del Gradientey Variedades Método del Gradiente Conjugado ⎩ Método de Fletcher-Reeves ½ ½ Métodos de Newton Variedades

DFP: Davidon - Fletcher - Powell BFGS

Todos los métodos numéricos que se utilizan en la actualidad reducen este problema a una secuencia de problemas unidimensionales.

2

Método de Gradiente o de Cauchy

Sea f : Rn → R diferenciable. La derivada direccional de f en la dirección d∈ Rn está dada por: Df (x; d) = ∇f (x)t d Para obtener la dirección de máximo descenso de la función f en un punto x ∈ Rn tal que ∇f (x) 6= 0, se debe resolver el problema:
d∈Rn

min ∇f (x)t d kdk2 = 1

La solución de este problema es: d=− ∇f (x) k∇f (x)k

Y por lo tanto la dirección de máximo descenso de la función f es: d = −∇f (x) 3

Definición 2: El vector d ∈ Rn es una dirección dedescenso de f , función diferenciable, en el punto x ∈ Rn si: ∇f (x)t · d < 0 ⇐⇒ (−∇f (x))t · d > 0 A través del método del gradiente, se busca definir una sucesión de puntos que tenga la dirección de máximo descenso de la función f . Definición 3: Las curvas de nivel θ de f están definidas por: ϕ(f, θ) = {x ∈ Rn tal que: f (x) = θ} Lema 4: Sea d ∈ Rn una dirección de descenso de la función f en el...