CONTENTS

Contents 1

I Optimización sin restricciones 3

1 Conceptos elementales del análisis convexo . . . . . . . . . . . . . . . . . . . 5
1.1 Reales extendidos, Límites inferior y superior . . . . . . . . . . . . . 5
1.2 Conjuntos convexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Funciones convexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Operaciones que preservan la convexidad . . . . . . . . . . . . . . . . . . . . 9
2.1 Funciones convexas cerradas . . . . . . . . . . . . . . . . . . . . . . . 10
3 Funciones convexas diferenciables . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1 Funciones convexas no suaves . . . . . . . . . . . . . . . . . . . . . . 11
4 Condiciones de optimalidad para la optimización sin restricciones . . . . . . 12
5 Métodos numéricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.1 Métodos de descenso . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.2 Búsqueda lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.3 Método del gradiente . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.4 Teorema de Convergencia Global . . . . . . . . . . . . . . . . . . . . 27
5.5 Método del Gradiente Acelerado . . . . . . . . . . . . . . . . . . . . . 33
5.6 Método de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.7 Métodos conjugados . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.8 Método de Newton modificado . . . . . . . . . . . . . . . . . . . . . . 42
5.9 Métodos de Broyden . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.10 Método BFGS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

II Optimización con restricciones 51

1 Introducción a la optimización con restricciones . . . . . . . . . . . . . . . . 53
1.1 Restricciones de igualdad . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.2 Condiciones necesarias de primer orden . . . . . . . . . . . . . . . . . 58
1.3 Condiciones de segundo orden . . . . . . . . . . . . . . . . . . . . . . 62
1.4 Valores propios en el plano tangente . . . . . . . . . . . . . . . . . . 65
1.5 Análisis de sensibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . 67

1
2 CONTENTS
 Part I

Optimización sin restricciones

3
 5

1 Conceptos elementales del análisis convexo

1.1 Reales extendidos, Límites inferior y superior
El conjunto extendido de los números reales consiste en R añadido dos símbolos −∞ y +∞,
i.e. R ∪ {−∞, +∞}, el cual tiene una extructura de cono ordenado:

1. Orden: x ≤ +∞ para todo R ∪ {+∞}

2. Adición: +∞ + x = x + ∞ = +∞ para todo R ∪ {+∞}

3. Multiplicación: t · ∞ = +∞, para todo t > 0

Note que (R ∪ {+∞}, +) no es un grupo ya que +∞ no tiene inverso aditivo. Se debe

tener especial cuidado cuando manipulamos funciones en R ∪ {+∞}

Reglas prácticas
1. Comparación y suma: sin problemas en R ∪ {+∞}, igual que en R.

2. Resta: antes de restar funciones, asegurarse que f (x) < +∞

3. Multiplicación: tf (x) similar a la multiplicación de un escalar por un vector, si t ≥ 0

asegurarse que f (x) < +∞

4. División: mismos problemas que en R, i.e. evitar división por 0

5. Convergencia: poner atención a los casos +∞ − ∞, o 0 · ∞

Recordemos que el supremo de un conjunto S (sup S) es el número real M tal que:

M ≥ x ∀x ∈ S,

tal que, si existe un número real M ′ tal que M ′ ≥ x para todo x ∈ S, entonces M ′ ≥ M .
De esta definición se siguen las propiedades. Sean E y F subconjuntos no vacios en R,
entonces

1. inf(E ∪ F ) = min{inf E, inf F }

2. Si F ⊂ E entonces inf F ≥ inf E

3. inf(E ∩ F ) max{inf E, inf F }

4. inf tE = t inf E, siempre que t > 0

5. inf(−E) = − sup E

Definimos además inf ∅ = +∞ y sup ∅ = −∞, esto se debe a la siguiente observación

inf E = inf(E ∪ ∅) = min{inf E, inf ∅}

6

Sea X ⊂ Rn , las cantidades int X, cl X y bd X se usan para notar al interior de X, la

clausura de X y la frontera de X respectivamente en la topología usual de Rn .

Definición I.1: Límite inferior y superior

El límite inferior de una sucesión {xn } de números reales, es ℓ ∈ R ∪ {−∞} tal que:

1. Para todo ε > 0, existe un índice n0 tal que xn > ℓ − ε para todo n ≥ n0 .

2. Para todo ℓ′ < ℓ, existe un índice n tal que xn < ℓ′ .

Se denota por
lim inf xn = ℓ.
n→∞

El límite superior de una sucesión {xn } de números reales, es u ∈ R ∪ {−∞} tal que:

1. Para todo ε > 0, existe un índice n0 tal que xn < u + ε para todo n ≥ n0 .

2. Para todo u′ > u, existe un índice n tal que xn > u′ .

Se denota por lim sup xn = u.

n→∞

Algunas propiedades importantes son las siguientes:

1. inf{xn } ≤ lim inf xn ≤ lim sup xn ≤ sup{xn }
n→∞ n→∞

2. − lim sup xn = lim inf −xn

n→∞ n→∞

3. lim sup(xn + yn ) ≤ lim sup xn + lim sup yn (siempre que el lado derecho esté definido)
n→∞ n→∞ n→∞

4. lim inf (xn + yn ) ≥ lim inf xn + lim inf yn (siempre que el lado derecho esté definido)
n→∞ n→∞ n→∞

5. lim sup(xn · yn ) ≤ lim sup xn lim sup yn (siempre que el lado derecho no sea 0 · ∞)
n→∞ n→∞ n→∞

6. lim inf (xn · yn ) ≥ lim inf xn lim inf yn (siempre que el lado derecho no sea 0 · ∞)
n→∞ n→∞ n→∞

1.2 Conjuntos convexos

Definición I.2: Conjunto convexo

Sea S ⊂ Rn , se dice que S es convexo si para todo x y y en S, y todo λ ∈ (0, 1),

λx + (1 − λ)y ∈ S

Geométricamente, se interpreta como el segmento cerrado [x, y] := {z ∈ Rn : z = λx +

(1 − λ)y, para 0 ≤ λ ≤ 1} está completamente contenido en S cuando cualesquiera de sus
puntos extremos están en S.
 7

Un cono convexo de Rn es un connjunto K ⊂ Rn tal que {αx : α > 0} ⊂ K para todo

x ∈ K.

Sean x1 , . . . , xk , k elementos de Rn . Tomamos k reales no negativos λ1 , . . . , λk tales que

k
X
λi = 1, entonces, su combinación convexa es
i=1

k
X
x= λ i xi .
i=1

Cuando la combinación admite λi negativos, la combinación se dice afín.

Definición I.3: Envolvente convexa

La envolvente convexa de un conjunto S ⊆ Rn es
k
X k
X
n
conv S = {x ∈ R : x = λi xi , λi = 1, xi ∈ S, λi ≥ 0, k > 0} (1.1.1)
i=1 i=1

Lema I.4
Si S ⊆ Rn , entonces conv S es un conjunto convexo y S es convexo, si y solo si,

S = conv S.

Considere S = {(0, 0)} × {(ξ, 1) : ξ ≥ 0}. Observemos que S es unn conjunto cerrado; sin
embargo, conv S no contiene a R+ × 0 y por tanto conv S no es cerrado!

Teorema I.5: Carathéodory

Cualquier x ∈ conv S ⊆ Rn se puede describir como una combinación convexa de n + 1
elementos de S.
8

1.3 Funciones convexas

Definición I.6
Sea C ⊆ Rn un conjunto convexo. Una función f : C → R se dice que es convexa, si
satisface la desigualdad:

f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y)

y estrictamente convexa si

f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y), x ̸= y (1.1.2)

para cualesquiera x y y en Rn y λ ∈ (0, 1). f se dice (estrictamente) cóncava si −f es

(estrictamente) convexa.
Decimos además que f : C → R es fuertemente convexa si
1
f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y) − cα(1 − α)∥x − y∥2 .
2
Si f : C → R ∪ {+∞}, con f ̸≡ +∞ se dice convexa si (1.1.2) se considera como una
desigualdad en R ∪ {+∞ }

Lema I.7: Desigualdad de Jensen

Una funciónn f : Rn → R es convexa, si y solo si
n
! n
X X
f λi xi ≤ λi f (xi ), (1.1.3)
i=1 i=1

para todo xi ∈ Rn y 1 ≥ λi ≥ 0 tales que

Pn
i=1 λi = 1.

Ejemplo :

1. La función afín x 7→ a⊤ x + b es convexa y cóncava a la vez.

2. La función cuadrática 21 x⊤ Qx + b⊤ x + c es convexa si Q es semidefinida positiva.

3. La función de pérdida de mínimos cuadrados x 7→ ∥y − Ax∥2 es convexa y es un tipo

de función cuadrática.

4. Toda norma es una función convexa.

P 
a⊤
5. log k
i=1 e i x+bi

■
 9

Teorema I.8
Toda función f : Rn → R convexa es localmente Lipschitz en cada x ∈ Rn .

Definición I.9: Epigrafo de una función

Se define el conjunto de subnivel α ∈ R, de una función f : Rn → R ∪ {+∞}
(f ̸≡ +∞), como el conjunto

levα f = {x : f (x) ≤ α},

y el epigrafo de f como el conjunto

epi f = {(x, α) ∈ Rn × R : f (x) ≤ α}.

El epigrafo estricto se obtiene al intercambiar “ ≤ ” por “ < ” en el conjunto anterior.

2 Operaciones que preservan la convexidad

Algunas operaciones funcionales preservan la convexidad e incluso la cerradura.

1. Sean ti ≥ 0 y fi convexa para i = 1, . . . , m, entonces m i=1 ti fi es convexa, siempre que

P
∩m
i=1 dom f i ̸
= ∅. También es cerrada si todas las f i es cerrada para i = 1, . . . , m.

2. Sea {fi }i∈I una familia de funciones convexas; si ∩i∈I dom fi ̸= ∅, entonces si existe x0
tal que supi∈I f (x0 ) < ∞, entonces f definida por

f (x) := sup f (x), es convexa

i∈I

3. La conjugada f ∗ , de una función f : Rn → R ∪ {+∞}, dada por

f ∗ (z) = sup {x⊤ z − f (x)}

x∈dom f

es una función convexa cerrada (incluso si f no lo es).

4. Si f : Rn → R ∪ {+∞} es convexa, y A ∈ Rn×m entonces g = f ◦ A es convexa.

5. Si f : Rn → R ∪ {+∞} es convexa y g : R → R es una función convexa creciente;

entonces (
g ◦ f si x ∈ dom f
g◦f =
+∞ c.c
es convexa.
10

2.1 Funciones convexas cerradas

Definición I.10: Función semi-continua inferior

Una función f : Rn → R es semicontinua superior en x ∈ Rn si para toda sucesión
(xk )k que converge a x, se cumple que

lim sup f (xk ) ≤ f (x),

k→∞

y es semicontinua inferior si

lim inf f (xk ) ≥ f (x).

k→∞

Además, si una función es tanto semicontinua superior e inferior, entonces se dice que es
una función continua.
La continuidad de una función implica que su grafo graf f = {(x, y) ∈ Rn × R : x ∈
dom f, y = f (x)} sea un conjunto cerrado. Desde el punto de vista del epigrafo de una
función, es de interés aquellas que tienen su epigrafo cerrado. La propiedad que garantiza
que una función tenga su epigrafo cerrado es la de semicontinuidad inferior.

Teorema I.11
f : Rn → R ∪ {+∞} (f ̸≡ +∞). Las siguientes propiedades son equivalentes

(i) f es semicontinua inferior

(ii) epi f es cerrado en Rn × R

(iii) levα f es cerrado para cualquier α ∈ R (podría ser vacío)

Demostración.

Si f es semicontinua inferior y {(yk , αk )} ⊂ epi f es una sucesión que converge a (y, α),
entonces f (yk ) ≤ αk ; y tomando el límite inferior k → ∞ se tiene

f (y) ≤ lim inf f (yk ) ≤ lim inf αk = α

k→∞ k→∞

Por tanto (f, α) ∈ epi f lo cual implica que que epi f es cerrado i.e. (i) ⇒ (ii).
Sea α ∈ R y {(yk )} es una sucesión convergente a y en levα f ̸= ∅, entonces f (yk ) ≤ α.
Es decir que (yk , α) ∈ epi f . Si asumimos (i), i.e. epi f es cerrado, entonces limk→∞ (yk , α) =
(y, α) ∈ epi f ; y en consecuencia, f (y) ≤ α, lo cual demuestra que levα f es cerrado, así
(i) ⇒ (iii).
La implicación (iii) ⇒ (i), se sigue de la definición de semicontinuidad inferior de f .
■
 11

Definición I.12: Función cerrada

Decimos que f : Rn → R ∪ {+∞} (f ̸≡ +∞) es una función cerrada si es semicontinua
inferior en cada punto de su dominio, o si su epigrafo es cerrado o, equivalentemente
sus conjuntos de subnivel son cerrados para cualquier nivel.

3 Funciones convexas diferenciables

Sea C ⊆ Rn convexo y abierto. Sea f : C → R una función convexa y diferenciable en C,
entonces
(a) f es convexa, si y solo si,

f (x) ≥ f (x0 ) + ∇f (x0 )⊤ (x − x0 ), ∀(x0 , x) ∈ C × C

(b) f es estrictamente convexa, si y solo si,

f (x) > f (x0 ) + ∇f (x0 )⊤ (x − x0 ), ∀(x0 , x) ∈ C × C, x ̸= x0

(c) f es fuertemente convexa (de módulo c), si y solo si,

1
f (x) > f (x0 ) + ∇f (x0 )⊤ (x − x0 ) + ∥x − x0 ∥2 , ∀(x0 , x) ∈ C × C, x ̸= 0
2

Sea f una función convexa dos veces diferenciable en C (un conjunto abierto de Rn )
(a) f es convexa en C, si y solo si, ∇2 f (x0 ) es semidefinida positiva en todo x0 ∈ C

(b) Si ∇2 f (x0 ) es definida positiva en todo x0 ∈ C, entonces f es estrictamente convexa.

(c) f es fuertemente convexa (de módulo c) en C, si y solo si, el eigenvalor más pequeño
de ∇2 f (x0 ) es minorado por c en C. Es decir, para todo x0 ∈ C y todo d ∈ Rn , se tiene
que
d⊤ ∇2 f (x0 )d ≥ c∥d∥2 (1.3.1)

3.1 Funciones convexas no suaves

Para introducir el concepto de subdiferencial, primero recordemos el de derivada direccional.
Sea f : Rn → R. Sean x ∈ Rn y d ∈ Rn fijos. Para t > 0, tenemos la función q(t) dada
por
f (x + td) − f (x)
t 7→ , (1.3.2)
t
la cual es una función continua, monótona creciente y localmente Lipschitz. Además,
notemos que
f (x + td) − f (x) f (x + td) − f (x)
f ′ (x; d) = lim q(t) = lim = inf
t↓0 t↓0 t t>0 t
12

y la función d 7→ f ′ (x; d) es sublineal; i.e.

f ′ (x; d1 + d2 ) ≤ f ′ (x; d1 ) + f ′ (x; d2 ),

para cualesquiera d1 y d2 en Rn .
Dado además que si f es convexa, es localmente acotada entonces (1.3.2) al ser decreciente
posee límite cuando t → 0. Es decir, posee derivada direccional f ′ (x; d).

Definición I.13: Subdiferencial

Para una función f : Rn 7→ R convexa, se define el subdiferencial de f en x0 , como

∂f (x0 ) = {z ∈ Rn : f (x) ≥ f (x0 ) + ⟨z, x − x0 ⟩}, (1.3.3)

o, equivalentemente, como

∂f (x0 ) = {z ∈ Rn : f ′ (x0 ; d) ≥ ⟨z, d⟩, ∀d ∈ Rn } (1.3.4)

Los elementos de ∂f (x0 ) son llamados subgradientes.

4 Condiciones de optimalidad para la optimización sin

restricciones
En este capítulo, vamos a consider problemas de optimización de la forma

minimizar f (x) (1.4.1)

sujeto a x ∈ Ω, (1.4.2)

donde f : Ω → R, es llamada función objetivo o función de costo y Ω es es un subconjunto

abierto de Rn que nombraremos conjunto factible. A lo largo de la mayor parte del capítulo,
se restringe la atención al caso donde Ω = Rn .
Notemos que Ω es el conjunto factible pero no corresponde en realidad a una restricción
por ser abierto. En su lugar, corresponde al dominio de definición de f .
Distinguimos dos tipos de soluciones, que definimos a continuación:

Definición I.14: Mínimo local

• Un punto x∗ ∈ Ω se dice que es un mínimo local de f sobre Ω si existe un ε > 0
tal que:
f (x∗ ) ≤ f (x), para todo x ∈ Ω tal que ∥x − x∗ ∥ < ε.

Si, además f (x) > f (x∗ ) para todo x ∈ Ω ∩ B(x∗ , ε) se dice que x∗ es un mínimo
local estricto de f sobre Ω.
 13

Definición I.15: Mínimo global

• Un punto x∗ ∈ Ω se dice que es un mínimo global de f sobre Ω si:

f (x∗ ) ≤ f (x), para todo x ∈ Ω.

Si, además, f (x) > f (x∗ ) para todo x ∈ Ω, x ̸= x∗ , se dice que x∗ es un mínimo
global estricto de f sobre Ω.

La búsqueda de mínimos globales puede ser complicada. En la práctica, la búsqueda de

un mínimo local puede ser suficiente. Existen varias técnicas para la búsqueda de mínimos
globales y es el principal objetivo de la optimización global.

Teorema I.16:
Sea Ω un subconjunto de Rn y sea f una función C 1 en Ω. Si x∗ es mínimo local de f
sobre Ω, entonces para cualquier dirección factiblea d ∈ Rn en x∗ , tenemos

∇f (x∗ )d ≥ 0.
a
i.e. x + td ∈ Ω para todo t < t̄, para cierto t̄

Demostración.

Para cualquier t, 0 ≤ t ≤ t̄, el punto x(t) = x∗ + td ∈ Ω. Para 0 ≤ t ≤ t̄, definimos la

función g(t) = f (x(t)). Entonces, g tiene un mínimo local en t = 0. Un g. Por el cálculo
ordinario, tenemos
g(t) − g(0) = g ′ (0)t + o(t), (1.4.3)
donde o(t) denota términos que tienden a cero más rápido que t. Si g ′ (0) < 0, entonces,
para valores suficientemente pequeños de t > 0, el lado derecho de (1.4.3) será negativo,
y por lo tanto g(t) − g(0) < 0, lo cual contradice la naturaleza de mínimo de g(0). Por
tanto, ∇f (x∗ )d = g ′ (0) ≥ 0. ■

Corolario I.17
Sea Ω un subconjunto de Rn y sea f ∈ C 1 una función en Ω. Si x∗ es mínimo local de
f sobre Ω y si x∗ es un punto interior de Ω, entonces ∇f (x∗ ) = 0

Ejemplo : Problemas de optimización

1. Para α > 0, A ∈ Rn×n , el problema de mínimos cuadrados regularizado

1 α
min{ ∥y − Ax∥2 + ∥x∥2 }
x 2 2
14

2. Si f es una imagen con ruido gausiano, se tiene el problema de eliminación de ruido

1 α
min{ ∥x − f ∥2 + ∥Dx∥2 }
x 2 2
donde D es un operador diferencial que aproxima el gradiente.

3. LASSO (Least Absolute Shrinkage and Selection Operator)

 
1 2
min ∥Ax − y∥ + β∥x∥1
x 2
La norma-1 induce dispersión (componentes nulas) en la solución produciendo una
selección de las variables más importantes. Es menos sensible a los “outliers”.

4. Máquinas de soporte vectorial (SVM) es un modelo de aprendizaje supervisado.

Cada dato xi tiene una etiqueta asociada yi ∈ {+1, −1}. Se busca un hiperplano
caracterizado por w y b que separe los datos con etiquetas 1 de los datos con etiqueta
−1. ( )
n
1 X
min ∥w∥22 + C max(0, 1 − yi (w⊤ xi + b)) ,
w,b 2 i=1

5. Presencia de una especie en un territorio. Si un sitio de un mapa está identificado

con un vector z de condiciones ambientales, el planteamiento de la entropía máx-
ima considera la distribución (de entre una familia de distribuciones de Gibbs) que
maximiza la probabilidad de la presencia de una especie en un sitio, dado por
( m n
)
1 X X
max log(qλ (xi )) − βj |λj |
λ m i=1 j=1

donde
Pn
j=1 λj fj (x)
qλ (x) = e zλ distribución de Gibbs
{fj , j = 1, · · · n} conjunto de características
zλ constante de normalización
fj (x) caracteística en el sitio x (x condiciones ambientales)
xi sitios de presencia

Aunque algunos de los problemas planteados tienen términos no diferenciables, los cuales
requieren técnicas de optimización no suave y análisis convexo, una práctica común es
reemplazar el término no diferenciable por una aproximación diferenciable de éste. Algunos
ejemplos de regularizaciones son las siguientes:
• Para 0 < γ → ∞, la siguientes funciones aproximan el valor absoluto
( 2
γ t2 if |t| ≤ γ1 ,
Huber: Para t ∈ R, hγ (t) = 1
|t| − 2γ si |t| > γ1 .
q
Berkovier-Engelman: Para t ∈ R, t 7→ t2 + γ1
 15

• Para 0 < γ → ∞, la siguiente función aproxima la función max



 t if t ≥ 2γ
1
,
  2
maxγ (0, t) = γ2 t + 2γ1
if |t| ≤ 2γ
1
, (1.4.4)

if t ≤ − 1 .

0
2γ

• Para 0 < γ → ∞, la siguiente función aproxima la función signo:

Huber: t 7→ t
hγ (t)
Berkovier-Engelman: t →7 q t
t2 + γ1

■
Además de la condición de punto crítico, un mínimo satisface condiciones de curvatura,
en términos de la segunda derivada.

Teorema I.18: Condiciones necesarias de segundo orden

Sea x∗ un punto interior del conjunto Ω, y supongamos que x∗ es un mínimo relativo
en Ω de la función f ∈ C 2 . Entonces

1. ∇f (x∗ ) = 0

2. d⊤ ∇2 f (x∗ )d ≥ 0 , para todo d.

Demostración.

La primera condición es simplemente el Teorema 4, y la segunda se aplica siempre que

∇f (x∗ )d = 0. En este caso, introduciendo x(t) = x∗ + td y g(t) = f (x(t)) como antes,
tenemos, en vista de que g ′ (0) = 0,
1
g(t) − g(0) = g ′′ (0)r2 + o(t2 ).
2
Si g (0) < 0, el lado derecho de la ecuación anterior es negativo para t suficientemente
′′

pequeño, lo cual, contradice que t = 0 es un mínimo local de g(0). Por lo tanto,

g ′′ (0) = d⊤ ∇2 f (x∗ )d ≥ 0.
■
Si exigimos un poco más de la segunda derivada, podemos establecer condiciones que,
si son satisfechas por x∗ entonces podemos asegurar que se trata de un mínimo. En otras
palabras, las condiciones son suficientes para asegurar que se trata de un mínimo.
16

Teorema I.19: Condiciones suficientes de segundo orden

Sea f ∈ C 2 una función definida en una vecindad donde el punto x∗ es un punto
interior. Supongamos, además, que

1. ∇f (x∗ ) = 0

2. F (x∗ ) es definida positiva.

Entonces x∗ es un mínimo local estricto de f .

La demostración se deja como ejercicio.

5 Métodos numéricos
Nos concentramos ahora en el desarrollo de mecanismos que nos permitan el cálculo de una
solución óptima. Conocemos de la sección anterior que un mínimo x∗ para una función
diferenciable f sin imponer restricciones, se caracteriza por ser un punto crítico:

x es mínimo local o global
 ∗
⇐=
∇f (x∗ ) = 0 =⇒
̸ x∗ es máximo local o global
x es punto de silla

 ∗

Si resolvemos la ecuación anterior, obtenemos un cadidato x∗ , ya que satisface las condi-

ciones necesarias de primer orden. Una vez obtenido x∗ el siguiente paso sería verificar las
condifiones suficientes para asegurar que se trata de un mínimo local (o global).
Por supuesto, no siempre es posible resolver la ecuación de punto crítico directamente.
Por tanto, la solución se construye mediante una sucesión xk que converge a x∗ . La forma
de construir la sucesión es lo que conocemos como un método de optimización.

5.1 Métodos de descenso

Dada una función f a ser minimizada, la idea general de los métodos de descenso es constrir
una sucesión minimizante {xk }k que converja a un mínimo x∗ (global o local) cuando k → ∞.
Lo cual se consigue si la sucesión deciende:

f (x0 ) > f (x1 ) > · · · > f (xk ) > · · · ≥ f (x∗ ), asumiendo que xk ̸= x∗ .

Es decir, f decrece en cada punto de la sucesión {xk }k . Esta sucesión minimizante se puede
generar de manera iterativa

xk+1 = xk + sk dk , k = 0, 1, . . .

Donde las cantidades involucradas corresponden a:

 17

xk punto actual
sk paso de descenso
dk dirección de descenso
x k+1
actualización de xk
k iteración
De manera más general podemos escribir un método mediante una multifunción, A : Rn →
2 o A : Rn ⇒ Rn
Rn

xk+1 ∈ A(xk ) k = 0, 1, . . .

k=0 que converge al límite r cuando

Consideremos una sucesión de números reales {rk }∞ ∗

k → ∞. Definimos varias nociones relacionadas con la velocidad de convergencia de dicha

sucesión.

Definición I.20:
Sea la sucesión {rk } convergente a r∗ . El orden de convergencia de {rk } se define
como el supremo de los números no negativos p que satisfacen

|rk+1 − r∗ |
0 ≤ lim sup < ∞.
k→∞ |rk − r∗ |p

• Convergencia lineal: con tasa de convergencia β

|rk+1 − r∗ |
lim = β < 1,
k→∞ |rk − r ∗ |

• Convergencia Superlineal:

|rk+1 − r∗ |
lim = 0.
k→∞ |rk − r ∗ |

Esto implica que el error decrece más rápido que en el caso lineal, pero no tiene
un factor constante.

• Convergencia Cuadrática: Eciste β > 0 tal que

|rk+1 − r∗ |
lim = β > 0.
k→∞ |rk − r ∗ |2

Esto implica que el error decrece proporcionalmente al cuadrado del error previo,
lo que significa una velocidad de convergencia muy rápida.

Valores mayores del orden p implican, en cierto sentido, una convergencia más rápida, ya
que la distancia al límite r∗ se reduce por la potencia p en un solo paso. De hecho, si la
secuencia tiene orden p y (como es usual) el límite

|rk+1 − r∗ |
β = lim
k→∞ |rk − r ∗ |p
18

existe, entonces asintóticamente tenemos

|rk+1 − r∗ | = β|rk − r∗ |p .

5.2 Búsqueda lineal

Asumiendo que disponemos de una dirección de descenso dk , nos encontramos con el problema
de elegir s tal que
x(s) = xk + sdk
produzca una disminución en f ; es decir

f (x(s)) = f (xk + sdk ) < f (xk ).

Dado que dk es una dirección de descenso, podemos asumir que existe al menos un s para
el cuaal se produzca esta disminución. La pregunta, es existe s tal que el problema

min g(s) = f (xk + sdk )

s

tiene solución? Si existe dicha solución (o su approximación), que nombraremos sk en-

tonces tomamos el paso de actualización:

xk+1 = xk + sdk .
El proceso de determinar el punto mínimo a lo largo de la dirección de descenso se llama
búsqueda lineal. Las técnicas de búsqueda lineal, que en realidad problemas de minimización
unidimensionales, constituyen la base de los algoritmos de programación no lineal. Existen
varios enfoques diferentes para esta fase importante de la minimización.

Interpolación cuadrática
Un esquema que a menudo es útil para la búsqueda lineal es el de proponer un modelo
cuadrático a lo largo de tres puntos. Esto tiene la ventaja adicional que no se requiere el
cálculo de derivadas.
Dados x1 , x2 , x3 y los valores correspondientes f (x1 ) = f1 , f (x2 ) = f2 , f (x3 ) = f3 .
Supongamos que la función f que deseamos minimizar tiene un solo mínimo y que sus se-
gundas derivadas parciales son continuas.
Para garantizar que la función cuadrática tenga un mínimo en [x1 , x3 ], usamos puntos x1 ,
x , x3 con x1 < x2 < x3 tales que f1 ≥ f2 ≤ f3 . En otras palabras, el valor en el punto medio
2

de estos tres puntos es menor que en cualquiera de los extremos.

Construimos la finción cuadrática que pasa por estos tres puntos
3 Q j
j̸=i (x − x )
X
q(x) = fi Q i j
,
i=1 j̸=i (x − x )

Si x4 es el punto como el punto donde la derivada de q se anula. Este se puede calcular

mediante la fórmula
 19

2.4

2.2

q(x)
1.8

1.6

1 2 3 4
x

Figure 0.1: Interpolación cuadrática

1 b23 f1 + b31 f2 + b12 f3 2 2

x4 = , donde aij = xi − xj , bij = xi − xj .
2 a23 f1 + a31 f2 + a12 f3
Sin embargo, el punto x4 no necesariamente es un valor cercano al fínimo de la función,
como se puede observar en la Figura 0.2.
Partiendo de que disponemos de los valores x1 < x2 < x3 tales que

f (x1 ) ≥ f (x2 ) ≤ f (x3 ),

el punto x4 se calcula a partir de un ajuste cuadrático de la manera estándar y se evalua

f (x4 ). Suponiendo (como en la figura ) que x2 < x4 < x3 , y teniendo en cuenta la naturaleza
unimodal de f , hay dos posibilidades:

1. Si f (x4 ) ≤ f (x2 ), los nuevos puntos son (x̄1 , x̄2 , x̄3 ) = (x2 , x4 , x3 )

2. Si f (x2 ) < f (x4 ) ≤ f (x3 ), los nuevos puntos son (x̄1 , x̄2 , x̄3 ) = (x1 , x2 , x4 )

En cualquiera de los casos, se puede determinar un nuevo patrón de tres puntos, x̄1 , x̄2 ,
x̄3 , que involucra a x4 y a dos de los puntos anteriores.

Ajuste Cuadrático: Método de Falsa Posición

Supongamos que en dos puntos xk y xk−1 , donde se tienen los valores f (xk ), f ′ (xk ), f ′ (xk−1 ),
es posible ajustar el polinomio cuadrático:

1 f ′ (xk−1 ) − f ′ (xk )
q(x) = f (xk ) + f ′ (xk )(x − xk ) + (x − xk )2 ≈ f (x).
2 xk−1 − xk
| {z }
≈f ′′ (xk )

q(x) tiene los mismos valores correspondientes.

20

2
f (x) = −0.005x2 + 5 sin(x) + 0.001e0.1x
P1 (x) = 0.716x2 − 7.880x + 17.858
P2 (x) = 2.101x2 − 19.589x + 40.519

x
Figure 0.2: Inicio (x1 , x2 , x3 ) = (2, 3, 9), Paso 2 (x1 , x2 , x3 ) = (3, 5.454, 9), Paso 3
(x1 , x2 , x3 ) = (3, 5.4540, 5.5010)

Se puede determinar una estimación xk+1 encontrando el punto donde se anula la derivada
de q. Así
xk−1 − xk
 
k+1 k ′ k
x = x − f (x ) ′ k−1 .
f (x ) − f ′ (xk )

Ajuste Cúbico
Dado los puntos xk−1 y xk , junto con los valores f (xk−1 ), f ′ (xk−1 ), f (xk ), f ′ (xk ), también
es posible ajustar un polinomio cúbico a los puntos con sus valores correspondientes. El
siguiente punto xk+1 puede determinarse entonces como el punto de mínimo local de este
polinomio cúbico.
Por tanto,
f ′ (xk ) + u2 − u1
 
k+1 k k k−1
x = x − (x − x ) ′ k ,
f (x ) − f ′ (xk−1 ) + 2u2
donde

′ k−1 ′ k f (xk−1 ) − f (xk )

u1 = f (x ) + f (x ) − 3 ,
xk−1 − xk
1/2
u2 = u21 − f ′ (xk−1 )f ′ (xk )

.
 21

Métodos aproximados
En la práctica, las búsquedas lineales se terminan antes de llegar al punto mínimo real. En
un método, por ejemplo, se elige un valor relativamente grande para x1 , y este valor se reduce
sucesivamente por un factor positivo β < 1 hasta que se obtiene una disminución suficiente
en el valor de la función. Los métodos aproximados.
Es importante determinar el parámetro de búsqueda s dentro de un porcentaje fijo de su
valor real. Específicamente, se selecciona una constante c, 0 < c < 1 (un valor razonable es
c = 0.10), y se encuentra el parámetro s en la búsqueda en línea de tal manera que satisfaga
|s − s̄| ≤ cs̄, donde s̄ es el verdadero valor minimizante del parámetro.

Regla de Armijo. Es un criterio práctico para terminar una búsqueda lineal. La idea
esencial es que la regla debe primero garantizar que el valor seleccionado de s no sea demasiado
grande ni demasiado pequeño. Para ello, definamos la función

ϕ(s) = f (xk + sdk ).

La regla de Armijo se implementa considerando la función ϕ(0) + εϕ′ (0)s para un ε fijo,
0 < ε < 1. Un valor de s no se considera demasiado grande si

ϕ(s) ≤ ϕ(0) + εϕ′ (0)s (1.5.1)

5.2

ϕ ϕ(s) = f (xk + spk )

aceptable aceptable

Figure 0.3: Regiones aceptables para s.

Para asegurar que s no sea demasiado pequeño, se selecciona un valor η > 1, y entonces
se considera que s no es demasiado pequeño si

ϕ(ηs) > ϕ(0) + εϕ′ (0)ηs (1.5.2)

Esto significa que si s se incrementa por el factor η, no cumplirá con (5.2). La región
aceptable definida por la regla de Armijo se muestra en la Fig. 0.1.
El test de Armijo se utiliza para definir una técnica simplificada de búsqueda lineal que
no emplea métodos de ajuste de curvas.
22

Se comienza con un valor arbitrario de s. Si satisface (5.2), se incrementa repetidamente

por η (se usan frecuentemente η = 2 o η = 10 y ε = 0.2) hasta que (5.2) se viole, y entonces
se selecciona el penúltimo valor de s. Si, por otro lado, el valor original de s no satisface
(5.2), se divide repetidamente por η hasta que el valor de s satisfaga (5.2).

Test de Goldstein. Similar que en la regla de Armijo, un valor de s no se considera

demasiado grande si satisface (5.2), con un ε dado, 0 < ε < 21 . Por otro lado, un valor de s
no se considera demasiado pequeño en la prueba de Goldstein si

ϕ(s) > ϕ(0) + (1 − ε)ϕ′ (0)s (1.5.3)

En otras palabras, ϕ(s) debe estar por encima de la función definida por el lado derecho
en (1.5.3).
Un valor aceptable de s para el criterio de Goldstein con el valor correspondiente xk+1 =
xk + sdk , es

f (xk+1 ) − f (xk )
ε≤ ≤ 1 − ε. (1.5.4)
s∇f (xk )dk
Test de Wolfe Si las derivadas de la función objetivo, así como sus valores, pueden evaluarse
de manera relativamente fácil, entonces el test de Wolfe, que es una variación del anterior,
se prefiere en ocasiones. En este caso, se selecciona ε con 0 < ε < 1/2, y se requiere que s
satisfaga y

ϕ′ (s) ≥ (1 − ε)ϕ′ (0). (1.5.5)

Una ventaja del test de Wolfe es que este último criterio es invariante a los cambios en los
factores de escala, mientras que (1.5.3) en el test de Goldstein no lo es.

Backtracking
Este es un método simplificado (a veces sobresimplificado) de búsqueda lineal que funciona
bien si se dispone de una estimación del paso adecuada. (Este es el caso para el método de
Newton multidimensional)
Una buena elección inicial es s = 1. El backtracking se define por la estimación inicial
s y dos parámetros positivos η > 1 y ε < 1 (generalmente ε < 0.5). El criterio de parada
utilizado es el mismo que la primera parte de la regla de Armijo o el test de Goldstein. Es
decir, definiendo ϕ(s) ≡ f (xk + sdk ), el procedimiento se detiene en el valor actual de s si

ϕ(s) ≤ ϕ(0) + εϕ′ (0)s.

Si este criterio no se satisface, entonces s se reduce por el factor 1/η. Es decir,

snuevo = sant /η.

A menudo se usa η ≈ 1.1 o 1.2.
Si el s inicial (como s = 1) satisface el test, entonces se toma como el tamaño del paso.
De lo contrario, s se reduce por 1/η. Repitiendo esto sucesivamente, el primer s que satisface
el test se declara como el valor final.
 23

Por definición, se sabe que el valor anterior sant = snuevo η no pasa la primera prueba, y
esto significa que pasa la segunda condición de la regla de Armijo.
Dado que la búsqueda a lo largo de una línea para un punto mínimo es parte fundamental
de la mayoría de los algoritmos de programación no lineales, es deseable establecer de inmedi-
ato que este procedimiento está cerrado; es decir, que el resultado final de los procedimientos
iterativos descritos anteriormente, cuando se ve como un solo paso algorítmico que encuentra
un mínimo a lo largo de una línea, define algoritmos cerrados.
Definimos el algoritmo de búsqueda S como una aplicación de R2n a Rn .
Asumimos que la búsqueda se realizará a lo largo de la semirrecta que parte desde x en la
dirección d. También asumimos que hay un punto mínimo a lo largo de la línea. Esto será el
caso, por ejemplo, si f es continua y crece indefinidamente cuando ∥x∥ → ∞.

Definición I.21
La aplicación S : R2n → Rn definida por

S(x, d) = {y : y = x + sd para algún s ≥ 0, f (y) = min f (x + sd)}. (1.5.6)

0≤s<∞

Puede haber varios vectores y que alcancen el mínimo, por lo que S es una multifunción.

Teorema I.22
Sea f continua en Rn . Entonces, la aplicación definida por (1.5.6) e es cerrada en (x, d)
si d ̸= 0.

Demostración.
Supongamos que {xk } y {dk } son sucesiones tales que xk → x, dk → d ̸= 0. Supongamos
también que y k ∈ S(xk , dk ) y que y k → y. Debemos demostrar que y ∈ S(x, d).
Para cada k, tenemos y k = xk + sk dk para algún sk . De aquí, podemos escribir

∥y k − xk ∥
sk = .
∥dk ∥
Tomando el límite k → ∞
∥y k − xk ∥ ∥y − x∥
lim sk = lim = := s̄.
k→∞ k→∞ ∥dk ∥ ∥d∥
Entonces se sigue que y = x + s̄d. Aún queda por demostrar que y ∈ S(x, d).
Por definición de S, para cada k y cada s, cumple que 0 ≤ s < ∞,

f (y k ) ≤ f (xk + sdk ).

Tomando otra vez k → ∞, obtenemos

f (y) ≤ f (x + sd).
24

Por lo tanto,
f (y) ≤ min f (x + sd),
0≤s<∞

y así y ∈ S(x, d). ■

■
Ejemplo :
Veamos que la prueba de Goldstein conduce a un algoritmo de búsqueda lineal cerrado.
Sea f ∈ C 2 en Rn . Fijamos ε, 0 < ε < 1/2. Entonces la aplicación S : R2n → Rn , definida
por
f (y) − f (x)
S(x, d) = {y : y = x + sd para algún s ≥ 0, ε ≤ ≤ 1 − ε}
s∇f (x)d
es cerrada en (x, d) si d ̸= 0.
En efecto, supongamos que {xk } y {dk } son secuencias con xk → x, dk → d ̸= 0.
Supongamos también que yk ∈ S(xk , dk ) y yk → y. Probemos que y ∈ S(x, d). Para cada
k, tenemos que y k = xk + sk dk para algún sk . Así

∥y k − xk ∥ ∥y − x∥
sk = k
→ ≡ s.
∥d ∥ ∥d∥

Por lo tanto, sk converge a algún s y y = x + sd. Definiendo:

f (x + sd) − f (x)
ϕ(x, d, s) = .
s∇f (x)d
Entonces ε ≤ ϕ(xk , dk , sk ) ≤ 1 − ε para todo k.
Por nuestras suposiciones sobre f (x), tenemos que ϕ es continua. Así, ϕ(xk , dk , sk ) →
ϕ(x, d, s) y ε ≤ ϕ(x, d, s) ≤ 1 − ε, lo que implica que y ∈ S(x, d). ■

Definición I.23: Multifunciones cerradas

Una multifunción A de X a Y se dice que es cerrada en x ∈ X si las condiciones:
(i) xk → x, xk ∈ X,
implican (iii) y ∈ A(x).
(ii) y k → y, y k ∈ A(xk ),

Definición I.24: Composición de multifunciones

Sean A : X → Y y B : Y → Z multifunciones. La aplicación C = BA se define como
la multifunción C : X → Z con
[
C(x) = B(y).
y∈A(x)
 25

Lema I.25
Sean A : X → Y y B : Y → Z multifunciones. Supongamos que A es cerrada en x y
B es cerrada en A(x). Supongamos también que si xk → x y y k ∈ A(xk ), existe un y
tal que, para alguna subsucesión {y ki }, y ki → y. Entonces, la aplicación C = BA es
cerrada en x.

Demostración.
Sean xk → x y z k → z con z k ∈ C(xk ), se debe mostrar que z ∈ C(x). Seleccionemos
y k ∈ A(xk ) tal que z k ∈ B(y k ), y de acuerdo con la hipótesis, tomemos y y {y ki } tal que
y ki → y. Dado que A es cerrado en x, por la definición, se deduce que y ∈ A(x).
Asimismo, verificamos (i) y (ii) de la Definición I.24 dado que y ki → y, z ki → z, y B es
cerrado en y, se deduce que z ∈ B(y) ⊂ B A(x) = C(x). ■
| {z }
∋y

Dos resultados importantes se deducen a partir de este lema.

Corolario I.26
Sean A : X → Y y B : Y → Z aplicaciones multifuncionales. Si A es cerrada en x,
B es cerrada en A(x) y Y es compacto, entonces la aplicación compuesta C = BA es
cerrada en x.

Corolario I.27
Sea A : X → Y una función y B : Y → Z una multifunción. Si A es continua en x y
B es cerrada en A(x), entonces la composición C = BA es cerrada en x.

5.3 Método del gradiente

Quizás, el método dedescenso más conocido por su simplicidad es el método del gradiente,
pues la dirección de descenso dk en cada iteración se toma como

dk = −∇f (xk ), k = 0, 1, . . .

Método del gradiente: Caso cuadrático

Consideramos el problema cuadrático, con Q ∈ Rn×n definida positiva y b ∈ Rn

min f (x) = x⊤ Qx − b⊤ x (1.5.7)

x

Introducimmos la función

1
E(x) = (x − x∗ )⊤ Q(x − x∗ ),
2
26

tenemos que E(x) = f (x) + 12 x∗ Qx∗ , lo que muestra que la función E difiere de f solo por
una constante. Además, notemos que E(x) = 12 ∥x − x∗ ∥2Q .
El gradiente (tanto de f como de E) se da explícitamente por

∇f (x) = Qx − b.

En el caso cuadrático (1.5.7), el método del gradiente queda formulado en el pseudocódigo:

Data: Q ∈ Rn×n s.d.p., b ∈ Rn , x(0) ∈ Rn
Result: xk solución aproximada
k=0
d0 = −(Ax0 − b)
while ∥dk ∥ > tol do
dk = −(Axk − b)
⊤
dk dk
sk =
dk ⊤ Qdk
xk+1 = xk + sk dk
k ←k+1
end
Algorithm 1: Algoritmo del descenso más profundo.

Lema I.28
El proceso iterativo del método del gradiente satisface
" #
k⊤ k 2
(d d )
E(xk+1 ) = 1 − ⊤ ⊤ −1 k
E(xk ). (1.5.8)
k k k
(d Qd )(d Q d )

Demostración.
Fijando y k = xk − x∗ , hacemos un cálculo directo:
⊤ ⊤
E(xk ) − E(xk+1 ) 2sk dk Qy k − s2k dk Qdk
= .
E(xk ) y T k Qy k
Usando dk = Qy k , tenemos
" ⊤ ⊤
#
E(xk ) − E(xk+1 ) 2(dk dk )2 (dk dk )2 ⊤
k
= ⊤
− ⊤
(dk Q−1 dk )−1
E(x ) k
(d Qd ) k 2 k
(d Qd )k 2

⊤
(dk dk )2
= .
(dk ⊤ Qdk )(dk ⊤ Q−1 dk )
■
 27

Lema I.29: Desigualdad de Kantorovich

Sea Q una matriz simétrica definida positiva y x ̸= 0, entonces

(x⊤ x)2 4λmin λmax

⊤ ⊤ −1
≥ , (1.5.9)
x Qx x Q x (λmin + λmax )2

donde λmax y λmin denotan los valores propios máximo y mínimo de Q.

El siguiente Teorema establece la convergencia en función de los valores máximo y mínimo

de la matriz Q que define el problema cuarático.

Teorema I.30: Convergencia del método del gradiente - Caso

Cuadrático
Para cualquier x0 ∈ Rn , el método de descenso más pronunciado converge al único
punto mínimo x∗ de f . Además, con E(x) = 12 (x − x∗ )⊤ Q(x − x∗ ), se cumple en cada
paso k que
 2
k+1 λmax − λmin
E(x ) ≤ E(xk ).
λmax + λmin
donde λmax y λmin denotan los valores propios máximo y mínimo de Q.

Demostración.
Por el Lema 5.3 y la desigualdad de Kantorovich
 
4λmin λmax max − λmin
λ 
k+1 k 2
E(x ) ≤ 1 − 2
E(x ) = E(xk ).
(λmax + λmin ) λ +λ
| max {z min }
<1

■
De acuerdo a la Definición de la tasa de convergencia, se tiene que además el método del
gradiente converge linealmente a la solución.

5.4 Teorema de Convergencia Global

El Teorema de Convergencia Global se utiliza para establecer la convergencia en la siguiente
situación general. Existe un conjunto solución Γ. Se generan puntos de acuerdo con el
algoritmo xk+1 ∈ A(xk ), y cada nuevo punto siempre reduce estrictamente una función de
descenso Z a menos que se alcance el conjunto solución Γ.
Por ejemplo, en la programación no lineal, el conjunto solución puede ser el conjunto de
puntos mínimos (posiblemente un solo punto), y la función de descenso puede ser la propia
función objetivo. Se encuentra un algoritmo adecuado que genera aproximaciones de la
solución que reducen estrictamente el valor de la función de costo.
28

Definición I.31
Sea Γ ⊂ X un conjunto de soluciones dado y sea A un algoritmo en X. Una función
continua Z con valores reales sobre X se dice que es una función de descenso para Γ y
A si satisface:

i) Si x ∈
/ Γ y y ∈ A(x), entonces Z(y) < Z(x).

ii) Si x ∈ Γ y y ∈ A(x), entonces Z(y) ≤ Z(x).

Teorema I.32: Teorema de Convergencia Global

Sea A un algoritmo en X, y supongamos que, dado x0 , se genera la secuencia {xk }∞
k=0
tal que
xk+1 ∈ A(xk ).
Sea Γ ⊂ X un conjunto solución dado, y supongamos:

(i) todos los puntos xk están contenidos en un conjunto compacto S ⊂ X,

(ii) existe una función continua Z en X tal que:

(a) si x ∈
/ Γ, entonces Z(y) < Z(x) para todo y ∈ A(x),
(b) si x ∈ Γ, entonces Z(y) ≤ Z(x) para todo y ∈ A(x),

(iii) La multifunción A es cerrada en puntos fuera de Γ.

Entonces, el límite de cualquier subsucesión convergente de {xk } es una solución.

Demostración.
Supongamos que la sunsucesión convergente {xki } converge al límite x. Dado que Z es
continua, se sigue que Z(xki ) → Z(x) si i → ∞.
Gracias a las suposiciones (i) (ii), se sigue la monotonía de Z en la sucesión {xk }. Es
decir, tenemos que Z(xk ) − Z(x) ≥ 0 para todo k. Ahora, por la convergencia de Z en la
subsucesión, se deduce que para ε > 0, existe K tal que

Z(xki ) − Z(x) < ε para todo i > K.

Entonces, para todo k ≥ kK

0 ≤ Z(xk ) − Z(x) =Z(xk ) − Z(xkK ) + Z(xkK ) − Z(x)

≤Z(xkK ) − Z(x) < ε,

lo que muestra que Z(xk ) → Z(x).

Para completar la demostración, solo es necesario mostrar que x es una solución. Por
contradicción, supongamos que x no es una solución. Es decir, x ∈
̸ Γ Consideremos la
 29

subsucesión {xki+1 }. Dado que todos los elementos de esta secuencia están contenidos
en un conjunto compacto, existe una subsucesión {xki+1 } (sin renombrar) que converge a
algún límite x̄. Por tanto, tenemos que xki → x, y xki+1 ∈ A(xki ). Dado que A es cerrada
en x, se sigue que x̄ ∈ A(x). Sin embargo, lo discutido anteriormente implica Z(x̄) = Z(x),
lo que contradice el hecho de que Z es una función de descenso. ■

Corolario I.33
Si bajo las condiciones del Teorema de Convergencia Global, si Γ consiste en un único
elemento x̄, entonces la sucesión {xk } converge a x̄.

Demostración.

Supongamos que, al contrario, existe una subsucesión {xki } y un ε > 0 tal que |xki − x̄| > ε
para todo i ≥ i0 para cierto i0 . Por otro lado, por compacidad debe existir una subsucesión
{xki } (sin renombrar) convergente a un límite notado por x′ . Claramente, |x′ − x̄| ≥ ε,
pero por el Teorema de Convergencia Global, x′ ∈ Γ = {x̄}, lo cual es una contradicción.
■
Formalmente, el algoritmo global para el método del gradiente

A : Rn → Rn , que da xk+1 ∈ A(xk ),

puede descomponerse en la forma A = SG. Donde G : Rn → R2n se define como

G(x) = (x, −∇f (x)⊤ ), proporcionando el punto inicial y la dirección de una búsqueda lineal
y posteriormente componiendo con la búsqueda lineal S : R2n → Rn .

Esta función es cerrada gracias al Lema I.25. En efecto, sabemos que S es cerrado si la
dirección de descenso d = ∇f (x) ̸= 0 y además que G es continuo.

El conjunto solución Γ se define como los puntos x donde ∇f (x) = 0. Entonces, f (x) es
una función de descenso para A, dado que para ∇f (x) ̸= 0 se tiene

lim f (x − s∇f (x)⊤ ) < f (x).

0≤s<∞

Lema I.34
Sea f diferenciable en Rn tal que ∇f (·) es β-Lipschitz. Entonces, para dos puntos
cualesquiera x y y, se cumple que:
β
f (x) − f (y) − ∇f (y)(x − y) ≤ ∥x − y∥2 .
2

Demostración.
30

Z 1
f (x) − f (y) − ∇f (y)(x − y) = (∇f (y + t(x − y)) − ∇f (y)) · (x − y) dt.
0
Z 1
≤ βt · ∥x − y∥2 dt
0
t2 1 β
=β ∥x − y∥2 = ∥x − y∥2
2 0 2
■

Teorema I.35: Descenso más profundo (caso convexo)

Sea f convexa y diferenciable tal que ∇f (·) es β-Lipschitz. Si f admite un minimizador
x∗ , entonces, el método de descenso más profundo con un paso de descenso sk = β1 ∀k,
genera una sucesión de soluciones xk tal que

β2
∥∇f (xk )∥ ≤ p ∥x0 − x∗ ∥,
k(k + 1)
y
β
f (xk ) − f (x∗ ) ≤ ∥x0 − x∗ ∥2 .
2(k + 1)

Proof. Para x dado, consideramos la función gx (y) = f (y)−∇f (x)⊤ y. Nótese que gx también
es convexa y satisface la condición de Lipschitz con constante β. Además, x es el minimizador
de gx (y) y ∇gx (y) = ∇f (y) − ∇f (x).
Aplicando el Lema I.34 a gx y observando las relaciones entre gx y f (x), tenemos

f (x) − f (y) − ∇f (y)⊤ (x − y) =gx (x) − gx (y)

1
≤gx y − ∇gx (y)⊤ ) − gx (y)
β
 
1 ⊤ β 1
≤∇gx (y) − ∇gx (y) + ∥∇gx (y)∥2
β 2 β2
1
=− ∥∇gx (y)∥2
2β
1
=− ∥∇f (x) − ∇f (y)∥2 . (1.5.10)
2β
De manera similar, tenemos
1
f (y) − f (x) − ∇f (y)⊤ (y − x) ≤ − ∥∇f (x) − ∇f (y)∥2 .
2β
Sumando ambas desigualdades, tenemos para cualquier x y y:
1
(∇f (x) − ∇f (y))⊤ (x − y) ≥ ∥∇f (x) − ∇f (y)∥2 . (1.5.11)
β
 31

Para simplificar la notación tomamos dk = xk − x∗ y δk = [f (xk ) − f (x∗ )] ≥ 0.

Ahora tomemos x = xk+1 y y = xk y notemos ∇f k = ∇f (xk ) y ∇f k+1 = ∇f (xk+1 ) en
(1.5.11). Así:

1 1
− (∇f k )⊤ (∇f k+1 − ∇f k ) = (xk+1 − xk )⊤ (∇f k+1 − ∇f k ) ≥ ∥∇f k+1 − ∇f k ∥2 ,
β β

desarrollando la norma al cuadrado en el lado izquierdo y eliminando términos con el lado

derecho, conduce a

∥∇f k+1 ∥2 ≤ (∇f k+1 )⊤ ∇f k ≤ ∥∇f k+1 ∥∥∇f k ∥, es decir , ∥∇f k+1 ∥ ≤ ∥∇f k ∥. (1.5.12)

La desigualdad (1.5.12) implica que ∥∇f k ∥ es monótonamente decreciente. Aplicando la

desigualdad (1.5.11) para x = xk y y = x∗ y recordando que ∇f (x∗ ) = 0, tenemos

⊤ 1
δ k ≤∇f k dk − ∥∇f k ∥2
2β
β k+1
= − β(xk+1 − xk )⊤ dk − ∥x − xk ∥ 2 (paso de actualización)
2
β
=− (∥xk+1 − xk ∥2 + 2(xk+1 − xk )⊤ dk ) (factorizando β/2)
2
β
= − (∥dk+1 − dk ∥2 + 2(dk+1 − dk )⊤ dk )
2
β
= (∥dk ∥2 − ∥dk+1 ∥2 ).
2
Sumando la relación anterior desde 0 hasta k, tenemos
k
X β β
δl ≤ (∥d0 ∥2 − ∥dk+1 ∥2 ) ≤ ∥d0 ∥2 . (1.5.13)
l=0
2 2

Usando de nuevo (1.5.10) para x = xk+1 y y = xk y observando que el paso se toma sk = 1/β,
tenemos

δk+1 − δk =f (xk+1 ) − f (xk )

 
k+1 ⊤ 1 k 1
≤(∇f ) − ∇f − ∥∇f k+1 − ∇f k ∥2
β 2β
1
=− (∥∇f k+1 ∥2 + ∥∇f k ∥2 ).
2β

Esta última estimación es válida para todo k, tenemos

k
X k
X k
X k
X k+1
X k
X
δl = δl (l + 1 − l) = δl (l + 1) − δl l = δl−1 l − δl l,
l=0 l=0 l=0 l=0 l=1 l=1

de aqui se sigue que

32

k
X k
X
δl =δk (k + 1) + (δl−1 − δl )l
l=0 l=1
k
X 1
≥δk (k + 1) + (∥∇f l ∥2 + ∥∇f l−1 ∥2 )
l=1
2β
k(k + 1)
≥δk (k + 1) + ∥∇f k ∥2
2β

Donde la última desigualdad se da por la monotonicidad decreciente de ∥∇f k ∥2 . Usando

(1.5.13) finalmente tenemos

k(k + 1) β
(k + 1)δ k + ∥∇f k ∥2 ≤ ∥d0 ∥2 .
2β 2

En vista de que δ k = f (xk )−f (x∗ ) ≥ 0 y d0 = x0 −x∗ , esta desigualdad prueba las acotaciones
deseadas.
Ejemplo : Métodos de Penalización
Tenemos un problema de optimización con restricciones:

minimizar f (x) sujeto a h(x) = 0.

Esto significa que queremos minimizar la función f (x), y que la solución satisfaga h(x) = 0.
Una forma de abordar este problema con restricciones es aproximarlo como un problema
sin restricciones añadiendo un término de penalización por violar la restricción. El nuevo
problema se convierte en:
1
minimizar f (x) + µh(x)2 ,
2
donde µ es un coeficiente de penalización, típicamente un valor grande. La idea es
que, al añadir este término, penalizamos cualquier violación de la restricción h(x) = 0. A
medida que µ se hace más grande, la solución al problema penalizado tiende a satisfacer
h(x) = 0 de manera más estricta.
A medida que µ aumenta, la solución a este problema penalizado acercará h(x) a cero,
aplicando efectivamente la restricción. El problema penalizado se puede resolver utilizando
métodos de optimización sin restricciones estándar como el descenso por gradiente.
Este enfoque de penalización convierte un problema de optimización con restricciones en
uno sin restricciones, lo que simplifica el proceso de solución mientras controla la violación
de la restricción a través del parámetro µ. ■
Ejemplo : Regularización de LASSO
Consideremos  
1 2
min ∥Ax − y∥ + β∥x∥1
x 2
1
Reemplazando ∥x∥1 = ni=1 |xi | por ∥x∥1,γ = ni=1 (x2i + γ1 ) 2 (usando Berkovier-Engelman)
P P
 33

se obtiene el problema regularizado

 
1
min ∥Ax − y∥ + β∥x∥1,γ , para cierto γ >> 1
2
x 2

El gradiente del término de mínimos cuadrados f (x) = 12 ∥Ax − y∥2 es:

∇f (x) = A⊤ (Ax − y)
El gradiente del término de regularización g(x) = ∥x∥1,γ es:
 ⊤
x1 x2 xn
∇g(x) = β   1/2 ,  1/2 , . . . , 
 
1/2 
1 1 1
x21 + γ
x22 + γ
x2n + γ

Por lo tanto, el gradiente de la función de costo total es:

 ⊤
x1 xn
∇J(x) = A⊤ (Ax − y) + β   1/2 , . . . , 
 
1/2 
1 1
x21 + γ
x2n + γ

El mínimo x∗ se caracteriza por satisfacer ecuación :

A⊤ Ax + βζ(x) = A⊤ y
 ⊤
donde ζ(x) = x1
1/2 ,..., xn
1/2
(x21 + γ1 ) (x2n + γ1 )
■
El rendimiento del método de descenso por gradiente está influenciado por la elección
particular de las variables x que se utilizan para definir el problema y un nuevo conjunto de
variables puede alterar sustancialmente las características de convergencia.
Supongamos que T ∈ Rn×n es una matriz invertible. Entonces, podemos hacer un cambio
de variable de x a un nuevo vector y, donde:
T y = x.
Este enfoque implica escalar el problema al introducir una matriz de transformación T ,
lo que podría mejorar las tasas de convergencia dependiendo de las propiedades de T y de
cómo encaja con la geometría del problema.
Minimizar f (x) es equivalente a encontrar y para minimizar h(y) = f (T y). Usando y
como el conjunto de variables subyacente, tenemos:
∇h(·) = ∇f (·)T,
donde ∇f es el gradiente de f con respecto a x.

5.5 Método del Gradiente Acelerado

Existe un método de descenso por gradiente acelerado que funciona de la siguiente manera:
34

p
0 1+ 1 + 4(λk )2 1 − λk
λ = 0, λk+1 = , αk = ,
2 λk+1
1
x̃k+1 = xk − ∇f (xk )⊤ , xk+1 = (1 − αk )x̃k+1 + αk x̃k .
β
Observemos que (λk )2 = λk+1 (λk+1 − 1), λk > k
2
y αk ≤ 0.
Se puede probar lo siguiente:

Teorema I.36: Convergencia del Método del Gradiente Aceler-

ado)
Sea f convexa y diferenciable tal que ∇f (·) es β-Lipschitz. Si f admite un minimizador
x∗ , entonces, el método de descenso más profundo acelerado genera una sucesión de
soluciones tal que:
2β 0
f (x̃k+1 ) − f (x∗ ) ≤ |x − x∗ |2 , ∀k ≥ 1.
k2

5.6 Método de Newton

La idea detrás del método de Newton es aproximar la función f cerca de un punto xk mediante
una función cuadrática, y minimizar esta función aproximada exactamente.
La función f (x) se aproxima mediante la expansión truncada de la serie de Taylor:
1
f (x) ≃ f (xk ) + ∇f (xk )(x − xk ) + (x − xk )⊤ ∇2 f (xk )(x − xk ), (1.5.14)
2
donde ∇f 2 (xk ) es la matriz Hessiana de segundas derivadas.
La minimización de este lado derecho ocurre en:
xk+1 = xk − [∇2 f (xk )]−1 ∇f (xk )⊤ , (1.5.15)
que es el corazón del método de Newton.
Si la matriz Hessiana en un mínimo local x∗ es definida positiva, el método está bien
definido cerca de la solución.
El método de Newton tiene convergencia cuadrática si la estimación inicial está lo
suficientemente cerca de la solución.

Teorema I.37: Convergencia local cuadrática

Sea f ∈ C 3 en Rn , y supongamos que en mínimo local x∗ , la Hessiana ∇2 f (x∗ ) es
definida positiva. Entonces, si el punto inicial está lo suficientemente cerca de x∗ , los
puntos generados por el método de Newton convergen a x∗ y el orden de convergen-
cia es al menos dos.

Demostración.
 35

Existen ρ > 0, β1 > 0, β2 > 0 tales que para todo x con ∥x − x∗ ∥ < ρ, se cumple
∥∇2 f (x)−1 ∥ < β1 y ∥∇f (x∗ )⊤ − ∇f (x)⊤ − ∇2 f (x)(x∗ − x)∥ ≤ β2 ∥x − x∗ ∥2 . Supongamos
ahora que xk es seleccionado con β1 β2 ∥xk − x∗ ∥ < 1 y ∥xk − x∗ ∥ < ρ. Entonces:

∥xk+1 − x∗ ∥ = ∥xk − x∗ − ∇2 f (xk )−1 ∇f (xk )⊤ ∥

= ∥∇2 f (xk )−1 [∇f (x∗ )⊤ − ∇f (x)⊤ − ∇2 f (xk )(x∗ − xk )]∥

≤ ∥∇2 f (xk )−1 ∥β2 ∥xk − x∗ ∥2

≤ β1 β2 ∥xk − x∗ ∥2 < ∥xk − x∗ ∥.

La última desigualdad muestra que xk+1 está más cerca de x∗ que la aproximación
anterior xk , y por lo tanto, todas las condiciones se aplican nuevamente a xk+1 . La
desigualdad anterior establece que la convergencia es de segundo orden.
■
Podemos escribir un pseudo código para el método de Newton, como sigue

Data: x0 , f , ∇f , ∇2 f , tol
Result: xk solución aproximada
k=0
Inicializar d0 (ejm. ∇2 (x0 )d0 = −∇f (x0 ))
while ∥dk ∥ > tol do
Resolver ∇2 (xk )dk = −∇f (xk )
sk = linesearch(xk , ∇f (xk ))
xk+1 = xk + sk dk
k ←k+1
end
Algorithm 2: Algoritmo de Newton

El método de búsqueda lineal con backtracking, utilizando α = 1 como la estimación inicial,

es se puede incorporar para usar con el método de Newton.

Ahora examinemos la situación cuando estamos cerca de la solución. Suponemos que todas
las derivadas de f hasta la tercera son continuas y uniformemente acotadas. Asumimos que
en una vecindad de la solución, ∇2 f (·) es definida positiva con a > 0 y A > 0, siendo,
respectivamente, cotas inferiores y superiores uniformes en los valores propios de ∇2 f (x).

Usando sk = 1 y ε < 0.5, tenemos para dk = −∇2 f (xk )−1 ∇f (xk ):

36

1
f (xk + dk ) =f (xk ) − ∇f (xk )⊤ ∇2 f (xk )−1 ∇f (xk ) + ∇f (xk )⊤ ∇2 f (xk )−1 ∇f (xk )
2
k 2
+ o(∥∇f (x )∥ )
1
=f (xk ) − ∇f (xk )⊤ ∇2 f (xk )−1 ∇f (xk ) + o(∥∇f (xk )∥2 )
2
<f (x ) − ε∇f (xk )⊤ ∇2 f (xk )−1 ∇f (xk ) + o(∥∇f (xk )∥2 ),
k
(1.5.16)

donde el término o está uniformemente acotado para todo xk . Dado que ∥∇f (xk )∥ → 0
(uniformemente) cuando xk → x∗ Para xk suficientemente cerca de x∗ , entonces f (xk + dk ) <
f (xk ) − ε∇f (xk )⊤ dk , y por lo tanto se satisface la primera parte de la regla de Armijo. Esto
significa que sk = 1 se utilizará durante toda la fase final.

Newton en problemas generales

En la práctica, la matriz Hessiana no siempre es definida positiva, en cuyo caso el método de
Newton debe modificarse para en regiones alejadas de la solución.
Un enfoque común es tomar

Mk = [εk I + ∇f 2 (xk )]−1

para algún valor no negativo de εk . Podemos interpretarlo como un compromiso entre el

descenso más profundo (εk muy grande) y el método de Newton (εk = 0). Siempre existe un
εk que hace a Mk definida positiva.
Sea ∇2 f k ≡ ∇2 f (xk ) y fijamos una constante δ > 0. Dado xk , calculamos los valores
propios de ∇2 f k y tomamos εk como la constante no negativa más pequeña para la cual la
matriz εk I + ∇2 f k tiene valores propios mayores o iguales a δ. Luego definimos

dk = −(εk I + ∇2 f k )−1 ∇f k
e iteramos de acuerdo con la fórmula

xk+1 = xk + sk dk ,

donde sk minimiza f (xk + sdk ), s ≥ 0.

Este algoritmo tiene las propiedades globales y locales deseadas. Primero, dado que los
valores propios de una matriz dependen continuamente de sus elementos, εk es una función
continua de xk , y por lo tanto la aplicación D : Rn → R2n definida por D(xk ) = (xk , dk )
es continua. Así, el algoritmo A = SD está cerrado en puntos fuera del conjunto solución
Ω = {x : ∇f (x) = 0}. Segundo, dado que εk I + ∇2 f k es definida positiva, dk es una dirección
de descenso, y así Z(x) ≡ f (x) es una función de descenso continua para A. Por lo tanto,
suponiendo que la secuencia generada está acotada, se aplica el Teorema del Convergencia
Global.
Además, si δ > 0 es más pequeño que el menor valor propio de ∇2 f (x∗ ), entonces para xk
suficientemente cercano a x∗ , tendremos εk = 0, y el método se reduce al método de Newton.
Así, este método también tiene un orden de convergencia igual a dos.
 37

La selección de un δ apropiado depende del problema a resolver. Un δ pequeño significa

que se deben invertir matrices casi singulares, mientras que un δ grande significa que el orden
dos de convergencia puede perderse. La experimentación y la familiaridad con una clase dada
de problemas son a menudo necesarias para encontrar el mejor δ.

5.7 Métodos conjugados

Los métodos de direcciones conjugadas fueron diseñados y analizados para el problema pu-
ramente cuadrático

1 ⊤
minimizar x Qx − b⊤ x,
2
donde Q es una matriz simétrica positiva definida de n × n.

Definición I.38
Dada una matriz simétrica Q, se dice que dos vectores d1 y d2 son Q-ortogonales, o
conjugados con respecto a Q, si d⊤
1 Qd2 = 0.

Se dice que un conjunto de vectores d0 , d1 , . . . , dk es un conjunto Q-ortogonal si

i Qdj = 0 para todo i ̸= j.
d⊤

En las aplicaciones que consideramos, la matriz Q será definida positiva, pero esto parte
de la definición. Por lo tanto, si Q = 0, cualquier par de vectores son conjugados, mientras
que si Q = I, la conjugación es equivalente a la noción usual de ortogonalidad.

Lema I.39
Si Q es definida positiva y el conjunto de vectores no nulos d0 , d1 , d2 , . . . , dk son Q-
ortogonales, entonces estos vectores son linealmente independientes.

Demostración.
Supongamos que existen constantes αi , i = 0, 1, 2, . . . , k, tales que

α0 d0 + · · · + αk dk = 0.
Multiplicando por Q y tomando el producto escalar con di obtenemos

α i d⊤
i Qdi = 0.

Dado que d⊤
i Qdi > 0 en vista de la definitud positiva de Q, tenemos αi = 0 ■
La proposición anterior (ya que vectores son linealmente independientes) implica que la
solución x∗ puede expandirse como

x∗ = α0 d0 + · · · + αn−1 dn−1 (3)

38

para ciertos αi ’s. De hecho, multiplicando por Q y luego tomando el producto escalar con
di se obtiene directamente

d⊤i Qx
∗
d⊤i b
αi =⊤
= ⊤
. (1.5.17)
di Qdi di Qdi
Esto muestra que los αi ’s y, por lo tanto, la solución x∗ pueden encontrarse mediante la
evaluación de productos escalares simples. De aqui, se deduce
n−1
∗
X d⊤i b
x = ⊤
di .
i=0
d i Qd i

Por tanto, se necesita un método eficiente para generar direcciones Q-ortogonales.

Teorema I.40: Dirección Conjugada

Sea {di }n−1
i=0 un conjunto de vectores no nulos Q-ortogonales. Para cualquier x ∈ R ,
0 n

la sucesión {xk } generada por el esquema:

xk+1 = xk + sk dk , k≥0

con
⊤
g k dk
sk = − (1.5.18)
dk ⊤ Qdk
y

g k = Qxk − b,
converge a la solución única, x∗ , de Qx = b después de n pasos, es decir, xn = x∗ .

Demostración.
Dado que los dk ’s son linealmente independientes, podemos escribir

x∗ − x0 = s0 d0 + s1 d1 + · · · + sn−1 dn−1
para algún conjunto de sk ’s. Como hicimos para obtener (1.5.17), multiplicamos por Q y
tomamos el producto escalar con dk para encontrar
⊤
dk Q(x∗ − x0 )
sk = . (1.5.19)
dk ⊤ Qdk

Ahora, siguiendo el proceso iterativo desde x0 hasta xk , obtenemos

xk − x0 = s0 d0 + s1 d1 + · · · + sk−1 dk−1 ,
y por la Q-ortogonalidad de los dk ’s, se sigue que
⊤
dk Q(xk − x0 ) = 0.
 39

Sustituyendo esta relación en (1.5.19) obtenemos

⊤ ⊤
dk Q(x∗ − xk ) g k dk
sk = =− ,
dk ⊤ Qdk dk ⊤ Qdk
que es lo que se quería demostrar. ■

Teorema I.41
Sea {di }n−1
i=0 una sucesión de vectores no nulos Q-ortogonales en R . Entonces, para
n

cualquier x ∈ R , la sucesión {x } generada por

0 n k

xk+1 = xk + sk dk
⊤
g k dk
sk = −
dk ⊤ Qdk
tiene la propiedad de que xk minimiza f (x) = 12 x⊤ Qx − b⊤ x sobre el subespacio x =
xk−1 + sdk−1 , −∞ < s < ∞, así como en la variedad lineal x0 + Bk , donde Bk =
span{d1 , d2, . . . dn−1 }.

Demostración.

Solo es necesario mostrar que xk minimiza f en la variedad lineal x0 + Bk , ya que contiene

al espacio afín x = xk−1 + sdk−1 . Dado que f es una función estrictamente convexa, la
conclusión será válida si se puede demostrar que g k es ortogonal a Bk .
Por inducción, veamos que g k ⊥ Bk . Dado que B0 está vacía, esa hipótesis es verdadera
para k = 0. Suponiendo que es verdadera para k, es decir g k ⊥ Bk , mostramos que
g k+1 ⊥ Bk+1 . Tenemos

g k+1 = g k + sk Qdk , (13)

y por tanto
⊤ ⊤ ⊤
dk g k+1 = dk g k + sk dk Qdk = 0 (14)
por la definición de sk . También, para i < k,
⊤ ⊤ ⊤
di g k+1 = di g k + sk di Qdk . (15)
El primer término en el lado derecho de (15) se anula debido a la hipótesis de inducción,
mientras que el segundo se anula por la Q-ortogonalidad de los di . Por lo tanto, g k+1 ⊥
Bk+1 . ■
40

Teorema I.42: Teorema del Gradiente Conjugado.

El algoritmo de gradiente conjugado es un método de dirección conjugada. Si no
termina en la solución, entonces:

(i) span{g 0 , g 1 , . . . , g k } = span{g 0 , Qg 0 , . . . , Qk g 0 }

(ii) span{d0 , d1 , . . . , dk } = span{g 0 , Qg 0 , . . . , Qk g 0 }

⊤
(iii) dk Qdi = 0 para i ≤ k − 1
⊤
gk gk
(iv) sk = dk ⊤ Qdk

⊤
g k+1 g k+1
(v) βk = gk ⊤ gk

Data: Q ∈ Rn×n s.d.p., b ∈ Rn , x(0) ∈ Rn

Result: x(k) solución aproximada de Ax = b
k=0
d0 = −g 0 = b − Ax0
while r(k) > tol do
⊤
gk gk
sk = dk ⊤ Qdk

xk+1 = xk + sk dk
g k+1 = Qxk+1 − b
⊤
g k+1 g k+1
βk = gk ⊤ gk

dk+1 = −g k+1 + βk dk
end
Algorithm 3: Algoritmo del Gradiente Conjugado para el problema cuadrático

Gradiente conjugado para problemas no cuadráticos

El problema general de minimización no restringida en Rn

minimizar f (x)
puede abordarse haciendo aproximaciones adecuadas al algoritmo de gradiente conjugado.
Hay varias maneras en que esto puede lograrse. La elección depende de las propiedades de f
que son fácilmente computables.

Aproximación Cuadrática
En el método de aproximación cuadrática hacemos las siguientes asociaciones en xk :
 41

g k ↔ ∇f (xk )⊤ , Q ↔ ∇2 f (xk ),

Si f es cuadrática, estas asociaciones son identidades. Esta aproximación es similar a la

filosofía subyacente del método de Newton, donde en cada paso la solución de un problema
general se aproxima mediante la solución de un problema puramente cuadrático usando estas
mismas asociaciones.
A pesar de que teóricamente el método de gradiente conjugado debe terminar en n pasos,
generalmente en la práctica se aprovecha la naturaleza iterativa del método, y simplemente
se continúa calculando nuevas direcciones de acuerdo con el algoritmo y terminar solo cuando
se cumple algún criterio de parada.

Métodos de Búsqueda en Línea

Se puede evitar la asociación directa Q ↔ F (xk ). Podemos aproximar sk mediante una

búsqueda lineal. Además, la fórmula para βk se reemplaza por una fórmula diferente que, sin
embargo, es equivalente a la del caso cuadrático.
El primer método propuesto fue el método de Fletcher-Reeves, en el cual se emplea (v) del
Teorema del Gradiente Conjugado; es decir,

⊤
g k+1 g k+1
βk = .
gk ⊤gk

Data: f , ∇f , x(0) ∈ Rn
Result: x(k) solución aproximad
while ∥∇f (xk )∥ > tol do
k=0
d0 = −g 0 = b − Ax0
for k = 0, 1, . . . , n − 1 do
xk+1 = xk + sk dk tal que sk minimiza f (xk + sdk )
g k+1 = ∇f (xk+1 )
if k < n − 1 then
⊤
g k+1 g k+1
βk = gk ⊤ gk

dk+1 = −g k+1 + βk dk
else
x0 ← x n
end
end
end
Algorithm 4: Algoritmo del Gradiente Conjugado para problemas no cuadrático con
reinicio
42

El método de Polak-Ribiere, calcula

⊤
(g k+1 − g k )⊤ g k+1
βk = .
gk ⊤gk

5.8 Método de Newton modificado

Supongamos que tenemos el siguiente esquema de descenso:
xk+1 = xk − sk B k ∇f (xk ), (1.5.20)
donde B k es una matriz simétrica de tamaño n × n y sk se elige para minimizar f (xk+1 ) =
f (xk + sk ). Si B k es la inversa de la hessiana de f , obtenemos el método de Newton, mientras
que si S k = I, obtenemos el método del descenso más profundo. La idea de seleccionar
B k como una aproximación a la inversa de la hessiana resulta natural. Examinamos este
acercamiento al problema de invertir la hessiana en esta sección.
En el caso del problema cuadrático estándar
1
f (x) = x⊤ Qx − b⊤ x,
2
donde Q es simétrica y definida positiva. Para este caso, podemos encontrar una expresión
explícita para sk en (1.5.20). El algoritmo se escribe como

xk+1 = xk − sk Bk ∇f (xk ), (1.5.21a)

donde,
∇f (xk ) = Qxk − b, (1.5.21b)
y
⊤
∇f (xk ) Bk ∇f (xk )
sk = . (1.5.21c)
∇f (xk )⊤ Bk QBk ∇f (xk )
Luego, podemos determinar la tasa de convergencia para este algoritmo modificando lig-
eramente el análisis realizado para el método de descenso más profundo.

Teorema I.43: Método de Newton Modificado (Caso cuadrático)

Sea x∗ mínimo (único) f , y E(x) = 21 (x − x∗ )⊤ Q(x − x∗ ). Entonces, para el esquema
(1.5.21) se cumple en cada paso k que:
 2
k+1 µmax k − µmin k
E(x ) ≤ E(xk ),
µmax k + µmin k
donde µmin k y µmax k son, respectivamente, los valores propios más pequeños y más
grandes de la matriz Bk Q para cada k.

Demostración.
 43

Por sustitución directa,

 2
k⊤ k
k
E(x ) − E(x k+1
) g Bk g
=  .
E(xk ) g k ⊤ Bk QBk g k g k ⊤ Q−1 g k
1/2 1/2 1/2
Definiendo Tk = Bk QBk y pk = Bk g k , obtenemos
 2
k⊤ k
k k+1
E(x ) − E(x ) p p
=  .
E(xk ) pk ⊤ T k pk pk ⊤ T k −1 pk
De la desigualdad de Kantorovich obtenemos:
 2
k+1 µmax k − µmin k
E(x ) ≤ E(xk ),
µmax k + µmin k
donde µmin k y µmax k son los valores propios más pequeños y más grandes de T k . Dado
que Bk 1/2 T k Bk −1/2 = Bk Q, vemos que Bk Q es similar a T k y, por lo tanto, tiene los
mismos valores propios. ■
La idea fundamental detrás los métodos casi-Newton es intentar construir la inversa de
la hessiana, o una aproximación de la misma, utilizando la información recopilada a medida
que progresa el proceso de descenso.
La aproximación en el paso k: Hk se utiliza en cada etapa para definir la siguiente dirección
de descenso estableciendo Bk = Hk en el método de Newton modificado. Idealmente, las
aproximaciones convergen a la inversa de la hessiana en el punto de solución, y el método
general se comporta de manera algo similar al método de Newton.
En esta sección mostramos cómo se puede construir la inversa de la hessiana a partir de
la información del gradiente obtenida en varios puntos.
Sea f una función en Rn de clase C 2 . Si para dos puntos xk+1 , xk definimos g k+1 =
∇f (xk+1 )⊤ , g k = ∇f (xk )⊤ y pk = xk+1 − xk , entonces

g k+1 − g k ≈ ∇2 (xk )pk .

Si la hessiana es constante: ∇2 f (xk ) = ∇2 f , entonces tenemos

q k ≡ g k+1 − g k = ∇2 f pk , (1.5.22)
y vemos que la evaluación del gradiente en dos puntos proporciona información sobre ∇2 f .
Si se conocen n direcciones linealmente independientes p0 , p1 , . . . , pn−1 y los q k asociados,
entonces ∇2 f (xk ) está determinada de manera única.
De hecho, si P = [p0 p1 · · · pn−1 ] y Q = [q 0 q 1 · · · q n−1 ] matrices de tamañon × n tenemos
que
∇2 f (xk ) = QP −1
Es natural intentar construir aproximaciones sucesivas Hk a ∇2 f (xk )−1 basadas en los datos
obtenidos de los primeros k pasos de un proceso de descenso, de manera que si ∇2 f (xk ) fuese
44

constante la aproximación sería consistente con (1.5.22) para estos pasos. Específicamente,
si ∇2 f (xk ) fuera constante, Hk+1 cumple que

Hk+1 q i = pi , 0 ≤ i ≤ k. (1.5.23)

Después de n pasos usando vectores linealmente independientes, obtenemos que

Hn = ∇2 f −1

Corrección de Rango Uno

Dado que ∇2 f (xk ) y ∇2 f (xk )−1 son simétricas, es natural requerir que la matriz Hk que
aproxima a ∇2 f (xk )−1 , sea simétrica. Investigemos la posibilidad de definir una fórmula
recursiva, que preserve la simetría, de la forma:

⊤
Hk+1 = Hk + ak z k z k , (1.5.24)

El vector z k y la constante ak definen una matriz de (como máximo) rango uno, mediante la
cual se actualiza la aproximación de la inversa. Los seleccionamos de manera que se satisfaga
(1.5.22). Al establecer i igual a k en (1.5.22) y sustituyendo la relación anterior obtenemos

⊤
pk = Hk+1 q k = Hk q k + ak z k z k q k (1.5.25)

Tomando el producto interno con q k tenemos

⊤ ⊤ ⊤
q k pk − q k Hk q k = ak (z k q k )2 . (1.5.26)

Por otro lado, usando (1.5.25) podemos escribir (1.5.24) como

(pk − Hk q k )(pk − Hk q k )⊤
Hk+1 = Hk + ,
ak (z k ⊤ q k )2

y, gracias a (1.5.26) obtenemos

(pk − Hk q k )(pk − Hk q k )⊤
Hk+1 = Hk + . (1.5.27)
q k ⊤ (pk − Hk q k )

Hemos determinado que una corrección de rango uno debe satisfacer (1.5.23) para i = k.
Queda por demostrar que, para el caso donde ∇2 f (xk ) es constante, (1.5.23) también se
satisface para i < k. Esto, a su vez, implica que la fórmula recursiva de rango uno (1.5.27)
converge a ∇2 f (xk )−1 después de, como máximo, n pasos.
 45

Teorema I.44
Sea F una matriz simétrica fija y sean los vectores p0 , p1 , p2 , . . . , pk . Notemos los
vectores qi = F pi , i = 0, 1, 2, . . . , k.
Comenzando con cualquier matriz simétrica inicial H0 , se considera:

(pi − Hi q i )(pi − Hi q i )⊤
Hi+1 = Hi + (1.5.28)
q i ⊤ (pi − Hi q i )
Entonces,
pi = Hk+1 q i , para i ≤ k. (1.5.29)

Demostración.

La demostración se hace por inducción. Se puede verificar directamente para k = 0.

Suponga que es verdadero para Hk y i ≤ k − 1. La relación fue verificada anteriormente
para Hk+1 e i = k. Ahora, para i < k, utilizamos la hipótesis inductiva. En efecto,
 ⊤ ⊤

Hk+1 q i = pi + y k pk qi − q k pi .

De la relación
⊤ ⊤ ⊤
q k p i = p k F pi = p k q i ,
de donde se deduce que el segundo término se anula. ■
Sin embargo, las matrices generadas por (1.5.28) no necesariamente son definidas positivas,
lo cual puede ser un problema para generar las direcciones de descenso.
Recordando que

pk = xk+1 − xk , y q k = ∇f (xk+1 ) − ∇f (xk ),

podemos escribir el siguiente algoritmo:

Data: f , ∇f , H0 ∈ Rn×n , x(0) ∈ Rn
Result: xk solución aproximada
k=0
while ∥∇f (xk )∥ > tol do
Calcular dk = −Hk ∇f (xk )
Calcular sk mediante una búsqueda lineal
Actualizar xk+1 ← xk − sk Hk+1 ∇f (xk )
Calcular pk = xk+1 − xk y q k = ∇f (xk+1 ) − ∇f (xk )
(pk − Hk q k )(pk − Hk q k )⊤
Calcular Hk+1 = Hk +
q k ⊤ (pk − Hk q k )
k ←k+1
end
Algorithm 5: Algoritmo de Newton modificado SR1
46

Método de Davidon–Fletcher–Powell
Propuesto por Davidon y luego desarrollado por Fletcher y Powell. Tiene la propiedad de que,
para una función objetivo cuadrática, simultáneamente genera las direcciones del método de
gradiente conjugado mientras construye la inversa de la Hessiana.
En cada paso, la inversa de la Hessiana se actualiza mediante la suma de dos matrices
simétricas de rango uno, y este esquema se denomina, por lo tanto, un procedimiento de
corrección de rango dos. El método también se conoce a menudo como el método de
métrica variable, el nombre originalmente sugerido por Davidon.
El procedimiento es el siguiente: comenzando con cualquier matriz H0 simétrica y definida
positiva, cualquier punto x0 , y con k = 0:
Data: f , ∇f , H0 ∈ Rn×n , x(0) ∈ Rn
Result: xk solución aproximada
k=0
while ∥∇f (xk )∥ > tol do
Calcular dk = −Hk ∇f (xk )
Calcular sk mediante una búsqueda lineal
Actualizar xk+1 ← xk − sk dk
Calcular pk = sk dk y q k = ∇f (xk+1 ) − ∇f (xk )
⊤ ⊤
pk pk Hk q k q k Hk
Calcular Hk+1 = Hk + ⊤ −
pk q k q k ⊤ Hk q k
k ←k+1
end
Algorithm 6: Algoritmo DFP
Una ventaja de este método es que el es quema recursivo
⊤ ⊤
pk pk Hk q k q k Hk
Hk+1 = Hk + − ,
pk ⊤ q k q k ⊤ Hk q k

genera una matriz definida positiva en cada paso.

5.9 Métodos de Broyden

Las fórmulas de actualización para la inversa de la Hessiana consideradas se basan en satis-
facer:
Hk+1 qi = pi , 0 ≤ i ≤ k
que se deriva de la relación:

qi = ∇2 f (xk )pi , 0 ≤ i ≤ k,
que se cumpliría en el caso puramente cuadrático.
Además, es posible actualizar aproximaciones a la Hessiana ∇2 f (xk ) en sí misma, en lugar
de su inversa. Por lo tanto, denotando la k-ésima aproximación de F como Bk , buscaríamos
análogamente satisfacer:
 47

q i = Bk+1 pi , 0 ≤ i ≤ k. (1.5.30)
En la ecuación (1.5.30) q i y pi se intercambian, y H es reemplazada por B.
Análogamente, cualquier fórmula de actualización para B que satisfaga (1.5.30) puede
convertirse mediante el mismo proceso en una fórmula complementaria para actualizar H.
Para ilustrar las fórmulas complementarias, considere la actualización de rango uno, que
es:

(pk − Hk q k )(pk − Hk q k )⊤
Hk+1 = Hk +
q k ⊤ (pk − Hk q k )
La fórmula complementaria correspondiente es:

(q k − B k pk )(q k − B k pk )⊤
Bk+1 = Bk + . (1.5.31)
pk ⊤ (q k − Bk pk )
Del mismo modo, la fórmula de Davidon–Fletcher–Powell (o simplemente DFP) es:
⊤ ⊤
DFP pk pk Hk q k q k Hk
Hk+1 = Hk + − ,
pk ⊤ q k q k ⊤ Hk q k
y su fórmula complementaria es:
⊤ ⊤
qk qk Bk pk pk Bk
Bk+1 = Bk + − .
q k ⊤ pk pk ⊤ Bk pk
Esta última actualización es conoce como aproximación BFGS cuyo nombre viene de las
iniciales de sus desarrolladores (Broyden-Fletcher-Goldfarb-Shanno ).
Otra manera de convertir una fórmula de actualización para H a una para B o viceversa
es tomar la inversa. Si,

Hk+1 qi = pi , 0 ≤ i ≤ k,
entonces

−1
qi = Hk+1 pi , 0 ≤ i ≤ k,
lo que implica que Hk+1
−1
satisface el criterio para una actualización de B(5.9).
Además, y lo más importante, la inversa de una fórmula de rango dos también es una
fórmula de rango dos.
La nueva fórmula se puede encontrar explícitamente mediante dos aplicaciones de la iden-
tidad de inversión general:

−1 A−1 ab⊤ A−1

A + ab⊤ = A−1 − (Sherman-Morrison)

,
1 + b⊤ A−1 a
donde A es una matriz n × n, y a y b son vectores de dimensión n, lo cual es válido siempre
que existan las inversas. (Esto se verifica fácilmente multiplicando por A + ab⊤ ).
48

5.10 Método BFGS

La actualización BFGS para B, al tomar la inversa, produce una actualización correspondi-
ente para H de la forma:
!
k⊤ k ⊤ ⊤ ⊤
q Hk q pk pk pk q k Hk + Hk q k pk
BFGS
Hk+1 = Hk + 1+ − . (1.5.32)
qk ⊤qk pk ⊤ q k q k ⊤ pk

Data: f , ∇f , H0 ∈ Rn×n , x(0) ∈ Rn

Result: xk solución aproximada
k=0
while ∥∇f (xk )∥ > tol do
Calcular dk = −Hk ∇f (xk )
Calcular sk mediante una búsqueda lineal
Actualizar xk+1 ← xk − sk dk
Calcular pk = sk dk y q k = ∇f (xk+1 ) − ∇f
! (xk )
⊤ ⊤ ⊤ ⊤
q k Hk q k pk pk pk q k Hk + Hk q k pk
Calcular Hk+1 = Hk + 1 +
BFGS
−
qk ⊤qk pk ⊤ q k q k ⊤ pk
k ←k+1
end
Algorithm 7: Algoritmo BFGS
Observemos que, tanto las actualizaciones DFP como BFGS, tienen correcciones de rango
dos simétricas que se construyen a partir de los vectores pk y Hk q k . Las combinaciones
ponderadas de estas fórmulas serán, por lo tanto, también simétricas de rango dos. Así, se
pueden construir aproximaciones del tipo:

H ϕ = (1 − ϕ)H DFP + ϕH BFGS , (1.5.33)

donde ϕ es un parámetro que puede tomar cualquier valor real. Claramente, ϕ = 0 y ϕ = 1
producen las actualizaciones DFP y BFGS, respectivamente. La familia de Broyden también
incluye la actualización de rango uno.

Convergencia de los métodos de cuasi-Newton

Los diversos esquemas para generar y usar simultáneamente una aproximación de la inversa
de la Hessiana son difíciles de analizar de manera definitiva. Por lo tanto, en cierta medida,
se debe recurrir al uso de analogías y análisis aproximados para determinar su efectividad.
Sin embargo, los métodos desarrollados anteriormente proporcionan una base para al menos
un análisis preliminar.
En la práctica, los métodos cuasi-Newton generalmente se ejecutan de manera continua,
comenzando con una aproximación inicial y mejorándola sucesivamente a lo largo del proceso
iterativo. Bajo diversas condiciones, aunque algo estrictas, se puede demostrar que este
procedimiento es globalmente convergente. Por otro lado, si los métodos quasi-Newton se
reinician cada n o n+1 pasos restableciendo la Hessiana inversa aproximada a su valor inicial,
 49

entonces la convergencia global está garantizada por la presencia del primer paso de descenso
de cada ciclo (que actúa como un paso separador).

Una mala distribución de valores propios, que surja de esta manera, jugará un papel
dominante siempre que existan factores que tiendan a debilitar su aproximación al método
de gradiente conjugado. Factores comunes de este tipo son los errores de redondeo, búsquedas
de línea inexactas y términos no cuadráticos en la función objetivo. De hecho, se ha observado
con frecuencia, de manera empírica, que el desempeño del método DFP es altamente sensible
a la precisión del algoritmo de búsqueda de línea, al punto de que las propiedades superiores
de convergencia paso a paso solo pueden obtenerse mediante un gasto excesivo de tiempo en
la fase de búsqueda de línea.

Estudiamos la convergencia global de BFGS, con una búsqueda de línea práctica, cuando
se aplica a una función convexa suave desde un punto inicial arbitrario x0 y desde cualquier
aproximación inicial de la Hessiana B0 que sea simétrica y definida positiva. Establecemos
nuestras suposiciones precisas sobre la función objetivo de manera formal:

Assumption I.45
1. La función objetivo f es dos veces continuamente diferenciable.

2. El conjunto de nivel Ω = {x ∈ Rn : f (x) ≤ f (x0 )} es convexo, y existen con-

stantes positivas m y M tales que

3.
m∥z∥2 ≤ z ⊤ ∇2 f (x)z ≤ M ∥z∥2
para todo z ∈ Rn y x ∈ Ω.

Teorema I.46
Sea B0 cualquier matriz inicial simétrica definida positiva, y sea x0 un punto inicial
para el cual se satisface la Suposición 8.1. Entonces, la sucesión {xk } generada por el
Algoritmo BFGS converge al minimizador x∗ de f .

Assumption I.47
La matriz Hessiana ∇2 f (·) es Lipschitz continua en x∗ , es decir,

∥∇2 f (x) − ∇2 f (x∗ )∥ ≤ L∥x − x∗ ∥,

50

Teorema I.48
Supongamos que f es dos veces continuamente diferenciable y que las iteraciones gen-
eradas por el algoritmo BFGS convergen a un minimizador x∗ para el cual, se cumple
la Hipótesis (5.10). Supongamos también que se satisface
X
∥xk − x∗ ∥ < ∞.
k

Entonces, xk converge a x∗ con tasa superlineal.

 Part II

Optimización con restricciones

51
 53

1 Introducción a la optimización con restricciones

En muchas aplicaciones, las variables de decisión representan recursos (e.g. energía, capital,
materia prima, etc.), que no pueden tomar valores negativos y/o tampoco pueden sobrepasar
ciertos valores límites. En otros casos, las variables de decición obedecen a requerimientos:
geométricos, algebraicos o modelos de EDO/EDP, y por tanto, deben satisfacer algun tipo
de ecuación.
Las incorporación restricciones en los problemas de optimización, no solo obedecen a
requerimientos prácticos. Desde el punto de vista matemático, en muchos casos la incorpo-
ración de restricciones pueden facilitar la minimización de ciertas funciones. En otros casos,
sin embargo, pueden complicar la minimización de la función objetivo.
Para un problema de minimización, podemos pensar en las restricciones como “obstáculos”
que impiden alcanzar valores menores de la función objetivo. Y en el momento en que
nos topamos con la restricción podemos pensar en que empujamos ese obstáculo y a esta
acción, le sigue una reacción proporcional, como el principio de acción-reacción en física.
Esta “reacción” proporcional, que se da al empujar el obstáculo, es lo que denominamos
multiplicador de Lagrange. Este caracteriza la dificultad de mover el “obstáculo” dado por la
restricción. Por tanto, conocer información de los multiplicadores de Lagrange es conocer la
naturaleza de las restricciones y el efecto que estas causan al minimizar la función objetivo.
Una de las diferencias más importantes respecto de la optimización sin restricciones es
que, para una función de costo diferenciable, el mínimo no necesariamente satisface que
∇f (x∗ ) = 0.

f (x)
f (x) f (x)
a x∗ b ∗ x∗ = a b
a b=x
x
x x
∇f (x∗ ) > 0
∇f (x∗ ) < 0

∇f (x∗ ) = 0

Figure 0.1: A diferencia de los problemas sin restricciones, el mínimo debe cumplir que
∇f (x∗ )⊤ (x − x∗ ) ≥ 0 para todo x admisible.

Consideramos un problema generale de programación no lineal de la forma:

min f (x)
sujeto a: h1 (x) = 0, g1 (x) ≤ 0,
h2 (x) = 0, g2 (x) ≤ 0,
.. (2.1.1)
.
hm (x) = 0, gp (x) ≤ 0,
x ∈ Ω ⊂ Rn ,
54

donde m ≤ n y las funciones f , hi con i = 1, 2, . . . , m, y gj con j = 1, 2, . . . , p son continuas.

Además, usualmente se asume que poseen derivadas parciales continuas de segundo orden.
Se puede simplificar la notación, introduciendo las funciones vectoriales h = (h1 , h2 , . . . , hm )
y g = (g1 , g2 , . . . , gp ), y reescribimos (2.1.1) equivalentemente como:

min f (x)
sujeto a h(x) = 0, g(x) ≤ 0,
x ∈ Ω.

Un concepto fundamental, que proporciona una gran cantidad de información es el de

restricción activa. Una restricción de desigualdad gi (x) ≤ 0 se dice que es

• activa en un punto factible x si gi (x) = 0,

• inactiva en x si gi (x) < 0.

Por convención, nos referimos a cualquier restricción de igualdad hi (x) = 0 como activa en
cualquier punto factible.
Las restricciones activas en un punto factible x restringen el dominio de factibilidad en
vecindades de x, mientras que las otras restricciones, inactivas, no tienen influencia en vecin-
dades de x.

1.1 Restricciones de igualdad

Un conjunto de restricciones de igualdad en Rn , dadas por:

h1 (x) = 0,
h2 (x) = 0,
..
.
hm (x) = 0,

definen un subconjunto de Rn . Precisamente, estas determinan una hipersuperficie que tiene

una dimensión de n − m si las restricciones son regulares. En lo que sigue, asumimos que las
funciones hi , con i = 1, 2, . . . , m, son de clase C 1 por lo que, la superficie definida por estas,
se dice que es suave.
 55

Definición II.1: Plano tangente

• Una curva en una superficie S es una familia de puntos x(t) ∈ S parametrizada
continuamente por t para a ≤ t ≤ b.

• La curva es diferenciable si ẋ = d
dt
x(t) existe, y es dos veces diferenciable si
ẍ(t) existe.

• Se dice que una curva x(t) pasa por el punto x∗ si x∗ = x(t∗ ) para algún t∗ ,
a ≤ t∗ ≤ b. La derivada de la curva en x∗ se define como ẋ(t∗ ) ∈ Rn .

Ahora, consideremos todas las curvas diferenciables en S que pasan por un punto x∗ .
El plano tangente en x∗ se define como la colección de las derivadas en x∗ de todas
estas curvas diferenciables. El plano tangente es un subespacio de Rn .

Qué relación tiene el plano tangente de una superficie definida por funciones hi con el
gradiente de h = (h1 , . . . , hm ) ?

Idealmente, nos gustaría expresar el plano tangente en términos de las derivadas de las
funciones hi que definen la superficie.

Introducimos el subespacio:

M = {y : h′ (x∗ )y = 0} ⊂ Rm

y analizamos bajo qué condiciones M es igual al plano tangente en x∗ . El concepto clave

para este propósito es el de un punto regular.

Definición II.2: Punto regular

Un punto x∗ que satisface la restricción h(x∗ ) = 0 se dice que es un punto regular de
la restricción si los vectores gradiente ∇h1 (x∗ ), ∇h2 (x∗ ), . . . , ∇hm (x∗ ) son linealmente
independientes.
56

Teorema II.3: Teorema de la función implítica

Sea x0 = (x01 , x02 , . . . , x0n ) un punto en Rn que satisface las siguientes propiedades:

1. Las funciones hi ∈ C p , i = 1, 2, . . . , m, en alguna vecindad de x0 , para algún

p ≥ 1.

2. hi (x0 ) = 0, i = 1, 2, . . . , m.

3. La matriz Jacobiana m × m:
 ∂h1 (x0 ) ∂h1 (x0 ) 
∂x1
··· ∂xm
J(x0 ) =  .. ... ..
. .
 

∂hm (x0 ) ∂hm (x0 )
∂x1
··· ∂xm

es no singular.

Entonces, existe una vecixndad de x̂0 = (x0m+1 , x0m+2 , . . . , x0n ) ∈ Rn−m , tal que, para
x̂ = (xm+1 , xm+2 , . . . , xn ) en esta vecindad, existen funciones ϕi (x̂), i = 1, 2, . . . , m,
tales que:

1. ϕi ∈ C p .

2. x0i = ϕi (x̂0 ), i = 1, 2, . . . , m.

3. hi (ϕ1 (x̂), ϕ2 (x̂), . . . , ϕm (x̂), x̂) = 0, i = 1, 2, . . . , m.

Teorema II.4
Si el punto x∗ de la superficie S definida por h(x) = 0 es regular, el plano tangente es
igual a:

M = {y : h′ (x∗ )y = 0} = Ker(h).

Demostración.

Notemos por T el plano tangente en x∗ . Podemos observar directamente que T ⊆ M ,

independientemente de que x∗ sea regular. Esto se debe a que cualquier curva x(t) que
pase por x∗ en t = t∗ y tenga derivada ẋ(t∗ ) tal que h′ (x∗ )⊤ ẋ(t∗ ) ̸= 0 no estaría en S.
Para demostrar que M ⊆ T , debemos mostrar que si y ∈ M , entonces existe una
curva en S que pasa por x∗ con derivada y. Para construir tal curva, consideramos las
ecuaciones:

h(x∗ + ty + h′ (x∗ )⊤ u(t)) = 0. (2.1.2)

| {z }
=:x(t)
 57

Para un valor fijo de t, consideramos u(t) ∈ Rm como la incógnita. Este es un sistema

no lineal de m ecuaciones y m incógnitas, parametrizado continuamente por t. En t = 0,
existe una solución u(0) = 0. La matriz Jacobiana del sistema con respecto a u en t = 0
corresponde a la matriz de tamaño m × m:

h′ (x∗ )h′ (x∗ )⊤ ,

la cual, es no singular ya que h′ (x∗ ) tiene rango completo gracias a que x∗ es un punto
regular. Por el Teorema de la Función Implícita, existe una solución u(t) diferenciable en
t en alguna intervalo −a ≤ t ≤ a.
La curva x(t) = x∗ +ty+h′ (x∗ )⊤ u(t) es, por construcción, una curva en S. Diferenciando
el sistema (2.1.2) con respecto a t en t = 0, obtenemos:
 
d
0= h(x(t)) = h′ (x∗ )y + h′ (x∗ )h′ (x∗ )⊤ u̇(0).
dt t=0

Por definición de y, tenemos h′ (x∗ )y = 0, y así, concluimos que u̇(0) = 0. Por lo tanto:

ẋ(0) = y + h′ (x∗ )⊤ u̇(0) = y,

y en consecuencia la curva u tiene derivada y en x∗ .

■
Ejemplo :
En R2 , sea h(x1 , x2 ) = x1 . Entonces, h(x) = 0 representa el eje x2 , y cada punto en ese eje
es regular. Si en su lugar tomamos h(x1 , x2 ) = x21 , nuevamente S es el eje x2 , pero ahora
ningún punto en el eje es regular. De hecho, en este caso M = R2 , mientras que el plano
tangente es el eje x2 .
■
Ejemplo :
En R2 , sea h(x1 , x2 ) = x21 +x22 −1. Entonces, h(x) = 0 representa la circunferencia centrada
de radio 1. En este caso toda curva puede ser parametrizada x(t) = (cos(t), sin(t)) donde
t puede variar entre 0 y 2π ■
El análisis de las condiciones necesarias y suficientes, para que un punto sea un extremo
local sujeto a restricciones de igualdad se facilita con la representación del plano tangente.

Empecemos derivando las condiciones necesarias de primer orden.

58

Lema II.5
Sea x∗ un punto regular de las restricciones h(x) = 0 y un punto extremo local (mínimo
o máximo) de f sujeto a estas restricciones.
Entonces, todo y ∈ Rn que satisfaga

h′ (x∗ )y = 0,
entonces, también debe satisfacer

∇f (x∗ )⊤ y = 0.

En otras palabras, el gradiente en x∗ es ortogonal al plano tangente.

Demostración.
Sea y cualquier vector en el plano tangente en x∗ y sea x(t) cualquier curva suave sobre
la superficie {x : h(x) = 0} que pase por x∗ con derivada y en x∗ ; es decir,

• x(0) = x∗ ,

• ẋ(0) = y, y

• h(x(t)) = 0 para −a ≤ t ≤ a, para algún a > 0.

Dado que x∗ es un punto regular, el plano tangente coincide con M = {y : h′ (x∗ )y = 0}.
Entonces, como x∗ es un punto extremo local de f sujeto a restricciones, tenemos
 
d
f (x(t)) = 0,
dt t=0
equivalentemente,
∇f (x∗ )⊤ y = 0.
■

1.2 Condiciones necesarias de primer orden

La noción de punto regular nos permite a establecer las condiciones necesarias de primer
orden en términos de una ecuación, mediante los multiplicadores de Lagrange.

Teorema II.6
Sea x∗ un punto extremo local de f sujeto a las restricciones h(x) = 0. Supongamos
además que x∗ es un punto regular de estas restricciones. Entonces, existe un λ ∈ Rm
tal que

∇f (x∗ )⊤ + λ⊤ h′ (x∗ ) = 0. (2.1.3)

Demostración.
 59

C(A⊤ ) C(A)

Espacio de filas Espacio de columnas

todos los todos los
A⊤ y Ax

dim = r dim = r

⊥ ⊥
x⊤ (A⊤ y = 0) y ⊤ (A⊤ x) = 0

Espacio nulo Espacio nulo

Ax = 0 A⊤ y = 0

ker(A) dim = n − r ker(A⊤ ) dim = n − r

Rn Rn

Figure 0.2: Teorema de la dimensión y relación entre los espacios nulo e imagen

Sea A ∈ Rm×n , notamos por C(A⊤ ) al espacio generado por las columnas de A⊤ . Gracias
a que Ker(A)⊥ ⊆ C(A⊤ ) y al Teorema II.4 se tiene que

T = Ker(h′ (x∗ )).

Del Lema II.5 concluimos que

∇f (x∗ ) ∈ Ker(h′ (x∗ ))⊥ ,

lo cual, a su vez, implica que ∇f (x∗ )⊤ se encuentra en el espacio generado por las filas de
h′ (x∗ ). Por tanto, existen λ̂i , i = 1, . . . , m tales que
m
X
∗
∇f (x ) = λ̂i ∇hi (x∗ ),
i=1

equivalentemente, tomanddo λi = −λ̂i :

m
X
∗ ⊤ ⊤ ′ ∗ ∗ ⊤
∇f (x ) + λ h (x ) = ∇f (x ) − λ̂i ∇hi (x∗ )⊤ = 0
i=1

■
60

Ejemplo :
El resultado anterior también se puede demostrar utilizando la equivalencia de un problema
de programación lineal y su dual. Por ejemplo: Problema Primal:

minimizar cT x
sujeto a Ax = b,
x≥0

Problema Dual:
maximizar yT b
sujeto a yT A ≤ cT
Recuerde que el teorema de dualidad para problemas lineales establece que si alguno
de los problemas anteriores Primal o Dual, tiene una solución óptima finita, entonces el
otro problema también la tiene, y los valores correspondientes de las funciones objetivo
son iguales. Si alguno de los problemas tiene una función objetivo no acotada, el otro
problema no tiene soluciones factibles.
■
Recapitulemos los resultados anteiores para el problema

minf (x)
sujeto a: h(x) = 0

Si x∗ es un mínimo y además es un punto regular, entonces existe λ ∈ Rm tal que se cumple

el siguiente sistema de optimalidad (compuesto por n + m variables y m + n ecuaciones):
(
∇f (x∗ )⊤ + λ⊤ h′ (x∗ ) = 0
h(x∗ ) = 0
Es conveniente introducir el Lagrangiano asociado con el problema con restricciones,
definido a continuación:

Definición II.7: Función Lagrangiana

El Lagrangiano o Función Lagrangiana, se define como L : Rn × Rm → R, dada por

L(x, λ) = f (x) + λ⊤ h(x)

Utilizando el Lagrangiano, ahora las condiciones necesarias de primer orden también

pueden expresarse en la forma:

∇x L(x, λ) = 0 (2.1.4)
∇λ L(x, λ) = 0, (2.1.5)

donde la segunda condición es simplemente una reformulación de las restricciones.

 61

Ejemplo :
Sea Q ∈ Rn×n y A ∈ Rm×n con n ≥ m.
1 ⊤
minimizar x Qx − y ⊤ x + c
2
sujeto a Ax = b

En este caso podemos escribir h(x) = Ax − b y su derivada corresponde a

h′ (x) = A, constante respecto de x.

Por tanto, un punto x es regular para la restricción, si las filas de A son linealmente
independientes; en otras palabras si rank(A) = m. En este caso,

T = M = {y ∈ Rn : Ay = 0} = Ker(A).

Si además x∗ es un punto regular y es un mínimo para f (·) con h(x∗ ) = 0, entonces

existe λ ∈ Rm tal que:

0 = ∇f (x∗ )⊤ + λ⊤ h′ (x∗ ) = x∗ ⊤ Q + y ⊤ + λ⊤ A
lo que es equivalente a: (
Q⊤ x∗ + y + A⊤ λ = 0,
Ax∗ − b = 0,
o, en forma matricial:
Q⊤ A⊤
   ∗  
x −y
= .
A 0 m×m λ b
■
Ejemplo : Entropía máxima
Consideremos la caracterización de distribuciones de probabilidad que ocurren natural-
mente como distribuciones de máxima entropía.
La probabilidad asociadaPan una variable discreta que toma n valores xi es pi , i = 1, . . . , n
(los pi satisfacen pi ≥ 0 y i=1 pi = 1.)
La entropía de tal densidad es
n
X
ε=− pi log(pi ).
i=1

El valor medio de la densidad es

n
X
x i pi .
i=1

Si se conoce (por la situación física) que el valor medio vale m el argumento de máxima
entropía sugiere que la densidad debe ser aquella que resuelva el siguiente problema:
62

n
X
maximizar − pi log(pi )
i=1
n
X
sujeto a pi = 1
i=1
Xn
xi pi = m,
i=1
pi ≥ 0, i = 1, 2, . . . , n.
Suponiendo que las restricciones de no negatividad son inactivas, podemos ignorar la
última condición sobre los pi .
Introduciendo dos multiplicadores de Lagrange, λ y µ, el Lagrangiano es:
n
X Xn Xn
L(p, (λ, µ)) = −pi log pi + λ( pi − 1) + µ( xi pi − m).
i=1 i=1 i=1

Las condiciones necesarias se encuentran inmediatamente como:

− log pi − 1 + λ + µxi = 0, i = 1, 2, . . . , n.
Esto se reduce a:

pi = e(λ−1)+µxi , i = 1, 2, . . . , n.
¿Qué condiciones se debe imponer para que el punto sea regular? ■

1.3 Condiciones de segundo orden

También podemos derivar las condiciones correspondientes de segundo orden para problemas
con restricciones. A lo largo de esta sección, se supone que f, h son de clase C 2 .

Condiciones de optimalidad de segundo Orden

Teorema II.8: Condiciones necesarias de segundo orden

Supongamos que x∗ es un mínimo local de f sujeto a h(x) = 0 y que x∗ es un punto
regular de estas restricciones. Entonces, existe un λ ∈ Rm tal que:

∇f (x∗ )⊤ + λ⊤ h′ (x∗ ) = 0.
Si denotamos por M el plano tangente M = {y : h′ (x∗ )(x∗ )y = 0}, entonces la matriz:
m
X
L(x∗ ) = ∇2 f (x∗ ) + λi ∇2 hi (x∗ )
i=1

es semidefinida positiva en M ; es decir, y L(x∗ )y ≥ 0 para todo y ∈ M .

⊤
 63

Demostración.

Observemos que para toda curva dos veces diferenciable sobre la superficie de restricción
S que pasa por x∗ (con x(0) = x∗ ). Haciendo una expansión de Taylor alrededor de t = 0
tenemos que

f (x(t)) − f (x∗ )
0≤
t
f (x(t)) − f (x(0))
=
t
t t o(t2 )
= ∇f (x∗ )⊤ ẋ(t) + ẋ(t))⊤ ∇2 f (x∗ )ẋ(t) + ∇f (x∗ )⊤ ẍ(t) +
| {z } 2 2 t
≤0

de donde,
t t o(t2 )
0 ≤ ẋ(t))⊤ ∇2 f (x∗ )ẋ(t) + ∇f (x∗ )⊤ ẍ(t) + .
2 2 t
Dividiendo para t > 0 y tomando el límite t → 0 se cumple que:

d2
f (x(t)) = ẋ(0)⊤ ∇2 f (x∗ )ẋ(0) + ∇f (x∗ )⊤ ẍ(0) ≥ 0. (2.1.6)
dt2 t=0

Además, derivando la relación λ⊤ h(x(t)) = 0 dos veces respecto a t, se obtiene:

m
X
λi ẋ(0)⊤ ∇2 hi (x∗ )ẋ(0) + λ⊤ h′ (x∗ )ẍ(0) = 0. (2.1.7)
i=1

Sumando (2.1.6) y (2.1.7), obtenemos :

d2
0≤ f (x(t)) =ẋ(0)T L(x∗ )ẋ(0) + (∇f (x∗ )⊤ + λ⊤ h′ (x∗ ))ẍ(0)
dt2 t=0
=ẋ(0)T L(x∗ )ẋ(0).

Dado que ẋ(0) es arbitrario en M , concluimos el resultado enunciado. ■

Ahora, al igual que en la optimización sin restricciones, un punto que satisface las condi-
ciones necesarias de primer orden, no necesariamente es una soución del problema (2.1.1). El
siguiente resultado provee de un criterio para decidir si tal punto es una solución.
64

Teorema II.9: Condiciones suficientes de segundo orden

Supongamos que existe un punto x∗ que satisface h(x∗ ) = 0, y un λ ∈ Rm tal que:

∇f (x∗ ) + λ⊤ ∇h(x∗ ) = 0.
m
X
Supongamos además que la matriz: L(x ) = ∇ f (x ) +
∗ 2 ∗
λi ∇2 hi (x∗ ), es definida
i=1
positiva en M = {y : ∇h(x∗ )y = 0}, es decir,

y ⊤ L(x∗ )y > 0, ∀y ∈ M, y ̸= 0

Entonces, x∗ es un mínimo local estricto de f sujeto a h(x) = 0.

Demostración.

Por contradicción, su pongamos que x∗ no es un mínimo relativo estricto. Entonces existe

una sucesión de puntos factibles {y k } que convergen a x∗ , tal que para cada k, f (y k ) ≤
f (x∗ ).
Podemos escribir cada y k en la forma y k = x∗ + sk dk , donde dk ∈ Rn , ∥dk ∥ = 1, y
sk > 0 para cada k. Claramente, sk → 0 y la sucesión {dk }, al ser acotada, contiene una
subsucesión convergente a algún d∗ . Sin renombrar a la subsucesión, consideremos que
{dk } converge a d∗ . Además, por factbilidad, tenemos que h(y k ) − h(x∗ ) = 0, por tanto,
dividiendo por sk y pasando al límite k → ∞, vemos que:

h′ (x∗ )d∗ = 0.
Usando la expansión de Taylor para hj y f en x∗ , tenemos para cada j existe ηj entre y k
y x∗ que verifica:

s2k k ⊤ 2
0 = hj (y k ) − hj (x∗ ) = sk ∇hj (x∗ )dk + d ∇ hj (ηj )dk , (2.1.8)
2
y, además
s2k k ⊤ 2
0 ≥ f (yk ) − f (x∗ ) = sk ∇f (x∗ )dk + d ∇ f (η0 )dk , (2.1.9)
2
Multiplicando (2.1.8) por λj y sumando estas a (2.1.9), en vista de la condición necesaria
de primer orden, deducimos que:
( m
)
s2k k ⊤ X
0≥ d ∇2 f (η0 ) + λi ∇2 hi (ηi ) dk ,
2 i=1

lo que conduce a una contradicción cuando k → ∞. ■

Ejemplo :
Considere el problema:
 65

maximizar x 1 x2 + x2 x3 + x1 x3
sujeto a x1 + x2 + x3 = 3.
Observemos que cualquier punto es regular respecto a la restricción. Las condiciones
necesarias se expresan en las ecuaciones:

x2 + x3 + λ = 0,
x1 + x3 + λ = 0,
x1 + x2 + λ = 0,
x1 + x2 + x3 − 3 = 0. (restricción)
que se pueden resolver para las cuatro incógnitas x1 , x2 , x3 , λ. La solución es:

x1 = x2 = x3 = 1, λ = −2.
De las condiciones anteriores de primer orden, la matriz ∇2 f (x) + λ∇2 h(x) en este caso
se convierte en:
 
0 1 1
L = 1 0 1 ,
1 1 0
la cual no es ni definida positiva ni definida negativa. En el subespacio M = {y : y1 + y2 +
y3 = 0}, sin embargo, observamos que:

y ⊤ Ly = y1 (y2 + y3 ) + y2 (y1 + y3 ) + y3 (y1 + y2 ),

= −(y12 + y22 + y32 ),

y por lo tanto, L es definida negativa en M . Por lo tanto, la solución encontrada es un
máximo local.
■

1.4 Valores propios en el plano tangente

Dado cualquier vector y ∈ M , el vector Ly está en Rn pero no necesariamente en M . Si
proyectamos Ly ortogonalmente de regreso a M , el resultado se denomina la restricción de
L a M actuando sobre y.
De esta manera, obtenemos una transformación lineal de M a M . Sin embargo, no tenemos
una representación explícita de la matriz que representa la transformación.
Un vector y ∈ M es un vector propio de LM si existe un número real λ tal que LM y = λy
y λ es un valor propio de LM .
Esto coincide con la definición estándar. En términos de L, vemos que y es un vector
propio de LM si Ly puede escribirse como la suma de λy y un vector ortogonal a M .
Para obtener una representación matricial de LM , es necesario introducir una base en el
subespacio M . Por simplicidad, es mejor introducir una base ortonormal, digamos e1 , e2 , . . . , en−m .
Definimos la matriz E = [e1 e2 · · · en−m ] de tamaño n × (n − m).
66

Entonces, cualquier vector y ∈ M puede escribirse como

n−m
X
y= zi ei = Ez, para algún z ∈ Rn−m
i=1

LEz representa la acción de L sobre dicho vector.

Para proyectar este resultado de regreso en M y expresar el resultado en términos de la
base e1 , e2 , . . . , en−m , simplemente multiplicamos por E ⊤ . Así, E ⊤ LEz es el vector cuyas
componentes dan la representación en términos de la base
La matriz
L|M = E ⊤ LE ∈ Rn−m×n−m
corresponde a la representación matricial de L restringida a M .
Los valores propios de L restringido a M pueden encontrarse determinando los valores
propios de E ⊤ LE y estos valores propios, son independientes de la elección de E.
Así obtenemos la equivalencia

y ⊤ L|M y > 0, ∀y ∈ Rn−m \ {0} ⇔ y ⊤ Ly > 0, ∀y ∈ M \ {0}

Hesianas proyectadas
Si A = h′ (x∗ ) es de rango completo, por tanto x∗ es regular. Entonces AA⊤ ∈ Rm×m es
una matriz invertible. Si y pertenece al plano tangente entonces, dado que AA⊤ z = y tiene
solución, entonces

0 = Ay = Az − Az = A(z − A⊤ (AA⊤ )−1 Az)

por tanto, la anterior ecuación se satisface tomando

y = (I − A⊤ (AA⊤ )A)z = (I − A† A)z

donde A† es la psudoinversa de A es tal que AA† = I ̸= A† A.

Definición II.10
• La proyección sobre el Ker(A) = M es la matriz PA = I − A† A

• La hessiana proyectada L|M = PA⊤ LPA .

Lema II.11
La matriz L (segunda derivada del Lagrangiano) es definida positiva en M si y solo si
la hessiana proyectada L|M es semi-definida positiva en Rn y tiene rango m − n.

Ejemplo :
Consideremos el problema:

extremizar x1 + x22 + x2 x3 + 2x23

 67

1 2
sujeto a (x + x22 + x23 ) = 1.
2 1
Las condiciones necesarias de primer orden son:

1 + λx1 = 0,
2x2 + x3 + λx2 = 0,
x2 + 4x3 + λx3 = 0.
Una solución a este conjunto es fácilmente visible como x1 = 1, x2 = 0, x3 = 0,
λ = −1. Examinemos las condiciones de segundo orden en este punto de solución. La
matriz lagrangiana es:
 
−1 0 0
L =  0 1 1 ,
0 1 3
y el subespacio correspondiente es:

M = {y : y1 = 0}.
En este caso, M es el subespacio generado por los dos últimos vectores base en R3 , y, por
lo tanto, la restricción de L a M puede encontrarse tomando la submatriz correspondiente
de L. Así, en este caso:
 
⊤ 1 1
E LE = .
1 3
observando que A = ∇h(x∗ )⊤ = (1, 0, 0), tenemos:
   
1   0 0 0
PA = I − 0 1 0 0 = 0 1 0 .
0 0 0 1
Entonces:
 
0 0 0
PA LPA = 0 1 1 ,
0 1 3
que es claramente semidefinida positiva y tiene rango 2. ■

1.5 Análisis de sensibilidad

Los multiplicadores de Lagrange asociados a un problema de minimización con restricciones,
tienen una interpretación de costos, similar a los costos asociados con restricciones en la
programación lineal. En el caso no lineal, los multiplicadores están asociados con la solución
particular, y corresponden a costos incrementales o marginales, es decir, costos asociados con
pequeñas variaciones de las restricciones.
68

Consideremos nuevamente el problema

minimizar f (x) sujeto a h(x) = 0,
el cual tiene una solución en el punto x∗ que es un punto regular de las restricciones. Además,
sea λ el vector de multiplicadores de Lagrange correspondiente. Ahora consideremos la familia
de problemas

minimizar f (x) sujeto a h(x) = c, (2.1.10)

donde c ∈ R . Para un valor suficientemente pequeño de c, el problema tendrá una
m

solución x(c) cercano a x(0) = x∗ . Para cada una de estas soluciones existe un valor óptimo
correspondiente f (x(c)), y este valor puede considerarse como una función del lado derecho
de la restrición dado por c.
Los componentes del gradiente de esta función pueden interpretarse como la tasa de cambio
incremental en el valor óptimo respecto de los cambios de la perturbación.
Mostraremos a continuación cómo estos costos están relacionados con los multiplicadores
de Lagrange del problema con c = 0.

Teorema II.12
Sean f y h de clase C 2 . Consideremos la familia de problemas

minimizar f (x) sujeto a h(x) = c. (2.1.11)

Supongamos que para c = 0 existe un mínimo local x∗ que es un punto regular y que,
junto al multiplicador de Lagrange λ, satisfacen las condiciones suficientes de segundo
orden para un mínimo local estricto.
Entonces, para todo c ∈ Rm en una vecindad que contiene a 0, existe un x(c), que
depende continuamente de c, tal que x(0) = x∗ y tal que x(c) es un mínimo local de
(2.1.11). Además,

∇c f (x(c))|c=0 = −λ⊤ . (2.1.12)

Demostración.
Consideremos el sistema de ecuaciones
∇f (x) + λ⊤ h′ (x) = 0, (2.1.13)
h(x) = c. (2.1.14)
Por hipótesis, existe una solución x∗ con multiplicador asociado λ a este sistema cuando
c = 0. La matriz Jacobiana del sistema x∗ es
L(x∗ ) h′ (x∗ )⊤
 
.
h′ (x∗ ) 0
Por hipótesis, x∗ es un punto regular y L(x∗ ) es definida positiva en M . Por tanto, se
deduce que esta matriz es no singular Por lo tanto, por el Teorema de la Función Implícita,
existe una solución x(c), λ(c) para el sistema, la cual es continuamente diferenciable.
 69

Por la regla de la cadena tenemos

∇c f (x(c))|c=0 = ∇x f (x∗ )⊤ Dc x(0).

y
Dc h(x(c))|c=0 = h′ (x∗ )Dc x(0).
En vista de (2.1.14), esta última es igual a la identidad I en Rm , mientras que (2.1.13)
implica que la primera puede escribirse como

∇c f (x(c))|c=0 = −λ⊤ .
■