otimizacion

IV SIMPOSIO CHILENO DE MATEMATICA
Cursillo

Introducci´n a la programaci´n matem´tica
o
o
a
Roberto Cominetti y Alejandro Jofr´
e
Departamento de Ingenier´ Matem´tica
ıa
a
Universidad de Chile

Resumen.
En estas notas presentamos los elementos b´sicos de la teor´ de la opa
ıa
timizaci´n para problemas de programaci´n matem´tica: minimizaci´n de
o
o
a
o
funciones definidas enIRn sujeto a un n´mero finito de restricciones de igualu
dad y desigualdad.
Las notas est´n organizadas como sigue: en la secci´n 1 revisamos r´a
o
a
pidamente los criterios de existencia de soluciones ´ptimas, mientras que
o
en la secci´n 2 investigamos las condiciones necesarias y suficientes (tanto
o
de primer como de segungo orden) para que un punto dado sea soluci´n
o
´ptima. En lasecci´n 3 estudiamos las propiedades de diferenciabilidad del
o
o
valor ´ptimo y de las soluciones ´ptimas de un problema de optimizaci´n que
o
o
o
depende de un par´metro.
a
Tanto en la secci´n 2 como en la secci´n 3 presentamos, adem´s de los
o
o
a
resultados cl´sicos, una serie de extensiones recientes de la teor´
a
ıa.

1

1. Existencia de m´
ınimos
En los cursos dec´lculo se prueba que una condici´n suficiente para que
a
o
una funci´n alcance su m´ximo y m´
o
a
ımino sobre un compacto es la continuidad de ´sta. Sin embargo, como veremos ahora, una semicontinuidad
e
ser´ suficiente.
a
Definici´n 1.1 Una funci´n f : D ⊂ IRn → IR se dir´ semicontinua infeo
o
a
rior (s.c.i.) en x0 ∈ D si para toda sucesi´n xk → x0 tal que {f (xk )} es
o
convergente, setiene
lim f (xk ) ≥ f (x0 ).
k

Equivalentemente, f es s.c.i. en x0 si para todo λ < f (x0 ) existe una vecindad
B(x0 , δ) tal que
λ < f (x)
∀x ∈ B(x0 , δ).
Diremos que f es semicontinua inferior si lo es todo punto.
Ejemplo.

Proposici´n 1.2
o
1) f es continua en x0 si y solo si f y −f son s.c.i. en x0 .
2) f : IRn → IR es s.c.i. si y solo si el ep´
ıgrafo de f ,
epi(f ) := {(x, α) :f (x) ≤ α}

es un conjunto cerrado en IRn+1 .

2

Teorema 1.3 Sea f : F ⊂ IRn → IR s.c.i. con F compacto. Entonces f
alcanza su m´
ınimo, es decir, existe x0 ∈ F tal que f (x0 ) = inf{f (x) : x ∈ F }.
Demostraci´n. Sea m := inf{f (x) : x ∈ F } y escojamos una sucesi´n (xk ) ∈
o
o
F tal que m = limk f (xk ). Como F es compacto, pasando eventualmente a
una subsucesi´n podemos suponerque xk converge a un punto x0 ∈ F . De
o
la s.c.i. en x0 se sigue que
m = lim f (xk ) ≥ f (x0 )
k

y por lo tanto m = f (x0 ) = min{f (x) : x ∈ F }. 2
Cuando el conjunto factible F no es compacto se puede mostrar la existencia de un m´
ınimo para el problema (P ) si suponemos que la funci´n es
o
inf-acotada, es decir
lim f (x) = +∞,
x →∞

ya que en este caso los conjuntos de nivel {x∈ IRn : f (x) ≤ λ} son compactos
para cada λ ∈ IR.

2. Condiciones de optimalidad
En esta parte veremos condiciones necesarias y suficientes para que un
punto x0 sea m´
ınimo local del problema
(P )

min{f (x) : x ∈ F }

donde f : IRn → IR y F ⊂ IRn . En el caso F = IRn , si x0 ∈ F es un m´
ınimo
local existe δ > 0 tal que
f (x0 ) ≤ f (x)

∀x ∈ B(x0 , δ)

y por lo tanto, paracada d ∈ IRn y t > 0 peque˜o se tendr´
n
a
(1)

f (x0 + td) − f (x0 ) ≥ 0.

Si asumimos que f es derivable en x0 , dividiendo por t y pasando al l´
ımite
cuando t ↓ 0 se deduce
f (x0 ) d ≥ 0,
3

y como d es arbitrario concluimos la condici´n necesaria de optimalidad para
o
el caso irrestricto:
f (x0 ) = 0.
Sin embargo cuando tenemos la restricci´n x ∈ F y x0 se encuentra en
o
lafrontera de F , el punto x0 + td no est´ necesariamente en F , por lo que
a
la desigualdad (1) no es cierta para cualquier direcci´n d ∈ IRn . Esto nos
o
motiva a introducir el conjunto de direcciones por las cuales nos movemos en
F a partir del punto x0 .

Definici´n 2.1 Se define el cono tangente al conjunto F en el punto x0
o
como
TF (x0 ) := {d ∈ IRn : ∃tk → 0+ , dk → d tal que x0 +...