Apunte 2ed
Apunte 2ed
A PUNTE M AT 279
curso obligatorio de la carrera
I NGENIER ÍA C IVIL M ATEM ÁTICA
Departamento de Matemática
Diciembre 2021
Prefacio
Este apunte ha sido redactado con la finalidad de proveer a estudiantes de los programas de In-
genierı́a de la Universidad Técnica Federico Santa Marı́a con herramientas básicas de Optimización
No Lineal1 . Estas notas cubren aspectos generales de la optimización en espacio abstracto, ası́ como
resultados más especı́ficos para espacios vectoriales normados. Los contenidos cubren resultados de
existencia de soluciones, caracterizaciones de estas, criterios analı́ticos para encontrarlas (condicio-
nes de optimalidad) y también métodos iterativos para aproximar soluciones óptimas.
Las notas aquı́ presentadas fueron organizadas de forma tal de cubrir los contenidos del curso
Optimización No Lineal (MAT279) que imparte regularmente el Departamento de Matemática de la
Universidad Técnica Federico Santa Marı́a. Este curso es parte de la malla de la carrera Ingenierı́a
Civil Matemática, y como tal requiere herramientas abstractas de Análisis. Sin embargo, todos los
resultados expuestos en el apunte han sido escritos de forma general, por lo cual cualquier estudiante
de ingenierı́a con un conocimiento básico en Análisis en Rn y Álgebra Lineal puede comprender el
material expuesto en estas notas.
Esta es la segunda versión del apunte, y pese a que muchos errores tipográficos fueron corregidos,
aún pueden quedar algunos. Todo posible error que el lector pueda encontrar en las notas es de nuestra
exclusiva responsabilidad. Agradecemos hacer llegar comentarios y observaciones a cualquiera de
los autores.
1 El término No Lineal debe ser entendido en este contexto como No Necesariamente Lineal.
I
Notación básica
Conjuntos básicos
R Números Reales.
Rn Conjunto de n-tuplas de Números Reales.
R ∪ {+∞} Números Reales (superiormente) extendidos.
N Números Naturales
Mn×m (R) Matrices a coeficientes reales de dimensión n × m
Sn Matrices reales simétricas de dimensión n
Sn+ (R) Matrices reales simétricas semi-definidas positivas de dimensión n
Sn++ (R) Matrices reales simétricas definidas positivas de dimensión n
Conjuntos Genéricos
X Espacio ambiente
S Conjunto de restricciones
BX (x, r) Bola cerrada de radio r > 0 y centro x ∈ X de un espacio métrico (X, d)
BX Bola cerrada unitaria de un espacio vectorial normado (X, k · k)
int S interior de S
S adherencia de S
Conjuntos Especiales
dom( f ) Dominio efectivo de f : X → R ∪ {+∞}
epi( f ) Epı́grafo de f : X → R ∪ {+∞}
Γγ ( f ) Conjunto de subnivel de f : X → R ∪ {+∞} y parámetro γ ∈ R
arg mı́nX ( f ) Conjunto de mı́nimos de f : X → R ∪ {+∞}
Normas
s y productos internos
n
|x| = ∑ xi2 Norma Euclideana de x = (x1 , . . . , xn ) ∈ Rn
i=1
k·k Norma de un espacio vectorial arbitrario X
n
x> y = ∑ xi yi Producto interno de x = (x1 , . . . , xn ) ∈ Rn e y = (y1 , . . . , yn ) ∈ Rn
i=1
h·, ·i Producto interno de un espacio Euclideano arbitrario X
Operadores funcionales
∇f Gradiente de f : X → R ∪ {+∞}
D f (x)(·) Diferencial de Gâteaux de f : X → R ∪ {+∞} en x ∈ X
∇2 f Matriz Hessiana de f : Rn → R ∪ {+∞}
D2 f (x)(·, ·) Segundo Diferencial de Gâteaux de f : X → R ∪ {+∞} en x ∈ X
III
Índice general
Prefacio I
Índice General V
1. Introducción a la Optimización 1
1.1. Clases de problemas de optimización destacados . . . . . . . . . . . . . . . . . . . 2
1.1.1. Programación lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2. Programación semidefinida . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3. Optimización Espectral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.4. Control Óptimo en tiempo discreto . . . . . . . . . . . . . . . . . . . . . . 3
1.1.5. Cálculo de Variaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.6. Control Óptimo en tiempo continuo . . . . . . . . . . . . . . . . . . . . . . 4
1.2. Problemas industriales de actualidad . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1. Compresión y recuperación de imágenes . . . . . . . . . . . . . . . . . . . 4
1.2.2. Mercado de uso de suelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3. Funciones a valores en R ∪ {+∞} . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.1. Definiciones básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.2. Convenciones algebraicas . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4. Semicontinuidad inferior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5. Existencia de mı́nimos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5.1. Caso especial: Espacios Métricos . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.2. Caso especial: Espacios Vectoriales Normados . . . . . . . . . . . . . . . . 16
1.6. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
V
Índice General
VI
Índice General
VII
CAPÍTULO 1
Introducción a la Optimización
En nuestro contexto X será un espacio dotado con alguna topologı́a T , la función f : X → R será
un criterio a minimizar, el cual llamaremos función objetivo y el conjunto S ⊆ X representará las
restricciones impuestas sobre el problema de interés.
El valor numérico que toma el problema (P) está dado por
el cual queda bien definido si adoptamos la convención val (P) = +∞ := sup{R} para el caso S = 0. /
Por otra parte, una solución del problema (P) será llamada óptimo o mı́nimo, y corresponderá a un
punto x̄ ∈ X que verifique la condición
Una solución óptima del problema (P) se dirá estricto si la condición anterior se tiene con desigualdad
estricta para todos los puntos diferentes al mı́nimo, es decir
En caso de haber un óptimo, y para para enfatizar la existencia de éste, el valor numérico que
toma el problema (P) se escribirá
En este capı́tulo nos enfocaremos en la existencia de mı́nimos para el problema (P) en un contexto
abstracto, es decir, en criterios para determinar que el conjunto sol (P) sea no vacı́o. En particular,
estudiaremos la noción de semicontinuidad inferior y algunas nociones de compacidad.
Observación 1.1. Notemos que supS ( f ) := supx∈X { f (x) | x ∈ S} = −ı́nfS (− f ). Por lo tanto la
teorı́a que desarrollaremos en este curso puede ser igualmente aplicada a problemas donde se busca
maximizar la función objetivo en vez de minimizarla, tomando en cuenta el cambio de signo descrito
anteriormente. Formulaciones del tipo maximización aparecen tı́picamente en Economı́a.
1
Clases de problemas de optimización destacados Capı́tulo 1
2
Capı́tulo 1 Introducción a la Optimización
En este caso, los espacio naturales para estudiar el problema son X = ` p (Rn )×`q (Rm ), donde `r (RN )
es el espacio de la sucesiones {ak } en RN tales que la siguiente serie converge
∞
∑ |ak |r < +∞.
k=0
3
Problemas industriales de actualidad Capı́tulo 1
donde u : [a, b] → Rm es una función medible, llamada control o input. En este caso tenemos que
L : [a, b] × Rn × Rm → R es una función de costo acumulativa mientras que g : Rn × Rn → R es una
función de costo sobre los puntos extremos de la trayectoria.
Bajo condiciones estándar, la ecuación diferencial está bien puesta, en el sentido que cada función
medible u : [a, b] → Rm produce una única solución si la condición inicial está dada. Lo que implica,
en principio, que el espacio natural para buscar mı́nimos es el conjunto de funciones medibles valores
en el conjunto U ⊆ Rm . Este espacio tiene pocas propiedades topológicas favorables, lo cual no lo
hace un buen candidato para plantear los problemas de control. En cursos más avanzados se verá que
tal dificultad puede ser salvada usando teoremas de selección y una formulación equivalente sobre el
espacio X = ACn [a, b].
Luego el problema de recuperación de imágenes consiste en encontrar una buena aproximación de x̄,
conociendo z, bajo supuestos a priori sobre x̄.
4
Capı́tulo 1 Introducción a la Optimización
Se dice que la imagen original es parsimoniosa (sparse en inglés) en alguna base ortonormal
v1 , . . . , vN (llamada wavelet), si x̄ = ∑N
i=1 yi vi , pocos yi no nulos. Muchas imágenes son parsimoniosas
en algunas bases de wavelets, lo que indica que la imagen puede ser muy bien representada a través
de pocos elementos de la base. Notar que si F ∈ MN×N (R) es la matriz cuadrada que tiene como
columnas los vectores ortonormales v1 , . . . , vN , se tiene que x̄ = Fy, con y = (y1 , . . . , yN ) y F > = F −1 ,
de donde y = F > x̄.
Si suponemos que la imagen x̄ es parsimoniosa con respecto a v1 , . . . , vN , entonces el vector
y = F > x̄ tiene muchas componentes nulas lo que significa que
kyk0 := |{i ∈ {1, . . . , N} : yi 6= 0}|
es un número pequeño. Por lo tanto, una manera de aproximar x̄ es considerar el problema
Minimizar kF > xk0 sobre todos los x ∈ RN que satisfacen la restricción Ax = z.
Como la función x 7→ kxk0 tiene malas propiedades, una relajación ampliamente usada en restau-
ración de imágenes consiste en usar la norma kyk1 = ∑N
i=1 |yi |, de donde se obtiene el problema
5
Funciones a valores en R ∪ {+∞} Capı́tulo 1
La componente Xhi de la matriz X ∈ Mm×n (R) representa en este caso la cantidad de hogares
tipo h que se localizan en la zona i. Este es problema se puede formular como un problema de
programación lineal y puede ser resuelto por el método simplex. Las soluciones de este tipo de
problemas se encuentran en los extremos del poliedro que generan las restricciones lineales y son
altamente sensibles a los valores de las utilidades de la matriz C, pudiendo pasar Xhi de 0 a Hh si
Chi pasa de no ser el máximo valor entre Ch1 , . . . ,ChN a serlo, por ejemplo. En el caso en que existe
incertidumbre en la estimación de las utilidades, en la literatura es ampliamente utilizado agregar una
penalización entrópica, obteniendo el problema
n m
1
Maximizar ∑ ∑ ChiXhi + λ Xhi(log(Xhi) − 1) sobre los X ∈ Mm×n(R)
i=1 h=1
tales que ∑ni=1 Xhi = Hh , ∀h = 1, . . . , m
∑m
h=1 Xhi = Si , ∀i = 1, . . . , n
La función X 7→ − ∑ni=1 ∑m h=1 Xhi (log(Xhi ) − 1) está muy relacionada con la entropı́a de Shannon
que mide el nivel de incertidumbre de variables aleatorias. Esta modificación permite evitar grandes
cambios de la solución a modificaciones menores de las variables Chi . Este problema será objeto de
estudio en este curso.
Usando la convención
α + (+∞) = (+∞) + α = +∞, ∀α ∈ R
tenemos que
val (P) = ı́nf { f (x) + δS (x)}.
x∈X
De esta manera, el problema (P) se puede formular como un problema sin restricciones, pero con una
función objetivo a valores en la recta Real extendida. Esto permite tratar problemas de optimización
abstracta de una forma unificada, independiente del conjunto de restricciones S, cuya información
estará incluida implı́citamente en la función objetivo.
6
Capı́tulo 1 Introducción a la Optimización
que ser introducidas. Por ejemplo, dada una función f : X → R ∪ {+∞}, su dominio efectivo es el
conjunto
dom( f ) := {x ∈ X | f (x) < +∞}.
Además, diremos que f : X → R ∪ {+∞} es propia si dom( f ) 6= 0./
En lo que sigue, y a menos que se diga otra cosa, asumiremos que la función objetivo tiene
valores sobre la recta Real extendida, es decir, f : X → R ∪ {+∞}. Además, obviaremos la presencia
de restricciones, las cuales asumiremos se encuentran implı́citamente definidas en la estructura de la
función objetivo via la relación
S = dom( f ).
Bajo estas circunstancias tendremos que
ı́nfX ( f ) := val (P) = ı́nf { f (x) | x ∈ dom( f )} y arg mı́nX ( f ) := sol (P).
x∈X
3. 0 · (+∞) = (+∞) · 0 = 0.
A1 , A2 ∈ T =⇒ A1 ∩ A2 ∈ T .
[
∀α ∈ Λ, Aα ∈ T =⇒ Aα ∈ T .
α∈Λ
En tal caso, llamamos a los elementos de T abiertos y al par (X, T ) un espacio topológico.
Los conjuntos que son el complemento de un abierto son los llamados cerrado de T .
7
Semicontinuidad inferior Capı́tulo 1
Γγ ( f ) := {x ∈ X | f (x) ≤ γ}.
Definición 1.1. Sea (X, T ) un espacio topológico. Una función f : X → R ∪ {+∞} se dice semicon-
tinua inferior respecto a la topologı́a T (abreviado T -s.c.i. o simplemente s.c.i. si la topologı́a es
clara del contexto) si y sólo si todos sus conjuntos de nivel inferior son cerrados, es decir,
Veremos ahora que este criterio, y otros más, son definiciones equivalentes para la semicontinuidad
inferior de una función. Definimos el epı́grafo de una función a valores sobre la recta Real extendida
f : X → R ∪ {+∞} como el subconjunto de X × R dado por
R +∞ +∞
epi(f )
Γγ (f )
X
dom f
8
Capı́tulo 1 Introducción a la Optimización
Usando un poco de abuso de notación, dado un espacio topológico (X, T ), denotamos por Tx la
familia de vecindades abiertas que contiene a un punto x ∈ X, es decir
A ∈ Tx ⇐⇒ A ∈ T ∧ x ∈ A.
Proposición 1.1. Sea (X, T ) un espacio topológico y f : X → R ∪ {+∞} una función dada. Las
siguientes afirmaciones son equivalentes:
(i) f es T -s.c.i. .
(iv) ∀x ∈ X, ∀γ < f (x), ∃Aγ ∈ Tx tal que ∀y ∈ Aγ tenemos que f (y) > γ.
(ii) =⇒ (iii) Sea x ∈ X y γ ∈ (−∞, f (x)) tenemos que A = {y ∈ X | f (y) > γ} ∈ Tx ya que
A ∈ T por (ii) y x ∈ A. De este modo γ ≤ lı́m infy→x f (y). Como lo anterior es válido para todo
γ < f (x), hacemos γ → f (x) y concluimos el resultado.
(iii) =⇒ (iv) Sea x ∈ X y γ ∈ (−∞, f (x)). Por (iii), tenemos que γ < sup ı́nf f (y). Usando la
A∈Tx y∈A
definición del supremo tenemos que existe A ∈ Tx tal que γ < ı́nf f (y), de donde concluimos
y∈A
fácilmente.
(iv) =⇒ (v) Tomemos (x, λ) ∈ / epi( f ), lo que equivale a λ < f (x). Consideremos γ ∈ R tal que
λ < γ < f (x). Luego (iv) implica la existencia de Aγ ∈ Tx tal que ∀y ∈ Aγ , f (y) > γ, de modo
que (y, γ) ∈
/ epi( f ). Se sigue que Aγ × (−∞, γ) y epi( f ) son disjuntos, y como Aγ × (−∞, γ) es
un abierto para la topologı́a T × TR que contiene al punto (x, λ), concluimos que X \ epi( f ) es
abierto, y por lo tanto epi( f ) es cerrado.
(v) =⇒ (i) Como Γγ ( f ) × {γ} se puede escribir como la intersección de epi( f ) con X × {γ},
deducimos que Γγ ( f ) × {γ} es cerrado en X × R, y de aquı́ que Γγ ( f ) es cerrado.
Notemos que epi( f ) = [−1, 1] × [0, +∞), este último siendo un conjunto cerrado de R2 , implica que
f es s.c.i.. Notemos además que Γγ ( f ) = [−1, 1] si γ ≥ 0 y Γγ ( f ) = 0/ si γ < 0, siendo en ambos casos
conjuntos cerrados de R.
9
Existencia de mı́nimos Capı́tulo 1
[ n
[
K⊆ Aα =⇒ ∃α1 , . . . , αn ∈ Λ tal que K ⊆ A αk .
α∈Λ k=1
Definición 1.2. Sea (X, T ) un espacio topológico. Una función f : X → R ∪ {+∞} se dice T -inf-
compacta (o simplemente inf-compacta si la topologı́a es clara del contexto) si todos sus conjuntos
de nivel inferior son relativamente compactos para la topologı́a T , es decir,
Notemos que si f : X → R ∪ {+∞} es T -s.c.i. entonces que la función sea inf-compacta para la
topologı́a T equivale a requerir que cada Γγ ( f ) sea compacto.
Con estas definiciones en mano podemos enunciar el teorema básico de existencia de mı́nimos.
Teorema 1.1 (Weierstrass-Hilbert-Tonelli I). Sea (X, T ) un espacio topológico, f : X → R ∪ {+∞}
una función propia T -s.c.i. y T -inf-compacta. Entonces, ı́nfX ( f ) ∈ R y arg mı́nX ( f ) 6= 0.
/
Demostración. Sea v̄ = ı́nfX ( f ). Notemos que v̄ ∈ R ∪ {−∞}, puesto que dom( f ) es no vacı́o. Sea
x0 ∈ dom( f ) y definamos γ0 = f (x0 ). Luego tenemos que v̄ ≤ γ0 y además
\ \
arg mı́nX ( f ) = Γγ ( f ) = Γγ ( f )
γ∈(v̄,+∞) γ∈(v̄,γ0 )
10
Capı́tulo 1 Introducción a la Optimización
n
\
Γγi ( f ) = Γγ ( f ) 6= 0.
/
i=1
Γγ ( f ) 6= 0.
T
Por compacidad concluimos la demostración puesto que tenemos entonces que /
γ∈(v̄,γ0 )
y=1
f (x) = γ < 1
Γγ (f )
Veremos una versión especializada para espacios métricos del teorema de Weierstrass-Hilbert-
Tonelli. Más aún, mostraremos una nueva técnica para demostrar dicho teorema conocida como
Método Directo, que fue iniciada por Hilbert y luego desarrollada por Tonelli.
Primero que todo, veamos que la semicontinuidad inferior, al igual que la continuidad, puede ser
caracterizada usando sucesiones.
11
Existencia de mı́nimos Capı́tulo 1
Una métrica sobre un conjunto X es una función d : X × X → [0, +∞) que satisface:
En tal caso, el par (X, d) se dice espacio métrico, el cuál es también un espacio topológico. La
topologı́a canónica inducida por la métrica, denotada Td , viene dada por
donde xk → x significa que para todo ε > 0 existe k0 ∈ N tal que xk ∈ BX (x, ε) para cada k ≥ k0 .
Proposición 1.2. Sea (X, d) un espacio métrico y Td la topologı́a generada por la métrica. Sea
f : X → R ∪ {+∞} una función dada. Luego, f es Td -s.c.i. si y sólo si
Demostración. Sea x ∈ X y A ∈ Tx . Luego existe ε > 0 tal que BX (x, ε) ⊆ A y por lo tanto, dada una
sucesión {xk } ⊆ X tal que xk → x, tenemos que existe k0 ∈ N para el cual lo siguiente es cierto
ı́nf f (y) ≤ ı́nf f (y) ≤ ı́nf f (xl ) ≤ sup ı́nf f (xl ) = lı́m inf f (xk )
y∈A y∈BX (x,ε) l≥k0 k∈N l≥k k→+∞
Como el lado derecho no depende de A ∈ Tx , podemos tomar supremo sobre estos conjuntos para
obtener
lı́m inf f (y) ≤ lı́m inf f (xk ).
y→x k→+∞
Luego si f es Td -s.c.i., por Proposición 1.1, obtenemos la condición necesaria. Para la otra implican-
cia demostremos que epi( f ) es cerrado en X × R para la topologı́a Td × TR , la cual también tiene la
estructura de espacio métrico. La conclusión entonces estará dada por la Proposición 1.1.
Sea {(xk , λk )} ⊆ epi( f ) tal que xk → x ∈ X y λk → λ ∈ R. Sigue que
(∀k ∈ N) f (xk ) ≤ λk ,
y el resultado se sigue de tomar lı́m infk→+∞ a ambos lados de la desigualdad y usar la hipótesis.
12
Capı́tulo 1 Introducción a la Optimización
Teorema 1.2 (Weierstrass-Hilbert-Tonelli II). Sea (X, d) un espacio métrico, Td la topologı́a gene-
rada por la métrica y f : X → R ∪ {+∞} una función Td -s.c.i.. Supongamos que ∃γ0 > ı́nfX ( f ) tal
que Γγ0 ( f ) es relativamente compacto. Entonces, ı́nfX ( f ) ∈ R y arg mı́nX ( f ) 6= 0.
/
Demostración. Construimos primero una sucesión {xk } minimizante para f , es decir, una sucesión
tal que f (xk ) → ı́nfX ( f ) con xk ∈ Γγ0 ( f ) para todo k ∈ N. Como ı́nfX ( f ) > −∞, la definición de
ı́nfimo implica la existencia de una sucesión (xk )k∈N de X tal que
γ0 − ı́nfX ( f )
(∀k ∈ N) ı́nf( f ) ≤ f (xk ) ≤ ı́nfX ( f ) + .
X k+1
Por otra parte, si ı́nfX ( f ) = −∞ tomamos xk ∈ X tal que f (xk ) ≤ mı́n{−k, γ0 } (a posteriori veremos
que este caso no puede ocurrir). Notemos que el caso ı́nfX ( f ) = +∞ está descartado pues
dom( f ) es no vacı́o. Luego, tenemos que xk ∈ X,
En particular, xk ∈ Γγ0 ( f ), que es relativamente compacto. Se sigue que, por el Teorema de Bolzano-
Weiertrass, podemos extraer una subsucesión de {xkl } que converge (en la topologı́a Td ) a algún
punto x̄ ∈ X. Además, notemos que f (xkl ) → ı́nfX ( f ) y por la semicontinuidad inferior tenemos
13
Existencia de mı́nimos Capı́tulo 1
para la semicontinuidad inferior y la inf-compacidad es una topologı́a con menos abiertos que la
generada por la norma (una topologı́a débil).
Un X espacio vectorial sobre R, se dice normado si (X, d) es un espacio métrico para alguna
métrica, y esta última satisface d(x, y) = kx − yk para cada x, y ∈ X, donde k · k : X → [0, +∞)
es una función llamada norma que verifica los siguientes axiomas:
kxk = 0 si y sólo si x = 0.
kx − yk ≤ kx − zk + kz − yk para cada x, y, z ∈ X.
En tal caso, el par (X, k · k) se dice espacio vectorial normado. Además, (X, k · k) será un espa-
cio de Banach si X es un espacio completo, es decir, toda sucesión de Cauchy en X converge.
Los casos de interés mencionados anteriormente son cuando la topologı́a sobre X es: (i) la to-
pologı́a débil inducida por un espacio de Banach reflexivo, o bien, (ii) la topologı́a débil-? sobre X
visto como el dual topológico de otro espacio de Banach.
14
Capı́tulo 1 Introducción a la Optimización
Lema 1.1 (Teorema de Kakutani). Sea (X, k · k) un espacio de Banach. X es reflexivo si y sólo
si BX es compacta en la topologı́a débil de X.
Recuerdo: Separabilidad
Cabe señalar que, en el caso en que X es de dimensión finita, la topologı́a débil y la topologı́a de
la norma (o fuerte) son equivalentes. En efecto, la inclusión σ(X, X∗ ) ⊂ Tk·k es clara de la definición
pues con Tk·k la familia de funcionales lineales continuos es continua y σ(X, X∗ ) es la topologı́a con
menos abiertos que logra lo mismo. Para la inclusión recı́proca, supongamos por simplicidad y sin
perder generalidad que X = Rn y k·k = k·k∞ : x 7→ máxi=1,...,n |xi | (pues las normas son equivalentes),
sea A ∈ Tk·k y sea x ∈ A. Como las bolas son una base de Tk·k , existe ε > 0 tal que BRn (x, ε) ⊂ A.
Fijando x1∗ , . . . , xn∗ como los vectores canónicos de Rn , se tiene que si y ∈ Rn cumple
(1.2) (∀i ∈ {1, . . . , n}) |yi − xi | = |h xi∗ , y − x i| < ε,
se tiene y ∈ BRn (x, ε) ⊂ A y luego A ∈ σ(X, X∗ ). Notemos que la última inclusión es sólo válida en
dimensión finita, ya que si la dimensión de X fuese infinita, no se puede incluir en una bola una
intersección finita de “franjas” del tipo
∩ni=1 {y ∈ X | |hxi∗ , y − xi| < ε},
ya que es un conjunto no acotado.
Supongamos que (X, k · k) es un espacio de Banach reflexivo. En dimensión infinita, sabemos
la topologı́a débil σ(X, X∗ ) no es metrizable. Sin embargo, aún podemos extraer una subsucesión
convergente de una sucesión acotada. Basta considerar Y = Y0 con Y0 el espacio vectorial generado
por la sucesión {xk }. Es fácil ver que Y también es un espacio de Banach reflexivo y con lo cual
BY := {y ∈ Y | kyk ≤ 1}, la bola unitaria cerrada en Y, es compacta para la topologı́a débil gracias al
Teorema de Kakutani. Más aún, como Y es separable y reflexivo, su dual topológico Y∗ es separable
y reflexivo, por lo que, BY es metrizable.
Topologı́a débil-?: En este caso algo similar a lo anterior sucede. Sin embargo, la separabilidad
del espacio es fundamental. Supongamos que (X, k · k) es un espacio de Banach, no necesariamente
15
Existencia de mı́nimos Capı́tulo 1
reflexivo. La afirmación anterior es una consecuencia del Teorema de Banach-Alaoglu y del hecho
que la bola unitaria dual es metrizable si y sólo si X es separable. En particular, si X es separable,
entonces cada sucesión acotada en X∗ admite una subsucesión convergente débilmente-?.
Recuerdo: Topologı́as débiles-? y Teorema de Banach-Alaoglu
Lema 1.2 (Teorema de Banach-Alaoglu). Sea (X, k·k) un espacio de Banach. La bola unitaria
del espacio dual X∗
BX∗ := {x∗ ∈ X∗ | kx∗ k∗ ≤ 1}
es compacta en la topologı́a débil-? en X∗ .
Definición 1.3. Sea (X, k · k) un espacio vectorial normado. Una función f : X → R ∪ {+∞} se dice
coerciva si y sólo si para todo λ > 0 existe r > 0 tal que para todo x ∈ X con kxk > r tenemos que
f (x) > λ, es decir,
lı́m f (x) = +∞.
kxk→∞
f p (x) = x p , ∀x ∈ R
16
Capı́tulo 1 Introducción a la Optimización
Supongamos que (X, k · k) se puede identificar con el dual topológico de algún espacio de
Banach (Y, k · kY ), es decir, X ∼
= Y∗ y
Supongamos ahora que (X, k·k) es un espacio de Banach reflexivo. Tendremos en este caso que
la coercividad de f : X → R ∪ {+∞} será equivalente a la inf-compacidad de f para σ(X, X∗ ),
la topologı́a débil inducida en X. Esto es consecuencia del teorema de Kakutani. Ejemplos de
este caso son problemas en X = ` p (Rn ) o X = L p [a, b] con p ∈ (1, +∞).
17
Ejercicios Capı́tulo 1
1.6. Ejercicios
1. P ROBLEMA DE MODELAMIENTO MATEM ÁTICO
Una fábrica realiza 3 componentes A, B y C usando la misma manera de producir para cada
uno de ellos. Una unidad de A toma 1 hora en producirse, una unidad de B toma 0.75 horas en
producirse y una unidad de C toma 0.5 horas. Además C debe ser terminado a mano tomando
0.25 horas por unidad. Cada semana la producción no a mano no debe sobrepasar las 300 horas
y la hecha a mano no debe superar las 45 horas. Las componentes son finalmente juntadas para
hacer 2 productos finales. Un producto consiste de 1 unidad de A y 1 de C, y se vende a $ 30,
mientras que el otro producto consiste en 2 unidades de B y una de C, y se vende a $ 45. A
lo más 130 unidades del primer producto y 100 del segundo se pueden vender cada semana.
Plantee el problema de programación lineal en 2 variables y resuélvalo gráficamente.
Muestre que val (Pm ) = val (P), es decir, (P) se puede escribir de forma equivalente como un
problema de programación lineal de dimensión infinita.
(vi ∈ W ∧ v j ∈ V \W ) ∨ (vi ∈ V \W ∧ v j ∈ W ).
18
Capı́tulo 1 Introducción a la Optimización
Este problema es NP-duro (es decir, es muy difı́cil de resolver y no se sabe si se puede resolver
en tiempo polinomial), por esta razón muchas veces se prefiere resolver un problema relajado.
Para esto se considera que las variables x1 , . . . , xn ahora son vectores (no números reales)
!
n 1 − xi> x j
(Pn ) Maximizar ∑ Ci j sobre los x ∈ Rn tales que kxi k2 = 1, ∀i = 1, . . . , n.
i, j=1 2
El problema (Pn ) parece igual de difı́cil que (P), pero esto no es ası́. De hecho, (Pn ) se puede
resolver en tiempo polinomial (en general de forma eficaz). En efecto este problema se pue-
de escribir como un problema de programación lineal en el espacio Sn+ (R), de las matrices
simétricas y semi-definidas positivas de dimensión n, es decir, un problema de programación
semi-definida.
4. P ROPIEDADES DE FUNCIONES S . C . I .
Sea (X, T ) un espacio topológico y { fα }α∈Λ una familia arbitraria no vacı́a de funciones T -
s.c.i. definidas sobre X, es decir, para cada α ∈ Λ tenemos que fα : X → R ∪ {+∞} es T -s.c.i..
a) Pruebe que sup ( fα ) es T -s.c.i., donde
α∈Λ
19
Ejercicios Capı́tulo 1
Suponga ahora que (X, k · k) e (Y, k · kY ) son dos espacios vectoriales normados y A : X → Y
es un funcional lineal continuo. Demuestre que x 7→ kAx − bkY es semicontinuo inferior en X
para la topologı́a de la norma.
20
Introducción a la Optimización Capı́tulo 1, Section 1.6
22
PARTE I
TEORÍA GLOBAL DE OPTIMIZACIÓN
Caso Convexo
Resumen. En esta parte del curso nos enfocaremos problemas de optimización conve-
xa, es decir, donde todos los elementos que determinan el problema de interés (función
objetivo y restricciones) satisfacen una propiedad estructural llamada convexidad. La
optimización convexa tiene el mismo status dentro de la teorı́a general de optimización
que las ecuaciones diferenciales lineales tienen en la teorı́a general de ecuaciones di-
ferenciales, pues es la base para muchas aplicaciones ya que incluye en particular la
programación lineal y los problemas cuadráticos.
23
CAPÍTULO 2
Teorı́a general
2.1. Introducción
Comenzamos esta parte del curso recordando la definición de un conjunto convexo. Para dar
sentido a la exposición y por simplicidad asumiremos en la mayor parte de lo que sigue que (X, k · k)
es un espacio de Banach. Note que gran parte de la discusión podrı́a hacerse simplemente sobre
espacio vectoriales topológicos localmente convexos, sin alterar mayormente las técnicas usadas.
Un conjunto S ⊆ X se dice convexo si y sólo si
Proposición 2.1. Sea X un espacio vectorial normado y § ⊂ X un conjunto convexo. Entonces, para
todo x ∈ int S e y ∈ S, se tiene
Proposición 2.2. Sea X un espacio vectorial y f : X → R ∪ {+∞} una función dada. Luego f es
convexa si y sólo si epi( f ) es un conjunto convexo de X × R. Además, si f es convexa, entonces se
tiene que dom( f ) y Γγ ( f ) son conjuntos convexos para cualquier γ ∈ R.
25
Teorı́a general Capı́tulo 2, Section 2.2
Demostración. Sean (x, µ) y (y, η) en epi( f ) y sea λ ∈ [0, 1]. Como f es convexa, se tiene f (λx+(1−
λ)y) ≤ λ f (x) + (1 − λ) f (y) ≤ λµ + (1 − λ)η, donde la última desigualdad proviene de la definición
de epi( f ). Para la recı́proca, basta notar que (x, f (x)) y (y, f (y)) están en epi( f ), por lo que de la
definición de conjunto convexo en X × R se deduce la desigualdad de convexidad. La convexidad de
Γγ ( f ) es directa de la definición (ejercicio).
Como mencionado anteriormente, en esta parte del curso nos centraremos en problemas de opti-
mización convexa. Nuestro problema modelo de optimización
Donde A ∈ Mn×n (R) y B ∈ Mn×m (R). El problema consiste en minimizar, para ciertas matrices
simétricas y definidas positivas P ∈ Sn++ (R) y Q ∈ Sm
++ (R), un funcional del tipo
1 ∞ > >
f ({xk }, {uk }) = ∑ xk Pxk + uk Quk
2 k=0
En este caso, el espacio natural para estudiar el problema es X = `2 (Rn ) × `2 (Rm ), donde `2 (RN ) es
el espacio de la sucesiones {xk } en RN tales que
∞
∑ |xk |2 < +∞.
k=1
26
Capı́tulo 2, Section 2.3 Minimización convexa
Z T
1 > >
(x, u) 7→ x(t) Px(t) + u(t) Qu(t) dt
2 0
La idea básica de la versión geométrica del teorema de Hahn-Banach es que conjuntos con-
vexos, no vacı́os y disjuntos, se pueden separar por un hiperplano. Si alguno de los conjuntos
resulta ser compacto y el otro cerrado, entonces la separación puede entenderse en un sentido
estricto. En la Figura 2.1 hemos bosquejado interpretaciones geométricas de este teorema. El
dibujo de la izquierda muestra la separación cuando uno de los conjuntos es abierto y el dibujo
de la derecha un caso de separación estricta.
Lema 2.1 (Hahn-Banach I). Sea (X, k · k) un espacio de Banach. Sean A, B ⊆ X dos subcon-
juntos convexos no vacı́os y disjuntos.
hx∗ , ai ≤ α − ε, ∀a ∈ A y hx∗ , bi ≥ α + ε, ∀b ∈ B.
27
Teorı́a general Capı́tulo 2, Section 2.3
H H
A
A
B B
Una consecuencia importante del teorema de Hanh-Banach (Lema 2.1) para nuestros propósitos
es que, para funciones convexas, la semi-continuidad inferior para la topologı́a fuerte es indistingui-
ble de la semi-continuidad inferior para la topologı́a débil σ(X, X∗ ).
Proposición 2.3. Sea (X, k · k) un espacio de Banach y f : X → R ∪ {+∞} una función propia
convexa y s.c.i.. Luego se tiene que
(∀x ∈ X) f (x) = sup {h(x) | h : X → R es una función afı́n continua en X tal que h(x) ≤ f (x)} .
Demostración. Como f es convexa, s.c.i. y propia, se sigue que su epı́grafo es convexo, cerrado y
no vacı́o. Definamos
(2.2) (∀x ∈ X) g(x) := sup {h(x) | h : X → R es una función afı́n continua en X tal que h ≤ f } .
Por definición se tiene que g ≤ f . Para demostrar la igualdad, por la definición del supremo basta
probar
(2.3) (∀x ∈ X)(∀r < f (x))(∃h : X → R afin continua en X tal que h ≤ f ) r < h(x).
1. Supongamos que x ∈ dom( f ). Sea r < f (x) < +∞. Luego (x, r) ∈
/ epi( f ) y gracias al Teorema
∗ ∗
Geométrico de Hahn-Banach (Lema 2.1), existen (x , s) ∈ X × R \ {(0, 0)} y α ∈ R tales que
En particular, como (x, f (x)) ∈ epi( f ), concluimos de (2.4) que s(r − f (x)) < 0 de donde s > 0.
28
Capı́tulo 2, Section 2.3 Minimización convexa
R
6
epi f
H = {(y, λ) ∈ X × R | h x∗ , y i + sλ = α}
r (x, r)
- X
x
1 ∗ α 1
(2.5) hx , x − yi + r < − h x∗ , y i ≤ λ, ∀(y, λ) ∈ epi( f ),
s |s s{z }
h(y)
Sea h̃ : X → R una función afı́n continua tal que h̃ ≤ f , cuya existencia está garantizada por la
primera parte pues f es propia. Luego para todo k ∈ N e y ∈ X se tiene que
Ahora bien, dado que el epı́grafo de una función afı́n continua es cerrado para la topologı́a débil
σ(X, X∗ ), se tiene entonces que epi(g) es cerrado para la topologı́a débil σ(X, X∗ ). En otras palabras,
g es σ(X, X∗ )-s.c.i. lo cual termina la demostración.
En vista del resultado anterior podemos presentar una nueva versión del teorema de existencia de
mı́nimos de Weierstrass-Hilbert-Tonelli, especializada para el caso convexo.
29
Teorı́a general Capı́tulo 2, Section 2.3
f (x̄) ≤ f (x), ∀x ∈ X.
En el teorema anterior la convexidad juega un rol esencial, pues permite conectar la semi-continuidad
inferior para las topologı́as fuerte y débil. Dicho esto, no hay que obviar las otras hipótesis del teore-
ma, especialmente la reflexividad del espacio X. Veremos a través de un ejemplo que la reflexividad
es también esencial para la validez del teorema anterior.
Es un ejercicio estándar de análisis el hecho que (C [0, 1], k ·k∞ ) es un espacio de Banach no reflexivo,
siendo su dual topológico el espacio de medidas de Borel regulares M [0, 1].
Consideremos el conjuntos de restricciones
Z 1/2 Z 1
S := x ∈ C [0, 1] x(t)dt − x(t)dt = 1 .
0 1/2
Es fácil ver que S es no-vacı́o, cerrado y convexo. De hecho S es un hiperplano cerrado para la
convergencia uniforme.
Consideremos el problema de minimización de encontrar el elemento de norma mı́nima en S.
Este problema puede plantearse como:
Evidentemente, la función x 7→ f (x) := kxk∞ + δS (x) es propia, convexa, s.c.i. para la topologı́a
fuerte. Además Γγ ( f ) es acotado para cualquier γ ∈ R, luego las hipótesis de teorema 2.1 se verifican,
excepto por la reflexividad.
Observemos que si x ∈ S, entonces
Z 1 Z 1 Z 1
2
1= x(t)dt − 1
x(t)dt ≤ |x(t)|dt ≤ kxk∞ .
0 2 0
30
Capı́tulo 2, Section 2.3 Minimización convexa
Ası́ vemos que val (P0 ) ≥ 1. Por otra parte, podemos construir una sucesión minimizante que alcanza
el valor 1. Para ello consideremos para cada k ∈ N \ {0}, los parámetros αk = 21 − k+1
1
y βk = k+1
k ,y
definamos xk : [0, 1] → R por
βk t ∈ [0, αk ]
1−2t
xk (t) = βk 1−2α k
t ∈ (αk , 1 − αk )
−β
t ∈ [1 − α , 1]
k k
k+1
Se verifica que xt ∈ S y kxk k∞ = βk = k con lo que concluimos que val (P0 ) = 1.
R
βk 6
1 D
D
D
D
r D R
αk D 12
-
1
D
D
D
−1 D
D −βk
Supongamos ahora que existe un mı́nimo para el problema (P0 ), es decir, existe x ∈ S tal que
kxk∞ = 1. Notemos que, dado que x ∈ S, se tiene que
Z 1/2 Z 1
(x(t) − 1)dt = (1 + x(t))dt
0 1/2
pero como |x(t)| ≤ 1 para todo t ∈ [0, 1], sigue que x(t) − 1 ≤ 0 ≤ 1 + x(t) en [0, 1]. Luego la integral
del lado izquierdo tiene un valor negativo y el valor de la integral de la derecha es positivo.
La única
1
opción es que ambas integrales valgan cero y por lo tanto, deducimos que x ≡ 1 sobre 0, 2 y que
x ≡ −1 sobre 21 , 1 lo que contradice la continuidad de x. En consecuencia, no existe un mı́nimo
31
Teorı́a general Capı́tulo 2, Section 2.3
Demostración. Sean x̄ e ȳ en arg mı́nX ( f ) y sea λ ∈ [0, 1]. Entonces, para todo z ∈ X, por convexidad
y definición de mı́nimo se tiene
de donde λx̄+(1−λ)ȳ ∈ arg mı́nX ( f ), y luego arg mı́nX ( f ) es convexo. Para la unicidad, si asumimos
que x̄ 6= ȳ, como se tiene f (x̄) = f (ȳ), la convexidad estricta implica
por lo que ni x̄ ni ȳ pueden ser mı́nimos, lo que nos lleva a una contradicción y a la conclusión.
Notemos que el teorema anterior implica que en el caso de haber más de un mı́nimo, digamos x̄1
y x̄2 , entonces todos los elementos del segmento
son también mı́nimos, lo que implica que arg mı́nX ( f ) es un conjunto infinito no numerable.
32
Capı́tulo 2, Section 2.4 Ejercicios
2.4. Ejercicios
1. Á LGEBRA DE FUNCIONES CONVEXAS Sea (X, k · k) un espacio vectorial normado y { fα }α∈Λ
una familia arbitraria no vacı́a de funciones convexas definidas sobre X, es decir, para cada
α ∈ Λ tenemos que fα : X → R ∪ {+∞} es convexa.
1
f (x) = x> Ax + b> x + c, ∀x ∈ Rn .
2
Muestre que si f es acotada inferiormente, entonces A ∈ Sn+ (R). Muestre además que f
es convexa (usando el criterio algebraico) y que además alcanza su mı́nimo en Rn .
Pruebe que f es estrictamente convexa si y sólo si A ∈ Sn++ (R).
33
Teorı́a general Capı́tulo 2, Section 2.4
5. F UNCIONES MARGINALES
Sean X e Y dos espacios vectoriales. Considere A ⊆ X y B ⊆ Y dos conjuntos convexos no
vacı́os. Sea ϕ : X × Y → R ∪ {+∞}, una función convexa tal que ı́nf{ϕ(x, y) | y ∈ B} > −∞
para todo x ∈ A. Pruebe que la función f (x) = ı́nf{ϕ(x, y) | y ∈ B} + δA (x) es convexa en X.
Supongamos en adelante que (X, h·, ·i) es un espacio de Hilbert, es decir, la norma k · k es
inducida por el producto interno: kxk2 = hx, xi.
e) Demuestre que
1 2
proy(x, S) = s ∈ S | hy − s, x − si ≤ ky − sk , ∀y ∈ S
2
proy(x, S) = {s ∈ S | hy − s, x − si ≤ 0, ∀y ∈ S}
34
CAPÍTULO 3
Optimización convexa diferenciable
La convexidad de una función es un criterio algebraico, que puede ser difı́cil de probar algunas veces.
Comenzaremos este capı́tulo indicando algunos criterios alternativos para las funciones diferencia-
bles y de paso recordemos algunas definiciones básica del cálculo diferencial.
A lo largo de este capı́tulo trabajaremos básicamente con funciones f : X → R ∪ {+∞} convexas
tales que dom( f ) será un abierto de un espacio de vectorial normado (X, k · k) no necesariamente de
Banach; la completitud del espacio no será esencial es esta parte.
Supongamos que f : X → R ∪ {+∞} es una función tal que dom( f ) tiene interior no vacı́o.
Diremos que la función f es Gâteaux diferenciable en x ∈ int(dom( f )) si
f (x + td) − f (x)
lı́m = `(d), ∀d ∈ X,
t→0+ t
donde ` : X → R es un funcional lineal continuo, que se conoce como la derivada de Gâteaux
de f . Usualmente este funcional lineal se denota por D f (x).
En el caso particular que X tenga la estructura de espacio de Hilbert con un producto interno
h · , · i, se tiene que cada x∗ ∈ X∗ admite un representante v ∈ X tal que
x∗ (y) = h v , y i, ∀y ∈ X.
35
Optimización convexa diferenciable Capı́tulo 3, Section 3.1
Teorema 3.1. Sean (X, k·k) un espacio vectorial normado y f : X → R∪{+∞} una función Gâteaux
diferenciable en dom( f ), el cual asumimos es un conjunto convexo abierto de X. Las siguientes
afirmaciones son equivalentes:
(i) f : X → R ∪ {+∞} es convexa.
(ii) f es subdiferenciable, es decir, para todo x, y ∈ dom( f ), se tiene f (y) ≥ f (x) + D f (x)(y − x).
(iii) D f es monótono, es decir, para todo x, y ∈ dom( f ) se tiene D f (x)(x − y) − D f (y)(x − y) ≥ 0.
Demostración. Dividamos la demostración en cuatro partes:
(i) ⇒ (ii) Sean x, y ∈ dom( f ) y t ∈ (0, 1). De la convexidad de f se deduce
f (x + t(y − x)) − f (x)
≤ f (y) − f (x).
t
Luego, haciendo t → 0 obtenemos D f (x)(y − x) ≤ f (y) − f (x).
(ii) ⇒ (iii) Sean x, y ∈ dom( f ). Usando (ii) y luego intercambiando los roles de x e y en la desigualdad se
tienen
f (x) − f (y) ≤ D f (x)(x − y) y f (y) − f (x) ≤ −D f (y)(x − y).
Finalmente, sumando ambas desigualdades se obtiene el resultado.
(iii) ⇒ (i) Dados x, y ∈ dom( f ) fijos. En vista que dom( f ) es abierto, podemos escoger ε > 0 tal que
x + t(y − x) ∈ dom( f ) para cualquier t ∈ (−ε, 1 + ε). Definamos φ : R → R ∪ {+∞} via la
fórmula (
f (x + t(y − x)) si t ∈ (−ε, 1 + ε)
φ(t) :=
+∞ si no.
Como f es Gâteaux diferenciable en dom( f ), se tiene que φ también lo es en su dominio. En
particular, φ es derivable en (−ε, 1 + ε) y por lo tanto continua en [0, 1]. Además, se tiene que
φ0 (t) = D f (x+t(y−x))(y−x) para cualquier t ∈ (−ε, 1+ε). Notemos que si −ε < s < t < 1+ε
se tiene que
1
φ0 (t) − φ0 (s) = D f (zt )(y − x) − D f (zs )(y − x) = (D f (zt )(zt − zs ) − D f (zs )(zt − zs )) ≥ 0,
t −s
donde zt := x + t(y − x) y zt := x + s(y − x), y por lo tanto φ0 es no decreciente en el intervalo
(−ε, 1 + ε). Luego se tiene por teorema del valor medio que
φ(t) − φ(0)
(∀t ∈]0, 1[)(∃t ∗ ∈]0,t[) = φ0 (t ∗ ) ≤ φ0 (t).
t
Por lo tanto, si definimos ϕ : ]0, 1[→ R : t 7→ (φ(t) − φ(0))/t, se tiene que ϕ es diferenciable en
]0, 1[ y
0 φ0 (t) − φ(t)−φ(0)
t
(∀t ∈]0, 1[) ϕ (t) = ≥ 0,
t
de donde ϕ es no decreciente. Finalmente, la convexidad se deduce de que, para todo t ∈]0, 1[,
f (x + t(y − x)) − f (x)
= ϕ(t) ≤ ϕ(1) = f (y) − f (x).
t
36
Capı́tulo 3, Section 3.1 Criterios de primer orden
Notemos que si X tiene la estructura de espacio de Hilbert con un producto interno h·, ·i, la
propiedad de subdiferenciabilidad y monotonı́a del teorema 3.1 se re-escriben respectivamente como:
(Subdiferenciabilidad) f (y) ≥ f (x) + h∇ f (x), y − xi, ∀x, y ∈ dom( f ).
(Monotonı́a) h∇ f (x) − ∇ f (y), x − yi ≥ 0, ∀x, y ∈ dom( f ).
Ejemplo 3.1.1. Usando la observación anterior y la subdiferenciablidad podemos probar fácilmente
que x 7→ exp(x) es una función convexa. Notemos que la desigualdad de la subdiferenciabilidad es
exp(y) ≥ exp(x) + exp(x)(y − x)
y se puede re-escribir, fijando z = y − x como
exp(z) ≥ 1 + z.
Esta última siendo una desigualdad fundamental de la función exponencial estudiada en cursos
básicos de cálculo.
Ejemplo 3.1.2. Usando ahora la monotonı́a podemos probar fácilmente que x 7→ − log(x) es una
función convexa. Notemos primero que dom(log) = (0, +∞) y que la desigualdad de la monotonı́a es
1 1
− + (x − y) ≥ 0
x y
la que podemos re-escribir como
(x − y)2
≥0
xy
la cual siempre es válida si x, y > 0.
| f (x + h) − f (x) − D f (x)(h)|
lı́m = 0.
h→0 khk
Cuando la derivada de Gâteaux es continua se puede concluir que la función es Fréchet diferen-
ciable, como asegura el siguiente resultado.
37
Optimización convexa diferenciable Capı́tulo 3, Section 3.2
Proposición 3.1. Sea (X, k · k) un espacio vectorial normado y sea f : X → R ∪ {+∞} una función
Gâteaux diferenciable en una vecindad de x ∈ X tal que D f es continuo en x (con la norma dual).
Entonces f es Fréchet diferenciable en x y su derivada de Fréchet es D f (x).
Demostración. Sea ε > 0 tal que f es Gâteaux diferenciable en BX (x, ε), sean h ∈ BX (x, ε) y x∗ ∈ X∗
y definamos φ : t 7→ f (x + th). Por Teorema del Valor Medio en R se tiene que existe t ∈]0, 1[ tal que
f (x + h) − f (x) = φ(1) − φ(0) = φ0 (t) = D f (x + th)(h). Luego
k f (x + h) − f (x) − D f (x)(h)k
≤ kD f (x + th) − D f (x)k∗ → 0
khk
Veremos a continuación un criterio de orden superior para determinar la convexidad de una fun-
ción. Antes de continuar recordemos algunas nociones de derivadas de orden superior.
38
Capı́tulo 3, Section 3.2 Criterios de orden superior
D f (x + th)(k) − D f (x)(k)
lı́m = B(h, k), ∀h, k ∈ X.
t→0+ t
Este funcional bilineal continuo se conoce como el diferencial de Gâteaux de segundo orden
de f en x y se denota como D2 f (x). Es importante mencionar que en el caso X = Rn se tiene
que D2 f (x) puede ser representado a través de la matriz Hesiana de f :
2
∂x1 ,x1 f (x) ∂2x1 ,x2 f (x) . . . ∂2x1 ,xn f (x)
∂2 f (x) ∂2 f (x) . . . ∂2 f (x)
x2 ,x1 x2 ,x2 x2 ,xn
2
∇ f (x) =
.. .. .. ..
. . . .
2 2 2
∂xn ,x1 f (x) ∂xn ,x2 f (x) . . . ∂xn ,xn f (x)
a través de la relación
Por otro lado, f se dice dos veces Fréchet diferenciable en x si f es dos veces Gâteaux di-
ferenciable en x y el operador lineal continuo ` : X → X∗ dado por h 7→ `(h) := D2 f (x)(h, ·)
satisface
kD f (x + h) − D f (x) − `(h)k∗ |D f (x + h)(k) − D f (x)(k) − D2 f (x)(h, k)|
lı́m = lı́m sup = 0.
h→0 khk h→0 kkk=1 khk
Teorema 3.2. Sea (X, k · k) un espacio vectorial normado y f : X → R ∪ {+∞} una función dos
veces Gâteaux diferenciable en dom( f ), este último siendo un convexo abierto de X. Entonces, f :
X → R ∪ {+∞} es convexa si y sólo si el operador D2 f es semi-definido positivo, es decir,
D2 f (x)(h, h) ≥ 0, ∀x ∈ dom( f ), ∀h ∈ X.
Demostración. Supongamos primero que f es convexa. Sean x ∈ dom( f ), h ∈ X y t > 0 tal que
x + th ∈ dom( f ), cuya existencia está garantizada pues dom( f ) es abierto. Del Teorema 3.1, se tiene
1
D f (x + th)(h) − D f (x)(h) = [D f (x + th)(x + th − x) − D f (x)(x + th − x)] ≥ 0.
t
39
Optimización convexa diferenciable Capı́tulo 3, Section 3.3
es derivable en (−ε, 1 + ε). De hecho, dado que f es dos veces Gâteaux diferenciable en dom( f ) se
tiene que φ es dos veces derivable con φ0 continua en [0, 1]. Usando la regla de la cadena se obtiene
que φ00 (t) = D2 f (x + t(y − x))(y − x, y − x). Luego, como D2 f es semi-definido positivo se tiene que
φ0 es no decreciente, y por lo tanto, la conclusión sigue usando los mismos argumentos que en la
demostración de [(iii) ⇒ (i)] del Teorema 3.1.
Una ligera modificación de la demostración del resultado anterior permite obtener una condición
necesaria para que una función sea estrictamente convexa.
Teorema 3.3. Sea (X, k · k) un espacio de Banach y f : X → R ∪ {+∞} una función de clase C 2 en
dom( f ), es último siendo un abierto de X. Si el operador D2 f es definido positivo, es decir,
Demostración. Ejercicio.
Notemos que el converso del teorema 3.3 no es válido, de hecho la función x 7→ x4 es estricta-
mente convexa, pero su segunda derivada en x = 0 es nula.
1
f (x) = x> Ax − b> x + c, ∀x ∈ Rn .
2
Teorema 3.4 (Regla de Fermat I). Sea (X, k · k) un espacio vectorial normado y f : X → R ∪ {+∞}
una función convexa Gâteaux diferenciable en dom( f ), este último siendo un abierto de X. Luego
x̄ ∈ X es un mı́nimo de f si y sólo si D f (x̄) = 0.
40
Capı́tulo 3, Section 3.3 Regla de Fermat
f (x1 , x2 ) = x12 − x2
Notemos que si A ∈ Sn++ (R) entonces A es invertible y x̄ = A−1 b. Esto se condice con el hecho
que f es estrictamente convexa y que por lo tanto su mı́nimo es único. Además, la existencia de
mı́nimo también está asegurada por el teorema de Weierstrass-Hilbert-Tonelli pues f es coerciva
como veremos a continuación.
1
f (x) = x> Ax − b> x + c
2
es coerciva. Más aún, si λ > 0 es el menor valor propio de A entonces
λ|x|2 ≤ x> Ax
41
Optimización convexa diferenciable Capı́tulo 3, Section 3.4
Demostración. Como la matriz A es simétrica, admite una descomposición del tipo A = PDP> con
D la matriz diagonal con los valores propios reales λ1 ≥ · · · ≥ λn de A y P la matriz cuyas columnas
son los vectores propios ortonormales v1 , . . . , vn asociados a los valores propios λ1 , . . . , λn ; notar que
PP> = P> P = I, con I siendo la matriz identidad. Además, como A es definida positiva, todos sus
valores propios son (estrictamente) positivos. Más aún, como v1 , . . . , vn constituyen una base de Rn ,
para todo x ∈ Rn , existen coeficientes reales ξ1 , . . . , ξn tales que
n
x = ∑ ξi vi = Py, donde y = (ξ1 , . . . , ξn ).
i=1
De este modo, |x|2 = x> x = (Py)> Py = y> P> Py = y> y = |y|2 . Por lo tanto
n
> >
(Ax)> x = (PDP> x) x = (DP> x) (P> x) = (Dy)> y = ∑ ξ2i λi ≥ λn |y|2 = λn |x|2 ,
i=1
Teorema 3.5. Supongamos que (X, k · k) es un espacio de Banach reflexivo. Sea f : X → R ∪ {+∞}
una función propia, convexa y s.c.i para la topologı́a generada por la norma e inferiormente acotada.
Consideremos ε > 0, λ > 0 y sea x0 ∈ X tal que
(ii) kxε − x0 k ≤ λ,
Demostración. Supongamos que λ = 1 (en caso contrario basta considerar la norma k · k/λ). Defina-
mos la función gε : X → R ∪ {+∞} : x 7→ f (x) + εkx − x0 k. Es fácil mostrar que gε es convexa, s.c.i.
y coerciva, por lo que el Teorema 2.1 implica que el conjunto sol(Gε ) es no vacı́o, donde
42
Capı́tulo 3, Section 3.5 Principio Variacional de Ekeland
Además, como
sol(Gε ) = {x ∈ X | gε (x) ≤ val(Gε )} = Γval(Gε ) (gε ),
se tiene que sol(Gε ) es convexo, cerrado y acotado. De ese modo, como f + δsol(Gε ) es propia, s.c.i.
y coerciva, el Teorema 2.1 implica que existe xε ∈ sol(Pε ), donde
Luego, como x ∈ sol(Gε ), se tiene que gε (xε ) ≤ gε (x) para todo x ∈ X, lo que implica
(3.3) ı́nf f (x) + εkxε − x0 k ≤ f (xε ) + εkxε − x0 k = gε (xε ) ≤ gε (x0 ) = f (x0 ) ≤ ı́nf f (x) + ε,
x∈X x∈X
Concluimos que, para todo x ∈ X \ {xε } se tiene f (xε ) < f (x) + εkx − xε k.
Para las últimas afirmaciones, supongamos que f es Gâteaux diferenciable y sea d ∈ X con
kdk = 1. Por la parte (iii),
En otras palabras, dado que d ∈ X es un vector arbitrario que satisface kdk = 1, hemos probado que
de donde
kD f (xε )k∗ = sup {D f (xε )(d) | kdk = 1} ≤ ε.
d∈X
Finalmente, para cada k ∈ N tomemos yk ∈ 1k − arg mı́nX ( f ). Luego, basta aplicar el resultado recien-
temente probado para obtener la existencia de xk ∈ X que satisface
1 1
f (xk ) ≤ f (yk ) ≤ ı́nfX ( f ) + y kD f (xk )k∗ ≤ .
k k
43
Optimización convexa diferenciable Capı́tulo 3, Section 3.5
Demostración. Sean x e y en X. Definamos, para todo t ∈ [0, 1] la función φ(t) = f (x + t(y − x)).
Usando la propiedad Lipschitzianidad de ∇ f y la desigualdad de Cauchy-Schwartz, se tiene
Z 1
f (y) − f (x) = φ0 (t)dt
0
Z 1
= h∇ f (x + t(y − x)), y − xidt
0
Z 1
= h∇ f (x), y − xi + h∇ f (x + t(y − x)) − ∇ f (x), y − xidt
0
Z 1
≤ h∇ f (x), y − xi + k∇ f (x + t(y − x)) − ∇ f (x)k ky − xkdt
0
Z 1
≤ h∇ f (x), y − xi + Lky − xk2 tdt
0
L
= h∇ f (x), y − xi + ky − xk2 ,
2
de donde se obtiene la primera desigualdad (3.5). Para la segunda, dado z ∈ X, gracias al Teorema
3.1, como f es convexa y Gâteaux diferenciable en X, se tiene que
45
Optimización convexa diferenciable Capı́tulo 3, Section 3.5
4. Afirmamos que la sucesión {kxk − x̄k} es convergente. En efecto, sumando a ambos lados de
∞
la última desigualdad el término ∑ sk obtenemos
l=k+1
∞ ∞
θk+1 := kxk+1 − x̄k2 + ∑ sk ≤ kxk − x̄k2 + ∑ sk =: θk
l=k+1 l=k
Luego la sucesión {θk } es decreciente y y todos sus términos son no negativos. Luego, {θk } es
∞
convergente, pero como ∑ sk → 0 si k → +∞ (pues la serie converge), se tiene que la sucesión
l=k
{kxk − x̄k} también converge.
5. Para concluir usamos el Lema 3.1. Tomemos un punto de acumulación débil de {xk }, digamos
xkn * y ∈ X si n → +∞. Tomando z = x̄ en (3.7) y usando la semicontinuidad inferior de f en
la topologı́a débil (por convexidad) deducimos que
αkn L 2
f (y) ≤ lı́m inf f (xkn +1 ) ≤ f (x̄) + lı́m inf h∇ f (xkn ), xkn − x̄i − αkn 1 − k∇ f (xkn )k .
n→∞ n→∞ 2
Sabemos que k∇ f (xkn )k → 0 si n → +∞ y que además {xkn } está acotada (pues converge débil-
mente). Luego, debido a las condiciones sobre {αk }, el limite inferior de la derecha es nulo y
por lo tanto debemos tener que f (y) ≤ f (x̄). Lo que implica a su vez que y ∈ arg mı́nX ( f ) y en
consecuencia el resultado final de convergencia se deduce del Lema 3.1 con S = arg mı́nX ( f ).
donde A ∈ Sn++ (R), b ∈ Rn y c ∈ R. Sabemos, por la Proposición 3.2 que existe un único x̄ que
minimiza esta función. Una forma de aproximar x̄ es utilizando el método del gradiente, cuya cons-
trucción iterativa está dada por (3.4). En este caso estudiaremos la velocidad de convergencia del
método con αk siendo el único real positivo que minimiza sobre R la aplicación
λ1
κ(A) :=
λn
α 7→ f (xk − α∇ f (xk ))
es estrictamente convexa y diferenciable, luego, usando la Regla de Fermat, αk puede ser calculado
explı́citamente. De hecho, tenemos que
1
f (x) = x> Ax − b> x + c, ∀x ∈ Rn ,
2
y sea x̄ su mı́nimo. Considere la sucesión {xk }k∈N generada por (3.4) partiendo desde x0 ∈ Rn
arbitrario y con αk dado por (3.8). Luego se tienen las estimaciones
κ(A) − 1 2k
(i) f (xk ) − f (x̄) ≤ [ f (x0 ) − f (x̄) ]
κ(A) + 1
κ(A) − 1 k
(ii) kxk − x̄kA ≤ kx0 − x̄kA
κ(A) + 1
1
2( f (x0 ) − f (x̄)) 2 κ(A) − 1 k
(iii) kxk − x̄k ≤ ,
λn κ(A) + 1
√
donde k · kA : x 7→ x> Ax define una norma en Rn .
kgk k2
αk = y xk+1 = xk − αk gk , ∀k ∈ N.
gk > Agk
47
Optimización convexa diferenciable Capı́tulo 3, Section 3.5
1
f (xk+1 ) = xk+1 > Axk+1 − b> xk+1 + c
2
1 > α2
= xk Axk − αk (Axk )> gk + k gk > Agk − b> xk + αk b> gk + c
2 2
α2
= f (xk ) − αk (Axk − b)> gk + k gk > Agk
2
kgk k4
(3.9) f (xk+1 ) = f (xk ) − , ∀k ∈ N.
2gk > Agk
Además, como la única solución óptima del problema está dada por x̄ = A−1 b, deducimos que
ı́nfX ( f ) = f (x̄) = − 21 b> A−1 b + c y más aún
1 −1 > 1 > 1 1
(A gk ) gk = (xk − A−1 b) (Axk − b) = xk > Axk − b> xk + b> A−1 b = f (xk ) − f (x̄), ∀k ∈ N.
2 2 2 2
conluimos
2
κ(A) − 1
4κ(A)
f (xk+1 ) − f (x̄) ≤ [ f (xk ) − f (x̄)] 1 − = [ f (xk ) − f (x̄)] , ∀k ∈ N
(κ(A) + 1)2 κ(A) + 1
2( f (xk ) − f (x̄)) = gk > A−1 gk = (xk − x̄)> A(xk − x̄) = kxk − x̄k2A , ∀k ∈ N,
48
Capı́tulo 3, Section 3.5 Métodos de descenso
Dado que A ∈ Sn++ (R) y vk+1 6= 0 llegamos a una contradicción. Notemos que esto implica que una
colección de vectores no nulos conjugados con respecto a A no puede contener más de n vectores.
El método del gradiente conjugado consiste en utilizar las direcciones dk dadas por la fórmula
(
−g0 si k = 0
(3.11) dk =
−gk + βk dk−1 si k ≥ 1,
donde denotamos gk := ∇ f (xk ) = Axk − b para todo k ∈ N y βk es un parámetro dado por la relación
de conjugación entre dk y dk−1 . Efectivamente, no es difı́cil ver que dk > Adk−1 = 0 si y sólo si
(Axk − b)> Adk−1 gk > Adk−1
(3.12) βk = = , ∀k ∈ N \ {0}.
dk−1 > Adk−1 dk−1 > Adk−1
Más aún, si el paso se escoge de forma óptima, gracias a la Regla de Fermat tenemos que
(Axk − b)> dk gk > dk
(3.13) αk = − = − , ∀k ∈ N.
dk > Adk dk > Adk
Ahora veremos que el método converge en una cantidad finita de pasos
Teorema 3.8. Sean A ∈ Sn++ (R), b ∈ Rn y c ∈ R. Considere la función f : Rn → R dada por
1
f (x) = x> Ax − b> x + c, ∀x ∈ Rn .
2
La sucesión {xk }k∈N generada por (3.10) partiendo desde x0 ∈ Rn arbitrario, con dk dado por (3.11),
βk dado por (3.12) y αk dado por (3.13), converge en a lo más n pasos.
49
Optimización convexa diferenciable Capı́tulo 3, Section 3.5
Demostración. Procederemos por inducción y probaremos que, para todo k ∈ {1, . . . , n}, si dk−1 6= 0
entonces
De este modo, si para algún k ∈ {1, . . . , n}, tuviesemos dk = 0, entonces 0 = dk = −gk + βk dk−1 , de
donde gk es colineal con dk−1 6= 0 y al mismo tiempo gk > dk−1 = 0, por lo que gk = 0 y xk es solución.
Además, el algoritmo terminará en a lo más n pasos, ya que a cada iteración k genera un dk que es
conjugado con respecto a A a d0 , . . . , dk−1 , lo cual se puede hacer a lo más n veces en Rn .
Para k = 1, si d0 = −g0 6= 0, de (3.10) y (3.13) deducimos
Ahora supongamos que para k ∈ {1, . . . , n − 1}, si se tiene dk−1 6= 0, entonces se cumple (3.14).
Supongamos que dk 6= 0 y tomemos i ∈ {0, . . . , k}. Si i = k entonces (3.10) y (3.13) implican que
pues ambos términos son nulos por la hipótesis de inducción. Por otra parte, combinando el hecho
que gi+1 = gi + αi Adi con (3.11) deducimos que
(β1 + 1)d0 − d1
1
si i = 0,
Adi = (gi+1 − gi ) = 1 α 0
αi (βi+1 di − di+1 − (βi di−1 − di )) si i ∈ {1, . . . , k − 1},
αi
de donde obtenemos,
dk+1 > Adi = −gk+1 > Adi + βk+1 dk > Adi = 0, ∀i ∈ {1, . . . , k − 1},
pues el segundo término es nulo por hipótesis de inducción y el primero es nulo pues acabamos de
probar que gk+1 > di = 0 para todo i ∈ {1, . . . , k} y Adi es una combinación lineal de di−1 , di , di+1 (y
Ad0 es combinación lineal de d0 , d1 ). Esto concluye la demostración.
En el caso que n sea muy grande (por ejemplo n ≥ 103 ), realizar las n iteraciones del método
del gradiente conjugado puede ser muy costoso. Por esta razón, es interesante saber lo preciso que
se vuelve el método al cabo de algunas iteraciones. El siguiente resultado provee una estimación de
este error y entrega una cota para la tasa de convergencia del método.
50
Capı́tulo 3, Section 3.5 Métodos de descenso
51
Optimización convexa diferenciable Capı́tulo 3, Section 3.5
k xk yk k xk yk k xk yk
0 1.0000 1.0000 7 0.4783 -0.2097 14 0.2288 0.0440
1 0.9000 -0.8000 8 0.4305 0.1678 15 0.2059 -0.0352
2 0.8100 0.6400 9 0.3874 -0.1342 16 0.1853 0.0281
3 0.7290 -0.5120 10 0.3487 0.1074 17 0.1668 -0.0225
4 0.6561 0.4096 11 0.3138 -0.0859 18 0.1501 0.0180
5 0.5905 -0.3277 12 0.2824 0.0687 19 0.1351 -0.0144
6 0.5314 0.2621 13 0.2542 -0.0550 20 0.1216 0.0115
52
Capı́tulo 3, Section 3.5 Métodos de descenso
Ahora estudiaremos la convergencia del método de Newton-Raphson. Cabe destacar que el teore-
ma de convergencia que mostraremos ahora se diferencia de los teoremas estudiados para los métodos
del Gradiente y Gradiente conjugado en que la elección del punto inicial juega un rol importante.
Teorema 3.10. Sea f : Rn → R ∪ {+∞} una función propia, convexa y dos veces Gâteaux diferen-
ciable en dom( f ), el cual asumimos abierto de Rn . Supongamos que existe x̄ ∈ arg mı́nRn ( f ) tal que
∇2 f (x̄) ∈ Sn++ (R), y que además ∇2 f es localmente Lipschitz continua en torno a x̄, es decir, para
algún r > 0 existe L > 0 tal que
k∇2 f (x) − ∇2 f (y)k ≤ L|x − y|, ∀x, y ∈ BRn (x̄, r),
p
donde kMk = supkxk=1 kMxk = λmáx (M > M) para cualquier M ∈ Mn×n (R). Entonces, existe ρ > 0
para el cual se tiene que si x0 ∈ BRn (x̄, ρ), la secuencia {xk } generada por (3.15) converge a x̄ y
satisface
|xk+1 − x̄| |xk+1 − x̄|
lı́m = 0, y lı́m sup 2
< ∞.
k→∞ |xk − x̄| k→∞ |xk − x̄|
Demostración. Para todo x ∈ dom( f ) denotemos por λx al menor valor propio de ∇2 f (x). Como
∇2 f (x̄) ∈ Sn++ (R), de la Proposición 3.2 se tiene
λx̄
∇2 f (x) ∈ Sn++ (R) con λx ≥ > 0, x ∈ BRn (x̄, ρ).
2
53
Optimización convexa diferenciable Capı́tulo 3, Section 3.5
De ese modo, para todo x ∈ BRn (x̄, ρ), existen matrices Px y Dx tales que ∇2 f (x) = Px Dx Px> con
Px−1 = Px> , de modo que ∇2 f (x)−1 = Px D−1 >
x Px y
1 2
q
k∇ f (x) k = λmáx (Px D−2
2 −1 >
x Px ) ≤ ≤ .
λx λx̄
Supongamos que xk ∈ BRn (x̄, ρ) para algún k ∈ N. Para simplificar la notación, notemos gk = ∇ f (xk )
y Hk = ∇2 f (xk ). De (3.15) se deduce que si xk = x̄ entonces xk+1 = x̄, por lo que suponemos que
xk 6= x̄. Como x̄ es mı́nimo de f , usando el Teorema de Fermat, la propiedad de Lipschitz continuidad
de ∇2 f y la relación
Z 1
gk = ∇ f (xk ) − ∇ f (x̄) = ∇2 f (x̄ + t(xk − x̄))(xk − x̄)dt,
0
tenemos que
|xk+1 − x̄| = |xk − x̄ − Hk−1 gk |
= |Hk−1 (Hk (xk − x̄) − gk ) |
Z 1
−1 2
= Hk [Hk − ∇ f (x̄ + t(xk − x̄))](xk − x̄)dt
0
2 1 Z
≤ |xk − x̄| |Hk − ∇2 f (x̄ + t(xk − x̄))|dt
λx̄ 0
Z 1
2L
≤ |xk − x̄|2 (1 − t)dt
λx̄ 0
L 1
= |xk − x̄|2 ≤ |xk − x̄|,
λx̄ 2
En particular, se tiene que xk+1 ∈ BRn (x̄, ρ). Además, usando inducción vemos que la sucesión {xk }
está contenida en BRn (x̄, ρ) si x0 ∈ BRn (x̄, ρ) y
1
|xk+1 − x̄| ≤ |x0 − x̄|, ∀k ∈ N.
2k+1
De aquı́ se concluye que xk → x̄, y que también tenemos
|xk+1 − x̄| L |xk+1 − x̄| L
≤ |xk − x̄| y ≤ ,
|xk − x̄| λx̄ |xk − x̄|2 λx̄
lo que finaliza la demostración.
Observación 3.2. El método también funciona si se asume que ∇2 f es uniformemente continua en
una vecindad acotada de x̄, es decir, para algún r > 0 tenemos que
∀ε > 0, ∃ρ > 0, ∀x, y ∈ BRn (x̄, r) : |x − y| ≤ ρ ⇒ k∇2 f (x) − ∇2 f (y))k ≤ ε.
En ese caso la convergencia es superlineal:
|xk+1 − x∗ |
lı́m = 0.
k→∞ |xk − x∗ |
Por otra parte, el método no necesita que la función sea convexa en todo su dominio, ya que la
demostración es local. Sin embargo, el método si necesita que el mı́nimo sea único y que la función
sea estrictamente convexa en una vecindad del mı́nimo.
54
Capı́tulo 3, Section 3.5 Métodos de descenso
En el Ejemplo 3.5.2, el punto inicial no tiene relevancia para la convergencia. Sin embargo,
en general la convergencia es garantizada sólo si se parte suficientemente cerca de la solución. El
siguiente ejemplo ilustra un caso en que el método puede diverger si se parte lejos de la solución.
k xk
0 10
1 -139
2 29892
3 -1403526593
55
Optimización convexa diferenciable Capı́tulo 3, Section 3.6
3.6. Ejercicios
1. F UNCI ÓN CONVEXA DEFINIDA POR UNA INTEGRAL
Consideremos el polinomio trigonométrico T : Rn → [0, 2π] → R definido por
T (x, w) = x1 + x2 cos(w) + x3 cos(2w) + . . . + xn cos((n − 1)w).
Muestre que la función f : Rn → R ∪ {+∞} definida por
Z 2π
− log(T (x, w))dw si T (x, w) > 0, ∀w ∈ [0, 2π],
f (x) = 0
+∞ si no
56
Capı́tulo 3, Section 3.6 Ejercicios
4. D ESIGUALDAD DE K ANTOROVICH
Sea A ∈ Sn++ (R) con valores propios 0 < λ1 ≤ λ2 ≤ · · · ≤ λn 0. El objetivo de esta pregunta es
demostrar la desigualdad
s s 2
1 λn λ1
|x|4 ≤ x> Ax x> A−1 x ≤ + |x|4 , ∀x ∈ Rn .
4 λ1 λn
n
¯ = y2 λi y pruebe que
b) Defina λ ∑ i
i=1
1 n 2
yi ¯
λ1 + λn − λ
¯ ≤ ∑ ≤ ,
λ i=1 λi λ1 λn
57
Optimización convexa diferenciable Capı́tulo 3, Section 3.6
58
CAPÍTULO 4
Optimización convexa no diferenciable
Recordemos que una forma de estudiar problemas de optimización con restricciones es incluir en
la definición de la función objetivo la restricción via una penalización fuerte. Dicho de otra forma,
resolver
Notemos que en caso que (P) sea un problema convexo, tendremos que fS será también una función
convexa. Es importante destacar que no importa la regularidad que impongamos sobre f , la función
fS no será jamás diferenciable en la frontera de S (salvo en el caso trivial S = X), lo cual en principio
no nos permitirı́a aplicar los resultados vistos en el capı́tulo anterior a funciones similares a fS .
Afortunadamente, para el caso de optimización convexa, la diferenciabilidad es una herramienta
útil pero no fundamental, pues mucho resultados pueden ser extendidos al caso no diferenciable
introduciendo un objeto matemático llamado subdiferencial.
En este capı́tulo, y sólo con el propósito de simplificar la exposición, trabajaremos básicamente
con funciones f : X → R ∪ {+∞} convexas definidas sobre un espacio de Banach (X, k · k). La
condición impuesta anteriormente, que dom( f ) sea un abierto de X, no será necesaria a partir de
ahora. Además, como lo hemos hecho hasta ahora h·, ·i : X∗ × X → R denotará en producto dualidad
entre X∗ y X. En el caso que X sea un espacio de Hilbert, identificaremos X∗ con X y el producto
interno será denotado al igual que el producto dualidad.
4.1. Subdiferencial
El concepto de subdiferencial viene a generalizar la idea del diferencial de una función. La defini-
ción calza bien para funciones convexas, sin embargo hay que notar que ésta no requiere en absoluto
de la convexidad de la función en cuestión.
59
Optimización convexa no diferenciable Capı́tulo 4, Section 4.1
Definición 4.1. Supongamos que (X, k · k) es un espacio de Banach y sea f : X → R ∪ {+∞} una
función dada. Un subgradiente de f en x ∈ X es un funcional x∗ ∈ X∗ que satisface
f (x) + hx∗ , y − xi ≤ f (y), ∀y ∈ X.
La colección de todos los subgradientes de f en x, denotada ∂ f (x), es el subdiferencial de f en x.
La idea esencial del subdiferencial es agrupar todas las posibles pendientes que pueden tener las
funciones afines continuas que minoran a la función convexa en cuestión.
Observación 4.1. Notemos que ∂ f (x) es un conjunto convexo, posiblemente vacı́o, y cerrado para
la topologı́a débil-? en X∗ (y por lo tanto cerrado para la topologı́a débil y fuerte de X∗ ), cualquiera
sea x ∈ X. Además, es claro que si f es propia, ∂ f (x) = 0/ cada vez que f (x) = +∞.
Ejemplo 4.1.1. Veamos algunos ejemplos:
Sea f (x) = |x| para cada x ∈ R, entonces ∂ f (0) = [−1, 1].
√
Sea f (x) = − x + δ[0,+∞) (x) para cada x ∈ R, entonces ∂ f (0) = 0.
/
R
R
(0, 0)
epi f R
epi f
R
0
L L
√
Figura 4.1: Epı́grafo de las funciones f (x) = |x| y f (x) = − x + δ[0,+∞) (x).
Como muestra uno de los ejemplos anteriores, el subdiferencial de una función convexa puede
ser vacı́o, incluso si la función es finita en el punto. Un criterio, relativamente simple, para evitar esto
es que la función sea continua. Esto es una consecuencia del Teorema de Hahn-Banach.
Proposición 4.1. Sean (X, k · k) un espacio de Banach y f : X → R ∪ {+∞} una función convexa.
Suponga que f es continua en x ∈ dom( f ), entonces ∂ f (x) 6= 0/
Demostración. Dado que f es continua en x, podemos encontrar r > 0 tal que f (x + rd) ≤ f (x) + 1
para cada d ∈ BX . De donde se tiene que int(epi( f )) 6= 0/ y además (x, f (x)) ∈
/ int(epi( f )). Luego por
∗ ∗
el Teorema de Hahn-Banach (Lema 2.1), existe (x , α) ∈ X × R \ {0} tal que
hx∗ , xi + α f (x) ≤ hx∗ , yi + αλ, ∀(y, λ) ∈ epi( f )
De aquı́ se concluye que α ≥ 0 pues (x, λ) ∈ epi( f ) para cualquier λ ≥ f (x). Además, como x + rd ∈
dom( f ) para cada d ∈ BX , tenemos que si α = 0 entonces
hx∗ , xi ≤ hx∗ , x + rdi, ∀d ∈ BX .
60
Capı́tulo 4, Section 4.1 Subdiferencial
Esto a su vez implica que kx∗ k∗ = 0 y por lo tanto (x∗ , α) = 0, llevándonos a una contradicción. Por
lo tanto α > 0, y sin perdida de generalidad podemos asumir que α = 1, multiplicando x∗ por α1 si es
necesario. Entonces, tenemos que
hx∗ , x − yi + f (x) ≤ λ, ∀(y, λ) ∈ epi( f ).
Tomando λ = f (y), vemos que x∗ ∈ ∂ f (x), y la proposición ha sido demostrada.
S x22 = x1
x̄ = (0, 0)
R
NS (0, 0)
x2 = x1
61
Optimización convexa no diferenciable Capı́tulo 4, Section 4.1
De aquı́ se concluye que si µ( f (x) − γ) = 0 se tendrá también que µx∗ ∈ NΓγ ( f ) (x).
62
Capı́tulo 4, Section 4.1 Subdiferencial
de donde obtenemos, al tomar ı́nfimo sobre t, que f 0 (x; d2 ) > −∞. Tomemos ahora ε > 0, por
definición de ı́nfimo podemos encontrar s2 > 0 para el cual f (x+s2 ds22 )− f (x) ≤ f 0 (x; d2 ) + ε. Sigue
que por la monotonı́a del cuociente tenemos
f (x + td1 ) − f (x)
f 0 (x; d1 + d2 ) ≤ + f 0 (x; d2 ) + ε, ∀t ∈ (0, s2 ].
t
Finalmente, tomando ı́nfimo sobre t en la desigualdad anterior llegamos a la conclusión, ya
que ε > 0 es un número positivo arbitrario.
63
Optimización convexa no diferenciable Capı́tulo 4, Section 4.1
f (x + td) − f (x)
hx∗ , di ≤ , ∀t ∈ (0, +∞).
t
De esta desigualdad se concluye fácilmente que hx∗ , di ≤ f 0 (x, d). Por otra parte, tomemos
x∗ ∈ X∗ tal que hx∗ , di ≤ f 0 (x, d) para todo d ∈ X. Usando la primera parte con t = 1 tenemos
Ahora veremos que la relación entre el subdiferencial y la derivada direccional de una función
convexa es unı́voca, en el sentido que la derivada direccional puede ser calculada a partir del sub-
diferencial. El siguiente resultado mostrará en particular que una función convexa es diferenciable
si y sólo si el subdiferencial tiene un único elemento. Cabe destacar que el resultado que veremos
a continuación es una consecuencia de la versión analı́tica del Teorema de Hahn-Banach, la cual es
equivalente a la versión geométrica de este teorema (Lema 2.1); a partir de uno se puede demostrar
el otro.
Recuerdo: Teorema analı́tico de Hahn-Banach
La versión analı́tica del Teorema de Hahn-Banach dice que un funcional lineal continuo defi-
nido solo en un subespacio de X que satisface una cota apropiada, puede ser extendido a todo
el espacio, satisfaciendo la misma cota. Por esta razón, mucha veces el teorema se conoce
como el Teorema de extensión de Hahn-Banach.
`0 (x) ≤ g(x), ∀x ∈ X0 .
Proposición 4.4. Sean (X, k · k) un espacio de Banach y f : X → R ∪ {+∞} una función convexa.
Suponga que f es continua en x ∈ dom( f ). Entonces
64
Capı́tulo 4, Section 4.1 Subdiferencial
De aquı́ no es difı́cil ver que v 7→ g(v) := f 0 (x; v) es positivamente homogénea. Además, si α < 0,
entonces
`0 (αd) = α f 0 (x; d) = − f 0 (x; −αd) ≤ f 0 (x; αd),
donde la última desigualdad viene del hecho que d 7→ f 0 (x; d) es sublineal y f 0 (x; 0) = 0. Luego por
el Teorema de extensión de Hahn-Banach (Lema 4.1), existe un funcional lineal ` : X → R tal que
`(d) = f 0 (x; d) y `(v) ≤ f 0 (x; v), ∀v ∈ X.
Tomando v = y − x para cualquier y ∈ dom( f ) y usando Proposición 4.3, vemos que
`(y − x) ≤ f 0 (x; y − x) ≤ f (y) − f (x).
Luego para concluir basta ver que ` es continuo, y que por lo tanto existe x∗ ∈ X∗ tal que ` = hx∗ , ·i.
Dado que f es continuo en x, se tiene que para todo ε > 0, existe r > 0 tal que | f (x) − f (y)| ≤ ε para
todo y ∈ BX (x, r). Luego tenemos, por la desigualdad del subdiferencial que
`(y − x) ≤ | f (x) − f (y)| ≤ ε, ∀y ∈ BX (x, r).
Evaluando en 2x − y en vez de en y, se obtiene la desigualdad con el valor absoluto. Esto implica
que ` es continuo en x, pero al ser lineal, debe ser continuo en todo punto de X y por lo tanto existe
x∗ ∈ X∗ tal que ` = hx∗ , ·i. Esto concluye la demostración del resultado.
65
Optimización convexa no diferenciable Capı́tulo 4, Section 4.1
Regla de la suma
Como mencionamos anteriormente, en muchas ocaciones estamos interesados en encontrar mı́ni-
mos de una función que se puede escribir como la suma de dos funciones convexas, con al menos una
de ella no diferenciable; por ejemplo funciones del tipo fS := f + δS . Por esta razón es importante
proveer una regla para calcular el subdiferencial de la suma de funciones convexas.
Teorema 4.2 (Moreau-Rockafellar). Sean (X, k · k) un espacio de Banach y f1 , f2 : X → R ∪ {+∞}
funciones propias convexas y s.c.i.. Supongamos que f1 es continua en x0 ∈ dom( f1 ) ∩ dom( f2 ).
entonces
∂ f1 (x) + ∂ f2 (x) = ∂( f1 + f2 )(x), ∀x ∈ X.
Demostración. Comencemos la demostración probando la inclusión (⊆) que resulta de la definición.
Efectivamente, tenemos que si x1∗ ∈ ∂ f1 (x) y x2∗ ∈ ∂ f2 (x) entonces
Notemos que (x, λ) ∈ B si y sólo si λ ≤ f1 (x), y por lo tanto r no puede ser positivo. Además, como
(x0 , g(x0 ) + ε) ∈ int(A) para algún ε > 0 debemos necesariamente tener que r < 0. En efecto, si r = 0
y dado que (x0 , f1 (x) + f2 (x) − f2 (x0 )) ∈ B, entonces tendrı́amos
h−x2∗ , yi − λ < h−x2∗ , ỹi − ( f1 (x) + f2 (x) − f2 (ỹ)), ∀(y, λ) ∈ int(A), ỹ ∈ dom( f2 )
66
Capı́tulo 4, Section 4.1 Subdiferencial
donde x2∗ = 1r y∗ . Notemos que, para todo y ∈ int dom f1 y λ ∈ R tales que f1 (y) − hx∗ , yi < λ, se tiene
que (y, λ) ∈ int(A) y luego, haciendo λ → f1 (y) − hx∗ , y − xi, obtenemos que
h−x2∗ , yi − f1 (y) + hx∗ , y − xi ≤ h−x2∗ , ỹi − ( f1 (x) + f2 (x) − f2 (ỹ)), ∀y ∈ int dom f1 , ỹ ∈ dom f2 .
lo que, en conjunto con la Proposición 2.1, implican que −x2∗ + x∗ ∈ ∂ f1 (x) y análogamente, tomando
y=x
f2 (x) + hx2∗ , y − xi ≤ f2 (y), ∀y ∈ dom( f2 ),
de donde concluimos que x2∗ ∈ ∂ f2 (x). Definiendo x1∗ = x∗ − x2∗ se tiene que x1∗ ∈ ∂ f1 (x) y x1∗ + x2∗ = x∗
lo que termina la demostración.
(0, 0)
R
C2 C1
Regla de la composición
Además de la Regla de la suma, el subdiferencial satisface un regla sobre la composición con
operadores lineales, la cual es lo más cercano que podemos obtener a una regla de la cadena para
subdiferenciales de funciones convexas. Esta regla será de particular utilidad para resolver problemas
tales como el problema de Compresión y recuperación de imágenes (Sección 1.2), el cual tiene una
estructura del tipo
Minimizar f (x) + g(Ax) sobre todos los x ∈ X
donde A : X → Y es un operador lineal continuo y g : Y → R ∪ {+∞} es una función convexa.
67
Optimización convexa no diferenciable Capı́tulo 4, Section 4.1
∂( f ◦ A)(x) = A∗ ∂ f (Ax), ∀x ∈ X.
Demostración. Tal como con el Teorema de Moreau-Rockafellar, una de las inclusiones es fácil y la
otra requiere más desarrollo. Sea x ∈ X y comencemos con la inclusión A∗ ∂ f (Ax) ⊆ ∂( f ◦ A)(x), que
es la más directa. De la definición misma se tiene que si y∗ ∈ ∂ f (Ax) entonces
f (Ax)+ ≺ y∗ , y − Ax ≤ f (y), ∀y ∈ Y.
En particular, esto es cierto para y = Az, con z ∈ X arbitrario. Entonces, usando la definición de
operador adjunto tenemos que A∗ y∗ ∈ ∂( f ◦ A)(x), pues
Veamos ahora la otra inclusión. Dado que f es continua en algún y0 ∈ im(A), tenemos que
int(epi( f )) 6= 0/ y además la siguiente inclusión siempre es cierta
puede ser separado del conjunto int(epi( f )). Efectivamente, ambos conjuntos son convexos (Propo-
sición 2.1) y no vacı́os, y además, si (y, λ) ∈ B ∩ int(epi( f )), entonces para algún z ∈ X debemos
tener que y = Az, λ = f (Ax) + hx∗ , z − xi y
Pero esta desigualdad estricta es imposible ya que x∗ ∈ ∂( f ◦ A)(x). Por lo tanto, B ∩ int(dom( f )) = 0/
y por el Teorema de separación de de Hahn-Banach (Lema 2.1), existe (y∗ , r) ∈ Y∗ × R \ {0} tal que
(4.2) ≺ y∗ , y +rλ <≺ y∗ , Az +r( f (Ax) + hx∗ , z − xi), ∀(y, λ) ∈ int(epi( f )), z ∈ X.
68
Capı́tulo 4, Section 4.2 Condiciones de optimalidad
Evaluando en y = Ax, z = x, λ > f (Ax), obtenemos que r < 0. Normalizando, podemos entonces
asumir que r = −1. Luego, en virtud de la Proposición 2.1, para todo y ∈ dom f , existe una suce-
sión {(yn , λn )}n∈N en int epi( f ) (que satisface (4.2)) tal que (yn , λn ) → (y, f (y)) ∈ epi( f ), de donde
haciendo n → ∞ se obtiene
(4.3) ≺ y∗ , y − f (y) ≤≺ y∗ , Az − f (Ax) − hx∗ , z − xi, ∀y ∈ dom f , z ∈ X.
Por otra parte, evaluando (4.3) en y = Ax y z = x ± d para algún d ∈ X \ {0}, llegamos a
hA∗ y∗ − x∗ , di = 0, ∀d ∈ X \ {0}
de donde podemos concluir que x∗ = A∗ y∗ . Ahora bien, evaluando (4.3) en z = x obtenemos
f (Ax)+ ≺ y∗ , y − Ax ≤ f (y), ∀y ∈ dom( f ),
lo que implica que y∗ ∈ ∂ f (Ax) y por lo tanto x∗ ∈ A∗ ∂ f (Ax), lo que completa la demostración.
El siguiente es un contraejemplo que muestra que la igualdad no se tiene si la condición que la
función sea continua en un punto de la imagen de A.
Ejemplo 4.1.4. Supongamos que X = R, Y = R2 , sea C = {(x, y) ∈ R2 | x2 + (y − 1)2 ≤ 1}, f = δC
y A : x 7→ (x, 0). Luego im A = R × {0}, A∗ : (x, y) 7→ x, dom f ∩ im A = C ∩ (R × {0}) = {(0, 0)}, de
donde f ◦ A = δ{0} y ∂( f ◦ A)(0) = R. Por otra parte, A0 = (0, 0) y ∂ f (A0) = ∂δC (0, 0) = {0} × R− ,
de donde A∗ ∂ f (A0) = {0} ( R = ∂( f ◦ A)(0). Notar que f no es continua en {(0, 0)} = dom f ∩ im A.
(0, 0)
im A = R × {0}
69
Optimización convexa no diferenciable Capı́tulo 4, Section 4.2
Teorema 4.3 (Regla de Fermat III). Sean (X, k · k) un espacio de Banach, f : X → R ∪ {+∞} una
función propia convexa y s.c.i., y S ⊆ X un conjunto convexo cerrado y no vacı́o. Supongamos que
alguna de las siguientes condiciones es cierta:
1. Existe x0 ∈ int(S) tal que f es finita en x0 .
2. Existe x0 ∈ S tal que f es continua en x0 .
Entonces, x̄ ∈ S es una solución de (P) si y sólo si
0 ∈ ∂ f (x̄) + NS (x̄)
o equivalentemente
∃x∗ ∈ ∂ f (x̄) tal que hx∗ , x − x̄i ≥ 0, ∀x ∈ S.
Demostración. Notemos que x̄ es una solución de (P) si y sólo si x̄ ∈ arg mı́n( fS ), con fS = f + δS .
Luego, por la Regla de Fermat (Teorema 4.1), x̄ es una solución de (P) si y sólo si 0 ∈ ∂ fS (x̄).
Finalmente, cualquiera de las condiciones de calificación del enunciado implican la hipótesis del
Teorema de Moreau-Rockafellar (Teorema 4.2). Por lo tanto, aplicando ese resultado obtenemos el
resultado buscado pues
∂ fS (x̄) = ∂ f (x̄) + ∂δS (x̄) = ∂ f (x̄) + NS (x̄).
Restricciones de desigualdad
Concentrémonos en el problema de programación convexa siguiente:
(PD ) Minimizar f (x) sobre los x ∈ X que satisfacen la restricción gi (x) ≤ 0 para i = 1, . . . , p.
Para obtener las condiciones de optimalidad del problema precedente necesitamos primero el
converso de la Proposición 4.2. Por simplicidad mostraremos el resultado para espacio de Banach
reflexivo, sin embargo el resultado es igual de válido para espacio que no lo son.
Proposición 4.6. Sean (X, k · k) un espacio de Banach reflexivo y f : X → R una función convexa y
continua tal que Γγ ( f ) 6= 0/ para cierto γ > ı́nfX ( f ). Luego para todo x ∈ Γγ ( f ) se tiene
η ∈ NΓγ ( f ) (x) =⇒ ∃µ ≥ 0, ∃x∗ ∈ ∂ f (x), tales que η = µx∗ y µ( f (x) − γ) = 0.
70
Capı́tulo 4, Section 4.2 Condiciones de optimalidad
Demostración. Recordemos primero que, gracias a Proposición 4.1, tenemos que ∂ f (x) 6= 0/ para
todo x ∈ X, pues f es continua en X. Separemos la demostración en varias etapas.
1. Tomemos η ∈ NΓγ ( f ) (x) y asumamos que η 6= 0; el caso η = 0 es directo de tomar µ = 0. Luego,
por definición tenemos
hη, yi ≤ hη, xi, ∀y ∈ Γγ ( f ).
Notemos que si f (y) < γ entonces necesariamente se tendrá que hη, yi < hη, xi. En efecto, si
esto no es ası́, dado que η ∈ NΓγ ( f ) (x) deberı́amos tener que hη, yi = hη, xi, pero por conti-
nuidad de f se tendrá que existe r > 0 tal que BX (y, r) ⊆ Γγ ( f ), con lo cual podemos afirmar
que
hη, y + rdi ≤ hη, xi, ∀d ∈ BX ,
y por lo tanto, dado que hη, yi = hη, xi, tenemos
rhη, di ≤ 0, ∀d ∈ BX ,
lo que implica que kηk∗ = 0, es decir η = 0, lo que no puede ser. Notemos además que lo
anterior es también válido si y = x. En consecuencia, si f (x) < γ se tendrá necesariamente que
η = 0, y la conclusión es válida tomando µ = 0.
2. Resta ver ahora el caso f (x) = γ para concluir la demostración. Consideremos el conjunto
Sη = {y ∈ X | hη, yi ≥ hη, xi}.
Notemos que si y ∈ Sη , entonces usando la contra-recı́proca de la afirmación demostrada ante-
riormente tenemos que f (y) ≥ γ = f (x). En otras palabras, x ∈ X es óptimo del problema
Minimizar f (y) sobre todos los y ∈ X que satisfacen la restricción y ∈ Sη .
Este problema es convexo y por lo tanto gracias al Teorema 4.3 tenemos que
0 ∈ ∂ f (x) + NSη (x).
3. Notemos que para cada ν ∈ NSη (x) \ {0} tenemos que si hν, yi = 0 entonces hη, yi = 0. En efec-
to, razonando por contradicción si existiese y ∈ X tal que hν, yi = 0 pero hη, yi =
6 0, podemos
asumir sin pérdida de generalidad que hη, yi > 0. La continuidad implica que podemos encon-
trar r > 0 tal que hη, y+rdi ≥ 0 para todo d ∈ BX . En particular, tendremos que y+rd +x ∈ Sη .
Ahora, dado que ν ∈ NSη (x) y hν, yi = 0 tenemos que
rhν, di = hν, y + rd + x − xi ≤ 0, ∀d ∈ BX .
Esto nos llevarı́a a concluir que kνk∗ = 0, lo cual no puede ser.
4. Sea ν ∈ NSη (x) \ {0} y consideremos B = {tν | t ∈ R}. Tenemos entonces que η ∈ B, pues si
no, por el Teorema de Hahn-Banach (Lema 2.1) existirá y∗∗ ∈ X∗∗ tal que
hy∗∗ , ηi < hy∗∗ ,tνi, ∀t ∈ R.
Como lo anterior es cierto para todo t ∈ R, necesariamente tenemos que tener hy∗∗ , νi = 0 y
por lo tanto hy∗∗ , ηi < 0. Ahora dado que X es reflexivo, existe y ∈ X tal que hy∗∗ , x∗ i = hx∗ , yi
para cada x∗ ∈ X∗ . Sigue que hν, yi = 0 y hη, yi < 0, lo cual contradice lo demostrado en el
punto anterior.
71
Optimización convexa no diferenciable Capı́tulo 4, Section 4.2
5. Juntando toda la información anterior llegamos a que existe µ ∈ R y x∗ ∈ ∂ f (x) tales que
η = µx∗ para el caso f (x) = γ. Dado que η 6= 0, entonces x∗ 6= 0 y µ 6= 0. En particular, por la
Regla de Fermat (Teorema 3.4) se tiene que γ = f (x) > ı́nfX ( f ) y por lo tanto existe y ∈ X tal
que f (y) < γ. Notemos además que
µhx∗ , y − xi = hµx∗ , y − xi ≤ 0,
Teorema 4.4 (Teorema de Kuhn-Tucker I). Sean (X, k · k) un espacio de Banach reflexivo, f : X → R
y g1 , . . . , g p : X → R funciones convexas y continuas. Supongamos que existe x0 ∈ X tal que
gi (x0 ) < 0, ∀i = 1, . . . , p.
Demostración. Notemos que gracias al Teorema 4.3, x̄ ∈ X es una solución de (PD ) si y sólo si
0 ∈ ∂ f (x̄) + NS (x̄),
con S = {x ∈ X | gi (x) ≤ 0, i = 1, . . . , p}. Recordemos que NS (x) = ∂δS (x) para cada x ∈ X. Además,
si denotamos Si = {x ∈ X | gi (x) ≤ 0} para cada i ∈ {1, . . . , p, sigue que
p
δS (x) = ∑ δSi (x), ∀x ∈ X.
i=1
gi (x0 ) < 0, ∀i = 1, . . . , p
η ∈ NSi (x) ⇐⇒ ∃µi ≥ 0, ∃xi∗ ∈ ∂gi (x), tales que η = µi xi∗ y µi gi (x) = 0.
Pero esto es consecuencia directa de la Proposición 4.2 y Proposición 4.6. Luego el teorema ha sido
demostrado.
72
Capı́tulo 4, Section 4.2 Condiciones de optimalidad
(PDI ) Minimizar f (x) sobre los x ∈ X tales que gi (x) ≤ 0 para i = 1, . . . , p y `(x) = (α1 , . . . , αq )
La versión que estudiaremos ahora del Teorema de Kuhn-Tucker es una extensión de Teorema 4.4.
Teorema 4.5 (Teorema de Kuhn-Tucker II). Sean (X, k·k) un espacio de Banach reflexivo, f : X → R
y g1 , . . . , g p : X → R funciones convexas y continuas. Sean x1∗ , . . . , xq∗ ∈ X∗ y α1 , . . . , αq ∈ R dados.
Supongamos que existe x0 ∈ X tal que
Demostración. Notemos que gracias al Teorema 4.3, x̄ ∈ X es una solución de (PDI ) si y sólo si
q
Lo que a su vez implica que ∑ j=1 λ j x∗j ∈ NH (x̄). Hemos aquı́ demostrado la implicancia (⇐).
73
Optimización convexa no diferenciable Capı́tulo 4, Section 4.2
2. Veamos ahora que NH (x̄) es un espacio vectorial. Dado que NH (x̄) es un conjunto convexo,
bastará mostrar que si η ∈ NH (x̄) entonces −η ∈ NH (x̄). En efecto, notemos que si η ∈ NH (x̄)
entonces
hη, x − x̄i ≤ 0, ∀x ∈ H
y que además, si x ∈ H, entonces igualmente 2x̄ − x ∈ H. Esto último se debe a que
hx∗j , 2x̄ − xi = 2α j − α j = α j , ∀ j = 1, . . . , q.
3. Notemos que lo demostrado en el paso anterior implica que para todo x ∈ X la siguiente pro-
piedad es cierta
Esto implica que hx∗j , x − x̄i = 0 para todo j = 1, . . . , q pues si no, podemos hacer λ j → ±∞ y
llegar a una contradicción. Ahora bien, por (4.9) tenemos que hη, x − x̄i = 0, lo cual tampoco
puede ser. Por lo tanto, η debe pertenecer a B y la conclusión sigue.
74
Capı́tulo 4, Section 4.3 Aproximación de Moreau-Yosida
Teorema 4.6 (Teorema de Kuhn-Tucker III). Sea (X, k·k) un espacio de Banach reflexivo, f : X → R
y g1 , . . . , g p : X → R funciones convexas y continuas. Sean x1∗ , . . . , xq∗ ∈ X∗ y α1 , . . . , αq ∈ R dados.
Supongamos que existe x0 ∈ X tal que
0 ∈ ∂x L(x̄, µ, λ) y µi gi (x̄) = 0, ∀i = 1, . . . , p.
Más aún, si la función objetivo f y las funciones g1 , . . . , g p son diferenciables en una vecindad de x̄,
entonces la condición anterior es equivalente a
p q
0 = ∇x L(x̄, µ, λ) = ∇ f (x̄) + ∑ µi ∇gi (x̄) + ∑ λ j x∗j y µi gi (x̄) = 0, ∀i = 1, . . . , p.
i=1 j=1
75
Optimización convexa no diferenciable Capı́tulo 4, Section 4.3
76
Capı́tulo 4, Section 4.3 Aproximación de Moreau-Yosida
1
2. Como (x, y) 7→ f (y) + 2α kx − yk2 es convexa, la convexidad de fα es directa del Ejercicio 2.
x−yα (x)
Veamos ahora que fα es Fréchet diferenciable con ∇ fα (x) = α . Por la parte anterior para
cualquier h ∈ X tenemos que
1
kx + h − yα (x + h)k2 − kx − yα (x)k2 .
fα (x + h) − fα (x) = f (yα (x + h)) − f (yα (x)) +
2α
x−yα (x)
Dado que α ∈ ∂ f (yα (x)) podemos deducir que
1 1
kx + h − yα (x + h)k2 − kx − yα (x)k2
fα (x + h) − fα (x) ≥ hx − yα (x), yα (x + h) − yα (x)i +
α 2α
pero
kx + h − yα (x + h)k2 − kx − yα (x)k2
= kyα (x + h) − yα (x) − h − (x − yα (x))k2 − kx − yα (x)k2
= kyα (x + h) − yα (x) − hk2 − 2hx − yα (x), yα (x + h) − yα (x) − hi
x−yα (x)
lo que implica que, si denotamos x∗ = α , entonces
x−yα (x)
Esto a su vez nos lleva a concluir que fα es Fréchet diferenciable con ∇ fα (x) = x∗ = α
pues, reuniendo las desigualdades anteriores llegamos a:
1
0 ≤ fα (x + h) − fα (x) − hx∗ , hi ≤ khk2 , ∀h ∈ X.
2α
3. Veamos que yα no-expansiva. Para ello notemos que ∇ fα (x) ∈ ∂ f (yα (x)), luego usando la
monotonı́a del subdiferencial tenemos
h∇ fα (x + h) − ∇ fα (x), yα (x + h) − yα (x)i ≥ 0, ∀h ∈ X,
hh − yα (x + h) + yα (x), yα (x + h) − yα (x)i ≥ 0, ∀h ∈ X,
y por lo tanto
77
Optimización convexa no diferenciable Capı́tulo 4, Section 4.3
Usando esto, y el hecho que yα es Lipschitz continuo, podemos extender las convergencia al
caso x ∈ dom( f ), lo que concluye la demostración
78
Capı́tulo 4, Section 4.4 Aproximación de Moreau-Yosida
Para aproximar los mı́nimos de f , proponemos generar una sucesión via la recurrencia
(4.10) xk+1 = proxαk f (xk ), ∀k ∈ N,
donde la condición inicial x0 ∈ X es arbitraria y αk > 0. En otras palabras tenemos que
1
fαk (xk ) = f (xk+1 ) + kxk − xk+1 k2 .
2αk
Estudiaremos ahora la convergencia de una sucesión generada por (4.10), el cual se conoce como
Método de Punto Proximal.
Teorema 4.7. Sean (X, h·, ·i) un espacio de Hilbert y f : X → R ∪ {+∞} una función propia convexa
y s.c.i. tal que arg mı́nX ( f ) es no vacı́o. Considere una sucesión {αk } ⊆ R que satisface
ı́nf αk = α > 0
k∈N
y la sucesión {xk } generada por (4.10) partiendo desde x0 ∈ X arbitrario. Entonces ∃x∞ ∈ arg mı́nX ( f )
tal que xk * x∞ cuando k → ∞.
Demostración. Sea k ∈ N y sea x̄ ∈ arg mı́nX ( f ). Usando la Proposición 4.7 y (4.10) deducimos
xk − xk+1
∈ ∂ f (xk+1 ),
αk
de donde, por convexidad de f obtenemos
1
(4.11) f (xk+1 ) + hxk − xk+1 , x̄ − xk+1 i ≤ f (x̄)
αk
o, equivalentemente,
1
kxk − xk+1 k2 + kxk+1 − x̄k2 − kxk − x̄k2 ≤ f (x̄).
f (xk+1 ) +
2αk
Usando que f (x̄) ≤ f (y) para cualquier y ∈ X, se obtiene
kxk+1 − x̄k2 ≤ kxk − x̄k2 − kxk − xk+1 k2 ,
de donde la sucesión {kxk − x̄k} es decreciente y positiva, por lo tanto convergente y {xk } es acotada.
Además, sumando sobre k entre 0 y n en la desigualdad anterior y usando la propiedad telescópica
deducimos
n
∑ kxk − xk+1k2 ≤ kx0 − x̄k2 − kxn+1 − x̄k2,
k=0
2
de donde concluimos que la serie ∑∞ k=0 kxk − xk+1 k es convergente y luego xk − xk+1 → 0. Para
concluir, basta usar el Lema 3.1. Sea z ∈ X un punto de acumulación débil de la sucesión {xk }, cuya
existencia está garantizada por el acotamiento de la misma. Digamos xkn * z. Usando que f es s.c.i.
para la topologı́a débil dado que es convexa (Proposición 2.3) y (4.11) se deduce
1
f (z) ≤ lı́m inf f (xkn ) = lı́m inf f (xkn ) + hxk −1 − xkn , x̄ − xkn i ≤ f (x̄),
k→+∞ n→+∞ αkn −1 n
donde la igualdad se obtiene del hecho que
ı́nf αkn ≥ α > 0, xkn −1 − xkn → 0 y xkn * z.
n≥0
De ese modo, z ∈ arg mı́nX ( f ) y el resultado se deduce de Lema 3.1 con S = arg mı́nX ( f ).
79
Optimización convexa no diferenciable Capı́tulo 4, Section 4.4
donde f : X → R ∪ {+∞} es una función convexa propia s.c.i. y g : X → R es otra función convexa,
pero Gâteaux diferenciable con gradiente L-Lipschitz continuo. Nos interesa ahora estudiar un méto-
do numérico para resolver problemas con esta estructura. El algoritmo que introduciremos se basa
en la siguiente idea:
Supongamos que x̄ ∈ arg mı́nX ( f + g). Entonces del teorema de Fermat y Teorema de Moreau-
Rockafellar (Teorema 4.2) se concluye
Esto motiva el Método del Gradiente Proximal. , que está definido a través de la recurrencia
donde x0 ∈ X es arbitrario y αk > 0. Notemos que esta es una extensión natural del método de punto
proximal. En efecto, ese algoritmo se recupera si tomamos el caso g ≡ 0.
Ahora estudiaremos la convergencia del método del Gradiente Proximal.
Teorema 4.8. Sea (X, h·, ·i) un espacio de Hilbert, f : X → R ∪ {+∞} y g : X → R dos funciones
propias convexas y s.c.i. tal que arg mı́nX ( f + g) es no vacı́o. Supongamos que g es Gâteaux diferen-
ciable en X con ∇g siendo L-Lipschitz continuo en X. Consideremos x0 ∈ X arbitrario, ε ∈ (0, L1 ) y
una sucesión {αk } ⊆ R tal que
2
ε ≤ αk ≤ − ε, ∀k ∈ N.
L
Entonces la sucesión {xk } generada por (4.13) converge débilmente a algún x∞ ∈ arg mı́nX ( f + g).
Demostración. Sea k ∈ N y sea x̄ ∈ arg mı́nX ( f + g). Usando la Proposición 4.7 y (4.13) deducimos
xk − xk+1
− ∇g(xk ) ∈ ∂ f (xk+1 ),
αk
de donde, por convexidad de f se obtiene
1
f (xk+1 ) + hxk − xk+1 , y − xk+1 i − h∇g(xk ), y − xk+1 i ≤ f (y), ∀y ∈ X,
αk
o, equivalentemente,
1
kxk − yk2 − kxk − xk+1 k2 − kxk+1 − yk2 ,
f (xk+1 ) ≤ f (y) + h∇g(xk ), y − xk+1 i + ∀y ∈ X.
2αk
80
Capı́tulo 4, Section 4.5 Método del Gradiente Proximal
L
g(xk+1 ) ≤ g(y) + h∇g(xk ), xk+1 − yi + kxk+1 − xk k2 , ∀y ∈ X.
2
Sumando las dos últimas desigualdades se deduce que, para todo y ∈ X,
(4.14)
1 L
( f + g)(xk+1 ) ≤ ( f + g)(y) + kxk − yk2 − kxk − xk+1 k2 − kxk+1 − yk2 + kxk − xk+1 k2 .
2αk 2
εL2
1 L
( f + g)(xk+1 ) ≤ ( f + g)(xk ) − − kxk − xk+1 k2 ≤ ( f + g)(xk ) − kxk − xk+1 k2 .
αk 2 4
εL2 n
∑ kxk − xk+1k2 ≤ ( f + g)(x0) − ( f + g)(xn+1)
4 k=0
2
de donde concluimos que la serie ∑∞k=0 kxk − xk+1 k es convergente y luego xk − xk+1 → 0.
Ahora, tomando y = x̄ en (4.14) de ε ≤ αk < 2/L se tiene
1
kxk − x̄k2 − kxk+1 − x̄k2 + (αk L − 1) kxk − xk+1 k2
( f + g)(xk+1 ) ≤ ( f + g)(x̄) +
2αk
1
kxk − x̄k2 − kxk+1 − x̄k2 + kxk − xk+1 k2 ,
(4.15) ≤ ( f + g)(x̄) +
2ε
de donde, usando que ( f + g)(x̄) ≤ ( f + g)(y) para cualquier y ∈ X, concluimos
de donde z ∈ arg mı́nX ( f + g) y el resultado se deduce de Lema 3.1 con S = arg mı́nX ( f + g).
81
Optimización convexa no diferenciable Capı́tulo 4, Section 4.5
4.5. Ejercicios
1. C ARACTERIZACI ÓN DE FUNCIONES CONVEXAS NO DIFERENCIABLE
Muestre que, análogamente al Teorema 3.1, se tiene que si (X, k · k) un espacio vectorial nor-
mado y f : X → R ∪ {+∞} es propia se tiene que las siguientes afirmaciones son equivalentes:
2. C ONJUGADA DE F ENCHEL
Sean (X, k · k) un espacio de Banach y f : X → R ∪ {+∞} una función propia convexas y s.c.i.
Definimos la función conjugada de f , denotada f ∗ : X∗ → R ∪ {+∞} via la fórmula:
a) Demuestre que f ∗ es una función convexa y s.c.i., y que f ∗ es propia si ı́nfX ( f ) > −∞.
b) Pruebe que x∗ ∈ ∂ f (x) si y sólo si f (x) + f ∗ (x∗ ) = hx∗ , xi.
c) Calcule la función conjugada de f = k · k.
3. S UBDIFERENCIAL DE LA NORMA
Sean (X, k · k) un espacio de Banach. Demostrar que ∂k · k(0) = BX∗ y que en general se tiene
que
∂k · k(x) = {x∗ ∈ X∗ | kx∗ k∗ ≤ 1, hx∗ , xi = kxk}, ∀x ∈ X.
4. I NF - CONVOLUCI ÓN
Sean (X, k·k) un espacio de Banach, f : X → R∪{+∞} y g : X → R∪{+∞} funciones propias
convexas y s.c.i.. Se define la inf-convolución de f y g mediante
∇( f g)(x̄) = ∇g(x̄2 ).
82
Capı́tulo 4, Section 4.5 Ejercicios
donde fi : Xi → R ∪ {+∞} son funciones propias convexas y s.c.i.. Muestre que para todo
α > 0 se tiene que
proxα f (x) = (proxα f1 (x1 ), . . . , proxα fn (xn )), , ∀x = (x1 , . . . , xn ) ∈ X.
Encontrar una expresión explı́cita para f (x) = kxk1 = ∑ni=1 |xi |, en el caso X = Rn .
b) Sea S ⊂ X un conjunto convexo, cerrado, no vacı́o de un espacio de Hilbert (X, h·, ·i) y
sea f = δS . Muestre que para todo α > 0 se tiene proxα f (x) = proy(x, S) para todo x ∈ X.
83
Optimización convexa no diferenciable Capı́tulo 4, Section 4.5
84
PARTE II
TEORÍA LOCAL DE OPTIMIZACIÓN
Caso general
Resumen. En esta parte del curso nos enfocares en estudiar problemas generales de opti-
mización, no necesariamente convexos. Veremos que la principal diferencia en este caso
es que el análisis es esencialmente local y que las condiciones necesarias de optimali-
dad pueden no ser suficientes. Esta parte del curso se dividirá en dos. En una primera
instancia estudiaremos problemas sin restricciones, que será el análogo al capı́tulo de
Optimización Convexa Diferenciable. Luego pasaremos a problemas de Programación
Matemática donde repasaremos las condiciones de optimalidad de Kuhn-Tucker.
85
CAPÍTULO 5
Optimización irrestricta
La optimización convexa entrega una buena intuición sobre lo que es la optimización en general,
y de alguna forma puede ser vista como el caso más favorable que uno puede estudiar. A partir de
ahora usaremos esa intuición para analizar problemas más generales.
A lo largo de este capı́tulo trabajaremos básicamente con funciones f : X → R ∪ {+∞} definidas
sobre un espacio de vectorial normado (X, k · k), que para muchos efectos será tomado simplemente
como Rn dotado de la norma Euclideana, que hemos denotado hasta ahora por | · |. En general, y de
forma similar a lo hecho en el capı́tulo 3 , asumiremos que f : X → R ∪ {+∞} es, al menos, Gâteaux
diferenciable en int(dom( f )).
87
Optimización irrestricta Capı́tulo 5, Section 5.2
Ejemplo 5.1.1. Consideremos la función sobre R definida por f (x) = x2 − x4 . No es difı́cil ver que
x̄ = 0 es un mı́nimo local de f . Efectivamente, la desigualdad
f (0) = 0 ≤ x2 − x4
es trivial bajo la condición |x| < 1 (de hecho es un mı́nimo local estricto). Luego, x̄ = 0 es un mı́nimo
local de f pero no es un mı́nimo global de f , puesto que f (x) < 0 para cualquier |x| > 1. Más aún,
se verifica que f (x) → −∞ si |x| → +∞, es decir, f no es acotada inferiormente.
x̄
R
La primera gran diferencia que existe entre la optimización convexa y el caso general es que,
contrariamente a lo mostrado en el ejemplo anterior, mı́nimos locales de funciones convexas son
también mı́nimos globales.
Proposición 5.1. Sea (X, k · k) un espacio vectorial normado y f : X → R ∪ {+∞} una función
convexa dada. Si x̄ ∈ X es un mı́nimo local de f entonces x̄ ∈ arg mı́nX ( f ).
Sea y ∈ X y probemos que f (x̄) ≤ y. Si y ∈ BX (x̄, r) no hay nada que probar, ası́ que supongamos que
x̄k (y − x̄) donde 2ky−x̄k ∈ (0, 1) y, además, z ∈ BX (x̄, r). Luego
r r
ky − x̄k > r y definamos z = x̄ + 2ky−
f (x̄) ≤ f (z) y, por convexidad de f , se tiene
r
f (z) ≤ f (x̄) + ( f (y) − f (x̄)),
2ky − x̄k
2ky−x̄k
de donde f (y) − f (x̄) ≥ r ( f (z) − f (x̄)) ≥ 0 de donde se deduce el resultado.
88
Capı́tulo 5, Section 5.2 Condiciones necesarias de optimalidad
ecuación D f (x̄) = 0. En el caso general esto es solamente una condición necesaria, pero no suficien-
te; por ejemplo la función x 7→ x3 satisface la condición en x̄ = 0, pero x̄ no es un mı́nimo (global ni
local) de la función.
A continuación estudiaremos condiciones necesarias de optimalidad, similares a la Regla de Fer-
mat. Dado que éstas involucran las derivadas de la función objetivo, nos bastará conocer el compor-
tamiento de la función en una vecindad del mı́nimo en cuestión. Por esta razón las condiciones de
optimalidad se puede obtener para mı́nimos locales y no solamente para mı́nimos globales.
(CNPO) D f (x̄) = 0.
y sea d ∈ X \ {0}. Para todo t < r/kdk se tiene que x̄ + td ∈ BX (x̄, r) y, luego,
f (x̄ + td) − f (x̄)
(5.1) ≥ 0.
t
Tomado lı́mite t → 0+ se concluye D f (x̄)(d) ≥ 0 para todo d ∈ X \ {0} y el resultado se concluye
reemplazando d por −d en el razonamiento anterior.
Notemos primero que (CNPO), para el caso de espacios de Hilbert y funciones Gâteaux diferen-
ciables se limita simplemente a la condición
∇ f (x̄) = 0.
Por otra parte, en la demostración del Teorema 5.1 podrı́amos cambiar f por − f y obtener la misma
conclusión. Esto quiere decir que (CNPO) es ciega con respecto a la operación que se está ejecutan-
do, ya sea minimizar o maximizar. Además, como mencionamos anteriormente en el ejemplo de la
función x 7→ x3 , hay puntos que pueden satisfacer (CNPO) y no ser ni mı́nimos ni máximos de una
función. Con el fin de abarcar todo estas clases de puntos introducimos la siguiente definición.
Definición 5.2 (Puntos crı́ticos). Sea (X, k · k) un espacio vectorial normado y f : X → R ∪ {+∞}
una función Gâteaux diferenciable en int(dom( f )). Diremos que un punto x̄ ∈ int(dom( f )) es un
punto crı́tico de f si satisface (CNPO), es decir, D f (x̄) = 0.
Ejemplo 5.2.1. Consideremos la función f : R → R definida por f (x) = 51 x5 − 13 x3 . Esta función
tiene tres puntos crı́ticos x̄1 = −1, x̄2 = −1 y x̄3 = 1. Del grafo de la función podemos concluir que,
x̄1 es un máximo local y x̄3 es un mı́nimo local. El punto x̄2 no es ni mı́nimo ni máximo local.
89
Optimización irrestricta Capı́tulo 5, Section 5.2
x̄
R
90
Capı́tulo 5, Section 5.3 Condiciones suficientes de optimalidad
Es importante destacar que (CNSO) para el caso X = Rn y f dos veces Gâteaux diferenciable se
traduce en
∇ f (x̄) = 0 y ∇2 f (x̄) ∈ Sn+ (R),
donde ∇2 f (x̄) es la matriz Hessiana de la función f en el punto x̄. En otras palabras, para utilizar
(CNSO) en este caso es útil conocer los valores propios de la matriz ∇2 f (x̄); si todos ellos son no
negativos, entonces podemos concluir que ∇2 f (x̄) ∈ Sn+ (R).
Ejemplo 5.2.2. Retomemos los datos del Ejemplo 5.2.1. En este caso tenemos que ∇2 f (x) = 4x3 −2x.
Dado que ∇2 f (−1) = −2 podemos inmediatamente descartar el punto x̄1 = −2 como mı́nimo local.
Notemos que ∇2 f (0) = 0 por lo que no podemos descartar analı́ticamente el punto x̄2 = 0 como
mı́nimo o máximo local. Además, efectivamente tenemos que ∇2 f (1) = 2 > 0 por lo que el punto
x̄3 = 1 es candidato a ser mı́nimo local.
De aquı́ concluimos que (x̄1 , ȳ1 ) = (0, 0) es candidato a ser mı́nimo local, pues los valores propios
de ∇2 (x̄1 , ȳ1 ) son 1 y 2. Además, (CNSO) nos permite también descarta los puntos (x̄2 , ȳ2 ) y (x̄3 , ȳ3 ),
pues la matriz Hessiana en este caso tiene un valor propio positivo y otro negativo (en ambos casos).
Teorema 5.3 (Condición suficiente de segundo orden). Sea (X, k · k) un espacio de vectorial nor-
mado y f : X → R ∪ {+∞} una función dos veces Fréchet diferenciable en una vecindad de x̄ ∈ X.
Supongamos que x̄ es un punto crı́tico de f y que existe α > 0 tal que
Demostración. Sea r > 0 tal que f es dos veces Fréchet-diferenciable en BX (x̄, r). Primero probare-
mos que, para h ∈ BX (0, r)
1
f (x̄ + h) − f (x̄) − D f (x̄)(h) − D2 f (x̄)(h, h) = o(khk2 ).
2
91
Optimización irrestricta Capı́tulo 5, Section 5.4
En efecto, llamando
1
ϕ(h) := f (x̄ + h) − f (x̄) − D f (x̄)(h) − D2 f (x̄)(h, h),
2
por simetrı́a de D2 f (x̄)(·, ·) se tiene
Dϕ(h)(k) = D f (x̄ + h)(k) − D f (x̄)(k) − D2 f (x̄)(h, k)
y la Fréchet diferenciablilidad de segundo orden implica
kDϕ(h)k∗
lı́m = 0.
h→0 khk
De ese modo, como ϕ(0) = 0 se tiene del Teorema del Valor Medio aplicado a t 7→ ϕ(th) que existe
λ ∈ (0, 1) tal que
(5.2) |ϕ(h)| = |ϕ(h) − ϕ(0)| = |Dϕ(λh)(h)| ≤ kDϕ(λh)k∗ khk,
de donde
|ϕ(h)| kDϕ(λh)k∗ kDϕ(λh)k∗
≤ ≤
khk2 khk kλhk
y el resultado se obtiene tomando h → 0.
Por lo tanto, usando este resultado y que D f (x̄) = 0 por ser punto crı́tico, se obtiene
1 α
f (x̄ + h) − f (x̄) = D2 f (x̄)(h, h) + o(khk2 ) ≥ khk2 + o(khk2 )
2 2
y tomando r > 0 tal que o(khk2 )/khk2 ≤ α/4 para todo h ∈ BX (0, r) \ {0} se deduce
f (x̄ + h) − f (x̄)
≥ α/4 > 0, ∀h ∈ BX (0, r) \ {0}.
khk2
Ejemplo 5.3.1. Retomando los datos del Ejemplo 5.2.3, tenemos que de todos los puntos crı́ticos
de la función, solamente el punto (x̄1 , ȳ1 ) = (0, 0) es candidato a ser mı́nimo local. Como ya vimos,
∇2 f (x̄1 , ȳ1 ) tiene valores propios positivos, es decir, es una matriz definida positiva. Por lo tanto,
usando (CSSO) podemos concluir que (x̄1 , ȳ1 ) es un mı́nimo local estricto de la función en cuestión.
92
Capı́tulo 5, Section 5.4 Métodos de Direcciones de Descenso
Otra dirección de descenso que vale la pena mencionar, y que estudiaremos en profundidad más
adelante, es la dirección de descenso del Método Quasi-Newton, la cuál se inspira en el método de
Newton-Raphson. La idea principal es tomar la dirección de descenso de la forma
dk = −B−1
k ∇ f (xk ), ∀k ∈ N
donde Bk ∈ Sn++ (R) es una matriz que aproxima a ∇2 f (xk ) en algún sentido. Notemos además que
1
, ∀k ∈ N.
cos θ f (xk , dk ) ≥
κ (Bk )
93
Optimización irrestricta Capı́tulo 5, Section 5.4
Regla de Armijo
La primera regla de búsqueda lineal inexacta que estudiaremos, llamada regla de Armijo, consiste
en pedir que el decrecimiento sea proporcional a un cierto ω1 ∈ (0, 1). Esto se traduce en que la
función decrece de forma lineal en la dirección dk . Dicho de otra forma, la condición de Armijo pide
que αk > 0 se escoja de forma tal que
Notemos que ω1 está fijo en la condición de Armijo (no cambia con k) y a priori no hay mayor
restricción sobre él. Sin embargo, en la práctica, y con el fin que (5.4) sea más fácil de verificar, se
toma ω1 pequeño (tı́picamente ω1 ' 10−4 ).
R
y = f (xk + αdk )
αk
f (xk ) α
f (xk + αk dk )
y = f (xk ) + α∇ f (xk )> dk
94
Capı́tulo 5, Section 5.4 Métodos de Direcciones de Descenso
Para encontrar un paso que satisfaga la condición de Armijo se procede en general usando una
técnica llamada backtracking y que está determinada por el siguiente algoritmo:
Normalmente, τ es pequeño (en general 10−2 ≤ τ ≤ 10−1 ) y esta elección de pasos se asocia
frecuentemente a direcciones de descenso de Newton-Raphson, pues en este caso se espera tener
convergencia con αk ' 1.
Regla de Goldstein
Notemos que la elección del paso con la regla de Armijo no provee una cota inferior para el paso,
y no hay en principio mayor inconveniente en escoger αk muy pequeño. El problema es que esto
puede llevar a que el algoritmo converja a un punto que no es necesariamente un punto crı́tico de la
función. En efecto, si el paso se escoge de forma tal que para algún ε > 0 se cumple
ε
0 < αk ≤ , ∀k ∈ N
2k+1 |d k|
Tendremos que la sucesion {xk } generada por (5.3) es de Cauchy y por lo tanto converge a algún
x̄ ∈ Rn . En efecto para todo l ∈ N tenemos
k+l−1 ∞
ε
|xk+l − xk | = ∑ αi di ≤ ∑ →0 si k → +∞.
i=k i=k 2i+1
95
Optimización irrestricta Capı́tulo 5, Section 5.4
R
y = f (xk + αdk )
αk
f (xk ) α
Proposición 5.2. Sea f : Rn → R ∪ {+∞} una función inferiormente acotada tal que dom( f ) es
un abierto de Rn . Supongamos además que f es continua y Gâteaux diferenciable en dom( f ). Sea
k ∈ N y xk una instancia del Método de Direcciones de Descenso (5.3) con dk siendo una dirección
de descenso. Entonces, para todo ω1 ∈ (0, 1/2) existe αk > 0 que verifica la Regla de Goldstein (5.5).
Demostración. En efecto, dado xk ∈ dom( f ), dk dirección de descenso, por diferenciabilidad de f se
tiene
f (xk + αdk ) − f (xk )
lı́m = ∇ f (xk )> dk < (1 − ω1 )∇ f (xk )> dk < ω1 ∇ f (xk )> dk .
α→0 + α
Además, como ∇ f (xk )> dk < 0 debido a que dk es dirección de descenso,
lı́m f (xk + αdk ) ≥ ı́nfn ( f ) > −∞ = lı́m f (xk ) + αω1 ∇ f (xk )> dk = lı́m f (xk ) + α(1 − ω1 )∇ f (xk )> dk .
α→∞ R α→∞ α→∞
Por lo tanto, por continuidad de las funciones α 7→ f (xk + αdk ), α 7→ f (xk ) + αω1 ∇ f (xk )> dk y
α 7→ f (xk ) + α(1 − ω1 )∇ f (xk )> dk , se deduce del teorema del valor intermedio que existen α2 < α1
tales que
α1 = ı́nf{α > 0 | f (xk + αdk ) = f (xk ) + αω1 ∇ f (xk )> dk }
α2 = sup{α ∈ (0, α1 ) | f (xk + αdk ) = f (xk ) + α(1 − ω1 )∇ f (xk )> dk }
y por lo tanto las condiciones de Goldstein (5.5) se cumplen para todo α2 ≤ αk ≤ α1 .
Regla de Wolfe
Otra forma de evitar el problema de convergencia a un punto que no es un punto crı́tico es
introducir una regla que considere información sobre la curvatura de la función. La condición de
Wolfe pide que αk > 0 satisfaga, para algún ω1 ∈ (0, 1) y ω2 ∈ (ω1 , 1), las siguientes condiciones
(5.6a) f (xk + αk dk ) ≤ f (xk ) + ω1 αk ∇ f (xk )> dk .
(5.6b) ∇ f (xk + αk dk )> dk ≥ ω2 ∇ f (xk )> dk .
96
Capı́tulo 5, Section 5.4 Métodos de Direcciones de Descenso
R
y = f (xk + αdk )
αk
f (xk ) α
f (xk + αk dk )
Notar que, al igual que con la regla de Goldstein, (5.6a) es la condición de Armijo (5.4). Más
aún, dado que ∇ f (xk + αdk )> dk es la pendiente de la función α 7→ f (xk + αdk ) en el punto α, la
condición (5.6b) dice que la pendiente α 7→ f (xk + αdk ) en αk debe ser mayor que una proporción
ω2 de la pendiente en α = 0, y en consecuencia αk estará lo suficientemente alejado de α = 0 para
evitar una falsa convergencia. Notemos además que ω2 , al igual que ω1 en la condición de Armijo,
está fijo (no cambia con k). En la práctica, y con el fin que (5.6b) sea más fácil de verificar, se toma
ω2 cercano a 1 (tı́picamente ω2 ' 0,99). Esta regla, debibo a su relación con la curvatura, se asocia
frecuentemente con direcciones de descenso del Método Quasi-Newton.
Veamos ahora que la regla de Wolfe está bien definida.
Proposición 5.3. Sea f : Rn → R ∪ {+∞} una función inferiormente acotada tal que dom( f ) es un
abierto de Rn . Supongamos que f es continua y Gâteaux diferenciable en dom( f ). Sea k ∈ N y xk
una instancia del Método de Direcciones de Descenso (5.3) con dk siendo una dirección de descenso.
Entonces, para todo 0 < ω1 < ω2 < 1 existe αk > 0 que satisface la condición de Wolfe (5.6).
Demostración. Consideremos
cuya existencia está garantizada por la demostración de la proposición anterior (Proposición 5.2).
Notemos que la primera condición de Wolfe (5.6a) se satisface para todo αk ≤ α1 . Por otra parte, por
Teorema del Valor Medio, se tiene que existe α2 ∈ (0, α1 ) tal que
f (xk + α1 dk ) − f (xk )
(5.7) ω2 ∇ f (xk )> dk < ω1 ∇ f (xk )> dk = = ∇ f (xk + α2 dk )> dk
α1
y por continuidad hay un intervalo alrededor de α2 donde las condiciones se siguen satisfaciendo.
97
Optimización irrestricta Capı́tulo 5, Section 5.4
98
Capı́tulo 5, Section 5.4 Métodos de Direcciones de Descenso
de donde
(ω2 − 1)
αk ≥ 2
∇ f (xk )> dk .
Lkdk k
Ocupando esta desigualdad en la primera condición de Wolfe y usando la definición de θk , se deduce
2
ω1 (ω2 − 1) ∇ f (xk )> dk ω1 (1 − ω2 )
f (xk+1 ) − f (xk ) ≤ =− cos2 (θk )k∇ f (xk )k2 ,
L kdk k L
y por lo tanto { f (xk )} es una sucesión real decreciente y acotada inferiormente, y en consecuencia
converge. Sumando sobre k se deduce
ω1 (1 − ω2 ) N−1 2
∑ cos (θk )k∇ f (xk )k2 ≤ f (x0 ) − f (xN ).
L k=0
99
Optimización irrestricta Capı́tulo 5, Section 5.4
Teorema 5.5. Sea f : Rn → R ∪ {+∞} una función propia y dos veces Gâteaux diferenciable en
dom( f ), el cual asumimos ser un abierto de Rn . Supongamos que existe x̄ ∈ Rn tal que ∇ f (x̄) = 0 y
∇2 f (x̄) ∈ Sn++ (R), y que además ∇2 f es localmente Lipschitz continua en torno a x̄. Entonces, existe
ρ > 0 para el cual se tiene que si x0 ∈ BRn (x̄, ρ), la secuencia {xk } generada por
donde λx̄ > 0. Para todo x ∈ BRn (x̄, r) e y ∈ Rn , usando la propiedad Lipschitz de ∇2 f se tiene
λx̄
∇2 f (x) ∈ Sn++ (R) con λx ≥ > 0, x ∈ BRn (x̄, ρ).
2
De ese modo, para todo x ∈ BRn (x̄, ρ), existen matrices Px y Dx tales que ∇2 f (x) = Px Dx Px> con
Px−1 = Px> , de modo que ∇2 f (x)−1 = Px D−1 >
x Px y
1 2
k∇2 f (x)−1 k = ≤
λx λx̄
Supongamos que xk ∈ BRn (x̄, ρ) para algún k ∈ N. Para simplificar la notación, notemos gk = ∇ f (xk )
y Hk = ∇2 f (xk ). De (5.8) se deduce que si xk = x̄ entonces xk+1 = x̄, por lo que suponemos que xk 6= x̄.
Como x̄ es un punto crı́tico de f , es decir, ∇ f (x̄) = 0, usando la propiedad de Lipschitz continuidad
de ∇2 f y la relación
Z 1
gk = ∇ f (xk ) − ∇ f (x̄) = ∇2 f (x̄ + t(xk − x̄))(xk − x̄)dt,
0
tenemos que
100
Capı́tulo 5, Section 5.4 Métodos de Direcciones de Descenso
En particular, se tiene que xk+1 ∈ BRn (x̄, ρ). Además, usando inducción vemos que la sucesión {xk }
está contenida en BRn (x̄, ρ) si x0 ∈ BRn (x̄, ρ) y
1
|xk+1 − x̄| ≤ |x0 − x̄|, ∀k ∈ N.
2k+1
De aquı́ se concluye que xk → x̄, y que también tenemos
Por otra parte, dado que Hk (xk+1 − xk ) + gk = 0 para todo k ∈ N, tenemos que
Z 1
|gk+1 | = |gk+1 − gk − Hk (xk+1 − xk )| = ∇2 f (xk + t(xk+1 − xk ))(xk+1 − xk )dt − Hk (xk+1 − xk ) .
0
Sigue que,
Z 1
L L
|gk+1 | ≤ |xk+1 − xk | ∇2 f (xk + t(xk+1 − xk )) − Hk dt ≤ |xk+1 − xk |2 ≤ kHk−1 k2 |gk |2 .
0 2 2
Esto a su vez implica que
4L
|gk+1 | ≤ |gk |2 , ∀k ∈ N.
λ2x̄
Por lo tanto, usando los mismos argumentos que más arriba, obtenemos la conclusión.
101
Optimización irrestricta Capı́tulo 5, Section 5.4
Teorema 5.6. Sea f : Rn → R ∪ {+∞} una función propia y dos veces Gâteaux diferenciable en
dom( f ), el cual asumimos ser un abierto de Rn . Supongamos que existe x̄ ∈ Rn tal que ∇ f (x̄) = 0 y
∇2 f (x̄) ∈ Sn++ (R), y que además ∇2 f es localmente Lipschitz continua en torno a x̄. Sea x0 ∈ Rn y
consideremos la sucesión generada por la recurrencia
xk+1 = xk − αk B−1
k ∇ f (xk ), ∀k ∈ N,
con {αk } dado por la regla de Wolfe (5.6) con ω1 ∈ (0, 1/2). Entonces existe ρ > 0 tal que
2. Si además se satisface
|(Bk − ∇2 f (x̄))dk |
(5.9) lı́m = 0,
k→+∞ |dk |
entonces
|xk+1 − x̄| |∇ f (xk+1 )|
lı́m = lı́m = 0.
k→∞ |xk − x̄| k→∞ |∇ f (xk )|
Demostración. Recordemos que, para x ∈ dom( f ) habı́amos denotado por λx al menor valor propio
de ∇2 f (x). Como ∇2 f (x̄) ∈ Sn++ (R), de la Proposición 3.2 se tiene
Luego, definiendo ρ = λx̄ mı́n{1/8, 1/(4L)}, si kBk − ∇2 f (x̄)k ≤ ρ se tiene que Bk es definida po-
sitiva, para todo y ∈ Rn , y> Bk y ≥ 7λx̄ |y|2 /8 y existen matrices Pk y Dk tales que Bk = Pk Dk Pk> con
Pk−1 = Pk> , de modo que B−1 −1 >
k = Pk Dk Pk y
8 2
kB−1
k k≤ ≤ .
7λx̄ λx̄
Supongamos que xk ∈ BRn (x̄, ρ) para algún k ∈ N. Para simplificar la notación, notemos gk = ∇ f (xk ).
De (5.8) se deduce que si xk = x̄ entonces xk+1 = x̄, por lo que suponemos que xk 6= x̄. Como x̄ es
un punto crı́tico de f , es decir, ∇ f (x̄) = 0, usando la propiedad de Lipschitz continuidad de ∇2 f y la
relación Z 1
gk = ∇ f (xk ) − ∇ f (x̄) = ∇2 f (x̄ + t(xk − x̄))(xk − x̄)dt,
0
102
Capı́tulo 5, Section 5.4 Métodos de Direcciones de Descenso
tenemos que
|xk+1 − x̄| = |xk − x̄ − B−1
k gk |
= |B−1
k (Bk (xk − x̄) − gk ) |
Z 1
−1 2
= Bk [Bk − ∇ f (x̄ + t(xk − x̄))](xk − x̄)dt
0
Z 1
2 2 2 2
≤ |(Bk − ∇ f (x̄))(xk − x̄)| + |xk − x̄| k∇ f (x̄) − ∇ f (x̄ + t(xk − x̄))kdt
λx̄ 0
Z 1
2
≤ |xk − x̄| ρ + L|xk − x̄| tdt
λx̄ 0
1
≤ |xk − x̄|,
2
y luego xk+1 ∈ BRn (x̄, ρ). Además, usando inducción vemos que la sucesión {xk } está contenida en
BRn (x̄, ρ) si x0 ∈ BRn (x̄, ρ) y
1
|xk+1 − x̄| ≤ k+1 |x0 − x̄|, ∀k ∈ N.
2
De aquı́ se concluye que xk → x̄ y la convergencia es lineal. Por otra parte, como xk ∈ BRn (x̄, ρ),
k∇2 f (xk )−∇2 f (x̄)k ≤ L|xk − x̄| ≤ λx̄ /4 y luego argumentando como en (5.10) se deduce k∇2 f (xk )−1 k ≤
4/(3λx̄ ) ≤ 2/λx̄ y
|xk+1 − x̄| = |xk − x̄ − B−1
k gk |
≤ |xk − x̄ − ∇2 f (xk )−1 gk | + |(B−1 2 −1
k − ∇ f (xk ) )gk |
= |∇2 f (xk )−1 ∇2 f (xk )(xk − x̄) − gk | + |∇2 f (xk )−1 (∇2 f (xk ) − Bk )dk |
Z 1
2 −1 2 2 2
≤ |∇ f (xk ) | [∇ f (xk ) − ∇ f (x̄ + t(xk − x̄))](xk − x̄)dt + |(∇ f (xk ) − Bk )dk |
0
Z 1
2 2 2 2
≤ |xk − x̄| k∇ f (xk ) − ∇ f (x̄ + t(xk − x̄))kdt + |(∇ f (xk ) − Bk )dk |
λx̄ 0
2 L 2 2 2 2
≤ |xk − x̄| + |(∇ f (x̄) − Bk )dk | + k(∇ f (xk ) − ∇ f (x̄))k |dk |
λx̄ 2
2 L 2 2
(5.11) ≤ |xk − x̄| + |(∇ f (x̄) − Bk )dk | + L|xk − x̄| |dk | .
λx̄ 2
Notando que (5.9) asegura la existencia de k0 ∈ N tal que, para todo k ≥ k0 ,
|(∇2 f (x̄) − Bk )dk | λx̄
≤ρ≤ ,
|dk | 8
se tiene que, para todo k ≥ k0 ,
|dk | |xk+1 − x̄| + |xk − x̄|
≤
|xk − x̄| |xk − x̄|
L 2 |(∇2 f (x̄) − Bk )dk | |dk | 2L |dk |
= 1 + |xk − x̄| + + |xk − x̄|
λx̄ λx̄ |dk | |xk − x̄| λx̄ |xk − x̄|
L 3 |dk |
≤ 1 + |xk − x̄| + ,
λx̄ 4 |xk − x̄|
103
Optimización irrestricta Capı́tulo 5, Section 5.4
104
Capı́tulo 5, Section 5.4 Métodos de Direcciones de Descenso
y luego
∇ f (xk + dk )> dk − ω2 ∇ f (xk )> dk = (1 − ω2 )∇ f (xk )> dk + dk> ∇2 f (xk + λdk )dk
= −(1 − ω2 )dk> Bk dk + dk> ∇2 f (xk + λdk )dk
= (1 − ω2 )dk> (∇2 f (x̄) − Bk )dk + dk> ∇2 f (xk + λdk ) − ∇2 f (x̄) dk
+ ω2 dk> ∇2 f (x̄)dk
≥ (1 − ω2 )dk> (∇2 f (x̄) − Bk )dk + dk> ∇2 f (xk + λdk ) − ∇2 f (x̄) dk
+ ω2 λx̄ |dk |2 ,
Preliminares
Describamos la idea esencial de ambos métodos. Supongamos conocida la iteración del Método
Quasi-Newton xk ∈ Rn y la matriz Bk ∈ Sn++ (R). Consideremos la función mk : Rn → R dada por
1
mk (d) = f (xk ) + ∇ f (xk )> d + d > Bk d, ∀d ∈ Rn .
2
Esta función tiene la propiedad que mk (0) = f (xk ) y ∇mk (0) = ∇ f (xk ). Además, al ser Bk simétrica
y definida positiva tenemos que mk es coerciva y por lo tanto tiene un único mı́nimo, digamos dk ,
que está caracterizado por la regla de Fermat. Dado que Bk es invertible, no es difı́cil ver que dk está
dado por la fórmula
(5.13) dk = −B−1
k ∇ f (xk ), ∀k ∈ N.
Es decir, es la dirección dada por el Método Quasi-Newton. Ahora bien, si tuviésemos a disposición
la siguiente iteración del Método Quasi-Newton xk+1 , nos gustarı́a hacer algo similar para determinar
dk+1 . Para esto, definimos la función fk+1 : Rn → R dada por
1
fk+1 (x) = f (xk+1 ) + ∇ f (xk+1 )> (x − xk+1 ) + (x − xk+1 )> Bk+1 (x − xk+1 ), ∀x ∈ Rn .
2
Es claro que ∇ fk+1 (xk+1 ) = ∇ f (xk+1 ). Nos gustarı́a además que fk+1 fuese también una buena apro-
ximación de f , para esto podemos pedir por ejemplo que ∇ fk+1 (xk ) = ∇ f (xk ), lo que se traduce
en:
Bk+1 sk = yk , con sk = xk+1 − xk = αk dk e yk = ∇ f (xk+1 ) − ∇ f (xk ).
105
Optimización irrestricta Capı́tulo 5, Section 5.4
Esta última, se conoce como la ecuación de la secante; notar que la incógnita en este caso es la matriz
Bk+1 . Ahora bien, dado que buscamos que Bk+1 sea definida positiva, necesitamos que s> k Bk+1 sk > 0.
Luego para que la ecuación de la secante tenga solución necesitamos que s> y
k k > 0. Esto se puede
asegurar si por ejemplo αk satisface la condición de Wolfe (5.6b). Efectivamente, si αk > 0 se escoge
usando la regla de Wolfe tendremos que
s> > >
k yk = αk dk yk ≥ αk (ω2 − 1)dk ∇ f (xk ) > 0.
Ahora bien, dado que la ecuación de la secante es una ecuación matricial, ésta posee infinitas
soluciones pues esta ecuación se compone de n ecuaciones que sumado a las n desigualdades prove-
nientes del hecho que Bk+1 es definida positiva, no compensan los 21 n(n + 1) grados de libertad de la
simetrı́a de Bk+1 .
Formula DFP
Una forma de construir Bk+1 es buscando, entre todas las soluciones a la ecuación de la secante,
la matriz más próxima a Bk en algún sentido. Dicho de otra forma, Bk+1 será la proyección Bk sobre
el espacio de soluciones de la ecuación de la secante. Esto se puede formular como el siguiente
problema de optimización
(PDFP ) Minimizar kB − Bk k sobre todos los B ∈ Sn (R) tales que Bsk = yk ,
donde s>
k yk > 0, Bk ∈ S++ (R) y M 7→ kMk es una norma sobre S (R).
n n
Observación 5.2. Para cada norma utilizada se obtendrá un forma de calcular Bk+1 y por lo tanto
un nuevo Método Quasi-Newton.
La fórmula DFP utiliza la norma
q Z 1
1/2 1/2
kMk = tr(W MW MW ) con W = ∇2 f (xk + tαk dk )dt.
0
La matriz W se conoce como la matriz Hessiana promedio de f y no es difı́cil ver que, gracias al
teorema fundamental del cálculo, W es una solución particular de la ecuación de la secante.
Bajo estas condiciones y usando las condiciones de optimalidad del problema (PDFP ), se tiene
que la matriz Bk+1 queda determinada por la recurrencia:
! !
1 1 1
Bk+1 = I − > yk s> k Bk I − > sk y> k + > yk y> k , ∀k ∈ N.
yk sk yk sk yk sk
Ahora bien, en el Método Quasi-Newton nos interesa conocer la inversa de Bk y no necesaria-
mente Bk misma. Dada la estructura de Bk+1 , podemos calcular su inversa usando la fórmula de
Sherman-Morrison-Woodbury:
A−1 uvT A−1
(A + uvT )−1 = A−1 − ∀A ∈ Mn×n (R) invertible, ∀u, v ∈ Rn .
1 + vT A−1 u
Esto implica que la fórmula DFP está dada por:
1 1
(DFP) B−1 −1
k+1 = Bk − −1
B−1 > −1
k yk yk Bk + >
sk s>
k, ∀k ∈ N.
y>
k Bk yk yk sk
106
Capı́tulo 5, Section 5.4 Métodos de Direcciones de Descenso
Formula BFGS
Una forma alternativa de obtener un método Quasi-Newton es calculando directamente la inversa
y plantear el problema (PDFP ) de una forma equivalente pero para la inversa de Bk+1 . En términos de
problema de optimización esto se escribe como sigue
donde s>
k yk > 0, Bk ∈ S++ (R) y M 7→ kMk es una norma sobre S (R). Notar que en este caso se tiene
n n
que M −1 será solución de la ecuación de la secante. Luego, usando las condiciones de optimalidad
del problema (PBFGS ), se tiene que la matriz Bk+1 queda determinada por la recurrencia:
Bk sk sTk Bk yk yTk
Bk+1 = Bk − T + T
sk Bk sk yk sk
Veamos ahora un teorema sobre la convergencia global del Método Quasi-Newton usando la
fórmula BFGS. Cabe destacar que bajo las hipótesis del siguiente resultado, la función objetivo es
coerciva y por lo tanto tiene un mı́nimo.
Teorema 5.7. Sea f : Rn → R ∪ {+∞} una función propia y dos veces Gâteaux diferenciable en
dom( f ), el cual asumimos ser un abierto de Rn . Supongamos que x0 ∈ Rn es tal que Γ f (x0 ) ( f ) es
convexo y existen λ, σ > 0 tal que
Entonces, la secuencia {xk } generada por el Método Quasi-Newton, con Bk determinada por la
fórmula BFGS, con paso αk dado por la regla de Wolfe (5.6) converge a x̄ ∈ arg mı́nRn ( f ).
Finalmente veremos que la tasa de convergencia del Método Quasi-Newton es cuadrática si las
matrices Bk se escogen usando la fórmula BFGS.
Teorema 5.8. Sea f : Rn → R ∪ {+∞} una función propia y dos veces Gâteaux diferenciable en
dom( f ), el cual asumimos ser un abierto de Rn . Supongamos que existe x̄ ∈ Rn tal que ∇ f (x̄) = 0
y ∇2 f (x̄) ∈ Sn++ (R), y que además ∇2 f es localmente Lipschitz continua en torno a x̄. Supongamos
que el método BFGS converge al punto crı́tico x̄. Luego, si
∞
∑ |xk − x̄| < +∞,
k=0
|(Bk − ∇2 f (x̄))(xk+1 − xk )|
lı́m =0
k→∞ |xk+1 − xk |
107
Optimización irrestricta Capı́tulo 5, Section 5.5
5.5. Ejercicios
1. M ÍNIMOS LOCALES QUE SON GLOBALES
Sea (X, k · k) un espacio vectorial normado y f : X → R ∪ {+∞} continua en dom( f ). Muestre
que x̄ es un mı́nimo global de f si y sólo si todo x tal que f (x) = f (x̄) es un mı́nimo local de f .
donde α y β son dos parámetros dados. Si el precio del kilo de pescado es p = 1, y los costos
unitarios asociados a x e y son los valores estrictamente positivos cx y cy , respectivamente,
entonces:
Demuestre que si los puntos crı́ticos de la parte anterior están en S, entonces estos son
máximos (globales) del problema.
Indicación: Estudie la convexidad del negativo de la función de beneficios.
108
CAPÍTULO 6
Optimización restricta
109
Optimización restricta Capı́tulo 6, Section 6.1
110
Capı́tulo 6, Section 6.2 Programación Matemática
Notemos que el Teorema 6.1 es una generalización del Teorema 5.1, pues en el caso que no hay
restricciones, es decir S = X, se tiene que TS (x) = X para todo x ∈ X; esto se debe a que int(X) = X.
Ejemplo 6.1.1. Cabe también destacar que el Teorema 6.1 al igual que el Teorema 5.1, es sólo
una condición necesaria y puede pno ser suficiente. En efecto, consideremos la función f (x) = x1
y la restricción S = {x ∈ R | 2 |x1 | ≤ x2 }; ver Figura 6.1. Luego, tenemos ∇ f (0, 0) = (1, 0) y
además TS (0, 0) = {d ∈ R2 | d1 = 0, d2 ≥ 0}. Con esto vemos que (CNPO) se satisface en el punto
x̄ = (0, 0). Sin embargo, este punto no es mı́nimo local pues, dado α > 0, cualquier punto de la forma
xα = (−α2 , α) ∈ S pertenece a S y satisface f (xα ) = −α2 . Por lo tanto, para cualquier α > 0 se tiene
que f (xα ) < 0 y xα puede ser tan cercano a (0, 0) como queramos.
S TS (x̄)
R
x̄
h j (x) = x∗j , x − α j , ∀ j = 1, . . . , q, ∀x ∈ X.
A partir de ahora, X será un espacio de Hilbert dotado de un producto interno denotado h·, ·i. Los
ejemplos modelos serán X = Rn y X = Sn (R).
111
Optimización restricta Capı́tulo 6, Section 6.2
Notar que el cono linealizante puede ser calculado explı́citamente usando los datos del problema,
y para ello basta solo conocer las derivadas de las funciones que definen al conjunto de restriccio-
nes del problema de programación matemática. Por esta razón, nos gustarı́a poder escribir (CNPO)
usando el cono linealizante en vez del cono tangente. Notemos que en general se tiene que el cono
tangente TS (x) está contenido en el cono linealizante LS (x) , y que esta inclusión puede ser estricta.
S = x ∈ R2 | x2 ≤ (1 − x1 )3 ,
x1 ≥ 0, y x2 ≥ 0 .
Notemos que la primera y tercera restricciones son activas, pero la segunda no. Luego, el cono
linealizante al conjunto en x̄ está dado por LS (x̄) = R × {0}, pero TS (x̄) = (−∞, 0] × {0}.
R R
x2 = (1 − x1 )3 x2 = (1 − x1 )3
S S
x2 = 0 R x2 = 0 R
TS (x̄) x̄ LS (x̄) x̄
x1 = 0 x1 = 0
112
Capı́tulo 6, Section 6.2 Programación Matemática
En el caso X = Rn , esto se reduce a que las derivadas parciales de f sean todas funciones conti-
nuas en una vecindad de x. Si F : Rn → Rm es una función vectorial con F = (F1 , . . . , Fm ), esta
se dirá continuamente diferenciable si cada función componente y 7→ Fi (y) es continuamente
diferenciable en torno a x.
Recordemos que JΦ (t, u) denota la matriz Jacobiana de Φ en el punto (t, u). En este caso, esta
matriz tiene la estructura
JΦ (t, u) = ∂t Φ(t, u) ∇u Φ(t, u)
donde
∂t Φ1 (t, u) ∂u1 Φ1 (t, u) . . . ∂uq Φ1 (t, u)
∂t Φ(t, u) :=
..
y ∇u Φ(t, u) :=
.. .. ..
. . . .
∂t Φq (t, u) ∂u1 Φq (t, u) . . . ∂uq Φq (t, u)
Teorema 6.2. Sea Φ : R × Rq → Rq un campo vectorial dado y ū ∈ Rq tal que Φ(0, ū) = 0.
Supongamos que Φ es continuamente diferenciable en una vecindad de (0, ū) con ∇u Φ(0, ū)
invertible. Entonces existe ε > 0 y una curva u : (−ε, ε) → Rq , continuamente diferenciable
tal que
Φ(t, u(t)) = 0, ∀t ∈ (−ε, ε) con u(0) = ū.
113
Optimización restricta Capı́tulo 6, Section 6.2
Condición de Mangasarian-Fromovitz
La condición de calificación de Mangasarian-Fromovitz (MF) es una de las más utilizadas pues
no se considera ser una hipótesis muy exigente para un problema de optimización.
Esta definición nos permitirá probar que el cono linealizante y el tangente coinciden en todos los
puntos que satisfacen (MF). Esto a su vez, es una consecuencia del Teorema de la Función Implı́cita.
Entonces, TS (x̄) ⊆ LS (x̄) para todo x̄ ∈ S. Si además x̄ ∈ S satisface (MF), entonces TS (x̄) = LS (x̄).
1. Sea x̄ ∈ S y probemos que TS (x̄) ⊆ LS (x̄). Sea d ∈ TS (x̄), luego existe {(tk , dk )} ⊆ (0, +∞) × X
tal que (tk , dk ) → (0, d) y además
Por lo tanto, dado que gi (x̄) = 0 para cualquier i ∈ I(x̄), tenemos que
Como las funciones son Fréchet diferenciables, haciendo k → +∞ obtenemos que d ∈ LS (x̄).
2. Supongamos ahora que x̄ ∈ S satisface (MF) y probemos que LS (x̄) ⊆ TS (x̄). Sea d ∈ LS (x̄) y
consideremos para cada j ∈ {1, . . . , q} la función Φ j : R × Rq → R definida por
!
q
Φ j (t, u) = h j x̄ + td + ∑ uk ∇hk (x̄) , ∀t ∈ R, ∀u ∈ Rq .
k=1
114
Capı́tulo 6, Section 6.2 Programación Matemática
Notemos que Φ es continuamente diferenciable y que Φ(0, 0) = 0. Más aún, tenemos que
En consecuencia,
h∇h1 (x̄), ∇h1 (x̄)i . . . ∇h1 (x̄), ∇hq (x̄) i
∇u Φ(0, 0) =
...
... ...
∇hq (x̄), ∇h1 (x̄) . . . ∇hq (x̄), ∇hq (x̄)
Más aún, dado que ∇h1 (x̄), . . . , ∇hq (x̄) son linealmente independientes gracias a (MF), te-
nemos que ∇u Φ(0, 0) es invertible, pues si ∇u Φ(0, 0)u = 0 para algún u ∈ Rq , entonces
* +
q
∇h j (x̄), ∑ uk ∇hk (x̄) = 0, ∀ j ∈ {1, . . . , q}.
k=1
q
Esto a su vez implica que ∑k=1 uk ∇hk (x̄) = 0, y a posterior esto también implica que u = 0.
3. Gracias al Teorema de la Función Implı́cita tenemos que existen ε > 0 y u : R → Rq continua-
mente diferenciable en (−ε, ε) tal que
satisface
h j (x(t)) = 0, ∀t ∈ (−ε, ε), ∀ j ∈ {1, . . . , q}.
Notemos también que u̇(0) = −[∇u Φ(0, 0)]−1 ∂t Φ(0, 0) = 0, pues
Como gi (x̄) = 0 para i ∈ I(x̄), vemos que podemos tomar una sucesión {tk } ⊆ (0, +∞) tal que
tk → 0 y gi (x(tk )) ≤ 0 para todo k ∈ N y por lo tanto x(tk ) ∈ S. Luego para concluir basta notar
que
q
u j (tk )
x(tk ) = x̄ + tk dk , con dk = d + ∑ ∇h j (x̄)
j=1 tk
u j (tk ) u j (tk )−u j (0)
y que dk → d, pues tk = tk → u̇ j (0) = 0 cuando k → +∞.
115
Optimización restricta Capı́tulo 6, Section 6.2
5. Finalmente, si para algún ı́ndice i ∈ I(x̄) tenemos que h∇gi (x̄), di = 0, definimos dα = d + αd,¯
con d¯ dado por (MF) y α > 0. En este caso tenemos que h∇gi (x̄), dα i < 0 y por lo tanto
dα ∈ TS (x̄), usando los argumentos de las partes anteriores. Finalmente, dado que TS (x̄) es
cerrado y dα → d si α → 0, concluimos que d ∈ TS (x̄).
p q 2 p
α ∑ µi∇gi(x̄) + ∑ λ j ∇h j (x̄) < − ∑ µi .
i=1 j=1 i=1
p q
Dado que α ∈ R es arbitrario, concluimos que ∑i=1 µi ∇gi (x̄) + ∑ j=1 λ j ∇h j (x̄) = 0, luego por (ILGA)
tenemos que µ = 0 y λ = 0, lo que no puede ser. En particular, concluimos que existe d ∈ X tal que
h∇gi (x̄), di = −1, i = 1, . . . , p y ∇h j (x̄), d , j = 1, . . . , q.
116
Capı́tulo 6, Section 6.2 Programación Matemática
(PPM ) Minimizar f (x) sobre x ∈ X tales que gi (x) ≤ 0, i ∈ {1, . . . , p}, h j (x) = 0, j ∈ {1, . . . , q}.
(KKT)
p q
0 = ∇x L(x̄, µ, λ) = ∇ f (x̄) + ∑ µi ∇gi (x̄) + ∑ λ j ∇h j (x̄) y µi gi (x̄) = 0, ∀i ∈ {1, . . . , p}.
i=1 j=1
Gracias al Teorema 6.1 tenemos que (CNPO) se verifica. Además, por el Teorema 6.3 sabemos que
TS (x̄) = LS (x̄), y por lo tanto para cualquier d ∈ X tenemos
Notemos que (KKT) es equivalente a pedir −∇ f (x̄) ∈ A. Si esto no fuese cierto y dado que X es
reflexivo (pues X es un espacio de Hilbert), tendrı́amos por Teorema de Hahn-Banach Geométrico
(Lema 2.1) que existe d ∈ X \ {0} tal que
p q
p
(6.2) ∑ µih∇gi(x̄), di + ∑ λ j h∇h j (x̄), di < −h∇ f (x̄), di, ∀µ ∈ R+ , λ ∈ Rq .
i=1 j=1
117
Optimización restricta Capı́tulo 6, Section 6.2
Una función f : X → R ∪ {+∞} definida en un espacio vectorial normado (X, k · k) se dice dos
veces continuamente diferenciable en x ∈ int(dom( f )) si es dos veces Fréchet diferenciable
en x (en particular, continuamente diferenciable) y D2 f (x) : X → X∗ × X∗ es continuo en una
vecindad de x, es decir,
∀ε > 0, ∃r > 0 tal que ∀y ∈ X kx − yk < r =⇒ sup |D2 f (x)(h, k) − D2 f (y)(h, k)| < ε.
h,k∈BX
118
Capı́tulo 6, Section 6.2 Programación Matemática
Se tiene Φ(0, 0, 0) = 0 y ∇(µ,λ) Φ(0, 0), la matriz Jacobiana de Φ con respecto a las variables µ
y λ está dada por
h∇g1 (x̄), ∇g1 (x̄)i . . . h∇g1 (x̄), ∇gNI (x̄)i h∇g1 (x̄), ∇h1 (x̄)i . . . ∇g1 (x̄), ∇hq (x̄)
.. .. .. .. .. ..
. . . . . .
h∇gNI (x̄), ∇g1 (x̄)i . . . h∇gNI (x̄), ∇gNI (x̄)i h∇gNI (x̄), ∇h1 (x̄)i . . . ∇gNI (x̄), ∇hq (x̄)
.
h∇h1 (x̄), ∇g1 (x̄)i . . . h∇h1 (x̄), ∇gNI (x̄)i h∇h1 (x̄), ∇h1 (x̄)i . . . ∇h1 (x̄), ∇hq (x̄)
.. .. .. .. .. ..
. . . . . .
∇hq (x̄), ∇g1 (x̄) . . . ∇hq (x̄), ∇gNI (x̄) ∇hq (x̄), ∇h1 (x̄) . . . ∇hq (x̄), ∇hq (x̄)
119
Optimización restricta Capı́tulo 6, Section 6.2
Notemos que la matriz ∇(µ,λ) Φ(0, 0) es invertible. En efecto, para todo u ∈ RNI y v ∈ Rq se
tiene que si ∇(µ,λ) Φ(0, 0)(u, v) = 0 entonces
NI q 2
>
0 = (u, v) ∇(µ,λ) Φ(0, 0)(u, v) = ∑ ui∇gi(x̄) + ∑ v j ∇h j (x̄) .
i=1 j=1
Gracias a (ILGA) deducimos que (u, v) = (0, 0). Luego, ocupando el Teorema de la Función
Implı́cita y dado que Φ es dos veces continuamente diferenciable, existe ε > 0 y funciones
µ : (−ε, ε) → RNI y λ : (−ε, ε) → Rq también dos veces continuamente diferenciables tales
que Φ(t, µ(t), λ(t)) = 0 para todo t ∈ (−ε, ε), con (µ(0), λ(0)) = (0, 0).
˙ q
se tiene x(0) = x̄ y ẋ(0) = d + ∑N
k=1 µ̇k (0)∇gk (x̄) + ∑`=1 λ` (0)∇h` (x̄). Además,
I
* +
NI q
d ˙ ` (0)∇h` (x̄), ∇gi (x̄)
0 = Φi (·, µ(·), λ(·))(0) = h∇gi (x̄), di + ∑ µ̇k (0)∇gk (x̄) + ∑ λ
dt k=1 `=1
* +
NI q
d ˙ ` (0)∇h` (x̄), ∇h j (x̄)
0 = Φ j (·, µ(·), λ(·))(0) = ∇h j (x̄), d + ∑ µ̇k (0)∇gk (x̄) + ∑ λ
dt k=1 `=1
NI q 2
˙ ` (0)∇h` (x̄)
0 = ∑ µ̇k (0)∇gk (x̄) + ∑ λ ,
k=1 `=1
4. Probemos ahora que x(t) es factible para todo t > 0 en una vecindad de t = 0. En efecto,
notemos que
gi (x(t)) = gi (x̄) + h∇gi (x̄), dit + o(t) = h∇gi (x̄), dit + o(t),
y como h∇gi (x̄), di < 0 se deduce que para t > 0 suficientemente pequeño se tiene gi (x(t)) < 0
y se tiene la factibilidad de x(t) para t > 0 en una vecindad de t = 0.
120
Capı́tulo 6, Section 6.2 Programación Matemática
5. Como x(t) es factible para t > 0 y dos veces continuamente diferenciable, la expansión de
Taylor de segundo orden de t 7→ f (x(t)) en torno a t = 0 implica que para t > 0 suficientemente
pequeño
1
f (x̄) ≤ f (x(t)) = f (x̄) + h∇ f (x̄), dit + D2 f (x̄)(d, d) + h∇ f (x̄), ẍ(0)i t 2 + o(t 2 ),
2
y como h∇ f (x̄), di = 0, dividiendo por t 2 y pasando al lı́mite, se deduce
(6.3) 0 ≤ D2 f (x̄)(d, d) + h∇ f (x̄), ẍ(0)i.
De manera similar, para i ∈ {1, . . . , NI } y j ∈ {1, . . . , q}, dado que las funciones t 7→ gi (x(t)) y
t 7→ h j (x(t)) son dos veces diferenciables y nulas en el intervalo (−ε, ε), estas satisfacen
(6.4) 0 = D2 gi (x̄)(d, d) + h∇gi (x̄), ẍ(0)i, ∀i ∈ {1, . . . , NI }
(6.5) 0 = D2 h j (x̄)(d, d) + ∇h j (x̄), ẍ(0) , ∀ j ∈ {1, . . . , q}.
En consecuencia ∑i∈I(x̄)\Id (x̄) µi h∇gi (x̄), di = 0 pues todos los otros términos del lado izquierdo
son cero. Ahora bien, dado que h∇gi (x̄), di < 0 y µi ≥ 0 para todo i ∈ I(x̄) \ Id (x̄), concluimos
que µi = 0 cualquiera sea i ∈ I(x̄) \ Id (x̄). Finalmente, multiplicando (6.4) por el correspon-
diente µi , (6.5) por el respectivo λ j y sumando deducimos el resultado.
Ahora revisaremos una condición suficiente para que un punto que verifica las condiciones de
(KKT) sea efectivamente un mı́nimo local del problema. Al igual que en el caso convexo, la curvatura
de la función sobre el conjunto de restricciones jugará un rol importante. En este caso, esta curvatura
se medirá a través de la segunda derivada del Lagrangiano.
Observación 6.3. Es importante destacar que en el siguiente resultado ninguna condición de califi-
cación es requerida. Sin embargo, el precio a pagar es que el espacio debe ser de dimensión finita.
Existen condiciones suficiente de segundo orden en espacios de dimensión infinita, pero requieren
utilizar otras nociones de cono de direcciones crı́ticas.
Teorema 6.6 (Condición Suficiente de Segundo Orden). Sea (X, h·, ·i) un espacio de Hilbert de
dimensión finita. Sea f : X → R ∪ {+∞} una función propia dos veces continuamente diferenciable
en una vecindad de x̄ ∈ int(dom( f )). Sean g1 , . . . , g p : X → R y h1 , . . . , hq : X → R funciones dos
veces continuamente diferenciables. Asumamos que
x̄ ∈ S = x ∈ X | gi (x) ≤ 0, i = 1, . . . , p, h j (x) = 0, j = 1, . . . , q
y que para cada d ∈ KS (x̄) \ {0} existen µ1 , . . . , µ p ≥ 0 y λ1 , . . . , λq ∈ R tales que (KKT) se satisface
y que además
(CSSO) D2xx L(x̄, µ, λ)(d, d) > 0.
Entonces x̄ es un mı́nimo local estricto del problema de programación matemática (PPM ).
121
Optimización restricta Capı́tulo 6, Section 6.3
Demostración. Supongamos por contradicción que x̄ no es un mı́nimo local estricto de (PPM ) y, por
lo tanto, existe una sucesión {xk } en S que converge a x̄ tal que f (xk ) ≤ f (x̄). Sea dk = kx 1−x̄k (xk − x̄).
k
Pasando a una subsucesión si es necesario, tenemos que dk → d ∈ X con kdk = 1 y más aún, con
esto vemos que d ∈ TS (x̄) ⊆ LS (x̄). Por otra parte,
Por otras parte, dado que ∇x L(x̄, µ, λ) = 0, de la expansión de Taylor de orden 2 de x 7→ L(x, µ, λ) en
torno a x̄ se deduce
1
0 ≥ L(xk , µ, λ) − L(x̄, µ, λ) = D2xx L(x̄, µ, λ)(xk − x̄, xk − x̄) + o(kxk − x̄k2 )
2
y dividiendo por kxk − x̄k2 y pasando al lı́mite concluimos D2xx L(x̄, µ, λ)(d, d) ≤ 0, lo que nos lleva a
una contradicción y por lo tanto x̄ debe ser un mı́nimo local estricto.
Una propiedad interesante del Lagrangiano es que, en el caso convexo (ver Teorema 4.4), si x̄ es una
solución del problema de programación matemática, entonces es también un mı́nimo (global e irres-
tricto) de la función x 7→ L(x, µ, λ) con (µ, λ) ∈ R p × Rq siendo multiplicadores asociados a x̄. Esto
sugiere que en el caso convexo, que si conociésemos los multiplicadores, minimizar sin restriccio-
nes la función x 7→ L(x, µ, λ) serı́a equivalente a resolver el problema de programación matemática.
Desafortunadamente, fuera del caso convexo esto no es cierto y un mı́nimo local del problema de
programación matemática no es necesariamente un mı́nimo local del Lagrangiano.
122
Capı́tulo 6, Section 6.3 Métodos de Penalización
1
Minimizar 1 − x − x3 sobre los x ∈ R tales que x ≤ 0.
3
No es difı́cil ver que x̄ = 0 es el mı́nimo (global) del problema. Además, imponiendo las condiciones
de (KKT) se tiene que el multiplicador asociado a la restricción es µ = 1. Sin embargo, la función
1
x 7→ L(x, 1) = 1 − x3
3
Para evitar la clase de problemas descritos con el ejemplo anterior se introduce una función llama-
da Lagrangiano aumentado del problema de programación matemática. En adelante, para simplificar
la exposición, nos enfocaremos en el caso de restricciones de igualdad, es decir, en el problema
(PI ) Minimizar f (x) sobre los x ∈ X tales que h j (x) = 0, j ∈ {1, . . . , q}.
Observación 6.4. Para el caso con restricciones de desigualdad usualmente se agrega una variable
adicional (llamada holgura) y se considera el problema de optimización equivalente:
Minimizar f (x) sobre (x, y) ∈ X×R p tales que gi (x)+y2i = 0, i ∈ {1, . . . , p}, h j (x) = 0, j ∈ {1, . . . , q}.
Ejemplo 6.3.2. Notemos que en el Ejemplo 6.3.1 el Lagrangiano aumentado (transformado la res-
tricción de desigualdad por igualdad agregando la variable de holgura) es
1 r
Lr (x, y, λ) = 1 − x − x3 + λ(x + y2 ) + (x + y2 )2 .
3 2
1 r
Lr (x, y, 1) = 1 − x3 + y2 + (x + y2 )2 , ∀x, y ∈ R.
3 2
No es difı́cil ver, usando (CSSO) para problemas irrestrictos, que (x̄, ȳ) = (0, 0) es efectivamente un
mı́nimo local (estricto) de (x, y) 7→ Lr (x, y, 1) pues la matriz Hessiana en (x̄, ȳ) = (0, 0) es la matriz
diagonal cuyas entradas son r y 2.
123
Optimización restricta Capı́tulo 6, Section 6.3
Teorema 6.7. Sea (X, h·, ·i) un espacio de Hilbert de dimensión finita. Sea f : X → R ∪ {+∞} una
función propia dos veces continuamente diferenciable en una vecindad de x̄ ∈ int(dom( f )). Sean
h1 , . . . , hq : X → R funciones dos veces continuamente diferenciables. Asumamos que x̄ es un mı́nimo
local de (PI ), tal que (KKT) se cumple para algún λ ∈ Rq y tal que
Entonces existe r0 ∈ R tal que para todo r ≥ r0 tenemos que x̄ es un mı́nimo local estricto del
Lagrangiano aumentado Lr (·, λ) del problema de programación matemática (PI ).
Demostración. Notemos que como h j (x̄) = 0 para todo j ∈ {1, . . . , q}, se tiene
q q
∇x Lr (x̄, λ) = ∇ f (x̄) + ∑ λ j ∇h j (x̄) + r ∑ h j (x̄)∇h j (x̄) = ∇L(x̄, λ) = 0,
j=1 j=1
por lo que basta demostrar, por CSSO en el caso irrestricto, que existe r suficientemente grande tal
que el operador bilineal
q q q
D2xx Lr (x̄, λ) = D2 f (x̄) + ∑ λ j D2 h j (x̄) + r ∑ ∇h j (x̄)∇h j (x̄)> + r ∑ h j (x̄)D2 h j (x̄)
j=1 j=1 j=1
q
= D2xx L(x̄, λ) + r ∑ ∇h j (x̄)∇h j (x̄)>
j=1
es definido positivo. Por contradicción, supongamos que existe una sucesión rk → ∞ y dk ∈ X tales
que
q
(6.6) D2xx Lr (x̄, λ)(dk , dk ) = D2xx L(x̄, λ)(dk , dk ) + rk ∑| ∇h j (x̄), dk |2 ≤ 0.
j=1
Dividiendo (6.6) por kdk k2 , podemos asumir que kdk k = 1 en la desigualdad anterior y, tomando
una subsucesión si fuese necesario, podemos asumir que dk → d 6= 0. Por otra parte, si dividimos
(6.6) por rk y usamos que D2xx L(x̄, λ)(dk , dk ) es acotada, pasando al lı́mite se obtiene ∇h j (x̄), d = 0
para todo j ∈ {1, . . . , q}. Finalmente, como (6.6) implica que D2xx L(x̄, λ)(dk , dk ) ≤ 0 para todo k ∈ N,
llegamos a una contradicción pues hemos demostrado que D2xx L(x̄, λ)(d, d) ≤ 0, con kdk = 1.
Esquema Algorı́tmico
La noción de Lagrangiano aumentado puede ser usado para construir algoritmo. Dado que a priori
uno no tiene información sobre el multiplicador asociado a un mı́nimo local, la búsqueda que debe
realizar un algoritmo basado en el Lagrangiano aumentado debe actualizar tanto la variable x como la
variable del multiplicador λ. Notemos que si λ ∈ R p y r > 0 fuesen dados, y x̄ ∈ X fuese un mı́nimo
local del Lagrangiano aumentado entonces tendrı́amos que
p
∇x Lr (x̄, λ) = ∇ f (x̄) + ∑ λ j + rh j (x̄) ∇h j (x̄) = 0.
j=1
124
Capı́tulo 6, Section 6.3 Métodos de Penalización
Luego, para que x̄ tenga opciones de ser un mı́nimo local de (PI ) deberı́a verificar
El siguiente método iterativo, que presentamos sólo a modo de información, sin discusión sobre su
convergencia, utiliza las ideas descritas más arriba. Cabe mencionar que este algoritmo se espera
que converja tomando en cada iteración r más grande, de forma de forzar que λ converja a algún
multiplicador que verifique (KKT).
Para estudiar mı́nimos locales del problema (PD ) se propone estudiar, para ε > 0 dado, los mı́nimos
locales de la aproximación de barrera logarı́tmica fε : X → R ∪ {+∞} definida por
p
f (x) − ε log(−g (x)) g (x) < 0, ∀i ∈ {1, . . . , p},
fε : x 7→
∑ i i
.
i=1
+∞ si no,
La idea del método consiste encontrar un mı́nimo de fε , denotado por lo general por x(ε) y luego
estudiar el comportamiento de ε 7→ x(ε) hacia algún mı́nimo local de (PD ) cuando ε → 0. Notar que,
por la forma de la aproximación de barrera logarı́tmica, tenemos que
En este caso los µi (ε) juegan el rol de multiplicadores aproximados y en consecuencia se espera
que el lı́mite de µi (ε) cuando ε → 0 sea un multiplicador asociado a un mı́nimo local de (PD ).
125
Optimización restricta Capı́tulo 6, Section 6.3
Proposición 6.2. Sea (X, h·, ·i) un espacio de Hilbert de dimensión finita. Sea f : X → R una función
continua. Sean g1 , . . . , g p : X → R funciones continua. Asumamos que
es acotado y su interior es denso en S. Entonces, para todo ε > 0 existe x(ε) ∈ arg mı́nX ( fε ). Más aún,
todo punto de acumulación de {x(ε) : ε > 0} es solución de (PD ), esto es, toda sucesión convergente
de la forma {x(εk )} converge a un mı́nimo del problema (PD ), donde εk → 0+ cuando k → +∞.
Notemos también que fε = +∞ si x ∈ / S. Más aún, para cualquier sucesión {xk } ⊆ int(S) se
tiene que si gi (xk ) → 0 para algún i ∈ {1, . . . , p} entonces fε (xk ) → +∞. Por lo tanto, tenemos
que fε es semicontinua inferior. Por otro lado, fε es propia pues int(S) 6= 0. / Finalmente, para
determinar la existencia a través del Teorema de Wierestrass-Hilbert-Tonelli (Teorema 1.1) nos
bastará ver que los conjuntos de subnivel de fε son acotados. Pero esto es una consecuencia
directa del hecho que dom( fε ) ⊆ int(S) y del hecho que S es acotado. Luego la existencia de
x(ε) para cualquier ε > 0 está garantizada.
Por otro lado, para cada i ∈ I(x̄), y por continuidad de gi , tenemos que gi (xk ) ≥ −1 para todo
k ∈ N suficientemente grande. En consecuencia, dado que I(x̄) es finito, ∃k0 ∈ N tal que
Luego, pasando al lı́mite vemos que f (x̄) ≤ f (x) para todo x ∈ int(S). Finalmente, dado que
x̄ ∈ S y int(S) es denso en S, usando la continuidad de f concluimos que x̄ ∈ sol (PD ).
126
Capı́tulo 6, Section 6.3 Métodos de Penalización
Observación 6.5. El hecho que int(S) sea denso en S es importante, pues de no ser ası́ la conver-
gencia a un mı́nimo del problema (PD ) no puede ser asegurada.
Teorema 6.8. Sea (X, h·, ·i) un espacio de Hilbert de dimensión finita. Sea f : X → R ∪ {+∞} una
función propia dos veces continuamente diferenciable en una vecindad de x̄ ∈ int(dom( f )). Sean
g1 , . . . , g p : X → R funciones dos veces continuamente diferenciables tal que la condición de cali-
ficación (ILGA) se verifica en x̄. Asumamos que x̄ es un mı́nimo local de (PD ) que verifica (KKT)
para algún µ̄ ∈ R p con complementaridad estricta, es decir, µ̄i > 0 para todo i ∈ I(x̄), además de la
condición suficiente de segundo orden
D2xx L(x̄, µ̄)(d, d) > 0, ∀d ∈ X \ {0} tal que h∇gi (x̄), di = 0, ∀i ∈ I(x̄).
Entonces existe una única trayectoria ε 7→ (x(ε), µ(ε)) continuamente diferenciable en una vecindad
de ε = 0 que verifica (KKTε ) tal que x(0) = x̄ y µ(0) = µ̄. Más aún, para cada ε > 0 suficientemente
pequeño se tiene que x(ε) es un mı́nimo local estricto de fε .
Por construcción, ambos campos vectoriales son continuamente diferenciables. Dado que x̄ es un
mı́nimo local de (PD ) que verifica (KKT) para algún µ̄ ∈ R p , tenemos que (0, x̄, µ̄) es solución de la
ecuación
Φ(ε, x, µ) = 0, donde Φ(ε, x, µ) := (F(ε, x, µ), G(x, µ)).
Luego, la existencia de una única trayectoria ε 7→ (x(ε), µ(ε)) continuamente diferenciable en una
vecindad de ε = 0 que verifica (KKTε ) tal que x(0) = x̄ y µ(0) = µ̄ es una consecuencia del Teorema
de la Función Implı́cita. En efecto, notemos que
∇x F(ε, x, µ) ∇µ F(ε, x, µ)
∇(x,µ) Φ(ε, x, µ) = , ∀(ε, x, µ) ∈ R × Rn × R p .
∇x G(x, µ) ∇µ G(x, µ)
127
Optimización restricta Capı́tulo 6, Section 6.3
Sigue que
µ̄1 ∇g1 (x̄)> d + ν1 g1 (x̄)
..
.
∇(x,µ) Φ(0, x̄, µ̄)(d, ν) = µ̄ p ∇g p (x̄)> d + ν p g p (x̄) , ∀(d, ν) ∈ Rn × R p .
p
2
∇xx L(x̄, µ̄)d + ∑ νi ∇gi (x̄)
i=1
En particular, si ∇(x,µ) Φ(0, x̄, µ̄)(d, ν) = 0 para ciertos (d, ν) ∈ Rn × R p , por complementaridad es-
tricta, para cada i ∈ I(x̄) tenemos que ∇gi (x̄)> d = 0 y νi = 0 para cada i ∈
/ I(x̄). Notemos además que
si d 6= 0, entonces multiplicando por d la última ecuación tendrı́amos que
0 = d > ∇2xx L(x̄, µ̄)d + ∑ νi ∇gi (x̄)> d = d > ∇2xx L(x̄, µ̄)d.
i∈I(x̄)
Sin embargo esto contradice la condición suficiente de segundo orden del enunciado. Por lo tanto
d = 0. Esto a su vez implica que
p
0 = ∇2xx L(x̄, µ̄)d + ∑ νi ∇gi (x̄) = ∑ νi ∇gi (x̄).
i=1 i∈I(x̄)
Luego, por (ILGA) tenemos que νi = 0 para cada i ∈ I(x̄), y en consecuencia ν = 0 y por lo tanto la
matriz ∇(x,µ) Φ(0, x̄, µ̄) es invertible. Gracias al Teorema de la Función Implı́cita, existe una única tra-
yectoria ε 7→ (x(ε), µ(ε)) continuamente diferenciable en una vecindad de ε = 0 que verifica (KKTε )
tal que x(0) = x̄ y µ(0) = µ̄.
Resta ver que x(ε) es un mı́nimo local estricto de fε . Para esto bastará estudiar la segunda derivada
de la función fε y luego aplicar la (CSSO). Notemos que
p
2 2 ε > ε 2
∇ fε (x) = ∇ f (x) + ∑ 2
∇gi (x)∇gi (x) − ∇ gi (x) , ∀x ∈ dom( fε ).
i=1 gi (x) gi (x)
128
Capı́tulo 6, Section 6.3 Métodos de Penalización
2. Supongamos ahora que ∇gi (x̄)> d 6= 0 para algún i ∈ I(x̄). No es difı́cil ver que
p
> > µi (ε)2
2
d ∇ fε (x(ε))d ≥ d ∇2xx L(x(ε), µ(ε))d + ∑ (∇gi (x(ε))> d)2 .
i=1 ε
∇2xx L(x(ε), µ(ε)) → ∇2xx L(x̄, µ̄), ∇gi (x(ε))> d → ∇gi (x̄)> d 6= 0 y µi (ε) → µ̄i > 0.
En particular tenemos que d > ∇2 fε (x(ε))d → +∞ si ε → 0. Por lo tanto, d > ∇2 fε (x(ε))d > 0
para ε > 0 suficientemente pequeño.
Finalmente, dado que d > ∇2 fε (x)d > 0 para cualquier d ∈ Rn \ {0} y ε > 0 pequeño, por Teorema
5.3, tenemos que x(ε) es un mı́nimo local estricto de fε para ε > 0 suficientemente pequeño.
Esquema Algorı́tmico
Al igual que en la parte anterior describiremos el esquema general que tiene un algoritmo basado
en la aproximación de barrera logarı́tmica. La idea esencial del método es que en cada iteración se
resuelve un sub problema de optimización sin restricciones para luego actualizar el parámetro de
penalización. La convergencia del método estará entonces dada por el hecho que ε 7→ x(ε) converge
a un mı́nimo local del problema original si ε → 0+ .
129
Optimización restricta Capı́tulo 6, Section 6.4
6.4. Ejercicios
1. C ARACTERIZACIONES DEL C ONO TANGENTE
Sea S ⊆ Rn un conjunto dado. Demuestre que
dist(x + td, S)
TS (x) = d ∈ R lı́m inf
n
≤0 , ∀x ∈ S.
t→0+ t
4. M ULTIPLICADORES DE KKT
Sea x̄ ∈ S := {x ∈ Rn : gi (x) ≤ 0, i = 1, ..., m, h j (x) = 0, j = 1, ..., p} tal que las funciones gi y
h j son diferenciables en x̄, ∀i = 1, ..., m, ∀ j = 1, ..., p. x̄ ∈ S
b) Para el problema mı́n{ f (x) : x ∈ C}, supongamos que el conjunto Λ(x̄) de multiplicadores
de Lagrange asociados a x̄ es no vacı́o. Pruebe x̄ satisface (MF) ssi el conjunto Λ(x̄) es
acotado.
130