Volumen Producción Panificadora

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

Nosinteresa resolver el problema siguiente:
Dada f : Rn → R, campo escalar 2 veces diferenciable con continuidad,
encontrar x ∈ Rn , solución de:
min f (x)

x∈Rn

(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ínimoo máximo global de 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 de2 variables

Desde un 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 ⇐⇒ ⎢
⎢
⎣

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

.
.
.

∂f (x)
∂xn

⎤

⎡

⎥ ⎢
⎥ ⎢
⎥=⎢
⎥ ⎣
⎦

⎤

0
0
..
.

⎥
⎥
⎥
⎦

0

2) La matriz hessiana ∇2 f (x) de f en x es definida positiva:
⎡

⎢
⎢
⎢
∇2 f (x) = ⎢
⎢
⎣

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

.
.
.

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

.
.
.

∂ 2 f (x)
∂x1 ∂xn

2

∂ 2 f (x)
∂x2 ∂xn

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

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

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

⎤
⎥
⎥
⎥
⎥
⎥
⎦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:
⎧
⎪
⎪
⎪
⎪ PrimerOrden
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
Métodos Descenso
⎪ Segundo Orden
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩ Cuasi-Newton

⎧
⎨ Método del Gradiente y 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 unasecuencia 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:
min ∇f (x)t d

d∈Rn

kdk2 = 1

La solución de este problemaes:
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 de descenso 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...