OPTIMIZACIÓN I - Alephsub0...2 Deﬁniciones y Teoremas c) Si D

OPTIMIZACIÓN I

EJERCICIOS RESUELTOS

Nadie nos arrebatará del paraíso que él creó

Club de Matemática EPN

Más que simple matemática

Viviana Gavilanes y Gabriel Granda

4

Cuadernos de Matemática


Esta página ha sido dejada intencionalmente en blanco.

CUADERNOS DE MATEMÁTICA

CLUB DE MATEMÁTICA EPN

V. GAVILANES Y G. GRANDA

OPTIMIZACIÓN IEJERCICIOS RESUELTOS

Nadie nos arrebatará del paraíso que él creó


Más que simple matemática

Cuaderno de Matemática del Club de Matemática EPN No. 4

OPTIMIZACIÓN I: EJERCICIOS RESUELTOS

Viviana Gavilanes y Gabriel Granda

Revisión Académica: MSc. Kateryn Herrera

Registro de derecho autoral No. La obra no cuenta con registro por el momento

ISBN: La obra no cuenta con ISBN por el momento

Publicado en linea por el proyecto Alephsub0,Quito, Ecuador.

Primera edición: 2020

c© Club de Matemática EPN 2020

Se permite la distribución de la presente obra.

ÍNDICE GENERAL

CAP. 1 DEFINICIONES Y TEOREMAS 1

CAP. 2 INTRODUCCIÓN 7

CAP. 3 FUNDAMENTOS DE ANÁLISIS CONVEXO 25

CAP. 4 CONDICIONES DE OPTIMALIDAD 53

CAP. 5 MÉTODOS DE DESCENSO 59

CAP. 6 MÉTODOS NEWTON Y CUASI-NEWTON 81

CAP. 7 CÓDIGOS EN MATLAB 119

7.0.1 Caso función cuadrática matricial de R4 en R . . . . . . . . . . . . . . . . . . . . 119

7.0.2 EJERCICIO 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

7.0.3 EJERCICIO 6.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

7.0.4 EJERCICIO 6.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

7.0.5 EJERCICIO 6.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

7.0.6 Algoritmo: Paso de Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

III

PREFACIO

La presente obra es una recopilación de ejercicios basados en las clases y evaluaciones de la

materia “Optimización I”, dictada en la carrera de Ingeniería Matemática y Matemática de la

Escuela Politécnica Nacional por el profesor Sergio González durante el semestre 2019-A y por

la profesora Kateryn Herrera durante el semestre 2019-B. La soluciones de los ejercicios fueron

elaboradas por Viviana Gavilanes y Gabriel Granda, alumnos de esta materia en los periodos

antes mencionados.

Este compendio de ejercicios tiene la finalidad de servir como una guía para aquellos estu-

diantes que tomen esta materia. En caso de que el lector encuentre errores puede dirigirlos a

[email protected] o [email protected].

“Optimización 1: Ejercicios” forma parte de la serie “Cuaderno de Matemática del Club de

Matemática EPN”, la cual, recolecta apuntes de clase y ejercicios resueltos generados por estu-

diantes de la Facultad de Ciencias. El Club de Matemática EPN, junto al proyecto Alephsub0 y

la Asociación de Estudiantes de Matemática e Ingeniería Matemática, administra la generación

y publicación en línea de estos trabajos e invita la comunidad de estudiantes que deseen apoyar

a este proyecto a sumarse al mismo.

V

CAPÍTULO 1

DEFINICIONES Y TEOREMAS

TEOREMA 1.1TEOREMA 1.1Sean X ⊆ R

n un convexo abierto y f : X → R una función. Entonces se tiene que f es

continua en X.

TEOREMA 1.2TEOREMA 1.2Sean S1, S2 ⊆ R

n conjuntos convexos no vacíos, tales que S1 ∩ S1 = ∅. Si S1 es un conjunto

acotado, entonces existe un hiperplano H que separa S1 y S2, es decir, existe p ∈ Rnr 0, tal

que

ınfpTx : x ∈ S1 ≥ suppTx : x ∈ S2.

TEOREMA 1.3: Método de CardanoTEOREMA 1.3: Método de CardanoDada la ecuación cúbica

x3 + a1x2 + a2x + a3 = 0,

donde a1, a2 y a3 ∈ R. Se calculan las siguientes cantidades:

Q =3a2 − a2

19

, R =9a1a2 − 27a3 − 2a3

154

,

S1 =3√

R +√

Q3 + R2 y S2 =3√

R−√

Q3 + R2.

En este caso, las tres raíces se pueden calcular como

x1 = S1 + S2 − a13 ,

x2 = − S1+S22 − a1

3 + i√

32 (S1 − S2),

x3 = − S1+S22 − a1

3 − i√

32 (S1 − S2).

Al ser el discriminante D = Q3 + R2, se tiene

a) Si D > 0, entonces una de las raíces es real y dos de ellas son complejas.

b) Si D = 0, entonces todas las raíces son reales y al menos dos son iguales.

1

2 Definiciones y Teoremas

c) Si D < 0, entonces todas las raíces son reales y distintas.

TEOREMA 1.4: Condición necesaria de primer ordenTEOREMA 1.4: Condición necesaria de primer ordenSean f : R

n −→ R una función continuamente diferenciable y x∗ ∈ Rn un mínimo local de

f . Entonces

∇ f (x∗) = 0.

TEOREMA 1.5: Condición suficiente de segundo ordenTEOREMA 1.5: Condición suficiente de segundo orden

Sean f : Rn −→ R una función y x∗ ∈ R

n un punto estacionario de f . Suponga que∇2 f (x∗)

es continua en una vecindad abierta de x∗ y que ∇2 f (x∗) es definida positiva. Entonces x∗

es un mínimo local estricto de f .

TEOREMA 1.6TEOREMA 1.6Si f : R

n −→ R es convexa, entonces cualquier mínimo local x∗ ∈ Rn es también mínimo

global de f . Si además f es diferenciable, entonces todo punto estacionario x∗ es un mínimo

global de f .

TEOREMA 1.7: Fórmula de Sherman-MorrisonTEOREMA 1.7: Fórmula de Sherman-Morrison

Sean A ∈ Rn×n una matriz invertible y u, v ∈ R

n vectores columna. Entonces A + u vT es

invertible si, y sólo si 1 + vT A−1 u 6= 0. En este caso,

(A + u vT)−1 = A−1 − A−1 u vT A−1

1 + vT A−1 u,

donde, u vT es el producto exterior de dos vectores u y v.

DEFINICIÓN 1.1: Regla de WolfeDEFINICIÓN 1.1: Regla de WolfeLa regla de Wolfe es una estrategia de búsqueda lineal, la cual, consiste en verificar las

condiciones

f (xk + αk pk)− f (xk) ≤ γ αk∇ f (xk)T pk y ∇ f (xk + αk pk)

T pk ≥ σ∇ f (xk)T pk,

para k ∈ N, con 0 < γ < σ < 1.

TEOREMA 1.8: Condición de ZoutendijkTEOREMA 1.8: Condición de ZoutendijkConsiderando cualquier iteración dada por

xk+1 = xk + αk pk,

donde pk es la dirección de descenso y αk satisface las condiciones de Wolfe para cada

k ∈ N. Sea f : Rn −→ R acotada por abajo y continuamente diferenciable en un conjunto

3

abierto,

N0 = x ∈ Rn : f (x) ≤ f (x0),

donde x0 ∈ Rn es el punto inicial de la iteración. Suponiendo que el gradiente de la función

f es Lipschitz continua en N0, es decir, que existe L > 0, tal que

‖∇ f (x)−∇ f (x)‖ ≤ L ‖x− x‖ , (1.1)

para cada x, x ∈ N0. Se tiene que

∑k∈N

cos2(θk) ‖∇ fk‖2< +∞. (1.2)

(1.2) es conocida como la condición de Zoutendijk.

TEOREMA 1.9TEOREMA 1.9Sean f : R

n → R una función y x ∈ Rn. Supongamos que ∇ f es continua en una vecindad

Vx de x. Dados γ ∈ ]0, 1[ y p una dirección de descenso de f en x, entonces existe α > 0, tal

que

f (x + αp)− f (x) ≤ γ∇ f (x)T p,

para todo α ∈ [0, α].

TEOREMA 1.10TEOREMA 1.10

Si la matriz A tiene rango completo, entonces AT A es una matriz cuadrada no singular y

simétrica definida positiva.

Demostración (p.26)

TEOREMA 1.11: Teorema de Convergencia Local del Método de NewtonTEOREMA 1.11: Teorema de Convergencia Local del Método de NewtonSean f : R

n −→ R una función dos veces continuamente diferenciable y x∗ ∈ Rn un punto

estacionario con ∇2 f (x) regular. Entonces existe ε > 0, tal que para todo x0 ∈ Bε (x∗) se

verifica que

• Si ηk ≤ η para un η ∈ (0, 1) suficientemente pequeño, entonces las iteraciones están

bien definidas y la sucesión xkk∈N de número reales converge linealmente a x∗.

• La tasa de convergencia es lineal, si lımk→+∞ ηk = 0.

• La tasa de convergencia es cuadrática, si

ηk = σ(‖∇ f (xk)‖),


y ∇2 f es localmente Lipschitz continua.

TEOREMA 1.12: Algoritmo del descenso máximoTEOREMA 1.12: Algoritmo del descenso máximo• Inicialización.- Sea x un punto inicial y ε > 0 un valor de control de fin del algoritmo.

Tomar x1 = x y hacer k = 1.

• Paso Principal.- Si ‖∇ f (xk)‖ < ε, FIN; el punto actual xk se considera una acepta-

ble aproximación al verdadero candidato a mínimo. En caso contrario, tomar dk =

−∇ f (xk), y sea λk la solución del problema

mınλ≥0

f (xk + λ dk),

tomar xk+1 = xk + λk dk, hacer k = k + 1 y repetir el paso principal.

TEOREMA 1.13: Función de perspectivaTEOREMA 1.13: Función de perspectivaSi f es una función convexa, entonces la función de perspectiva de f

g(x, t) = t f( x

t

)

,

es convexa en su dominio, dom(g) =

(x, t) : xt ∈ dom( f ), t > 0

.

TEOREMA 1.14TEOREMA 1.14Sean f : R

n → R una función dos veces continuamente diferenciable y x ∈ Rn un óptimo

local de f . Supongamos que∇2 f es Lipschitz continua en una vecindad Vx de x y que existe

k > 0, tal que

pT∇2 f (x)p ≥ k ‖p‖2 ,

para todo p ∈ Rn. Entonces existe ρ > 0, tal que si ‖xn − x‖ < ρ, entonces

a) Las iteraciones de Newton

xk+1 = xk −[

∇2 f (xk)]−1∇ f (xk),

convergen a x.

b) Existe c > 0, tal que

‖xk+1 − x‖ ≤ c ‖xk − x‖2 .

5

TEOREMA 1.15TEOREMA 1.15

Sean F : Rn → R

n una función continuamente diferenciable y x ∈ Rn tal que F′(x) es

invertible. Supongamos que la sucesión de números reales (xn)n∈Nconverge a x y que xk 6=

x para todo k ∈ N, entonces los siguientes enunciados son equivalentes

1. (xn)n∈Nconverge q−superlinealmente a x y F(x) = 0.

2. ‖(Mk − F′(x)) (xk+1 − xk)‖ = o(‖xk+1 − xk‖), donde,

Mksk = −F(xk) y xk+1 = xk + sk,

para cada k ∈ N.

3. ‖(Mk − F′(xk)) (xk+1 − xk)‖ = o(‖xk+1 − xk‖), donde,

Mksk = −F(xk) y xk+1 = xk + sk,

para cada k ∈ N.


CAPÍTULO 2

INTRODUCCIÓN

EJERCICIO 2.1. Determine los intervalos de α, donde Bα y Eα son matrices definidas positi-

vas, semidefinidas positivas e indefinidas.

Bα =

1 −α 1

α −4 α

1 −α 1

y Eα =

1 α 0 0

α 2 α 0

0 α 2 α

0 0 α 1

.

Solución: Para cada α ∈ R, el determinante de a matriz Bα es

Bα =

∣

∣

∣

∣

∣

∣

∣

∣

∣

1 −α 1

α −4 α

1 −α 1

∣

∣

∣

∣

∣

∣

∣

∣

∣

= −4 + α2 − α(−α + α) + (−α2 + 4) = 0,

con esto, tenemos que la matriz Bα es indefinida para todo α ∈ R.

Por el criterio de Silvester, vamos a calcular el determinante de cada una de las submatrices

de Eα, tenemos que

Eα =

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

1 α 0 0

α 2 α 0

0 α 2 α

0 0 α 1

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

= 1

∣

∣

∣

∣

∣

∣

∣

∣

∣

2 α 0

α 2 α

0 α 1

∣

∣

∣

∣

∣

∣

∣

∣

∣

− α

∣

∣

∣

∣

∣

∣

∣

∣

∣

α 0 0

α 2 α

0 α 1

∣

∣

∣

∣

∣

∣

∣

∣

∣

= α4 − 5α2 + 4,

así, la primera condición es

α4 − 5α2 + 4 ≥ 0,

de donde,

α ∈]−∞,−2] ∪ [−1, 1] ∪ [2,+∞[. (2.1)

7

8 Introducción

Por otro lado, tenemos que∣

∣

∣

∣

∣

∣

∣

∣

∣

1 α 0

−α 2 α

0 α 2

∣

∣

∣

∣

∣

∣

∣

∣

∣

= 4− 3α2,

así, obtenemos que

4− 3α2 ≥ 0,

lo cual, se cumple para

α ∈ [−√

2,√

2]. (2.2)

Finalmente, obtenemos que∣

∣

∣

∣

∣

∣

1 α

α 2

∣

∣

∣

∣

∣

∣

= 2− α2,

con esto, la condición es

2− α2 ≥ 0,

de donde, se sigue que

α ∈[

−2√

33

,2√

33

]

. (2.3)

Combinando (2.1), (2.2) con (2.3), se sigue que

• Eα es definida positiva para todo α ∈]− 1, 1[, y

• Eα es semi-definida positiva para todo α ∈ [−1, 1].

EJERCICIO 2.2. Calcular las derivadas de las siguientes funciones:

a) Sea b ∈ Rn, consideremos la función:

f : Rn −→ R

x 7−→ bTx,

b) Sea A ∈ Rn×n, consideremos la función:

g : Rn −→ R

x 7−→ 12 xT Ax,

9

c) Sea A ∈ Rn×n simétrica, consideremos la función:

h : Rn −→ R

x 7−→ 12 xT Ax.

1. Primer método:

Solución. a) En primer lugar, podemos reescribir a f como

f (x) = [b1, b2, . . . , bn]T · [x1, x2, . . . , xn],

de donde, operando el producto escalar, tenemos que

f (x) = b1 · x1 + b2 · x2 + · · ·+ bnxn. (2.4)

Por otro lado, sabemos que

∂ f

∂x=

∂xTb

∂x=

[

∂xTb

∂x1,

∂xTb

∂x2, . . . ,

∂xTb

∂xn

]

,

luego, combinado la igualdad precedente con (2.4), se sigue que

∂ f

∂x= [b1, b2, . . . , bn] = b.

b) Podemos reescribir g(x) como

g(x) =n

∑j=1

n

∑i=1

aijxixj,

además, sabemos que su derivada se calcula por:

∂g

∂x=

∂xT Ax

∂x=

[

∂xT Ax

∂x1,

∂xT Ax

∂x2, . . . ,

∂xT Ax

∂xn

]

.

Ahora, sea k ∈ N, calculemos la k-ésima derivada. En efecto,

∂g

∂x=

∂

∂xk

(

n

∑j=1

n

∑k=1

aijxixj

)

,

=∂

∂xk

(

x1

n

∑i=1

ai1xi + · · ·+ xk

n

∑i=1

aikxi + · · ·+ xn

n

∑i=1

ainxi

)

,

= x1ak1 + · · ·+(

n

∑i=1

aikxi + xkakk

)

+ · · ·+ xnakn,

10 Introducción

=n

∑j=1

akjxj +n

∑i=1

aikxi,

con esto, tenemos que∂g

∂x=

12(A + AT)x.

c) Ahora, si A es simétrica, entonces AT = A, de donde, por el literal anterior tenemos

que∂h

∂x=

12(A + A)x = Ax.

2. Segundo método.

Sea v ∈ Rn.

Solución. a) Por la definición de derivada de Gâteux, tenemos que

∂ f

∂xv = lım

t→0

f (x + tv)− f (x)

t,

= lımt→0

bT(x + tv)− bT x

t,

= lımt→0

t bT v

t,

= bT v,

de donde,∂ f

∂x= bT .

b) Por la definición de derivada de Gâteux, tenemos que

∂g

∂xv = lım

t→0

g(x + tv)− g(x)

t,

= lımt→0

12

(

(x + tv)T A (x + tv)− xT A x

t

)

,

= lımt→0

12

(

xT A x + t vT A x + t xT A v + t2 vT A v− xT A x

t

)

,

= lımt→0

12(vT A x + xT A v + t vT A v),

=12

xT(AT + A)v,

de donde,∂h

∂x=

12

xT(AT + A) =12(A + AT) x.

11

c) Si A es simétrica, entonces AT = A, de donde, por el literal anterior tenemos que

∂h

∂x= Ax.

EJERCICIO 2.3. Considere la función

f : R2 −→ R

(x, y) 7−→ f (x, y) =

xy(x2−y2)x2+y2 si (x, y) 6= (0, 0),

0 si (x, y) = (0, 0).

a) Calcule ∂ f∂x y ∂ f

∂y para (x, y) 6= (0, 0).

b) Pruebe que∂ f

∂x(0, 0) =

∂ f

∂y(0, 0) = 0. (2.5)

c) Pruebe que∂2 f

∂x ∂y(0, 0) = 1 y

∂2 f

∂y ∂x(0, 0) = −1.

Explique, ¿por qué las derivadas mixtas son diferentes?

Demostración. a) Para v = [x, y] 6= [0, 0], tenemos que

f (x, y) =xy(

x2 − y2)

x2 + y2 .

La derivada parcial de f respecto la variable x, viene dada por

∂ f (v)

∂x=

y[(

x2 − y2 + x(2x)) (

x2 + y2)]− xy(

x2 + y2) 2x

(x2 − y2)2 ,

=y(

3x2 − y2) (x2 + y2)− 2x2y(

x2 + y2)

(x2 − y2)2 ,

es decir, tenemos que

∂ f (v)

∂x=

y(

3x2 − y2) (x2 + y2)− 2x2y(

x2 + y2)

(x2 − y2)2 .

Por otro lado, tenemos que

∂ f (v)

∂y=

x[(

x2 − y2)− 2y2] (x2 + y2)− xy(

x2 − y2) 2y

(x2y2),

12 Introducción

=x(x2 − 3y2)

(

x2 + y2)− 2xy2 (x2y2)

(x2 + y2)2 ,

es decir,∂ f (v)

∂y=

x(x2 − 3y2)(

x2 + y2)− 2xy2 (x2y2)

(x2 + y2)2 .

b) Sean v = (x, y) y v0 = (0, 0), por la definición de derivada direccional de f con respecto a

x en v0, tenemos que

∂ f (vo)

∂x= lım

t→0

f (v0 + t (1, 0))− f (v0)

t= lım

t→0

f (t, 0)− f (0, 0)t

,

= lımt→0

1t

(

t × 0(t2 − 0)t2

)

= 0,

pues f (0, 0) = 0. Nuevamente, por la definición de derivada direccional de f con respecto

a y en v0, obtenemos

∂ f (vo)

∂y= lım

t→0

f (v0 + t (0, 1))− f (v0)

t= lım

t→0

f (0, t)− f (0, 0)t

,

= lımt→0

1t

(

0 × t(−t2)

t2

)

= 0,

dado que f (0, 0) = 0. Por lo tanto, (2.5) se verifica.

c) Sean v = (x, y) y v0 = (0, 0), por la definición de derivada direccional de∂ f

∂ycon respecto

a x en v0, tenemos que

∂2 f (v0)

∂x∂y=

∂

∂x

(

∂ f

∂y(v0)

)

= lımt→0

1t

(

∂

∂yf (v0 + t(1, 0))− ∂

∂yf (v0)

)

= lımt→0

1t

(

∂

∂yf ((t, 0))

)

= lımt→0

1t

(

t5 − 4 t2 0− t 0(t2 + 0)2

)

= lımt→0

1 = 1,

pues por el literal b), ∂∂y f (v0) = 0.Análogamente, por la definición de derivada direccional

de∂ f

∂xcon respecto a y en v0, tenemos que

∂2 f (vo)

∂y∂x=

∂

∂y

(

∂ f (vo)

∂x

)

= lımt→0

1t

(

∂

∂xf (v0 + t(0, 1))− ∂

∂xf (v0)

)

,

= lımt→0

1t

(

∂

∂xf ((0, t))

)

,

= lımt→0

1t

(

0 (t) + 4(0)t3 − t5

(t2)2

)

= lımt→0

(−1) = −1.

13

Las derivadas mixtas son diferentes, pues v0 es un punto de discontinuidad de f por lo que

f no es diferenciable en v0, esto implica que la matriz Hessiana obtenida no es simétrica

en v0 y por lo tanto∂2 f (0, 0)

∂y∂x6= ∂2 f (0, 0)

∂x∂y.

EJERCICIO 2.4. Obtenga y clasifique los puntos críticos de las siguientes funciones:

1)f : R

2 −→ R

(x, y) 7−→ x4 + x2y + y2,

2)f : R

2 −→ R

(x, y) 7−→ xy exp(x + 2y),

3)f : R

2 −→ R

(x, y) 7−→ 4x+

9y+ x + y + 1.

Solución: 1) Por definición de gradiente de f , tenemos que

∇ f (x, y) = [4x3 + 2xy, x2 + 2y],

de donde,

4x3 + 2xy = 0,

x2 + 2y = 0.

Ahora, resolviendo el sistema obtenemos que

x(4x2 + 2y) = 0,

así,

x = 0 o 4x2 + 2y = 0,

luego, consideremos dos casos:

a) Si x = 0, entonces junto con la segunda ecuación, tenemos que

02 + 2y = 0,

es decir,

y = 0,

14 Introducción

con esto, el punto crítico es v∗1 = (0, 0).

Ahora, vamos a determinar las derivadas de segundo orden, en efecto,

∂2 f

∂x2 = 12x2 + 2y y∂2 f

∂y2 = 2,

además, las derivadas parciales mixtas son

∂2 f

∂y∂x=

∂2 f

∂x∂y= 2x.

Con esto, la matriz Hessiana es:

H(x, y) =

12x2 + 2y 2x

2x 2

,

de donde,

H(0, 0) =

0 0

0 2

,

así, el determinante de la matriz es:

H(0, 0) =

∣

∣

∣

∣

∣

∣

0 0

0 2

∣

∣

∣

∣

∣

∣

= 0,

por lo tanto, no se puede decir nada sobre el punto crítico.

b) Por otro lado, si 4x2 + 2y = 0, tenemos que

−8y + 4y = 0,

de donde,

x = 0 y y = 0,

así, v∗2 = (0, 0).

Con esto, el punto crítico es v∗ = (0, 0).

2) Nuevamente, vamos a calcular el gradiente de f ,

∇ f (x, y) = [y exp(x + 2y)(1 + x), x exp(x + 2y)(1 + 2y)] ,

15

de donde,

y exp(x + 2y)(1 + x) = 0,

x exp(x + 2y)(1 + 2y) = 0.

Ahora, sabemos que et> 0 para todo t ∈ R. Así, tenemos que

y(1 + x) = 0 y x(1 + 2y) = 0.

Tenemos los siguientes casos:

– Si x = 0, entonces y = 0, de donde,

v∗1 = [0, 0].

– Por otro lado, si x = −1, entonces y = −12

, con lo cual,

v∗2 =

[

−1,−12

]

.

Ahora, vamos a determinar la matriz Hessiana, para lo cual, debemos calcular las deriva-

das parciales de segundo orden,

∂2 f

∂x2 = y exp(x + 2y)(2 + x) y∂2 f

∂y2 = 4x exp(x + 2y)(1 + y),

por otro lado, las derivadas parciales mixtas vienen dadas por:

∂2 f

∂y∂x=

∂2 f

∂x∂y= (1 + x)(1 + 2y) exp(x + 2y).


H(x, y) =

y exp(x + 2y)(2 + x) (1 + x)(1 + 2y) exp(x + 2y)

(1 + x)(1 + 2y) exp(x + 2y) 4x exp(x + 2y)(1 + y)

,

de donde, para v∗1 = [0, 0], tenemos que

H(0, 0) =

0 1

1 0

,

16 Introducción

de donde, el determinante es:

H(0, 0) =

∣

∣

∣

∣

∣

∣

0 1

1 0

∣

∣

∣

∣

∣

∣

= −1 < 0,

de donde, v∗1 = (0, 0) es un punto de silla de f .

Por otro, lado para v2 =(

−1,− 12

)

, se tiene que

H(−1,− 12 ) =

− 12 exp(−2) 0

0 −2 exp(−2)

,

luego, el determinante es

H(−1,− 12 ) =

∣

∣

∣

∣

∣

∣

− 12 exp(−2) 0

0 −2 exp(−2)

∣

∣

∣

∣

∣

∣

= exp(−2) > 0,

además, tenemos que∂2 f

∂x2

(

−1,− 12

)

= −12

exp(−2) < 0,

de donde, v∗2 =

[

−1,−12

]

es un máximo local de f .

3) Tenemos que el gradiente de f es

∇ f (x, y) =

[

− 4x2 + 1,− 9

y2 + 1]

,

de donde, tenemos el sistema

− 4x2 + 1 = 0,

− 9y2 + 1 = 0.

Luego, tenemos que

−4 + x2 = 0 y − 9 + y2 = 0,

para x ∈ R r 0, de donde,

x = ±2 y y = ±3.

Así, los puntos críticos son:

v∗1 = (2, 3), v∗2 = (−2,−3), v∗3 = (2,−3) y v∗4 = (−2, 3).

17

Ahora, vamos a calcular las derivadas parciales

∂2 f

∂x2 =8x3 ,

∂2 f

∂y2 =18y3 y

∂2 f

∂x∂y=

∂2 f

∂y∂x= 0.


H(x, y) =

8x3 0

0 18y3

.

Sin pérdida de generalidad, consideremos los puntos críticos v1 = (2, 3) y v3 = (2,−3),

así, tenemos que

– Si v1 = (2, 3), entonces la matriz Hessiana es:

H(x, y) =

1 0

0 23

de donde, el determinante de la función es:

H(x, y) =

∣

∣

∣

∣

∣

∣

1 0

0 23

∣

∣

∣

∣

∣

∣

=23> 0,

por otro lado, tenemos que∂2 f

∂x2 (2, 3) = 1 > 0, con esto, concluimos que

v∗1 = (2, 3),

es un punto mínimo local de f .

– Si v1 = (−2, 3), entonces la matriz Hessiana es:

H(x, y) =

−1 0

0 23

de donde, el determinante de la función es:

H(x, y) =

−1 0

0 23

= −23< 0,

con esto, concluimos que

v∗3 = [−2, 3],

no es un punto mínimo de f .

18 Introducción

EJERCICIO 2.5. Sean A ∈ Rn×n una matriz simétrica, b ∈ R

n y c ∈ R. Considere:

f : Rn −→ R

x 7−→ f (x) = xT A x + 2 bT x + c.

Probar que:

a) Si A es semi-definida positiva, entonces

f es acotada por abajo en Rn si, y sólo si b ∈ z ∈ R

n : ∃y ∈ Rn tal que z = A y

b) x∗ ∈ Rn es un punto estacionario de f si, y sólo si Ax∗ = −b.

c) Si A es semi-definida positiva, entonces x∗ ∈ R es un mínimo global de f si, y sólo si

Ax∗ = −b.

d) Considere A definida positiva, entonces x∗ = −A−1 b es un mínimo global estricto de

f .

Demostración. a) Sea A una matriz simétrica semi-definida positiva.

Para la primera implicación, supongamos que f es acotada por abajo en Rn, entonces existe

M ∈ R tal que

M ≤ f (x),

es decir, existe xnn∈N una sucesión minimizante de número reales, tal que

lımn→+∞

f (xn) = ınfx∈Rn

f (x) = M,

así, por la definición de mínimo, se sigue que

lımn→+∞

∇ f (xn) = 0.

Ahora, el gradiente de f es

∇ f (x) = 2xT A + 2 bT ,

de donde,

∇ f (x) = 0⇒ xT A = −bT ,

19

lo cual, se cumple si, y sólo si existe y ∈ Rn, tal que yT A = −bT , es decir, si

b ∈ z ∈ Rn : ∃y ∈ R

n, tal que z = Ay.

Recíprocamente, supongamos que b ∈ z ∈ Rn : ∃y ∈ R

n, tal que z = Ay. Vamos a

probar que f es acotada por abajo en Rn, si tomamos x∗ = −y, tal que Ay = b, entonces

∇ f (−y) = 0,

es decir, x∗ es un mínimo local de f . Ahora, como f es diferenciable, por el Teorema 1.6, se

sigue que x∗ es un mínimo global, es decir,

f (x∗) ≤ f (x),

para todo x ∈ Rn. Luego, tomando M = f (x∗) se tiene que

M ≤ f (x),

para todo x ∈ Rn. Por lo tanto, hemos probado que f es acotada inferiormente.

b) Supongamos que x es un punto estacionario de f . Vamos a verificar que Ax = −b. Note-

mos que

∇ f (x) = 0,

implica que

2xT A + 2bT = 0,

de donde, es claro que Ax = −b.

Recíprocamente, supongamos que Ax = −b, vamos a probar que x es un punto estaciona-

rio de f . En efecto, se tiene que

∇ f (x) = 2xT A + 2bT = 2((A x)T + bT) = 2(−bT + bT) = 0.

c) Supongamos que la matriz A es semi-definida positiva.

Para la primera implicación, se procede de forma análoga como en la primera implicación

del literal a).

Para la otra implicación, supongamos que Ax = −b, vamos a probar que x es un mínimo

global de f . En efecto, al calcular la Hessiana de f , obtenemos que ∇2 f (x) = A para todo

20 Introducción

x ∈ Rn, de donde, como A 0, colegimos que f es convexa. Además, notemos que x es

un punto estacionario de f , pues∇ f (x) = 0 y como f es diferenciable, por el Teorema 1.6,

se tiene que x es un mínimo global.

d) Supongamos que A ≻ 0, como ∇2 f (x) = A, por el teorema de la caracterización, se sigue

que f es estrictamente convexa, así, todo punto estacionario es un mínimo global estricto

de f . Ahora, al evaluar x∗ = −A−1b en el gradiente de f , se tiene que ∇ f (x∗) = 0. En

efecto,

∇ f (−A−1b) = 2(−A−1b)T A + 2bT = −2bT A−1 A + 2bT = −2bT + 2bT = 0,

de donde, tenemos que x es un punto estacionario. Por lo mencionado anteriormente, he-

mos probado que x es un mínimo global estricto de f .

EJERCICIO 2.6. Sean A ∈ Rn×n y b ∈ R

m, donde m > n y rank(A) = n. Pruebe que x∗ ∈ Rn

es solución del problema

mınx∈Rn

f (x) :=12‖Ax− b‖2

2 ,

si x∗ es solución del sistema AT A x = AT b. ¿Es necesaria la condición dada sobre el rango

de la matriz A para tener unicidad de soluciones?

Demostración. Primero, si tenemos la función

g(x) = ‖x‖22 =

(

n

∑k=1

x2k

) 12

2

=n

∑k=1

x2k ,

entonces, su gradiente es∂

∂xjg(x) =

∂

∂xk

n

∑k=1

x2k =

n

∑k=1

∂

∂xjx2

k ,

como

∂

∂xjx2

k =

0 si j 6= k,

2 xj si j = k.

tenemos que∂

∂xjg(x) = 2 xj,

por lo tanto, se sigue que

∇g(x) = 2 x.

21

Si calculamos ∇ f (x) para cualquier x ∈ Rn, tenemos que

∇ f (x) = AT(A x− b) = 0.

Si ∇ f (x) = 0, se sigue que

AT(A − b) = 0⇒ AT A x = AT b,

por lo tanto, x∗ es solución del sistema de ecuaciones lineales AT A x = AT b.

Sí es necesario que la matriz A sea de rango completo, pues por el Teorema 1.10, tenemos

que AT A es una matriz simétrica definida positiva y por lo tanto invertible. Así, la siguiente

solución es única

x∗ = (AT A)−1 AT b

y, además, está bien definida.


f : R2 −→ R

(x, y) 7−→ f (x, y) = (x2 + y− 11)2 + (x + y2 − 7)2.

a) Encuentre todos los puntos estacionarios de f .

b) Determine, ¿qué puntos estacionarios son mínimos de la función f ?

c) ¿Puede determinar cuáles de estos mínimos son globales y cuáles locales?

Demostración. a) Por la definición de punto estacionario, vamos a buscar v = (x, y) ∈ R2, tal

que

∇ f (v) = 0.

Al calcular el gradiente de f en v, tenemos que

∇ f (v) = [4x(x2 + y− 11) + 2(x + y2 − 7), 2(x2 + y− 11) + 4y(x + y2 − 7)] = [0, 0],

de donde, obtenemos el sistema de ecuaciones:

4x(x2 + y− 11) + 2(x + y2 − 7) = 0,

2(x2 + y− 11) + 4y(x + y2 − 7) = 0.(2.6)

22 Introducción

Para encontrar los puntos que resuelven al sistema (2.6), tenemos que encontrar los puntos

que satisfacen

x2 + y− 11 = 0 y x + y2 − 7 = 0,

mediante el método de sustitución, se sigue que

x4 − 22 x2 + x + 114 = 0 y y2 = (11− x2)2.

Aplicando Ruffini a la primera ecuación, tenemos que

1 0 − 22 1 114

3 3 9 − 39 − 114

1 3 − 13 − 38 0

de donde, obtenemos

P1 = [3, 2] y (x− 3)(x3 + 3x2 − 13x− 38) = 0,

para resolver esta ecuación cúbica, aplicamos el Método de Cardano (ver Teorema 1.3) y

obtenemos tres raíces reales, de donde, encontramos los siguientes puntos

* P2 ≈ [−3.78,−3.28],

* P3 ≈ [−2.81, 3.13],

* P4 ≈ [3.58,−1.85].

Por lo tanto, la función tiene cuatro puntos estacionarios.

b) Para verificar qué puntos Pi, donde i ∈ 1, 2, 3, 4 son mínimos de la funcion f usaremos el

Teorema 1.5 . Notemos que f es continua e infinitamente diferenciable, pues está expresada

como suma de polinomios. Al calcular la Hessiana de f en v, obtenemos

∇2 f (v) =

∂2 f

∂x2∂2 f

∂x∂y∂2 f

∂y∂x

∂2 f

∂y2

=

12x2 + 4y− 42 4x + 4y

4y + 4x 12y2 + 4x− 26

.

Al evaluar la Hessiana en los puntos hallados en a), tenemos que

∇2 f (P1) =

74 20

20 34

, ∇2 f (P2) ≈

116.34 −28.24

−28.24 87.98

,

23

∇2 f (P3) ≈

65.27 1.28

1.28 80.32

y ∇2 f (P4) ≈

104.40 6.92

6.92 29.39

.

Dado que las matrices son simétricas, por el criterio de Sylvester, podemos concluir que

∇2 f (Pi) ≻ 0, i.e., la Hessiana es definida positiva para cada i ∈ 1, . . . , 4. Finalmente, por

el Teorema (1.5) se sigue que los cuatro puntos estacionarios son mínimos locales estrictos

de f . Gráficamente tenemos que

c) Al evaluar la función f en los puntos obtenidos en a), tenemos que

f (Pi) = 0,

para cada i ∈ 1, . . . , 4. Por lo tanto, los cuatro mínimos estrictos son mínimos globales.

24 Introducción

CAPÍTULO 3

FUNDAMENTOS DE ANÁLISIS CONVEXO

EJERCICIO 3.1. Sean a, b ∈ R2 y γ ∈ [0, 1], se define el Pétalo de Penot como el conjunto:

Pγ(a, b) := x ∈ R2 : γ ‖a− x‖+ ‖x− b‖ ≤ ‖b− a‖.

Pruebe que este conjunto es convexo para todo a, b ∈ R2 y γ ∈ [0, 1].

Demostración. Sean a, b ∈ R2, γ ∈ [0, 1] , x, y ∈ Pγ(a, b) y λ ∈ [0, 1], vamos a demostrar que

Pγ(a, b) es un conjunto convexo; es decir, debemos probar que

γ ‖a− [λx + (1− λ)y]‖+ ‖λx + (1− λ)y− b‖ ≤ ‖b− a‖ .

Como x, y ∈ Pγ(a, b), por definición se sigue que

γ ‖a− x‖+ ‖x− b‖ ≤ ‖b− a‖ y γ ‖a− y‖+ ‖y− b‖ ≤ ‖b− a‖ . (3.1)

Definamos c := γ ‖a− [λx + (1− λ)y]‖+ ‖λx + (1− λ)y− b‖, tenemos que

c = γ ‖a− λx + λy− y‖+ ‖λx + y− λy− b‖ ,

= γ ‖λa + (1− λ)a− λx− (1− λ)y‖+ ‖λx + (1− λ)y− λ− (1− λ)b‖ ,

de donde, por la desigualdad triangular y (3.1), se tiene que

c ≤ γ[λ ‖a− x‖+ (1− λ) ‖a− y‖] + [λ ‖x− b‖+ (1− λ) ‖y− b‖],

= λ[(γ ‖a− x‖+ ‖x− b‖)] + (1− λ)[(γ ‖a− y‖+ ‖y− b‖)],

≤ λ ‖b− a‖+ (1− λ) ‖b− a‖ ,

= ‖b− a‖ .

Con esto, hemos probado que Pγ(a, b) es un conjunto convexo para todo a, b ∈ R y todo

25

26 Fundamentos de Análisis Convexo

γ ∈ [0, 1].

EJERCICIO 3.2. Sean C1, C2 conjuntos convexos en Rn, tales que int(C1) 6= ∅ y

int(C1) ∩ C2 = ∅. Pruebe que existe un hiperplano que separa C1 y C2.

Demostración. Consideremos el conjunto:

C := int(C1)− C2 = c1 − c2 : c1 ∈ C1 y c2 ∈ C2,

donde C es un conjunto no vacío, debido a que C1 y C2 son no vacíos, además C es un conjunto

convexo.

Por otro lado, tenemos que 0 /∈ C, pues C1 y C2 son conjuntos disjuntos. Ahora, por el Coro-

lario 1.2 aplicado a C y 0 /∈ C, tenemos que existe un hiperplano que separa a int (C1) y C2 es

decir, existe p ∈ Rnr 0, tal que

pTx1 ≤ pTx2,

para todo x1 ∈ int (C1) ⊆ C1 y todo x2 ∈ C2. Con esto, hemos probado que

suppTx : x ∈ C1 ≤ ınfpTx : x ∈ C2.

EJERCICIO 3.3. Sea B un conjunto convexo y compacto en Rn. Pruebe que el hiperplano de

soporte de B contiene al menos un punto extremo de B.

Demostración. Sea x ∈ ∂(B). Consideremos el hiperplano de soporte de B en x definido por

H = x ∈ Rn : pT(x− x) = 0. (3.2)

como B es compacto en Rn, es decir, es cerrado y acotado, tenemos que

∂(B) ⊆ B,

de donde, x ∈ B. Así, junto con (3.2), obtenemos que

H ∩ B 6= ∅,

además, H ∩ B es un conjunto convexo, debido a que H y B son conjuntos convexos y la inter-

sección de conjuntos convexos es un conjunto convexo. Ahora, tomemos z ∈ H ∩ B un punto

extremo, vamos a demostrar que z también es un punto extremo de B, procederemos por reduc-

27

ción al absurdo, supongamos que z no es un punto extremo de B, así,

z = λa + (1− λ)b,

donde a, b ∈ H y a, b /∈ B. Como z ∈ H, por definición del hiperplano H, se sigue que

pT(z− x) = 0. (3.3)

Por otro lado, por definición de hiperplano de soporte, sabemos que B está contenido en uno

de los subespacios que genera H, sin pérdida de generalidad, supongamos que

B ⊆ H−,

luego, para todo x ∈ H ∩ BC, obtenemos que

pT(x− x) > 0,

de donde, para a, b ∈ H ∩ BC, se sigue que

pT(a− x) > 0 y pT(b− x) > 0,

es decir,

pTa > pTx y pTb > pTx. (3.4)

De (3.3) tenemos que

pT(λa + (1− λ)b− x) = λpTa + (1− λ)b− pTx,

luego, combinando la igualdad precedente con (3.4), obtenemos que

pT(λa + (1− λ)b− x) > λpTx + (1− λ)x− pTx = 0,

con esto, tenemos que

pT(z− x) > 0, (3.5)

por la tricotomía de los números reales, (3.3) y (3.5) implican una contradicción. Por lo tanto,

z ∈ Rn es un punto extremo de B.


EJERCICIO 3.4. Sean A y B conjuntos no vacíos en Rn. Demuestre que:

conv(A + B) = conv(A) + conv(B).

Demostración. Sabemos que A ⊆ conv(A) y B ⊆ conv(B), así, tenemos que

A + B ⊆ conv(A) + conv(B),

de donde, puesto que conv(A + B) es el conjunto convexo más pequeño que contiene a A + B,

se sigue que

conv(A + B) ⊆ conv(A) + conv(B). (3.6)

Para la otra contenencia, tomemos x ∈ conv(A) + conv(B) y vamos a demostrar que

x ∈ conv(A + B), tenemos que

x = a + b,

con a ∈ conv(A) y b ∈ conv(B), de donde, por la definición de envolvente convexa, tenemos que

a =n

∑i=1

αiyi y b =k

∑i=1

βizi,

donde y1, . . . , yn ∈ A, z1, . . . , zk ∈ B y además,

n

∑i=1

αi =k

∑j=1

βi = 1,

luego, obtenemos que

x =n

∑i=1

αiyi +k

∑i=1

βizi,

=

(

k

∑j=1

β j

)(

n

∑i=1

αiyi

)

+

(

n

∑i=1

αi

)(

k

∑j=1

β jzj

)

,

=n

∑i=1

k

∑j=1

αiβ j(xi + yj),

donde,n

∑i=1

k

∑j=1

αiβ j =

(

n

∑i=1

α1

)(

k

∑j=1

β j

)

= 1,

es decir, hemos probado que x se escribe como combinación convexa de elementos de S + T, por

29

lo tanto,

conv(A) + conv(B) ⊆ conv(A + B). (3.7)

Combinando (3.6) y (3.7), se sigue que

conv(A + B) = conv(A) + conv(B).


f : R −→ R

x 7−→ f (x) = exp(−x).

a) Calcule ınfx∈R

f (x).

b) Proporcione un ejemplo de sucesión minimizante.

c) Pruebe que ninguna sucesión minimizante para f es convergente.

Demostración. a) Notemos que

f (x) = exp(−x) > 0,

para todo x ∈ R. Así, tenemos que 0 es una cota inferior del conjunto

x ∈ R : f (x) = exp(x),

por lo tanto, vamos a demostrar que

ınfx∈R

f (x) = 0,

por reducción al absurdo, supongamos que existe una cota superior más grande que 0, es

decir,

0 < t < exp−x,

de donde, dado que la función logaritmo es creciente, se sigue

ln(t) < −x,

lo cual, es una contracción, por lo tanto, podemos concluir que

ınfx∈R

f (x) = 0.


b) Consideremos la sucesión (n)n∈N, tenemos que

lımn→+∞

exp(−n) = lımn→+∞

1exp(n)

= 0,

con esto, se tiene que la sucesión (n)n∈Nes una sucesión minimizante.

c) Por reducción al absurdo, supongamos que existe una sucesión minimizante para f con-

vergente, es decir, existe (xn)n∈Nuna sucesión de números reales y l ∈ R tales que

l = lımn→+∞

xn.

Por otro lado, como (xn)n∈Nes una sucesión minimizante, sabemos que

0 = lımn→+∞

exp(−xn) = exp(

− lımn→+∞

xn

)

,

de donde, obtenemos que

exp(−l) = 0,

lo cual, contradice el hecho de que

exp(x) > 0,

para todo x ∈ R.

Por lo tanto, podemos concluir que ninguna sucesión minimizante para f es convergente.

TEOREMA 3.1TEOREMA 3.1Sean S ⊆ R

n un conjunto convexo y abierto y f : S → R dos veces continuamente diferen-

ciable. Si la matriz Hessiana es definida positiva para todo x ∈ S, entonces la función f es

estrictamente convexa. Pruebe que el recíproco no es cierto.

Demostración. Consideremos la función:

f : R −→ R

x 7−→ x4,

gráficamente, tenemos que

31

0 1 2 3 4−1−2−3−4

0

−1

1

2

3

4

x

y

Ahora, notemos que f ”(x) = 12x2 ≥ 0, para todo x ∈ R, es decir, su matriz Hessiana es semi-

definida positiva, y sin embargo, f es una función estrictamente convexa, en efecto, sean x, y ∈ R

y λ ∈ ]0, 1[, vamos a demostrar que

f (λx + (1− λ)y) < λ f (x) + (1− λ) f (y).

Usando el hecho de que g(x) = x2 es estrictamente convexa, vamos a deducir el resultado,

(λx + (1− λ)y)4 =(

(λx + (1− λ)y)2)2

<

(

λx2 + (1− λ)y2)2

< λ(

x2)2

+ (1− λ)(

y2)2

= λx4 + (1− λ)y4.

EJERCICIO 3.6. Determinar cuál de las siguientes funciones son convexas, estrictamente

convexas, uniformemente convexas o cóncavas:

a) f1(x) = exp(x),

b) f2(x) = x2,

c) f3 = mın1− x2, 0,

d) f4(x) = max|x1|, |x2|,

e) f5(x) = ‖x‖ (norma euclidiana),

f) f6(x) =1x

∫ x0 F(t) dt, donde F es una función convexa.


Solución: a) Usando la caracterización de funciones convexas, basta con demostrar que la ma-

triz Hessiana de f1 es definida positiva, en efecto, tenemos que

f ′′1 (x) = exp(x) > 0,

para todo x ∈ R. Con esto, hemos probado que f1(x) es una función estrictamente convexa.

b) De igual forma, puesto que

f ′′2 (x) = 2 > 0,

para todo x ∈ R, se sigue que f2 es una función estrictamente convexa.

Gráficamente, se tiene que

0 1 2 3 4−1−2−3−4

0

−1

1

2

3

4

x

y

c) Reescribiendo la función f3, se tiene que

f3 : R −→ R

x 7−→

0 si − 1 ≤ x ≤ 1,

1− x2 si x < −1 o x > 1.

Ahora, al calcular la segunda derivada, obtenemos

f ′′3 (x) =

0 si − 1 ≤ x ≤ 1,

−2 si x < −1 o x > 1.

Con esto, tenemos que para todo x ∈ R

f ′′3 (x) ≤ 0,

por lo tanto, f3 es cóncava.

33

d) Sean x, y ∈ R2 y λ ∈ [0, 1], vamos a demostrar que f4 es una función convexa, es decir,

debemos probar que

f4(λx + (1− λ)y) ≤ λ f4(x) + (1− λ) f4(y). (3.8)

Notemos que

max1≤i≤2

|λxi + (1− λ)yi| ≤ max1≤i≤2

|λ|xi|+ (1− λ)|yi| ≤ λ max1≤i≤2

|xi|+ (1− λ) max1≤i≤2

|yi|,

para todo i ∈ 1, 2, de donde, con esto hemos probado (3.8). Por lo tanto, f4 es una función

convexa.

e) Sean x, y ∈ R y λ ∈ [0, 1], vamos a demostrar que f5 es una función convexa, es decir, vamos

a demostrar que

f5(λx + (1− λy)) ≤ λ f5(x) + (1− λ) f5(y). (3.9)

En efecto, por la desigualdad triangular, tenemos que

‖λx + (1− λ)y‖ ≤ ‖λx‖+ ‖(1− λ)y‖ ,

de donde, por la homogeneidad de la norma, se sigue que

‖λx + (1− λy)‖ ≤ λ ‖x‖+ (1− λ) ‖y‖ ,

es decir, (3.9) se satisface. Por lo tanto, hemos probado que f5 es una función convexa.

f) Tenemos que

f ′6(x) = − 1x2

∫ x

0F(t) dt +

1x

d

(

∫ x

0F(t) dt

)

dx, (3.10)

de donde, si consideramos F(x) =

d

(

∫ x

0F(t) dt

)

dx, obtenemos que

f ′′6 (x) =2x3

∫ x

0F(t) dt− 1

x2 F(x)− 1x2 F(x) +

1x

F(x),

=2x3

∫ x

0F(t) dt− 2

x2 F(x) +1x

F(x),

=2x3

∫ x

0

[

F(t) dt− F(x)− F′(x)(t− x)]

dt,



f ′′6 (x) =2x3

∫ x

0

[

F(t) dt− F(x)− F′(x)(t− x)]

dt. (3.11)

Por otro lado, puesto que F es convexa y diferenciable, para todo x ∈ R, se tiene que

F(t) ≥ F(x) + F′(x)(t− x),

para todo t ∈ R, lo cual, es equivalente a tener que

F(t)− F(x)− F′(x)(t− x) ≥ 0,

de donde, por la monotonía de la integral, se sigue que

∫ x

0

[

F(t)− F(x)− F′(x)(t− x)]

dt ≥ 0,

combinando la desigualdad precedente con (3.11), obtenemos que

f6”(x) ≥ 0,

con esto, podemos concluir que f6 es una función convexa.

EJERCICIO 3.7. Considere la función:

f : Rn −→ R

x 7−→ log

(

1

1− ‖x‖2

)

,

¿ f es estrictamente convexa en C := x ∈ Rn : ‖x‖ < 1?

Solución: La función f no es estrictamente convexa, en efecto, consideremos:

x =

[

12

, 0, . . . , 0]T

y y =

[

12

, 0, . . . , 0]T

,

es fácil ver que

x, y ∈ C,

35

además, tomemos λ = 12 , luego, tenemos que

f

(

12

x +12

y

)

= log

1

1−∥

∥

∥

12 x + 1

2 y∥

∥

∥

2

,

= log

1

1−∥

∥

∥

(

14 , 0, . . . , 0

)

+(

14 , 0, . . . , 0

)∥

∥

∥

2

,

= log(

43

)

.

Por otro lado, se tiene que

12

f (x) +12

f (y) =12

log

(

1

1− ‖x‖2

)

+12

log

(

1

1− ‖y‖2

)

,

=12

log(

43

)

+12

log(

43

)

,

= log(

43

)

,


log(

43

)

= f

(

12

x +12

y

)

=12

f (x) +12

f (y) = log(

43

)

.

Por lo tanto, podemos concluir que f no es estrictamente convexa.

EJERCICIO 3.8. Sea f : Rn → R, demuestre o refute las siguientes proposiciones:

a) La función f := max1≤i≤n

fi es convexa si fi : Rm → R es convexa para todo i = 1, ..., n.

b) La función f := mın1≤i≤n

fi es convexa si fi : Rm → R es convexa para todo i = 1, ..., n.

Demostración. 1. Supongamos que

fi : Rm → R,

es una función convexa para todo i ∈ 1, . . . , n, vamos a demostrar que f es una función

convexa, para ello, sean x, y ∈ Rn y λ ∈ [0, 1], debemos probar que

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

tenemos que

f (λx + (1− λ)y) = max1≤i≤n

fi(λx + (1− λ)y),


por otro lado, por hipótesis, tenemos que

fi(λx + (1− λ)y) ≤ λ fi(x) + (1− λ) fi(x),

para todo i ∈ 1, . . . , n, así, se sigue que

max1≤i≤n

fi(λx + (1− λ)y) ≤ max1≤i≤n

λ fi(x) + (1− λ) fi(x) ,

≤ max1≤i≤n

fi(x) + (1− λ) max1≤i≤n

fi(y) = λ f (x) + (1− λ) f (y),

con esto, hemos probado que f es convexa.

2. Consideremos las funciones

f1 : R −→ R

x 7−→ xy

f2 : R −→ R

x 7−→ 2x,

las cuales, son funciones convexas, y sin embargo

f = mın f1, f2,

no es una función convexa. En efecto, para x = 4, y = −2 y λ = 12 , tenemos que

f1

(

12

x +12

y

)

= f1 (1) = 1 y f2

(

12

x +12

y

)

= 2,

con esto, obtenemos que

f (λx + (1− λ)y) = 1,

por otro lado, tenemos que

λ f1(x) =12

f1(4) = 2 y λ f2(x) =12

f2(4) = 4,

y además,

(1− λ) f1(y) =12

f1(−2) = −1 y (1− λ) f2(y) =12

f2(−2) = −2,

con esto, se sigue que

λ f (x) + (1− λ) f (y) = 2− 2 = 0,

de donde,

1 = f (λx + (1− λ)y) ≥ λ f (x) + (1− λ) f (y) = 0,

37

con esto, podemos concluir que el resultado no es cierto.

EJERCICIO 3.9. Sean Cimi=1 ⊂ R

n y bimi=1 ⊂ R. Considere la función

f : Rn −→ R

x 7−→ f (x) = max1≤i≤m

CTi x + bi.

Pruebe que la función es convexa. Además responda: ¿f es estrictamente convexa?, ¿f es

uniformemente convexa?

Demostración. • Sean x, y ∈ Rn y λ ∈ [0, 1], cualesquiera. Vamos a demostrar que f es con-

vexa, para ello, debemos verificar la desigualdad

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

Por la convexidad de Rn, sabemos que xλ = λ x + (1− λ)y ∈ R

n. Por definición de f ,

tenemos que

f (xλ) = max1≤i≤m

CTi [λ x + (1− λ)y] + bi = max

1≤i≤mλ CT

i x + (1− λ)CTi y + bi

Si fijamos k ∈ 1, . . . , m, por propiedades del máximo, tenemos que

λCTk x + (1− λ)CT

k y + bk ≤ λ max1≤i≤m

CTi x + bi+ (1− λ) max

1≤i≤mCT

i y + bi. (3.13)

En efecto, ya que λ ≥ 0 y 1− λ ≥ 0, se tiene que

CTk x ≤ max

1≤i≤nCT

i x y CTk y ≤ max

1≤i≤nCT

i y.

Ahora, como (3.13) es cierto para cualquier k ∈ 1, . . . , n, tenemos que

max1≤i≤m

λ CTi x + (1− λ)CT

i y + bi ≤ λ max1≤i≤m

CTi x + bi+ (1− λ) max

1≤i≤mCT

i x + bi,

de donde, por definición de f , tenemos que (3.12) se verifica. Por lo tanto, f es convexa.

• Vamos a probar que f no es estrictamente convexa. En efecto, tomemos m = 2,

Ci2i=1 =

12

1

;

13

1

⊂ R2 y bi2

i=1 = (4, 5) ⊂ R.


Ahora, consideremos n = 2 y definamos

x =

1

1

, y =

0

0

y λ =12

,

de donde,

xλ = λ x + (1− λ)y =

1212

.

Por un lado, tenemos que

f (xλ) = max[

12

, 1]

xλ + 4 ,[

13

, 1]

xλ + 5

= max

194

,173

,

es decir,

f (xλ) =173

. (3.14)

De otro lado,

f (x) = max

[

12

, 1]

1

1

+ 4 ,[

13

, 1]

1

1

+ 5

= max

112

,193

=193

,

f (y) = max

[

12

, 1]

0

0

+ 4 ,[

13

, 1]

0

0

+ 5

= max4, 5 = 5,

de donde,

λ f (x) + (1− λ) f (y) =173

. (3.15)

Por (3.14) y (3.15), se tiene que

f (λ x + (1− λ)y) = λ f (x) + (1− λ) f (y).

Por lo tanto, f no es estrictamente convexa.

• Vamos a verificar que f no es uniformemente convexa. En efecto, tomando el mismo caso,

datos y resultados obtenidos en el literal anterior, por un lado, tenemos que

f (xλ) + µλ(1− λ) ‖y− x‖2 =173

+12

µ,

de otro lado,

(1− λ) f (x) + λ f (y) =173

,

39

como u > 0, es claro que

f (xλ) + µλ(1− λ) ‖y− x‖2> (1− λ) f (x) + λ f (y),

se satisface. Por lo tanto, f no es uniformemente convexa.

EJERCICIO 3.10. Muestre que la función

f (x) =‖Ax− b‖2

1− xTx, (3.16)

es convexa en el conjunto B(0, 1) = x : ‖x‖ < 1.

Demostración. Sean x, y ∈ B(0, 1) y λ ∈ [0, 1], en primer lugar, notemos que

(λx + (1− λ)y)T(λx + (1− λ)y) = ‖(λx + (1− λ)y)‖2 ,

≤ λ ‖x‖2 + (1− λ) ‖y‖2 ,

< λ + (1− λ) = 1,

con esto, podemos concluir que

1− (λx + (1− λ)y)T(λx + (1− λ)y) > 0,

por lo tanto,

f (λx + (1− λ)y) =‖A(λx + (1− λ)y− b)‖2

1− (λx + (1− λ)y)T (λx + (1− λ)y),

está bien definido.

Ahora, notemos que la función f es la composición de la función g(t, x) = yTyt con la trans-

formación afín (y, t) = (Ax − b, 1 − xTx), por lo tanto, para probar que f es convexa, basta

con demostrar que g es convexa en (y, t) : t > 0. En efecto, notemos que g es la función de

perspectiva de

h : Rn −→ R

y 7−→ yTy,

la cual, es una función convexa. Así, por el Teorema 1.13, podemos concluir que g es una función

convexa, de donde, se sigue que

f (x) =‖Ax− b‖2

1− xTx,

es una función convexa en el conjunto B(0, 1) = x : ‖x‖ < 1.


EJERCICIO 3.11. Determinar el valor de a ∈ R tal que

f : R3 −→ R

x 7−→ ax21 + x2

2 + 2x23 − 4ax1x2 + 2x2x3,

sea convexa en todo su dominio.

Demostración. Puesto que f es una función polinómica, tenemos que f es una función diferen-

ciable, por lo tanto, para probar que f es una función convexa, basta con demostrar que

f ”(x) ≥ 0,

para todo x ∈ R3.

Las derivadas parciales de la función f son

∂ f

∂x1= 2ax1 − 4ax2,

∂ f

∂x2= 2x2 − 4ax1 + 2x3 y

∂ f

∂x3= 4x3 + 2x2,

de donde, las derivadas segundas derivadas parciales son

∂2 f

∂x21= 2a,

∂2 f

∂x22= 2 y

∂2 f

∂x23= 4,

y las derivadas parciales mixtas son

∂2 f

∂x1∂x2=

∂2 f

∂x2∂x1= −4a,

∂2 f

∂x1∂x3=

∂2 f

∂x3∂x1= 0 y

∂2 f

∂x2∂x3=

∂2 f

∂x3∂x2= 2.

Con esto, la matriz Hessiana de f es

H =

2a −4a 0

−4a 2 2

0 2 4

,

por el criterio de Sylvester, H es definida positiva si todo menor principal es no-negativo, así,

tenemos que

H =

∣

∣

∣

∣

∣

∣

∣

∣

∣

2a −4a 0

−4a 2 2

0 2 4

∣

∣

∣

∣

∣

∣

∣

∣

∣

= 2a

∣

∣

∣

∣

∣

∣

2 2

2 4

∣

∣

∣

∣

∣

∣

+ 4a

∣

∣

∣

∣

∣

∣

−4a 2

0 4

∣

∣

∣

∣

∣

∣

= 2a(8− 4) + 4a(−16a) = 8a− 64a2> 0,

41


a− 8a2 = a(1− 8a) > 0,

de donde, obtenemos que

a <18

.

Ahora, tenemos que

H =

∣

∣

∣

∣

∣

∣

2a −4a

−4a 2

∣

∣

∣

∣

∣

∣

= 4a− 16a2> 0,


a− 4a2 = a(1− 4a) > 0,

con lo cual, se sigue que

a <14

.

Finalmente, tenemos que

2a > 0,

con esto, podemos concluir que H es definida positiva si a ∈[

0, 18

[

.

EJERCICIO 3.12. Suponga que f : Rn → R es una función convexa. Demuestre que el con-

junto de minimizadores globales de f es un conjunto convexo.

Demostración. El conjunto de minimizadores globales es

A = x : f (x) < f (y), ∀y ∈ Rn,

sean x1, x2 ∈ A y λ ∈ [0, 1], vamos a demostrar que

λx1 + (1− λ)x2 ∈ A,

es decir, debemos probar que

f (λx1 + (1− λ)x2) < f (y),

para todo y ∈ Rn.

En efecto, sea y ∈ Rn, puesto que f es una función convexa, tenemos que

f (λx1 + (1− λ)x2) ≤ λ f (x1) + (1− λ) f (x2). (3.17)


Por otro lado, dado que x1, x2 ∈ A, sabemos que

f (x1) < f (y) y f (x2) < f (y),

luego, combinando la desigualdad precedente con (3.17), obtenemos que

f (λx1 + (1− λ)x2) < λ f (y) + (1− λ) f (y) = λ f (y) + f (y)− λ f (y) = f (y),

es decir, hemos probado que

λx1 + (1− λ)x2 ∈ A,

con esto, se sigue que A es un conjunto convexo.

EJERCICIO 3.13. Sean f1, f2 : Rn → R funciones convexas y diferenciables. Considere la fun-

ción f definida por:

max f1(x), f2(x),

para todo x ∈ Rn. Sea x ∈ R

n, tal que f (x) = f1(x) = f2(x). Muestre que ξ es un subgra-

diente de f en x si, y sólo si

ξ = λ∇ f1(x) + (1− λ)∇ f2(x),

con λ ∈ [0, 1].

Demostración. a) Para la primera implicación supongamos que ξ ∈ Rn es un subgradiente de f

en x, así, se sigue que

f (x) ≥ f (x) + (x− x)Tξ, (3.18)

para todo x ∈ Rn.

Ahora, puesto que f1 y f2 son funciones diferenciables, tenemos que

f (x) = max

f1(x) + (x− x)T∇ f1(x) + o1(‖x− x‖), f2(x) + (x− x)T∇ f2(x) + o2(‖x− x‖)

.

para todo x ∈ Rn.

Por hipótesis, tenemos que

f (x) = f1(x) = f2(x),

de donde, si suponemos que f (x) = f1(x) + (x− x)T∇ f1(x) + o1(‖x− x‖), junto con (3.18),

43

obtenemos que

f1(x) + (x− x)T∇ f1(x) + o1(‖x− x‖) ≥ f1(x) + (x− x)Tξ,

para todo x ∈ Rn, lo cual es equivalente a tener que

(x− x)Tξ [∇ f1(x− ξ)] + o1(‖x− x‖) ≥ 0,

para todo x ∈ Rn, análogamente, si suponemos f (x) = f2(x)+ (x− x)T∇ f2(x)+ o2(‖x− x‖),

se sigue que

(x− x)Tξ [∇ f2(x− ξ)] + o2(‖x− x‖) ≥ 0,

para todo x ∈ Rn, por lo tanto, tenemos que

max

(x− x)Tξ [∇ f1(x− ξ)] + o1(‖x− x‖), (x− x)Tξ [∇ f2(x− ξ)] + o2(‖x− x‖)

≥ 0.

(3.19)

Por reducción al absurdo, supongamos que ξ /∈ Conv∇ f1(x),∇ f2(x), así, existe un

hiperplano αx = β, ‖α‖ = 1, tal que

αTξ > β y αT∇ f1(x) < β , αT∇ f2(x) < β,

es decir, se tiene que

αT(∇ f1(x)− ξ) < 0 y αT(∇ f2(x)− ξ) < 0. (3.20)

Por otro lado, (x− x) = εα, con ε→ 0+, así, de (3.19), tenemos que

max

αTξ [∇ f1(x− ξ)] + o1(‖x− x‖), αTξ [∇ f2(x− ξ)] + o2(‖x− x‖)

≥ 0,

lo cual, es contradictorio con (3.20), por lo tanto, podemos concluir

ξ ∈ Conv∇ f1(x),∇ f2(x),

es decir,

ξ = λ∇ f1(x) + (1− λ)∇ f2(x),

con λ ∈ [0, 1].


b) Para la otra implicación, supongamos que ξ ∈ Rn es tal que

ξ = λ∇ f1(x) + (1− λ)∇ f2(x),

con λ ∈ [0, 1] y x ∈ Rn, vamos a demostrar que ξ es un subgradiente de f en x ∈ R

n, para

ello, debemos probar que

f (x) ≥ f (x) + ξT(x− x),

para todo x ∈ Rn. En efecto, como f1 y f2 son convexas y diferenciables, tenemos que

f (x) ≥ f1(x) ≥ f (x) +∇ f (x)T(x− x),

y

f (x) ≥ f2(x) ≥ f (x) +∇ f (x)T(x− x),

de donde, para λ ∈ [0, 1], se sigue que

f (x) ≥ f (x) + [λ∇ f1(x) + (1− λ)∇ f2(x)]T (x− x),

para todo x ∈ Rn, luego, por hipótesis, tenemos que

f (x) ≥ f (x) + ξT(x− x),

para todo x ∈ Rn, es decir, hemos probado que ξ es un subgradiente de f en x.

EJERCICIO 3.14. Demuestre que el subdiferencial de una función convexa calculado en x ∈int (dom( f )) es un conjunto acotado.

Demostración. Sean ξ ∈ Rn el subdiferencial de f en x ∈ int (dom( f )) y λ > 0 suficientemente

pequeño. Puesto que int (dom( f )) es un conjunto abierto, tenemos que

x + λξ ∈ int(dom( f )),

luego, por la definición de subgradiente, obtenemos que

f (x + λξ) ≥ f (x) + ξT(λξ)

= f (x) + λ ‖ξ‖2 ,

45


‖ξ‖2 ≤ f (x + λξ)− f (x),

con esto, hemos probado que ξ ∈ Rn es acotado.

EJERCICIO 3.15. En el Teorema 1.1, si tomamos X ⊆ Rn, un conjunto cerrado, ¿el resultado

es cierto?

Solución: En ese caso, el resultado no siempre es cierto. En efecto, consideremos el intervalo:

I = [−1, 1] = x ∈ R : −1 ≤ x ≤ 1,

que es un conjunto convexo y cerrado. Por otro lado, consideremos la función convexa f definida

por

f : I −→ [0, 1]

x 7−→

0 si − 1 < x < 1,

1 si x = −1 o x = 1.

Gráficamente, tenemos que

0 1 2−1−2

0

−1

1

2

x

y

b b

Es claro que f presenta dos puntos de discontinuidad, por lo tanto, se tiene que f no es continua

sobre I.

EJERCICIO 3.16. Para cada 1 ≤ i ≤ m, considere γi > 0, ai ∈ Rn y las funciones f , g : R

n →R definidas por:

f (x) :=m

∑i=1

γi exp(aTi x) y g(x) := ln

(

m

∑i=1

γi exp(aTi x)

)

.

Pruebe que f y g son convexas.


Demostración. Antes de realizar la demostración, probemos que la función:

h : R −→ R

x 7−→ exp(x),

es una función convexa. En efecto, el resultado se sigue debido a que h′′(x) = exp(x) > 0.

Ahora, sean x, y ∈ Rn y λ ∈ [0, 1], vamos a demostrar que f (λx + (1− λ)y) ≤ λ f (x) + (1−

λ) f (y), tenemos que

exp(

λaTi (λx + (1− λ)y)

)

= exp(

λaTi x + (1− λ)aT

i y)

,

para cada i ∈ 1, · · · , m, de donde, usando la convexidad de la función exponencial, obtenemos

que

exp(


)

≤ λ exp(aTi x) + (1− λ) exp(aT

i y),

para cada i ∈ 1, · · · , m, luego, puesto que γi > 0 para cada i ∈ 1, · · · , m, de la desigualdad

precedente, obtenemos que

γi exp(


)

≤ γiλ exp(aTi x) + γi(1− λ) exp(aT

i y),

para cada i ∈ 1, · · · , m, así,

m

∑i=1

γi exp(


)

≤ λm

∑i=1

γi exp(aTi x) + (1− λ)

m

∑i=1

γi exp(aTi y),

es decir,

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

con esto, hemos probado que f es convexa.

Sean x, y ∈ Rn y λ ∈ ]0, 1[, vamos a demostrar que

g(λx + (1− λ)y) ≤ λg(x) + (1− λ)g(y),

en efecto, para cada i ∈ N, consideremos

ui = γi exp(

aTi x)

y wi = γi exp(

aTi y)

,


g(λx + (1− λ)y) = ln

(

m

∑i=1

γi exp(aTi (λx + (1− λ)y))

)

,

47

= ln

(

m

∑i=1

γi exp(λaTi x) exp((1− λ)aT

i y)

)

,

= ln

(

m

∑i=1

uλi w1−λ

i y

)

,

es decir,

g(λx + (1− λ)y) = ln

(

m

∑i=1

uλi w

(1−λ)i y

)

. (3.21)

Por otro lado, por la desigualdad de Holder, sabemos que

n

∑i=1

uλi w

(1−λ)i ≤

(

n

∑i=1

uλ

1λ

i

)λ ( n

∑i=1

w(1−λ) 1

1−λi

)(1−λ)

,

de donde, por la monotonía de la función logaritmo, obtenemos que

ln

(

n

∑i=1

uλi w

(1−λ)i

)

≤ ln

(

n

∑i=1

ui

)λ ( n

∑i=1

wi

)(1−λ)

,

= ln

(

n

∑j=1

ui

)λ

+ ln

(

n

∑j=1

wi

)(1−λ)

,

= λ ln

(

n

∑j=1

ui

)

+ (1− λ) ln

(

n

∑j=1

wi

)

,

luego, junto con (3.21), obtenemos que

g(λx + (1− λ)y) ≤ λg(x) + (1− λ)g(y).

EJERCICIO 3.17. Supongamos que

f (x) = h(g1(x), g2(x), . . . , gk(x)),

donde, h : Rk → R es convexa y gi : R

n → R para cada i ∈ 1, . . . , k. Además, supongamos

que para cada i ∈ 1, . . . , k, uno de los siguientes enunciados se verifica:

a) h es no decreciente en la i-ésima componente y gi es convexa.

b) h es no creciente en la i-ésima componente y gi es cóncava.

c) gi es afín.

Demuestre que f es convexa.


Demostración. Sean x, y ∈ Rn y λ ∈ [0, 1]. Vamos a demostrar que f es convexa en cada literal,

para ello, debemos verificar que f satisface la siguiente desigualdad

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

a) Supongamos que h es no decreciente en la i-ésima componente y gi es convexa. Como gi es

convexa, tenemos que

gi(λx + (1− λ)y) ≤ λgi(x) + (1− λ)gi(y),

para todo i ∈ 1, . . . , k, de donde, puesto que h es no decreciente, obtenemos que

h(gi(λx + (1− λ)y) ≤ h(λgi(x) + (1− λ)gi(y)),

para todo i ∈ 1, . . . , k, luego, de la desigualdad precedente y usando la convexidad de h,

se sigue que

h(gi(λx + (1− λ)y) ≤ λh(gi(x)) + (1− λ)h(gi(y)),

para todo i ∈ 1, . . . , k, es decir, hemos verificado (3.22). Por lo tanto f es convexa.

b) Supongamos que h es no creciente en la i-ésima componente y gi es cóncava. Como gi es

cóncava, tenemos que

gi(λx + (1− λ)y) ≥ λgi(x) + (1− λ)gi(y),

para todo i ∈ 1, · · · , k, de donde, puesto que h es no creciente, obtenemos que

h(gi(λx + (1− λ)y) ≤ h(λgi(x) + (1− λ)gi(y)),

para todo i ∈ 1, · · · , k, luego, de la desigualdad precedente y usando el hecho de que h es

convexa, se sigue que

h(gi(λx + (1− λ)y) ≤ λh(gi(x)) + (1− λ)h(gi(y)),

para todo i ∈ 1, · · · , k, es decir, hemos verificado (3.22). Por lo tanto f es convexa.

c) Supongamos que gi es afín para todo i ∈ 1, · · · , k, es decir,

gi(x) = Aix + bi,

49

donde ATi ∈ R

n y bi ∈ R. Por la composición de funciones, tenemos que

f (x) = h(A1(λx + (1− λ)y) + b1, . . . , Ak(λx + (1− λ)y) + bk). (3.23)

Por otro lado, notemos que

Ai(λx + (1− λ)y) + bi = λAix + (1− λ)Aiy + bi = λ(Aix + bi) + (1− λ) (Aiy + bi) ,

para todo i ∈ 1, · · · , k, con esto y (3.23), obtenemos que

h(gi(λx + (1− λ)y) = h (λ(Aix + bi) + (1− λ) (Aiy + bi)) ,

para todo i ∈ 1, · · · , k. Finalmente, puesto que h es convexa, tenemos que

h(gi(λx + (1− λ)y) ≤ λh (Aix + bi) + (1− λ)h (Aiy + bi) ,

para todo i ∈ 1, · · · , k. Por lo tanto, hemos verificado (3.22), es decir, f es convexa.

EJERCICIO 3.18. Pruebe que una función f : Rn → R, continuamente diferenciable, es uni-

formemente convexa si, y sólo si existe µ > 0, tal que para todo x, y ∈ Ω, se tiene que

∇ f (x)T(y− x) + µ ‖y− x‖2 ≤ f (y)− f (x). (3.24)

Demostración. Para la primera implicación, supongamos que f es uniformemente convexa y de

clase C1, vamos a demostrar (3.24). Por definición de convexidad uniforme, sabemos que existe

µ > 0, tal que para cualesquier x, y ∈ Rn y λ ∈ [0, 1], se tiene que:

f (λ y + (1− λ) x) + µ λ(1− λ) ‖y− x‖2 ≤ λ f (y) + (1− λ) f (x),

como λ y + (1− λ)x = x + λ(y − x), al dividir la desigualdad precedente para λ tal que 0 <

λ ≤ 1, obtenemos

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

λ+ µ λ(1− λ) ‖y− x‖2 ≤ f (y)− f (x),

tomando el límite cuando λ→ 0+, se sigue que

lımλ→0+

(

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

λ

)

+ µ ‖y− x‖2 ≤ f (y)− f (x), (3.25)


Por otro lado, por la definición de derivada direccional de f en y− x, tenemos que

Dy−x f (x) = lımλ→0

(

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

λ

)

= d f (x)(y− x) = ∇T f (x)(y− x),

combinando la igualdad precedente con la desigualdad (3.25), se sigue el resultado.

Recíprocamente, supongamos que f es continuamente diferenciable y satisface (3.24), vamos

a probar que f es uniformemente convexa, para ello, debemos hallar µ > 0 tal que para todo

x, y ∈ Rn se verifique que

f ((1− λ)x + λy) + µλ(1− λ) ‖x− y‖2 ≤ λ f (y) + (1− λ) f (x). (3.26)

En efecto, sean x, y ∈ Rn y λ ∈ [0, 1], cualesquiera, por la convexidad de R

n, podemos definir

xλ = (1− λ)x + λy ∈ Rn, de donde,

(1− λ)x + λy− xλ = 0. (3.27)

Por como consideramos xλ, notemos que,

(1− λ)(x− xλ) + λ(y− xλ) = (1− λ) x + λ y− xλ = 0,

así,

∇ f (xλ)T ((1− λ)(x− xλ) + λ(y− xλ)) = 0. (3.28)

Además, por la definición de xλ y las propiedades de la norma se sigue que

(1− λ) ‖x− xλ‖2 + λ ‖y− xλ‖2 = (1− λ) ‖λ(y− x)‖2 + λ ‖(1− λ)(y− x)‖2

= λ(1− λ) ‖y− x‖2 (3.29)


G = (1− λ)( f (x)− f (xλ)) + λ( f (y)− f (xλ)) (3.30)

= λ f (y) + (1− λ) f (x)− f ((1− λ)x + λy), (3.31)

de donde, por (3.24) aplicado a (3.30) y la linealidad del producto escalar, obtenemos que existe

µ > 0 tal que

G ≥ ∇ f (xλ)T ((1− λ)(x− xλ) + λ(y− xλ)) + µ

[

(1− λ) ‖x− xλ‖2 + λ ‖y− xλ‖2]

. (3.32)

51

Reemplazando (3.31), (3.28) y (3.29) en (3.32), tenemos que

λ f (y) + (1− λ) f (x)− f ((1− λ)x + λy) ≥ µλ(1− λ) ‖y− x‖2 .

Finalmente, multiplicando por menos uno a la desigualdad anterior y reordenando según co-

rresponda, hemos probado (3.26).


CAPÍTULO 4

CONDICIONES DE OPTIMALIDAD

EJERCICIO 4.1. Sea f : R3 → R dada por:

f (x, y, z) = 2x2 + xy + y2 + yz + z2 − 6x− 7y− 8z + 9.

a) Halle un punto estacionario de f .

b) Verifique que el punto hallado es un mínimo local.

c) Muestre que el punto estacionario es un mínimo global de f .

Solución: a) Por la definición de punto estacionario, vamos a buscar v = (x, y, z) ∈ R3, tal

que

∇ f (v) = 0.

Al calcular el gradiente de f en v, tenemos que

∇ f (v) = [4x + y− 6, x + 2y + z− 7, y + 2z− 8] = 0,

de donde, obtenemos el sistema de ecuaciones:

4x + y− 6 = 0,

x + 2y + z− 7 = 0,

y + 2z− 8 = 0,

(4.1)

Al resolver (4.1), obtenemos el siguiente punto estacionario

x∗ =[

65

,65

,175

]T

.

b) Para verificar que x∗ es un mínimo local, por el Teorema 1.6, basta demostrar que f es

53

54 Condiciones de Optimalidad

diferenciable, para ello, recordemos que una función f es diferenciable, si

∂ f

∂x,

∂ f

∂yy

∂ f

∂z,

existen y son continuas.

En efecto, tenemos que

∂ f

∂x= 4x + y− 6,

∂ f

∂y= x + 2y + z− 7 y

∂ f

∂z= y + 2z− 8,

existen y son continuas, por ser funciones polinómicas, así, por el Teorema 1.6, tenemos

que x∗ es un mínimo local.

c) Para demostrar que x∗ es un mínimo global, por el Teorema 1.6, basta con verificar que f

es una función convexa, para lo cual, vamos a probar que la matriz Hessiana es definida

positiva. En efecto,∂2 f

∂x2 = 4, y∂2 f

∂y2 =∂2 f

∂z2 = 2,

además,

∂2 f

∂x∂y=

∂2 f

∂y∂x= 1,

∂2 f

∂x∂z=

∂2 f

∂z∂x= 0 y

∂2 f

∂y∂z=

∂2 f

∂z∂y= 1,

con esto, tenemos que la matriz Hessiana es:

H =

4 1 0

1 2 1

0 1 2

Al aplicar el Criterio de Sylvester, podemos ver que todo menor principal es no-negativo,

en efecto, tenemos que

det(H) =

∣

∣

∣

∣

∣

∣

∣

∣

∣

4 1 0

1 2 1

0 1 2

∣

∣

∣

∣

∣

∣

∣

∣

∣

= 14 > 0

además,∣

∣

∣

∣

∣

∣

4 1

1 2

∣

∣

∣

∣

∣

∣

= 8− 1 = 7 > 0 y 4 > 0.

Por lo tanto, hemos probado que f es convexa. Por lo tanto, x∗ es un mínimo global de f .

55

EJERCICIO 4.2. Considere el siguiente problema de minimización

mınx∈R2

f (x) = x21 − x1x2 + 2x2

2 − 2x1 + exp(x1 + x2).

a) Escriba las condiciones de optimalidad necesarias de primer orden.

b) ¿Es x = [0, 0] un mínimo local? ¿Puede encontrar una dirección p a lo largo de la cual

la función decrezca? Intente minimizar la función empezando por x = (0, 0) en la

dirección encontrada en el literal anterior.

Solución. a) Notemos que f es una función continuamente diferenciable, pues es la composi-

ción entre sumas de polinomios y exponenciales, si x∗ es un mínimo local de f . Entonces

∇ f (x∗) = (exp(x1 + x2) + 2x1 − x2 − 2, exp(x1 + x2)− x1 + 4x2) = (0, 0) (4.2)

b) Por el literal a), basta calcular ∇ f (x), si es igual al vector nulo, x es punto mínimo de f ,

caso contrario no.

∇ f (x) = (−1, 1),

por lo tanto x no es un mínimo local de f . Para encontrar una dirección p = (a, b) tal que

la función decrezca, donde a, b ∈ R, p debe satisfacer

∇ f (x)T p < 0,

así,

[−1, 1][a, b]T < 0

de donde, b < a. En particular, podemos tomar p = [1,−1] . Definamos

ϕ(λ) = f (xk + λpk).

Tomemos k = 1, x0 = [0, 0] y p0 = [1,−1]. Además, f (x0) = 1, debemos resolver el

problema auxiliar

mınλ≥0

ϕ(λ) = mınλ≥0

4λ2 − 2λ + 1.


8λ− 2 = 0,


de donde,

λ0 := λ =14

.

Ahora, al calcular x1 = x0 + λ0 p0, obtenemos

x1 = [0.25,−0.25], f1 = 0.75 y ∇ f1 = [−0.25,−0.25].

Aplicando el Método de Newton con búsqueda lineal (Armijo) (ver Código 7.0.2) y punto

inicial x1 = [0.25,−0.25], en 5 iteraciones se encuentra el punto estacionario

x∗ = [0.3304,−0.2017] y f (x∗) = 0.7337.

Al evaluar el gradiente y la Hessiana de f en x∗, obtenemos que

∇ f (x∗) = [−1.511 × 10−04, 1.487 × 10−04] ≈ [0, 0]

y

∇2 f (x∗) =

3.1373 0.1373

0.1373 5.1373

.

Usando el criterio de Sylvester, colegimos que ∇2 f (x∗) es definida positiva. Por lo tanto,

x∗ es un mínimo de f .

El gráfico error-iteración es el siguiente:

1 1.5 2 2.5 3 3.5 4 4.5 5

Iteraciones

10-12

10-10

10-8

10-6

10-4

10-2

100

102

Err

or

x12-x1*x2+2*x2

2-2*x1+exp(x1+x2)

57

EJERCICIO 4.3. Encuentre las condiciones necesarias y suficientes para la existencia de una

solución del problema:

mınx∈Rn

f (x) =12‖Ax− b‖2 +

12

xTx.

Solución: En primer lugar, notemos que

12‖Ax− b‖2 =

12〈Ax− b, Ax− b〉 ,

=12〈Ax, Ax〉 − 〈Ax, b〉+ 1

2〈b, b〉 ,

=12

⟨

x, AT Ax⟩

−⟨

x, ATb⟩

+12〈b, b〉 ,

con esto, f puede reescribirse como

f (x) =12

xT AT Ax− xT ATb +12

bTb +12

xTx,

de donde, tenemos que si la matriz A es de rango completo, entonces AT A es simétrica y definida

positiva, y además x∗ ∈ Rn es solución del problema de minimización si, y sólo si

AT Ax = ATb,

con esto, podemos concluir que una condición necesaria y suficiente para la existencia de la

solución del problema es que la matriz A sea de rango completo.

EJERCICIO 4.4. Sean A ∈ Rn×n una matriz simétrica, b ∈ R

n y c ∈ R. Considere la función

f : Rn −→ R

x 7−→ f (x) = xT A x + 2 bT x + c

Pruebe que

a) Existe un punto estacionario x∗ para f , siempre que A 0 y que b sea elemento del

rango de A. Además, x∗ es único si A ≻ 0

b) Si A 0, entonces todo punto estacionario de f es un mínimo global.

Demostración. a) El gradiente de la función f es

∇ f (x) = (A + AT)x + 2b = 2Ax + 2b,


de donde, por definición de punto estacionario, tenemos que

Ax + b = 0,

por lo tanto, x∗ es solución del problema

Ax = −b,

tenemos los siguientes casos

(a) Si A 0 y dado que b es elemento del rango de A, entonces el sistema de ecuaciones

Ax = −b tiene solución (o infinitas soluciones).

(b) Por otro lado, si A ≻ 0 y dado que b es elemento del rango de A, entonces el sistema

de ecuaciones Ax = −b tiene solución única, dada por

x∗ = −A−1b.

b) Si A 0, entonces

∇ f 2(x) = 2A,

es semi-definida positiva, es decir, f es una función convexa y diferenciable, por lo tanto,

todo punto estacionario de f es un mínimo global.

CAPÍTULO 5

MÉTODOS DE DESCENSO


f : R2 −→ R

(x1, x2) 7−→ (x1 − 2x22)

2.

¿Cuál de las siguientes direcciones son de descenso en x = [0, 1]?

• d = [1, 1],

• d = [1,−1],

• d = [2, 1],

• d = [1, 3],

Demostración. Por definición de gradiente, tenemos que

∇ f (x1, x2) =[

2(x1 − 2x22),−8x2(x1 − 2x2

2)]

,

de donde, para x = [0, 1], se sigue que

∇ f (0, 1) = [−4, 16] ,

ahora, sabemos que p es una dirección de descenso si ∇ f (x)T p < 0. Así, tenemos que

∇ f (0, 1)Td = [−4, 16] [1,−1]T = −4− 16 = −20 < 0,

por lo tanto, d = [1,−1] es una dirección de descenso.

59

60 Métodos de descenso


f : R2 −→ R

x 7−→ f (x) = (x1 + x22)

2.

En el punto x = [1, 0]T , consideramos la dirección de búsqueda p = [−1, 1]T , pruebe que p

es una dirección de descenso y encuentre todos los mínimos del problema siguiente:

mınα>0

f (x + α p). (5.1)

Demostración. • Vamos a probar que p es una dirección de descenso, es decir, que∇ f (x)T p <

0. En efecto, al calcular el gradiente de f en x = (x1, x2) ∈ R2, obtenemos

∇ f (x) = [2(x1 + x22), 4x2(x1 + x2

2)],

de donde, para x = [1, 0]T , tenemos que

∇ f (x) = [2, 0]T .

Así,

∇ f (x)T p = [2, 0]

−1

1

= −2,

luego, ∇ f (x)T p < 0, por lo tanto, p es una dirección de descenso.

• Encontremos todos los mínimos del problema (5.1), para ello, notemos que

x + α p = [1− α, α]T ,

así, por la definición de f obtenemos

mınα>0

f (x + α p) = mınα>0

(α2 − α + 1)2

Calculamos ∂ fdα = 2(α2 − α + 1)(2α− 1) de donde, al hacer ∂ f

dα = 0, tenemos que

α2 − α + 1 = 0 o 2α− 1 = 0,

para la primera ecuación, obtenemos dos números complejos,

α1 =−1 + 3i

2y α1 =

−1− 3i

2,

61

que descartamos. Mientras que para la segunda ecuación, se obtiene el punto estacionario

α = 12 > 0. Ahora, como

∂ f

∂α(α) = 2

(

6α2 − 6α + 3)

,

obtenemos que∂ f

∂α

(

12

)

= 3 > 0,

de donde, concluimos que α es un mínimo local de (5.1).

EJERCICIO 5.3. Sea (xn)n∈Nuna sucesión generada por un algoritmo de descenso. Sea ade-

más, yk = ∇ f (xk + 1)−∇ f (xk) y dk para todo k ∈ N, una dirección de descenso. Pruebe

que si f es fuertemente convexa, entonces la condición de la curvatura: yTk dk > 0 se verifica

para cualquier xk y xk+1.

Demostración. Supongamos que f es fuertemente convexa; es decir, los valores propios de∇2 f (x)

son positivos y acotados desde 0, así, existe µ > 0 tal que

pT∇ f (x)p ≥ µ ‖p‖2> 0, (5.2)

para todo p ∈ Rn.

Por otro lado, usando el desarrollo de Taylor, para todo k ∈ N, si xk+1 = xk + αk pk, entonces

se tiene que

∇ f (xk + αk pk) = ∇ f (xk) +∫ 1

0

[

∇2 f (xk + y · αk · pk)αk · pk

]

dy.

Ahora, sabemos que yk = ∇ f (xk+1) − ∇ f (xk) para todo k ∈ N, así, junto con la igualdad

precedente, se sigue que

αk pTk yk = αk pT

k [∇ f (xk + 1)−∇ f (xk)] ,

= αk pTK

∫ 1

0

[

∇2 f (xk + y · αk · pk)αk · pk

]

dy,

= α2k

∫ 1

0

[

pTk∇2 f (xk + y · αk · pk)pk

]

dy,

es decir,

αk pTk yk = α2

k

∫ 1

0

[


]

dy, (5.3)

para todo k ∈ N.


Notemos que gracias a (5.2) y por la monotonía de la integral, se sigue que

∫ 1

0

[


]

dy ≥ µ ‖p‖2∫ 1

0dy = µ ‖p‖2 ,

para todo k ∈ N, luego, combinando la desigualdad precedente con (5.3), se sigue que

αk pTk yk ≥ α2

kµ ‖p‖2> 0,

para todo k ∈ N, además, sabemos que dk es una dirección de descenso, es decir, dk = xk+1 −xk = αk pk, así, se sigue que

yTk dk > 0,

para todo k ∈ N.

EJERCICIO 5.4. Considere el método del descenso más profundo, para el cual, pk = −∇ f (xk).

Demuestre que las direcciones pk y pk+1 son ortogonales para todo k ∈ N.

Demostración. Consideremos la función φ(α) = f (xk + αpk) para cada k ∈ N. Por otro lado,

sabemos que xk+1 se determina buscando un punto crítico α∗ de la función φ, así,

φ′(α∗) = ∇ f (xk + α∗ · pk)T · pk = 0,

de donde, puesto que pk = −∇ f (xk), obtenemos que

∇ f (xk+1)T · ∇ f (xk) = 0,

para todo k ∈ N, por lo tanto, hemos probado que las direcciones pk y pk+1 son ortogonales para

todo k ∈ N.

EJERCICIO 5.5. Considere la siguiente función de Rosenbrock

f : R2 −→ R

(x, y) 7−→ 100(y− x2)2 + (1− x)2.

• Muestre que (1, 1) es el único punto estacionario de f . ¿Es un mínimo local?

• Calcule los valores propios máximo y mínimo de la matriz ∇2 f ((1, 1)) y también su

número de condición.

• ¿Para qué valores de (x, y) ∈ R2, la matriz ∇2 f (x, y) es definida positiva?

63

• Considerando el valor inicial x0 = (−1, 1) realice a mano 3 iteraciones de los algorit-

mos del descenso más profundo y de Newton, utilizando la estrategia de Armijo.

Solución: a) Vamos a calcular el gradiente de f , tenemos que

∇ f (x) =[

−400x(y− x2) + 2(x− 1), 200(y− x2)]T

,

de donde, para hallar los puntos estacionarios, igualamos el gradiente a cero y obtenemos

que

−400x(y− x2) + 2(x− 1) = 0

200(y− x2) = 0.(5.4)

Resolviendo el sistema (5.4), obtenemos que

x∗ = [1, 1]T ,

es el único punto estacionario de f .

Ahora, para probar que es un mínimo local, vamos a determinar la matriz Hessiana, para

lo cual, calculamos las derivadas parciales de segundo orden, en efecto, se tiene que

∂2 f

∂x2 = −400(y− 3x2) + 2 ,∂2 f

∂y2 = 200 y∂2 f

∂x∂y=

∂2 f

∂y∂x= −400x,

con esto, la matriz Hessiana es

H(x, y) =

−400(y− 3x2) + 2 −400x

−400x 200

,

de donde,

H(1, 1) =

802 −400

−400 200

,

luego, calculando del determinante, tenemos que

|H(1, 1)| =

∣

∣

∣

∣

∣

∣

802 −400

−400 200

∣

∣

∣

∣

∣

∣

= 400 > 0,

por otro lado, tenemos que∂2 f

∂x2 ([1, 1]) = 802 > 0,


así, el punto

x∗ = [1, 1],

es un mínimo local de f .

b) Tenemos que

|H(1, 1)| =

∣

∣

∣

∣

∣

∣

λ− 802 400

400 λ− 200

∣

∣

∣

∣

∣

∣

= λ2 − 1002λ + 400,


λ2 − 1002λ + 400,

de donde,

λmáx = 501 +√

250601 y λmín = 501−√

250601,

son los valores propios máximo y mínimo respectivamente.

Ahora, vamos a determinar el número de condición de la matriz, el cual, viene dado por:

K(H) = ‖H‖∞

∥

∥

∥H−1∥

∥

∥

∞,

de donde, la matriz inversa de H es

H−1 =

12 1

1 401200

,

así, tenemos que

K(A) = 3612, 01.

c) Por el criterio de Silvester, vamos a calcular los sub-determinantes de la matriz Hessiana, así,

tenemos que

−400(y− 3x2) + 2 > 0,

de donde,

600x2 − 200y + 1 > 0,

por otro lado, se tiene que

H(x, y) =

∣

∣

∣

∣

∣

∣

−400(y− 3x2) + 2 −400x

−400x 200

∣

∣

∣

∣

∣

∣

= 80000x2 − 80000y + 400,

65

de donde, puesto que buscamos los valores para los cuales la Hessiana es definida positiva,

se sigue que

200x2 − 200y + 1 > 0,

así, podemos ver que la matriz es definida positiva, para todo x ∈ R e y ∈ R tales que x ≥ y.

d) • Método del Gradiente conjugado utilizando la búsqueda lineal de Armijo:

Consideremos

γ = 1e−4, y p0 = −∇ f (−1, 1) = (4, 0),

con esto, vamos a realizar las iteraciones del algortimo de Armijo hasta que se satisfaga

la condición, en efecto, para α = 1, tenemos que

f (x0 + α0)− f (x0) = 6400,

por otro lado,

γα∇ f (x0)T p0 = −0.0016,

de donde,

6400 > −0.0016,

es decir, la condición de Armijo no se cumple.

Ahora, tomemos α = 12 , así, tenemos que

−4 = f(

x0 +12 p0

)

≤ γα∇ f (x0)t p0 = −0.008,

es decir, se cumple la condición de Armijo, por lo tanto,

x1 = x0 +12

p0

= [−1, 1] + [2, 0]

= [1, 1],

de donde, tenemos que x1 es el mínimo, en efecto,

f (1, 1) = 0.

• Método de Newton con la estrategia de búsqueda lineal del Armijo:


Por el método de Newton, sabemos que la dirección de descenso viene dada por

pk = −(

∇2 f (xk))−1∇ f (xk),

de donde, para k = 0, tenemos que

p0 = (2,−4).

Usando los mismos parámetros de la parte anterior, tomando α = 1, tenemos que

1596 = f (x0 + p0) > γ∇ f (x0)T p0 = −0.008,

es decir, no se satisface la condición.

Iterativamente, cuando α = 18 , obtenemos que

−0.5469 = f

(

x0 +18

p0

)

≤ 18

γ∇ f (x0)T p0 = −0.0001,


x1 = x0 +18

p0

=

[

−34

,−12

]

,

además,

f (x1) = 3.4531.

Ahora, para determinar el valor de x2, por Armijo con α = 1, tenemos que

−0.7993 = f (x1 + p1) ≤ γ∇ f (x1)T p1 = −0.0008,

es decir, se satisface la condición de Armijo, por lo tanto,

x2 = [−0.6204, 0.3681] y f (x2) = 2.6538.

Finalmente, vamos a determinar el valor de x3, se tiene que para α = 12 la condición de

Armijo se cumple, en efecto,

−0.4116 = f

(

x2 +12

p2

)

− f (x2) ≤ ∇ f (x2)T p2 = −0.00006504,

67


x3 = [−0.4345, 0.1459] y f (x3) = 2.2423.

EJERCICIO 5.6. Sea f : Rn → R continuamente diferenciable y x ∈ R

n tal que ∇ f (x) 6= 0.

Sea A ∈ M(Rn×n) una matriz definida positiva, cuya norma asociada en Rn esta dada por:

‖p‖A :=√

pT Ap. (5.5)

• Determine la dirección del profundo descenso correspondiente a ‖·‖ es decir, la solu-

ción de

mın‖p‖A

∇ f (x)T p.

Sugerencia: Use la factorización A = MT M.

Solución: Por la desigualdad de Cauchy-Schwarz, tenemos que

−∇ f (x)T p ≤ |∇ f (x)T p| = | 〈∇ f (x), p〉 | ≤ ‖∇ f (x)‖A ‖p‖A ,

de donde,

∇ f (x)T p ≥ −‖∇ f (x)‖A , (5.6)

para todo p ∈ Rn tal que ‖p‖A = 1.

Por otro lado, por (5.5), sabemos que

‖∇ f (x)‖A =√

∇ f (x)T A∇ f (x),

así, puesto que A es una matriz definida positiva, tenemos que A = MT M, donde, M es una

matriz triangular inferior con entradas diagonales estrictamente positivas, así,

‖∇ f (x)‖A =√

∇ f (x)T MT M∇ f (x)

=√

(M∇ f (x))T(M∇ f (x))

=√

〈(M∇ f (x), (M∇ f (x)〉

=

√

‖(M∇ f (x)‖2,


luego, combinando la igualdad precedente con (5.6), se sigue que

∇ f (x)T p ≥ −‖M∇ f (x)‖ ,

así, la igualdad se alcanza únicamente, si

p = − ∇ f (x)

‖M∇ f (x)‖ .

EJERCICIO 5.7. Considere el problema de optimización para x = [x1, x2] ∈ R2, dado por:

mın(x1,x2)

= f (x1, x2) := x21 + 2x2

2.

a) Si el valor inicial de iteración del algoritmo de descenso más profundo es x0 = [2, 1],

demuestre que la sucesión de puntos generados, usando una búsqueda lineal exacta,

está dada por

xk =

(

13

)k [

2, (−1)k]

.

b) Muestre que si f (xk+1) =19

f (xk). ¿Qué concluye acerca del método aplicado a este

problema?

Demostración. a) Antes de realizar la demostración, determinemos el diferencial de f :

∇ f (x1, x2) = [2x1, 4x2].

Por inducción, supongamos que k = 1, vamos a calcular la dirección de descenso p0, en

efecto, se tiene que

p0 = −∇ f (x0)

= −∇ f (2, 1)

= −[2(2), 4(1)]T

= −[4, 4]T ,

es decir,

p0 = [−4,−4]T .

69

Ahora, vamos a determinar el valor del paso, para ello, consideremos la función:

φ(α) = f (x0 + αp0) = f (2− 4α, 1− 4α),

de donde,

φ(α) = (2− 4α)2 + 2(1− 4α)2,

luego, derivando, se tiene que

φ′(α) = 8(4− 12α),


φ′(α) = 0⇔ 8(4− 12α) = 0,

de donde,

α =13

,

por lo tanto,

x1 = x0 + αp0 = [2, 1] +13[−4, 4] =

[

23

,−13

]T

,

es decir,

x1 =13[2,−1]T ,

así, el resultado es válido para k = 1.

Supongamos que el resultado es válido para k = n, es decir,

xn =

(

13

)n [

2, (−1)k]T

,

vamos a demostrar que el resultado es cierto para k = n + 1. Tenemos que la dirección de

descenso para k = n, viene dada por:

pn = ∇ f (xn) =

(

13

)n

[4, 4(−1)n] ,

de donde, se tiene que

xn + αpn =

(

13

)n

[2 + 4α, (−1)k + 4(−1)kα],

así, consideremos la función:

φ(α) = f (xn + αpn) =

(

13

)2n

(2 + 4α)2 + 2(

13

)2n

((−1)n + 4(−1)nα)2 ,


luego, derivando, se sigue que

φ′(α) = 8(

13

)2n

(2 + 4α) + 16(

13

)2n

(−1)n [(−1)n + 4α(−1)n] ,

de donde, igualando a cero, obtenemos que

α

[

32(

13

)2n

+ 64(−1)2n

(

13

)

]

= −16(

13

)2n

− 16(

13

)2n

(−1)2n,

luego, simplificando, se tiene que

α(2 + 4) = −2,

es decir,

α = −13

.

Con esto, tenemos que

xn+1 = xn + αpn

=

(

13

)n [23

, (−1)n

(

−13

)]

=

(

13

)n+1 [2, (−1)n+1

]

,

por lo tanto, el resultado se sigue.

b) Sea k ∈ N, vamos a demostrar que

f (xk+1) =19

f (xk),

en efecto, se tiene que

f (xk+1) = 4(

13

)2k+2

+

(

13

)2k+2

(−1)2k+2

=19

[

4(

13

)

2k +

(

13

)2k]

,

es decir,

f (xk+1) =19

[

4(

13

)2k

+

(

13

)2k]

. (5.7)


f (xk) = 4(

13

)2k

+

(

13

)

(−1)2k,

71

= 4(

13

)2k

+

(

13

)2k

,

de donde, combinado la igualdad predecedente con (5.7), se sigue que

f (xk+1) =19

f (xk),

para todo k ∈ N.

EJERCICIO 5.8. Pruebe que ‖Bx‖ ≥ ‖x‖‖B−1‖ para toda matriz no singular B. Use este resul-

tado para probar que

cos(θ) ≥ 1M

,

donde θ es el ángulo entre la dirección de descenso d, es decir

Bd = −∇ f (x).

Demostración. Por la definición de norma matricial, tenemos que

‖A‖ = supx 6=0

‖Ax‖‖x‖ ,

de donde, se sigue que

‖Ax‖ ≤ ‖A‖ ‖x‖ . (5.8)

Ahora, notemos que

‖x‖ =∥

∥

∥BB−1x∥

∥

∥ ,

luego, combinado la igualdad precedente con (5.8), tenemos que

‖x‖ ≤∥

∥

∥B−1∥

∥

∥ ‖Bx‖ ,

es decir,

‖Bx‖ ≥ ‖x‖‖B−1‖ .

Puesto que B es una matriz simétrica definida positiva, sabemos que la matriz B1/2 existe y

es tal que

B = B1/2B1/2 y∥

∥

∥B1/2∥

∥

∥ = ‖B‖1/2 .


Además, sabemos que

cos(θ) = − ∇ f T p

‖∇ f ‖ ‖p‖

=pTBp

‖Bp‖ ‖p‖ ,

de donde, usando la primera parte del ejercicio, se tiene que

cos(θ) ≥ pTBp

‖B‖ ‖p‖2 =pTB1/2B1/2 p

‖B‖ ‖p‖2

=

∥

∥

∥B1/2 p

∥

∥

∥

2

‖B‖ ‖p‖2 ≥‖p‖2

∥

∥B−1/2∥

∥

2 ‖B‖ ‖p‖2

=1

‖B−1‖ ‖B‖ ≥1M


cos(θ) ≥ 1M

.

EJERCICIO 5.9. De un ejemplo de una función real g : Rn −→ R tal que g(0) = −1, g(1) =

− 14 y muestre que la condición de la curvatura (yk

Tdk > 0) no se verifica en este caso.

(yk = ∇ f (xk+1)−∇ f (xk) y dk = xk+1 − xk).

Solución: Consideremos la función:

f : R −→ R

x 7−→ 11 + x

,

de donde, tenemos que

f ′(x) = − 1(1 + x)2 ,

así, basta tomar g = f ′ y se sigue que

f (0) = 1, f (1) =12

, g(0) = −1 y g(1) = −14

,


dTy = ( f (1)− f (0))(g(1)− g(0)) = −38< 0.

73

EJERCICIO 5.10. Muestre que la condición fuerte de Wolfe implica la condición de la curva-

tura (yTk dk > 0).

Demostración. La segunda condición fuerte de Wolfe, establece que

|∇ f (xk + αk pk)T pk| ≤ β|∇ f (xk)

T pk|,

de donde, puesto que pk es una dirección de descenso, se sigue que

∇ f (xk + αk pk)T pk ≥ −β∇ f (xk)

T pk = β∇ f (xk)T pk,

luego, dado que 0 < β < 1, tenemos que

∇ f (xk + αk pk)T pk − f (xk)

T pk ≥ β∇ f (xk)T pk −∇ f (xk)

T pk

= (β− 1) f (xk)T pk > 0,

ahora, puesto que yk = ∇ f (xk + αk pk)− f (xk)T , se sigue que

yTk pk > 0,

de donde,

yTk αk pk > 0,

es decir,

yTk dk > 0.

EJERCICIO 5.11. Sean f : Rn → R una función, x, p ∈ R

n y λ > 0, tales que x + λp cumple

la condición de Armijo. Considere 0 < µ < λ, ¿µ cumple la condición de Armijo? Pruebe

esto o dé un contraejemplo.

Solución: Por el Teorema 1.9, sabemos que x, p ∈ Rn y λ > 0 son tales que x + λp cumple la

condición de Armijo, es decir,

f (x + αp)− f (x) ≤ γ∇ f (x)T p,

de donde, puesto que µ < λ, se sigue que

f (x + µp)− f (x) ≤ γ∇ f (x)T p,


es decir, µ cumple la condición de Armijo.

EJERCICIO 5.12. Asumiendo la condición de Zoutendijk, si existe una constante c > 0, tal

que cos θk ≥ ‖∇ fk‖pk

y una constante c tal que ‖∇ fk‖pk≥ c > 0 para k ∈ N, entonces

lımk→+∞

‖∇ fk‖ = 0. (5.9)

Demostración. Asumiendo la condición de Zoutendijk, por el Teorema 1.8, se sigue que

∑k∈N

cos2(θk) ‖∇ fk‖2< +∞, (1.4)

donde, el ángulo θk entre pk y −∇ fk está definido por

cos θk =−∇ f T

k pk

‖∇ fk‖ ‖pk‖. (5.10)

Como

cos θk ≥‖∇ fk‖

pky

‖∇ fk‖pk

≥ c > 0,

podemos asegurar que θk es está limitado por 90.

Ahora, como la serie (1.2) es convergente, tenemos que

lımk→+∞

cos2(θk) ‖∇ fk‖2 = 0, (5.11)

vamos a probar que (5.9) se cumple.

En efecto, sea ε > 0, debemos hallar N ∈ N tal que para cada k > N

‖∇ fk‖ < ε. (5.12)

De (5.11), por la definición de límite, existe N ∈ N tal que para cualquier k > N se tiene que

∥

∥

∥(cos(θk) ‖∇ fk‖)2∥

∥

∥ < ε,

de donde, por propiedades de la norma, para cada k > N, tenemos que

∥

∥

∥(cos(θk) ‖∇ fk‖)2∥

∥

∥ ≤ ‖cos(θk) ‖∇ fk‖‖2< ε2,

al tomar la raíz cuadrada a la desigualdad anterior, para cada k > N, obtenemos

‖cos(θk) ‖∇ fk‖‖ < ε,

75

de donde, por la desigualdad de Cauchy-Schwarz, para cada k > N, se sigue que

‖cos(θk)‖ ‖∇ fk‖ < ε,

Al reemplazar (5.10) en la desigualdad anterior, para cada k > N, tenemos que

∥

∥

∥

∥

∥

−∇ f Tk pk

‖∇ fk‖ ‖pk‖

∥

∥

∥

∥

∥

‖∇ fk‖ =∥

∥∇ f Tk

∥

∥ ‖pk‖‖∇ fk‖ ‖pk‖

‖∇ fk‖ < ε,

de donde, para cada k > N, colegimos que

∥

∥

∥∇ f T

k

∥

∥

∥< ε.

Finalmente, tomando N = N, se satisface (5.12). Por lo tanto, hemos probado (5.9).

Obs: Condición de Zoutendijk

EJERCICIO 5.13. Sean A ∈ Rn×n una matriz simétrica definida positiva, b ∈ R

n y c ∈ R.

Considere la función

f : Rn −→ R

x 7−→ f (x) = xT A x + 2 bT x + c.

Sean, además x ∈ Rn, dado, y p ∈ R

n una dirección de descenso de f en x. Pruebe que el

paso α∗ que se obtiene por búsqueda lineal exacta, i.e.,

ϕ(α∗) = mınα>0

f (x + α p), (5.13)

está dado por

α∗ := −∇ f (x)T p

2 pT A p(5.14)

y que α∗ > 0.

Demostración. Para calcular el gradiente de f , usando los resultados del ejercicio (2.2) tenemos

que

∇ f (x) = A x + 2 b. (5.15)

Consideremos

ϕ(α) = f (x + α p),


por definición de f tenemos que

ϕ(α) = α2 pT A p + α(xT A p + 2 bT p) + xT A x + c,

para resolver (5.13), vamos a encontrar α∗ tal que ϕ′(α∗) = 0, así,

ϕ′(α∗) = 2α pT A p + xT A p = 0,

de donde,

α∗ = − (xT A + 2 bT)p

2 pT A p

dado que xT A = x AT y con (5.15) evaluado en x y reemplazado en α∗, se sigue que (5.14).

Por otro lado, notemos que p es dirección de descenso, por lo tanto verifica que

∇ f (x)T p < 0,

y dado que A ≻ 0,

pT A p > 0,

Finalmente, considerando las desigualdades precedentes junto con (5.14), colegimos que

α∗ > 0.

EJERCICIO 5.14. Muestre que si f : Rn → R es una función cuadrática, entonces verifica la

condición de Armijo

f (xk + αpk) ≤ f (xk) + σ1α∇ f (xk)T pk,

con σ1 = 0.5.

Demostración. Dado que f es una función cuadrática, sabemos que

f : R −→ R

x 7−→ 12

xT Ax + bTx,

con A ∈ Rn×n una matriz simétrica, así, obtenemos que

∇ f (x) = Ax + b.

Sea k ∈ N, por otro lado, sabemos que

αk = −∇ f (xk)

T

pTk Apk

. (5.16)

77

Ahora, tenemos que

f (xk + αk pk) =12

(

(xk + αk pk)T A(xk + αk pk)

)

+ bT(xk + αk pk),

= f (xk) + αkxTK Axk +

12

α2k pT

k Apk + αkbT pk,

= f (xk) +12

α2k pT

k Apk + αk

(

xTk A + bT

)

pk,

de donde, combinando la igualdad precedente con (5.16), obtenemos que

f (xk + αk pk) = f (xk) +12

(

∇ f (xk)T pk

)2

pTk Apk

− ∇ f (xk)T pk

pTk Apk

∇ f (xk)T pk,

= f (xk)−12

(

∇ f (xk)T pk

)2

pTk Apk

,

es decir,

f (xk + αk pk) = f (xk)−12

(

∇ f (xk)T pk

)2

pTk Apk

. (5.17)


f (xk) + σ1αk∇ f (xk)T pk = f (xk) + σ1

(

−∇ f (xk)T pk

pTk Apk

)

∇ f (xk)T pk,

= f (xk)− σ1

(

∇ f (xk)T pk

)2

pTk Apk

,

con esto, se sigue que

f (xk) + σ1αk∇ f (xk)T pk = f (xk)− σ1

(

∇ f (xk)T pk

)2

pTk Apk

. (5.18)

Por lo tanto, combinando (5.17) y (5.18), para σ1 = 0.5, se sigue que

f (xk + αk pk) = f (xk)−12

(

∇ f (xk)T pk

)2

pTk Apk

= f (xk) + σ1αk∇ f (xk)T pk,

además, si 0 < σ1 <12

, entonces

f (xk + αk pk) < f (xk) + σ1αk∇ f (xk)T pk.


EJERCICIO 5.15. Sean C ∈ Rn×n una matriz simétrica y definida positiva, c ∈ R

n y considere

la función cuadrática:f : R

n −→ R

x 7−→ f (x) = cT x +12

xT C x.

Sea p ∈ Rn una dirección de descenso de f en x y α∗ > 0 el paso óptimo, es decir,

f (x + α∗ p) = mınα≥0

f (x + α p). (5.19)

a) Pruebe que f es estrictamente convexa.

b) Pruebe que, en efecto, α∗ > 0.

c) Escriba el desarrollo en series de Taylor de ϕ(α) = f (x + α p) alrededor de α = 0.

Pruebe que α∗ está bien definido y es único.

d) Pruebe que α∗ satisface la condición de Armijo para γ ∈(

0, 12

]

, pero no necesaria-

mente para γ >12 .

Demostración. 1. Para probar que f es convexa, vamos a demostrar que yT∇2 f (x)y ≥ 0, para

todo x ∈ Rn y para todo y ∈ R

n, en efecto, tenemos que

∇ f (x) = c +12(C + CT)x,

de donde, dado que C es una matriz simétrica, obtenemos que

∇ f (x) = c + Cx,

luego, la matriz Hessiana es

∇2 f (x) = C,

así, puesto que C es definida positiva, sabemos que

yTCy ≥ 0,

con esto, hemos probado que

yT∇2 f (x)y ≥ 0,

para todo x ∈ Rn y para todo y ∈ R

n, por lo tanto, podemos concluir que f es una función

convexa.

79

2. En primer lugar, tenemos que

f (x + αp) = cT(x + αp) +12(x + αp)TC(x + αp),

= cTx + αcT p +12

[

xTCx + αxTCp + αpTCx + α2 pTCp]

,

de donde, dado que C es simétrica, se sigue que

f (x + αp) = cTx + αcT p +12

[

xTCx + 2αxTCp + α2 pTCp]

,


d f

dα= cT p +

12

[

2xTCp + 2αpTCp]

= cT p + xTCp + αpTCp,

luego, sabemos que α∗ es tal que

cT p + xTCp + α∗pTCp = 0,

es decir, se tiene que

α∗ = − (cT − xTC)p

pTCp= − (∇ f (x))T p

pTCp. (5.20)

Ahora, dado que p es una dirección de descenso y C es definida positiva, sabemos que

−∇ f (x)T p > 0 y pTCp > 0,

de donde, junto con (5.20), obtenemos que

α∗ = − (∇ f (x))T p

pTCp> 0.

3. Tenemos que

ϕ′(α) = cT p + xTCp + αpTCp y ϕ”(α) = pTC. (5.21)

Por otro lado, el desarrollo en series de Taylor de ϕ, viene dado por

ϕ(α) =ϕ(α1)

0!+

ϕ′(α1)

1!(α− α1) +

ϕ(α1)

2!(α− α1)

2,

de donde, dado que α1 = 0, obtenemos que

ϕ(α) =ϕ(0)

0!+

ϕ′(0)1!

α +ϕ(0)

2!α2,


luego, junto con (5.21), se sigue que

ϕ(α) = cTx +12

xTCx + α(

cT p + xTCp)

+α2

2pTC.

4. La condición de Armijo, establece que

f (x + αp)− f (x) ≤ αγ∇ f (x)T p.

Tenemos que

f (x + α∗p)− f (x) = cTx + α∗cT p +12

xTCx + α∗xTCp +12(α∗)2 pTCp− cTx− 1

2xTCx

= α∗cT p + α∗xTCp +12(α∗)2 pTCp

= α∗(

cT + xTC)

p +12(α∗)2 pTCp

= α∗∇ f (x)T p +12(α∗)2 pTCp

=

(

∇ f (x))T p)2

pTCp+

12

(

∇ f (x)T p)2

pTCp

= −12

(

∇ f (x))T p)2

pTCp,

de donde, si γ ≤ 12 , obtenemos que

f (x + α∗p)− f (x) = −12

(

∇ f (x))T p)2

pTCp≤ −γ

(

∇ f (x))T p)2

pTCp= α∗γ∇ f (x)T p,

es decir, hemos probado que la condición de Armijo se satisface para γ ∈]

0, 12

]

.

CAPÍTULO 6

MÉTODOS NEWTON Y CUASI-NEWTON

EJERCICIO 6.1. Sean x ∈ R2 y f (x) = 1

2 xT Ax con minimizador único x∗ = (0, 0) y

A =

2 −1

−1 2

.

1. Determine todos los valores iniciales x0 con ‖x0‖2 = 1 de modo que usando el Método

del Descenso más profundo con búsqueda lineal exacta se encuentre la solución en

x1 = x∗.

2. Determine todos los valores iniciales en x0 con ‖x0‖ = 1 de modo que empleando el

Método de Newton con paso constante se encuentra la solución en x1 = x∗.

Demostración. Notemos que A es una matriz simétrica, así, tenemos que

∇ f (x) = Ax y ∇2 f (x) = A.

1. En el Método del Descenso más profundo las direcciones vienen dadas por

pk = −∇ f (xk) = −Axk,

para cada k ∈ N.

Además, sabemos que

x1 = x0 + α0 p0

= x0 − α0 Ax0,

81

82 Métodos Newton y Cuasi-Newton

con esto, obtenemos el sistema de ecuaciones,

x(1)0 − α0(2x

(1)0 − x

(2)0 ) = 0,

x(2)0 − α0(2x

(2)0 − x

(1)0 ) = 0,

donde α0 es fijo y x(1)0 , x

(2)0 son las incógnitas, luego, resolviendo, se tiene que

(

x(1)0

)2=(

x(2)0

)2,

además, dado que ‖x0‖2 =(

x(1)0

)2+(

x(2)0

)2= 1, podemos concluir que

x0 =

[

1√2

,1√2

]T

.

2. Por otro lado, en el Método de Newton, las direcciones viene dadas por

∇ f 2(xk)pk = −∇ f (xk),

para cada k ∈ N, de donde, dado que A es una matriz invertible, se sigue que

pk = −A−1 Axk = −xk,

para cada k ∈ N. Así, obtenemos que

x1 = x0 + p0

= x0 − x0

= 0.

Con esto tenemos que x0 ∈ R2 es cualquiera, tal que

‖x0‖ = 1.


f : R2 −→ R

(x1, x2)T 7−→ f (x) = x2

1 + 2x1 x2 − x32 + 2x2

2

a) Pruebe que f tiene un mínimo local en [0, 0]T .

83

b) Determine si el método de Newton converge cuadráticamente en una vecindad de

[0, 0]T .

c) Proponga un método de tipo Newton considerando como punto inicial xT0 = [1, 1], tal

que la convergencia sea superlineal.

[Sugerencia:] Use las condiciones de Dennis-Moré.

Demostración. a) Vamos a probar que [0, 0]T es un mínimo local de f , para ello, calculemos el

gradiente de f en x ∈ R2, así,

∇ f (x) = [2 x1 + 2 x2, 2 x1 − 3 x22 + 4 x2],

de donde,

∇ f (0, 0) = [0, 0]T , (6.1)

así, [0, 0]T es un punto estacionario de f .

Ahora, vamos a probar que [0, 0]T es mínimo local de f , para ello, calculamos la Hessiana,

la cual, viene dada por

∇2 f (x) =

2 2

2 −6 x2 + 4

,

de donde,

∇2 f (0, 0) =

2 2

2 4

,

luego,∣

∣

∣

∣

∣

∣

2 2

2 4

∣

∣

∣

∣

∣

∣

= 8− 4 = 4 > 0,

con esto, podemos concluir que

x∗ = [0, 0]T ,

es un mínimo local de f .

b) Para determinar si el Método de Newton converge cuadráticamente en una vecindad de

[0, 0]T . Debemos probar que f es Lipschitz continua en una vecindad Vx de x, es decir,

debemos hallar L > 0, tal que

pT∇2 f (x)p ≥ L ‖p‖2 , (6.2)


para todo p = [p1, p2] ∈ R2.

En efecto, sea p = (p1, p2), tenemos que

pT∇2 f (x) p = [p1, p2]T∇2 f (0, 0) [p1, p2] = [p1, p2]

2 2

2 4

[p1, p2]T ,

=[

2p1 + 2p2 2p1 + 4p2

]

[p1, p2]T ,

= 2(p21 + 2p1 p2 + 2p2

2) ≥ (p21 + p2

2) (6.3)

De otro lado, tenemos que

‖p‖2 = p21 + p2

2. (6.4)

De (6.3) y (6.4) tenemos que

∇2 f (x) pT = 2(p21 + 2p1 p2 + 2p2

2) ≥12(p2

1 + p22) = ‖p‖2 .

Por lo tanto, tomando L = 12 (6.2), se prueba que f es Lipschitz continua en una vecindad

de x. Con esto, por el Teorema 1.14, hemos probado que el Método de Newton Converge

cuadráticamente.

• Consideremos el siguiente método de tipo Newton para hallar el mínimo de f en R2:

Mk dk = −∇ f (xk) y xk+1 = xk + dk, (6.5)

para cada k ∈ N, donde la matriz Mk = ∇2 f (xk), es decir,

Mk =

∂2 f (xk)

∂x21

∂2 f (xk)∂x1x2

∂2 f (xk)∂x2x1

∂2 f (xk)

∂x22

.


Mk −∇2 f (x∗) =

2 2

2 −6 x(k)2 + 4

−

2 2

2 4

=

0 0

0 −6x(k)2

(6.6)

Además, tenemos que

xk+1 − xk = dk,

donde, dk = −(

∇2 f (xk))−1∇2 f (xk), ahora, vamos a determinar el valor del paso. En

85

efecto, tenemos que

dk = −(

∇2 f (xk))−1∇ f (xk),

=

3x(k)2 −2

2−6x(k)2

12−6x

(k)2

12−6x

(k)2

16x

(k)2 −2

2x(k)1 + 2x

(k)2

2x(k)1 − 3

(

x(k)2

)2+ 4x

(k)2

,

=

6x(k)1 x

(k)2 +3

(

x(k)2

)2−2x

(k)1

2−6x(k)2

3x(k)2 −2x

(k)1

2−6x(k)2

.

Así, se sigue que

(

Mk −∇2 f (x∗))

(xk+1 − xk) =

0 0

0 −6x(k)2

6x(k)1 x

(k)2 +3

(

x(k)2

)2−2x

(k)1

2−6x(k)2

3x(k)2 −2x

(k)1

2−6x(k)2

,

=

0

12(

x(k)2

)2−18

(

x(k)2

)3

2−6x(k)2

,

con esto, obtenemos que

∥

∥

∥

(

Mk −∇2 f (x∗))

(xk+1 − xk)∥

∥

∥= o(‖xk+1 − xk‖).

Por lo tanto, por las Condiciones de Dennis-Moré, podemos concluir que el método con-

verge superlinealmente.

EJERCICIO 6.3. Sea f (x) = 12 xT x + 1

4 σ(xT A x)2, donde

A =

5 1 0 12

1 4 12 0

0 12 3 0

12 0 0 2

Resuelva el problema mınx∈Rn

f (x) con el método de Newton globalizado, tomando los si-

guientes puntos de inicialización:

• xT1 =

[

cos (70), sen (70), cos (70), sen (70)]

,

• xT2 =

[

cos (50), sen (50), cos (50), sen(50)]

,


con σ1 = 1 y σ2 = 104. Discuta los resultados numéricos y las tasas de convergencia obteni-

dos.

Solución: Para resolver el problema de minimización, debemos hallar el gradiente y la Hessiana

de f , para ello, notemos que podemos reescribir f como

f (x) =12

f1(x) +14

σ f2(x),

donde,

f1(x) = xT x y f2(x) = (xT A x)2.

Así, tenemos que

∇ f (x) =12∇ f1(x) +

14

σ∇ f2(x)

Por la definición de derivada de Gâteux, tenemos que

∇ f1(x)Tv = lımt→0

f1(x + tv)− f1(x)

t,

= lımt→0

(x + tv)T(x + tv)− xT x

t,

= lımt→0

xT x + 2t xT v + t2 vT v− xT x

t,

= 2 xT v,

de donde,

∇ f1(x) = 2 x.

Para calcular el gradiente de f2, dado que A es simétrica por el literal c) del EJERCICIO 2.2 y la

derivada de la composición de funciones, tenemos que

∇ f2(x) = 2(xT A x)(xT A x)′ = 4 xT A x A x

Por lo tanto

∇ f (x) = xT + σxT A x A x.

Calculamos la hessiana de f , ∇2 f (x), como sigue

∇2 f (x) v = lımt→0

x + t v + σ((xT + t vT)A(x + t v)A(x + t v)− x− σxT A x A x)

t

= lımt→0

t v + σ[

(xT A x + 2 t xT A v + t2 vT A v)(A x + t A v)− xT x A A x]

t

87

= lımt→0

t v + σ(

3t xT A v A x + 3t2 vT A v A v + t3 vT A v A v)

t

= (I + 3 σA x xT A)v,

de donde,

∇2 f (x) = I + 3 σA x xT A

Al implementar las funciones f , ∇ f y ∇2 f y al aplicar el método de Newton globalizado (7.0.1)

a (7.0.3). En ambos casos; es decir, cuando σ1 = 1 y σ2 = 104 se tiene que, con los puntos de

inicialización x1 y x2, al algoritmo le toma 8 y 19 iteraciones, respectivamente, para converger a

la solución

xT = [0, 0, 0, 0].

Obtenemos los siguientes gráficas y tablas de error vs iteraciones:

• Newton Globalizado con σ1 = 1

Figura 6.1: Tabla Newton Globalizado con σ1 = 1 comparando las tolerancias en los dos puntos de inicia-lización en cada iteración.


1 2 3 4 5 6 7 8

Iteraciones

0

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

Err

or

sigma1 = 1

x1 = [cos(70), sin(70), cos(70), sin(70)]

x2 = [cos(50), sin(50), cos(50), sin(50)]

Figura 6.2: Gráfica Newton Globalizado con σ1 = 1 comparando el error (diferencia entre el valor de lafunción real y el valor de la función en cada iteración) entre los dos puntos de inicialización.

• Newton Globalizado con σ1 = 104

Figura 6.3: Tabla Newton Globalizado con σ2 = 104 comparando las tolerancias en los dos puntos deinicialización en cada iteración.

89

0 2 4 6 8 10 12 14 16 18 20

Iteraciones

0

0.5

1

1.5

2

2.5

3

3.5

4

4.5

Err

or

104 sigma2 = 10

4

x1 = [cos(70), sin(70), cos(70), sin(70)]

x2 = [cos(50), sin(50), cos(50), sin(50)]

Figura 6.4: Gráfica Newton Globalizado con σ2 = 104 comparando el error (diferencia entre el valor de lafunción real y el valor de la función en cada iteración) entre los dos puntos de inicialización.

EJERCICIO 6.4. Sea

f (x, y) =12(x2 + y2) exp

(

x2 − y2)

.

Usando el punto inicial [x0, y0]T = [1, 1]T , encuentre los mínimos locales de f usando el

método globalizado de Newton. Repita el experimento con la matriz modificada de Newton

∇2 f (x) + 3 I, es decir, (∇2 f (x) + 3 I) dk = −∇ f (xk).

Solución. • Encontraremos los mínimos locales de f usando el método globalizado de New-

ton, para ello, calculamos el gradiente y la Hessiana de f para cualquier v = [x, y] ∈ R2 y

obtenemos

∇ f (v) = [exp(x2 − y2) x(x2 + y2 + 1), exp(x2 − y2) y(1− x2 − y2)]

y

∇2 f (v) =

ex2−y2(2x4 + 2x2y2 + 5x2 + y2 + 1) x ex2−y2 (−2x2y− 2y3)

ex2−y2y(

−2x3 − 2xy2) ex2−y2(2 y4 + 2x2y2 − 5y2 − x2 + 1)

T

.

Considerando los códigos 7.0.4 implementados en MATLAB con el punto de inicializa-

ción (x0, y0) = (1, 1)T , en 2551633 iteraciones el algoritmo encuentra el mínimo x∗ =


[3.4067x 10−7, 4.6281]T ≈ [0, 4.63]T . La gráfica del punto x en la curva f es el siguiente:

Figura 6.5: Gráfica Newton Globalizado aplicado a f con el punto de inicialización (1, 1).

A continuación podemos ver el gráfico de iteraciones vs. error y el punto x en la curva f

con el método de Newton globalizado:

0 0.5 1 1.5 2 2.5 3

Iteraciones 106

10-8

10-6

10-4

10-2

100

Err

or

(1/2)*(x12+x2

2)*exp(x1

2-x2

2)

Figura 6.6: Iteraciones vr. error con el Método de Newton sin modificar

• Implementando el Método de Newton Modificado, considerando el punto del literal ante-

rior, en 1232396 iteraciones se obtiene el mínimo de la función. A continuación, se puede

observar el gráfico iteraciones vs. error del Método de Newton Modificado:

91

0 2 4 6 8 10 12 14

Iteraciones 105

10-8

10-6

10-4

10-2

100

Err

or

(1/2)*(x12+x2

2)*exp(x1

2-x2

2)

Figura 6.7: Iteraciones vs. error con el Método de Newton Modificado

EJERCICIO 6.5. Sea B ∈ Rn×n una matriz definida positiva cuyos valores propios son (λi)

ni=1,

donde 0 < λ1 ≤ λ2 ≤ · · · ≤ λn. Pruebe que la función Ψ(B) = Tr(B)− ln(det(B)), se puede

escribir como

Ψ(B) =n

∑i=1

(λi − ln(λi)),

use esta expresión para probar que Ψ(B) > 0.

Demostración. Tenemos que

Ψ(B) = Tr(B)− ln(det(B)),

ahora, recordemos que

Tr(B) =n

∑i=1

λi y det(B) =n

∏i=1

λi,

así, se tiene que

Ψ(B) =n

∑i=1

λi − ln

(

n

∏i=1

λi

)

=n

∑i=1

λi −n

∑i=1

ln(λi)

=n

∑i=1

(λi − ln(λi)),


es decir,

Ψ(B) =n

∑i=1

(λi − ln(λi)).

Ahora, notemos que

λi > ln(λi),

para cada i ∈ 1, . . . , n, es decir,

λi − ln(λi) > 0,

para cada i ∈ 1, . . . , n, con esto, se sigue que

Ψ(B) =n

∑i=1

(λi − ln(λi)) > 0.

EJERCICIO 6.6. Sea Hkk∈N una sucesión de matrices que satisfacen la condición siguiente

m ‖q‖2 ≤ qT Hk q ≤ M ‖q‖2 , (6.7)

para cada q ∈ Rn y k > 0, donde 0 < m < M. Pruebe que Hk es invertible, para todo k > 0 y

que pk := −H−1k ∇ f (xk) es una dirección de descenso que satisface la condición del ángulo.

Demostración. Notemos que para cada q ∈ Rnr 0,

m ‖q‖2 ≤ qT Hk q ≤ M ‖q‖2 ,

para cada k ∈ N, de donde, dado que ‖q‖ > 0 y m > 0, se sigue que

qT Hkq > 0,

para cada k ∈ N y para todo q ∈ Rnr 0, es decir, para cada k ∈ N, Hk es una matriz definida

positiva, así,

det(Hk) > 0,

para todo k ∈ N, con esto, podemos concluir que Hk es invertible para cada k ∈ N.

Ahora, vamos a demostrar que

pk = −H−1k ∇ f (xk),

para cada k ∈ N es una dirección de descenso que satisface la condición de ángulo, es decir,

93

debemos probar que existe η ∈ ]0, 1[ tal que

−∇ f (xk)T pk ≥ η ‖∇ f (xk)‖ ‖pk‖ .


− ∇ f (xk)T pk

‖∇ f (xk)‖ ‖pk‖=∇ f (xk)

T H−1k ∇ f (xk)

‖∇ f (xk)‖ ‖pk‖

=

(

Hk H−1k ∇ f (xk)

)TH−1

k ∇ f (xk)

‖∇ f (xk)‖ ‖pk‖

=

(

H−1k ∇ f (xk)

)THk

(

H−1k ∇ f (xk)

)

‖∇ f (xk)‖ ‖pk‖,

de donde, dado que

(

H−1k ∇ f (xk)

)THk

(

H−1k ∇ f (xk)

)

≥ m∥

∥

∥H−1

k ∇ f (xk)∥

∥

∥

2,

se sigue que

− ∇ f (xk)T pk

‖∇ f (xk)‖ ‖pk‖≥

m∥

∥

∥H−1k ∇ f (xk)

∥

∥

∥

2

‖∇ f (xk)‖∥

∥

∥H−1

k ∇ f (xk)∥

∥

∥

=m∥

∥

∥H−1k ∇ f (xk)

∥

∥

∥

‖∇ f (xk)‖. (6.8)


‖∇ f (xk)‖2 =∥

∥

∥Hk H−1

k ∇ f (xk)∥

∥

∥

2

=(


)T (


)

=(

H−1k ∇ f (xk)

)TH2

k

(

H−1k ∇ f (xk)

)

,

de donde, dado que

(

H−1k ∇ f (xk)

)TH2

k

(

H−1k ∇ f (xk)

)

≤ M2∥

∥

∥H−1k ∇ f (xk)

∥

∥

∥

2,

se sigue que

‖∇ f (xk)‖ ≤ M∥

∥

∥H−1

k ∇ f (xk)∥

∥

∥,

lo cual, es equivalente a tener que

1‖∇ f (xk)‖

≥ 1

M∥

∥

∥H−1k ∇ f (xk)

∥

∥

∥

. (6.9)


Luego, combinando (6.8) y (6.9), obtenemos que

− ∇ f (xk)T pk

‖∇ f (xk)‖ ‖pk‖≥

m∥

∥

∥H−1k ∇ f (xk)

∥

∥

∥

M∥

∥

∥H−1

k ∇ f (xk)∥

∥

∥

=m

M,


−∇ f (xk)T pk ≥

m

M‖∇ f (xk)‖ ‖pk‖ ,

de donde, tomando η = mM ∈ ]0, 1[, se sigue el resultado.

EJERCICIO 6.7. Demostrar que si la fórmula DFP hace que las matrices Hk sean definidas

positivas, entonces para todo k ∈ N, δTk yk > 0.

Demostración. Supongamos que la matrices obtenidas mediante la actualización DFP son defini-

das positivas, es decir,

yT Hky > 0,

para todo y ∈ Rn y para todo k ∈ N.

Por otro lado, por la actualización DFP, sabemos que

Hk+1 = Hk +δkδT

k

δTk yk

− HkykyTk Hk

yTk Hkyk

,

para cada k ∈ N, con esto, tenemos que

Hk+1yk = Hkyk +δk

(

δTk yk

)

δTk yk

− Hkyk

(

yTk Hkyk

)

yTk Hkyk

= Hkyk + δk − Hkyk = δk,

para cada k ∈ N. Luego, se sigue que

yTk Hk+1yk = yT

k δk > 0,

para todo k ∈ N.

EJERCICIO 6.8. Sea B una matriz simétrica, entonces existe λ ≥ 0 tal que B + λI es definida

positiva.

Demostración. Consideremos dos casos:

95

1. Si B es una matriz simétrica definida positiva, entonces basta tomar λ = 0 y se sigue el

resultado.

2. Ahora, supongamos que B no es definida positiva, dado que B es una matriz simétrica

todos sus valores propios son reales y además, existen Q, D ∈ Rn×n tales que

B = QDQT ,

donde D = diag(λ1, . . . , λn).

Sin pérdida de generalidad, supongamos que

λ1 ≤ λ2 ≤ · · · ≤ λn,

y además que λ1 ≤ 0, así, tomemos

λ = −λ1 + ε > 0,

donde ε > 0, es arbitrario pero fijo, así, notemos que

λi + λ ≥ ε > 0,

para i ∈ 1, . . . , n. Con esto, tenemos que

B + λI = QAQT + λQQT = Q(A + λI)QT ,

donde, los valores propios son

0 < (λ1 − λ1) + ε ≤ (λ2 − λ1) + ε ≤ · · · ≤ (λn − λ1) + ε,

por lo tanto, B + λI es simétrica definida positiva.

Con esto, hemos probado que existe λ ≥ 0 tal que B + λI es definidad positiva.


f : R −→ R

x 7−→ −14

x4.

Para cualquier valor inicial x0, pruebe que el método de Newton converge hacia el máximo

x∗ = 0 de f .


Demostración. Consideremos la función:

g : R −→ R

x 7−→ 14

x4,

vamos a demostrar que el método de Newton converge hacia el mínimo x∗ = 0, en efecto,

tenemos que

∇g(x) = x3 y ∇2g(x) = 3x2,

de donde, la direcciones del Método de Newton vienen dadas por

pk = −x3

k

3x2k

= − xk

3,

para cada k ∈ N. Así, se tiene que

xk+1 = xk −xk

3

=2xk

3,

para todo k ∈ N, iterativamente, obtenemos que

xk =

(

23

)k

x0,

para cada k ∈ N, de donde,

lımn→+∞

(

23

)n

x0 = 0.

Con esto hemos probado que el método de Newton converge al mínimo x∗ = 0 de g, es decir,

hemos demostrado el mencionado que método converge al máximo de f .

EJERCICIO 6.10. Sea f dos veces continuamente diferenciable, donde∇2 f es Lipschitz conti-

nua y∇2 f (x∗) una matriz definida positiva. Sea ρs el valor propio más pequeño de∇2 f (x∗).

Encuentre ρ tal que ∇2 f (x) sea definida positiva para todo x ∈ B(x∗, ρ).

Demostración. Sean x ∈ B(x∗, ρ) y y ∈ Rn, vamos a determinar el valor de ρ, dado que ρs > 0 es

el valor propio más pequeño, tenemos que

yT∇2 f (x)y = yT∇2 f (x)y− yT∇2 f (x∗)y + yT∇2 f (x∗)y

≥ yT(∇2 f (x)−∇2 f (x∗))y + ρs ‖y‖2 ,

97

por otro lado, puesto que ∇2 f es Lipschitz continua, sabemos existe L > 0, tal que

∥

∥

∥∇2 f (x∗)−∇2 f (x)

∥

∥

∥≤ L ‖x∗ − x‖ ,

ahora, dado que x ∈ Bρ(x∗), de la desigualdad precedente, tenemos que

∥

∥

∥∇2 f (x∗)−∇2 f (x)∥

∥

∥ < Lρ,


yT∇2 f (x)y > (ρs − Lρ) ‖y‖2 ,

de donde, para que ∇2 f (x) sea definida positiva, se debe tener que

ρs − Lρ > 0,

luego, se sigue que

ρ <ρs

L.

EJERCICIO 6.11. Sea f la función,

f : R −→ R

x 7−→ x2,

y ε f (x) =sen(100x)

10. Dado x0 = 1, encuentre un mínimo local de f + ε f con el método de

Newton.

Solución: Tenemos que

∇g(x) = ∇ f (x) +∇ε f (x) = 2x + 10 cos(100x) y ∇2g(x) = 2− 1000 sen(100x),

de donde, para k = 1, se sigue que

p0 = −0.0209, x1 = 0.9791 y f (x1) = 0.9089.

Iterativamente, para k = 4, tenemos que

p3 = 0.00011352, x4 = 0.98761352 y f (x4) = 0.8774,

finalmente, para k = 5, obtenemos que

p4 = −0.00000013575, x5 = 0.9876133843 y f (x5) = 0.8774.


Con esto, se tiene que

∇ f (x5) = 0.000000047145 ≈ 0 y ∇2 f (x5) = 982.2983 > 0,

es decir,

x5 = 0.9876133843,

es un punto estacionario de f .


f : R2 −→ R

(x, y) 7−→ 16x4 − 16x3 + 6x2 − x +1

16+ 3x2y2.

a) ¿Puede aplicar Newton iniciando en x0 =[

12 , 1]T

? Justifique su respuesta.

b) Modifique la Hessiana∇2 f (xk)+µI para aplicar este algoritmo. ¿Qué valor seleccionó

de µ. ¿Por qué?

c) Compruebe que también se puede usar los valores propios para determinar el valor

de µ.

d) Proponga un algoritmo que determine µ tomando en cuenta el valor de los valores

propios.

Solución: a) Vamos a calcular el gradiente de f , tenemos que

∇ f (x, y) = [64x3 − 48x2 + 12x− 1 + 6xy2, 6x2y]T ,

de donde, la matriz Hessiana, viene dada por

H(x, y) =

192x2 + 6y2 − 96x + 12 12xy

12xy 6x2

,

de donde,

H

(

12

, 1)

=

18 6

6 32 ,

.

Luego, el determinante de la matriz precedente es

∣

∣

∣

∣

H

(

12

, 1)∣

∣

∣

∣

= −9 < 0,

99

por lo tanto, no se puede aplicar el método de Newton iniciando en x0 =

[

12

, 1]T

.

b) Consideremos u = 112 > 0, pues con este valor tenemos que la matriz simétrica

∇2 f (x0) +112

I,

es definida positiva, en efecto, se tiene que

∇2 f (x0) +112

I =

472 6

6 7

,

de donde,

det(

∇2 f (x0) +112

I

)

=2572

> 0.

c) Vamos a calcular los valores propios de la matriz Hessiana, tenemos que

|λI − H| =

∣

∣

∣

∣

∣

∣

λ− 18 −6

−6 λ− 32

∣

∣

∣

∣

∣

∣

= λ2 − 392

λ− 9 = 0.

Con esto, tenemos que los valores propios son:

λ1 =39 + 3

√185

4≈ 19.95 y λ2 =

39− 3√

1854

≈ −0.45,

así, tomemos µ = 0.5 y se sigue que

∇2 f (x0) + µI =

372 6

6 2

,

es definida positiva, en efecto, tenemos que

∣

∣

∣∇2 f (x0) + µI∣

∣

∣ = 1 > 0.

d) Supongamos que A es una matriz simétrica no definida positiva, por el Ejercicio (6.8), consi-

deremos el siguiente algoritmo:

• Calcular los valores propios de A,

• Tomar

u > max1≤k≤n

|λk|,

donde, λk para cada k ∈ 1, . . . , n, es el valor propio de A.


EJERCICIO 6.13. Sea f : Rn → R una función dos veces continuamente diferenciable y

considere la iteración de Newton siguiente:

∇2 f (xk) dk = −∇ f (xk) y xk+1 = xk + dk, (6.10)

para cada k ∈ N.

Sea M ∈ Rn×n una matriz no singular y v ∈ R

n fijo. Pruebe que aplicando el método de

Newton al problema

mıny∈Rn

h(y) = f (My + v), (6.11)

con punto inicial y0 = M−1 (x0 − v), genera la sucesión ykk∈N con yk = M−1(xk − v),

donde xkk∈N corresponde a la sucesión generada por (6.10), desde un punto inicial x0,

esta propiedad se conoce como Invariante por Escalonamiento.

Demostración. En primer lugar, notemos que

∇h(x) = MT∇ f (My + v) y ∇h2(x) = MT∇ f 2(My + v)M.

El Método de Newton, para la función h, viene dado por

∇2h(Myk + v)pk = −∇h(Myk + v) y yk+1 = yk + pk,

para todo k ∈ N. Así, tenemos que

yk+1 = yk −(

∇2h(Myk + v))−1∇h(Myk + v)

= yk −(

MT∇ f 2(Myk + v)M)−1

MT∇ f (Myk + v)

= yk −M−1∇(

f 2(Myk + v))−1∇ f (Myk + v),

para cada k ∈ N. La demostración de este resultado la realizaremos por inducción, en efecto,

para k = 0, se tiene que

y1 = y0 −M−1(

∇ f 2(My0 + v))−1∇ f (My0 + v),

dado que y0 = M−1(x0 − v), obtenemos que

y1 = M−1(x0 − v)−M−1(

∇ f 2(MM−1(x0 − v) + v))−1∇ f (MM−1(x0 − v) + v)

101

= M−1(x0 − v)−M−1(

∇ f 2(x0))−1∇ f (x0),

ya que

d0 = −(

∇ f 2(x0))−1∇ f (x0) y d0 = x1 − x0,

obtenemos que

y1 = M−1(x0 − v) + M−1d0 = M−1(x0 − v) + M−1(x1 − x0) = M−1(x1 − v).

Supongamos que el resultado es válido para n = k, es decir,

yk = M−1(xk − v),

vamos a demostrar que el resultado se cumple para n = k + 1. En efecto, tenemos que

yk+1 = yk −M−1(

∇ f 2(Myk + v))−1∇ f (Myk + v),

de donde, dado que

dk = −(

∇2 f (xk))−1∇ f (xk) y dk = xk+1 − xk,

se sigue el resultado

yk+1 = yk + M−1dk = M−1(xk − v) + M−1(xk+1 − xk) = yk + M−1(xk+1 − v).

EJERCICIO 6.14. Sea f : R2 → R una función dos veces continuamente diferenciable. Con-

sidere el siguiente método de tipo Newton para hallar el mínimo de f en R2 :

Mk sk = −∇ f (xk), xk+1 = xk + sk, (6.12)

donde la matriz Mk, está dada por

Mk =

∂2 f (xk)

∂x21

0

0 ∂2 f (xk)

∂x22

. (6.13)

donde, xk = [xk1, xk

2]T es el k−ésimo término iterado.

Si x = [0, 0]T , pruebe que si lımk→+∞

xk = x, entonces la convergencia del método tipo

Newton es superlineal.


Demostración. Por la Condiciones de Dennis - Moré, sabemos

∥

∥

∥

(

Mk −∇2 f (xk))

(xk+1 − xk)∥

∥

∥= o(‖xk+1 − xk‖),

implica convergencia superlineal. Tenemos que

Mk −∇2 f (xk) =

∂2 f (xk)

∂x21

0

0 ∂2 f (xk)

∂x22

−

∂2 f (xk)

∂x21

∂2 f (xk)∂x∂y

∂2 f (xk)∂y∂x

∂2 f (xk)

∂x22

=

=

0 − ∂2 f (xk)∂x∂y

− ∂2 f (xk)∂y∂x 0

,

así, consideremos el operador T, tal que

T =

0 − ∂2 f∂x∂y

− ∂2 f∂y∂x 0

,


Mk −∇2 f (xk) = Txk,

para cada k ∈ N, de donde, dado que f ∈ C2, T es un operador acotado, así, se sigue que

∥

∥

∥Mk −∇2 f (xk)∥

∥

∥ = ‖T(xk))‖ ≤ ‖T‖ ‖xk‖ = ‖T‖ ‖xk − x‖ . (6.14)

Sea ε > 0, dado que lımn→+∞

xn = x, sabemos existe N ∈ N tal que

∥

∥

∥Mk −∇2 f (xk)

∥

∥

∥<

ε

‖T‖ ,

para cada k ≥ N, así, junto con (6.14), obtenemos que

∥

∥

∥Mk −∇2 f (xk)∥

∥

∥ < ε. (6.15)


∥

∥

∥

(

Mk −∇2 f (xk))

(xk+1 − xk)∥

∥

∥ ≤∥

∥

∥Mk −∇2 f (xk)∥

∥

∥ ‖xk+1 − xk‖ ,

para cada k ∈ N, de donde, junto con (6.14), se sigue que

∥

∥

∥

(

Mk −∇2 f (xk))

(xk+1 − xk)∥

∥

∥< ε ‖xk+1 − xk‖ ,

para cada k ≥ N, con lo cual, hemos probado que

∥

∥

∥

(

Mk −∇2 f (xk))

(xk+1 − xk)∥

∥

∥ = o(‖xk+1 − xk‖).

103

EJERCICIO 6.15. Sean H ∈ Rn×n una matriz regular y u, v ∈ R

n vectores dados. Demuestre

que la matriz H + uvT es regular siempre que 1 + vT H−1u 6= 0. Además pruebe que

(H + uvT)−1 =

(

I − H−1uvT

1 + vT H−1u

)

H−1.

(Esta identidad se la conoce como la fórmula de Sherman-Morrison)

Demostración. Para la primera parte, gracias a la identidad det(I + H−1uvT) = (1 + vT H−1u) ,

tenemos que

det(H + uvT) = det(H)det(I + H−1uvT),

= det(H)(1 + vT H−1u),

de donde, puesto que det(H) 6= 0, se sigue que H + uvT es no singular, si

1 + vT H−1u 6= 0.

Sean x, y ∈ Rn, consideremos el sistema

(H + uvT)x = y,

tenemos que

Hx + uvTx = y,

de donde,

x = H−1y− H−1uvTx, (6.16)

ahora, tomemos s = vTx ∈ R, de la igualdad precedente, tenemos que

x = H−1y− H−1us;

por otro lado, notemos que

s = vTx = vT H−1y− vT H−1us,

de donde,

(1 + vT H−1u)s = vT H−1y,

es decir,

s =vT H−1y

1 + vT H−1u,


luego, combinado la igualdad precedente con (6.16), obtenemos que

x = H−1y− H−1u

(

vT H−1y

1 + vT H−1u

)

=

(

H−1 − H−1uvT H−1

1 + vT H−1u

)

y,

con esto, hemos probado que

(H + uvT)−1 = H−1 − H−1uvT H−1

1 + vT H−1u=

(

I − H−1uvT

1 + vT H−1u

)

H−1.

EJERCICIO 6.16. Usando la fórmula de Sherman-Morrison, pruebe que la inversa de la ma-

triz HSR1+ correspondiente al SR1, está dada por

B+ = B +(s− By)(s− By)T

(s− By)Ty.

Demostración. Consideremos

u = yk − Bksk y v =u

(yk − Bksk)Tsk=

yk − Bksk

(yk − Bksk)Tsk,

para cada k ∈ N.

Ahora, para cada k ∈ N, notemos que

Bk + uvT = Bk + (yk − Bksk)

(

yk − Bksk

(yk − Bksk)Tsk

)T

= Bk +(yk − Bksk)(yk − Bksk)

T

(yk − Bksk)Tsk

= Bk+1.

Por otro lado, para cada k ∈ N, por la fórmula de Sherman-Morrison, obtenemos que

Hk+1 = B−1k+1 = B−1

k −B−1

k uvT B−1k

1 + vTB−1k u

,

de donde, para cada k ∈ N, junto con (??), se sigue que

Hk+1 = Hk −(Hkyk − sK)(Hkyk − sK)

T

(yk − Bksk)Tsk + (yk − Bksk)T(Hkyk − sk)

= Hk −(sK − Hkyk)(sK − Hkyk)

T

(yk − Bksk)T Hkyk

= Hk +(sK − Hkyk)(sK − Hkyk)

T

(sk − Hkyk)Tyk,

105

es decir, para cada k ∈ N, hemos probado que

Hk+1 = Hk +(sK − Hkyk)(sK − Hkyk)

T

(sk − Hkyk)Tyk.

EJERCICIO 6.17. Considere la función cuadrática

f : Rn −→ R

x 7−→ f (x) =12

xT A x + bT x + c,

donde, A ∈ Rn×n es simétrica y definida positiva. Prueba que el método SR1 termina en

n + 1 pasos, es decir; Hn = (∇2 f )−1.

Sugerencia: Considere que (δi)n−1i=0 son linealmente independientes y pruebe, por induc-

ción en k, que Hk yj = δj, para j ∈ 0, 1, . . . , k − 1, separando los casos j < k y j = k. La

actualización SR1 está dada por Hk+1 = Hk +(δk−Hk yk)(δk−Hk yk)

T

(δk−Hk yk)T yk.

Demostración. En primer lugar, notemos que

∇ f (x) = Ax + b,

de donde,

∇2 f (x) = A.

Vamos a usar el hecho de que

yk = Aδk, (6.17)

para cada k = 0, 1, . . . , n− 1.

Para k = 1, por la fórmula de actualización del SR1, tenemos que

H2 = H1 +(δ1 − H1 y1)(δ1 − H1 y1)

T

(δ1 − H1 y1)T y1,

de donde, se tiene que

H2y1 = H1y1 +(δ1 − H1y1)

[

(δ1 − H1y1)Ty1]

(δ1 − H1y1)Ty1

= H1y1 + δ1 − H1y1

= s1δ1,


Para k = 0, es fácil ver que H2 y0 = δ0. Ahora, supongamos que el resultado es válido para

n = i ≥ 1, vamos a demostrar que el resultado se cumple para n = i + 1. En efecto, tenemos que

Hi+1yj = Hiyj +(δi − Hi yi)(δi − Hi yi)

T

(δi − Hi yi)T yiyi. (6.18)

Consideremos los siguientes casos:

1. Si j < 1, por (6.17), tenemos que

(δi Hiyi)Tyj = δT

i yj − yTi Hiyj

= δTi Aδj − δT

i Aδj = 0.

Luego, junto con (6.18) y por hipótesis de inducción, obtenemos que

Hi+1yj = δj.

Ahora, si i = j, tenemos que

Hi+1yi = Hiyi +(δi − Hi yi)

[

(δi − Hi yi)T]

yi

(δi − Hi yi)T yi= δi.

Con esto, podemos concluir que

Hk Aδj = δj,

de donde, dado que (δi)ni=0 son linealmente independientes, obtenemos que

Hk = A−1 =(

∇2 f (x))−1

.

EJERCICIO 6.18. Considere la actualización del BFGS

Bk+1 = Bk +yk yT

k

yTk δk

− Bk δk δTk Bk

δTk Bk δk

, (6.19)

para todo k ∈ N, pruebe que

tr(Bk+1) = tr(Bk)−‖Bk δk‖2

δTk Bk δk

‖yk‖2

yTk δk

, (6.20)

y que

det(Bk+1) = det(Bk)yk δk

δTk Bk δk

. (6.21)

107

Demostración. • Vamos a probar (6.20), para ello, dado que la traza es una función lineal,

tenemos que

tr(Bk+1) = tr(Bk) +1

yTk δk

tr(yk yTk )−

1δT

k Bk δk

tr(Bk δk δTk Bk),

para todo k ∈ N. Además, como tr(u uT) =n

∑i=1

u2i = ‖u‖2 , se sigue que

tr(Bk+1) = tr(Bk)−1

δTk Bk δk

‖Bk δk‖2 +‖yk‖2

yTk δk

,

para todo k ∈ N.

• Vamos a probar (6.21), para ello, recordemos las siguientes propiedades del determinante.

Para todo u, v ∈ Rn, se tiene que

det(I + u vT) = 1 + vT u

y, de manera más general

det(I + x yT + u vT) = (1 + yT x)(1 + vT u)− (xT v)(yT u). (6.22)

Podemos reescribir (6.19) como sigue

Bk+1 = Bk

(

I +B−1

k yk yTk

yTk δk

− δk(Bk δk)T

δTk Bk δk

)

,

para todo k ∈ N. Ahora, tomemos

x = B−1k yk, y =

yk

yTk δk

, u = − δk

δTk Bk δk

y v = Bkδk,

para todo k ∈ N. Aplicando (6.22) y el hecho de que det(AB) = det(A)det(B), se tiene

que

det(Bk+1) = det(Bk) det(I + x yT + u vT),

=

[

det(Bk)

(

1 +yT

k

yTk δk

B−1k yk

)(

1− δTk Bk

δk

δTk Bkδk

)

−(

yTk B−1

k Bkδk

)

(

− yTk

yTk δk

δk

δTk Bkδk

)]

,

= det(Bk)

[(

1 +yT

k B−1k yk

yTk δk

)(

1− δTk Bk δk

δTk Bk δk

)

+

(

yTk δk

δTk Bk δk

)]

,

= det(Bk)

[(

1 +yT

k B−1k yk

yTk δk

)

× 0 +

(

yTk δk

δTk Bk δk

)]

,


= det(Bk)yT

k δk

δTk Bk δk

,

para todo k ∈ N. Por lo tanto, se sigue el resultado.

EJERCICIO 6.19. Aplicar dos iteraciones del método cuasi-Newton usando la actualización

SR1, al problema

max(x,y)∈R2

−x2 + 2y− xy

1 + x + y,

partiendo del punto x0 = (1, 1) y tomando σ = 0.1 para la búsqueda lineal de Armijo y

H0 = −I ¿Las direcciones encontradas son de descenso?

Solución: Antes de realizar el ejercicio, notemos que el problema es equivalente a resolver

mın(x,y)∈R2

x2 − 2y +xy

1 + x + y,

con H0 = I.

Vamos a determinar el gradiente de f , tenemos que

∇ f (x, y) =

[

−2x− y(1 + y)

(1 + x + y)2 , 2− x(1 + x)

(1 + x + y)2

]T

,

por el Método de Newton, para k = 0, se tiene que

H0 p0 = −∇ f (x0),

de donde,

p0 =

[

−209

,169

]T

,

ahora, vamos a determinar el valor de x1, para ello, por el Método de Armijo, para α = 116 ,

obtenemos que

0.5060 = f

(

x0 +1

16p0

)

− f (x0) ≤ γ1

16∇ f (x0)

T p0 = 0.8098,

es decir, se cumple la condición de Armijo, por lo tanto,

x1 = [1, 1]T +16

[

−209

,169

]T

=

[

3136

,109

]T

.

109

Ahora, para determinar la dirección de descenso, por el método de SR1, tenemos que

H1 = H0 +(y0 − H0δ0)(y0 − H0δ0)

T

(y0 − H0δ0)Tδ0,

donde,

y0 = ∇ f (x1)−∇ f (x2) = [0.4092, 0.0408] y δ0 = x1 − x0 = [0.8611, 1, 1111],


H1 =

1.5349 4.029

4.029 6.4035

,

luego, por el método iterativo de Newton, tenemos que

H1 p1 = −∇ f (x1) = [1.9877,−1.1915]T ,

de donde,

p1 = [−3.1319, 1.6866];

para determinar x2, tomando α = 116 , tenemos que

0.5506 = f

(

x1 +116

p1

)

− f (x1) ≤ γ1

16∇ f (x1)

T p1 = 0.9282,

así, se tiene que

x2 = [0.6653; 1.2165]T .

EJERCICIO 6.20. Verifique que la matrices dadas por:

Hk+1 = Hk +ykyT

k

yTk dk

− HkdkdTk Hk

dTk Hkdk

y

Bk+1 = Bk +(dk − Bkyk)d

Tk + dk(dk − BKyk)

T

yTk dk

− (dk − Bkyk)Tyk

(

dTk yk

)2 dkdTk ,

para todo k ∈ N.

Solución: Consideremos γk =1

yTk dk

, así, Bk+1 puede reescribirse de la siguiente forma

Bk+1 =(

I − γkδkyTk

)

Hk

(

I − γkδkyTk

)

+ γkδkδTk ,


para todo k ∈ N. Por otro lado, notemos que

Hk +ykyT

k

δTk Hkδk

− HkδkδTk Hk

δTk Hhδk

= Hk + [Hkδk yk]

1δT

k Hkδk0

0 1yT

k δk

[

dTk Hk yT

k

]T,

para todo k ∈ N. Ahora, empleando la fórmula generalizada de Sherman-Morrison con

A = Hk, u = [Hkδk yk] y vT =

1δT

k Hkδk0

0 1yT

k δk

[

dTk Hk yT

k

]T,

para todo k ∈ N, obtenemos que

Bk+1 = Bk − Bk [Hkδk yk]

I −

1δT

k Hkδk0

0 1yT

k δk

[

dTk Hk yT

k

]T

−1

·

1δT

k Hkδk0

0 1yT

k δk

[

dTk Hk yT

k

]T,

para todo k ∈ N. Con esto, tenemos que

Bk+1 = Bk − [δk Bkyk]

0 δTk yk

yTk δk yT

k (δk + Bkyk)

−1[

dTk yT

k Bk

]T

= Bk − (δk Bkyk)

−yTk (δk + Bkyk)

(δTk yk)2

1yT

k δk1

δTk yk

0

−1

[

dTk yT

k Bk

]T

= Bk −(

− δkyTk (δk + Bkyk)

(δTk yk)2

+Bkyk

δTk yk

δk

yTk δk

)

(δTk ykBk)

T

= Bk +δkyT

k (δk + Bkyk)(

δTk yk

)2 − BkykδTk + δT

k ykBk

yTk δk

,

para todo k ∈ N. De donde, dado que γk =1

yTk dk

, se sigue que

Bk+1 =(

I − γkδkyTk

)

Hk

(

I − γkδkyTk

)

+ γkδkδTk ,

para todo k ∈ N.

EJERCICIO 6.21. Invariante por escalonamiento:

Sean f : Rn → R una función dos veces continuamente diferenciable y A ∈ Rn×n una

111

matriz invertible. Además considere sk dado por un método de descenso:

Mksk = −∇2 f (xk) y xk+1 = xk + sk,

para todo k ∈ N. Aplique este método a h(y) = f (Ay + v), donde v ∈ Rn. Dado y0 =

A−1(x0 − v), demuestre que

yk = A−1(xk − v).

Demuestre que la actualización tipo BFGS es invariante por escalamiento.

Demostración. En primer lugar, tenemos que

∇h(y) = AT f (Ay + v) y ∇2h(y) = AT∇2 f (Ay + v)A.

Además, por el Método de Descenso, se tiene que

Mkdk = −∇h(yk) = −AT f (Ayk + v),

para cada k ∈ N, de donde,

dk = −Mk−1

AT f (Ayk + v),

para cada k ∈ N. Vamos a demostrar el resultado por inducción, en efecto, para k = 0, conside-

remos M0 = B0 la matriz de iteración para f y M0−1

= ATB0 A la matriz de iteración para h, se

tiene que

d0 = −(

AT B0 A)−1

AT∇ f (Ay0 + v)

= −A−1B0∇ f (Ay0 + v),

de donde, puesto que y0 = A−1(x0 − v), obtenemos que

d0 = −A−1B0∇ f (x0). (6.23)

Por otro lado, sabemos que

B0s0 = −∇ f (x0),

de donde,

s0 = −B−10 ∇ f (x0),


luego, combinando la igualdad precedente con (6.23), se sigue que

d0 = A−1s0. (6.24)

Ahora, vamos a demostrar que y1 = A−1(x1 − v), en efecto, tenemos que

y1 = y0 + A−1s0

= A−1(x0 − v) + A−1(x1 − x0)

= A−1(x1 − v),

es decir,

y1 = A−1(x1 − v).

Además, vamos a demostrar por inducción que

Bk = AT Bk A,

en efecto, para k = 1, aplicando la fórmula de actualización del BFGS, tenemos que

B1 = B0 −B0s0sT

0 B0

sT0 H0s0

+y0yT

0

yT0 s0

,

de donde, dado que

y0 = ∇ f (x1)−∇ f (x0),

se sigue que

B1 = B0 −B0s0sT

0 B0

sT0 B0s0

+(∇ f (x1)−∇ f (x0))(∇ f (x1)−∇ f (x0))

T

(∇ f (x1)−∇ f (x0))Ts0. (6.25)


B1 = B0 −B0d0dT

0 B0

dT0 B0d0

+z0zT

0

zT0 d0

= AT B0 A−(

AT B0 A)

d0dT0(

AT B0 A)

dT0 ATB0 Ad0

+(∇h(y1)−∇h(y0))(∇h(y1)−∇h(y0))

T

(∇h(y1)−∇h(y0))Td0

= AT B0 A− AT (B0 A)(

A−1s0) (

A−1s0)T (

AT B0)

(A−1s0)T

AT B0 A (A−1s0)A

+(∇h(y1)−∇h(y0))(∇h(y1)−∇h(y0))

T

(∇h(y1)−∇h(y0))T (A−1s0)

113

= AT B0 A− AT B0s0sT0 B0

sT0 B0s0

A

+AT(∇ f (x1)−∇ f (x0))(AT∇ f (x1)−∇ f (x0))

T

(AT∇ f (x1)−∇ f (x0))T A−1s0

= AT B0 A− AT B0s0sT0 B0

sT0 B0s0

A

+ AT (∇ f (x1)−∇ f (x0))(∇ f (x1)−∇ f (x0))T

(∇ f (x1)−∇ f (x0))Ts0A

= AT

(

B0 −B0s0sT

0 B0

sT0 B0s0

+(∇ f (x1)−∇ f (x0))(∇ f (x1)−∇ f (x0))

T

(∇ f (x1)−∇ f (x0))Ts0

)

A


B1 = AT B1 A.

Ahora, supongamos los resultados son válidos para n = k ∈ N, es decir,

yk = A−1(xk − v) y Bk = ATBk A,

vamos a demostrar que los resultados son válidos para n = k + 1, es decir, debemos probar que

yk+1 = A−1(xk+1 − v) y ˆBk+1 = AT Bk+1 A,

por la hipótesis de inducción, tenemos que

dk = −(

AT Bk A)−1

AT∇ f (AA−1(xk − v) + v)

= −A−1B−1k ∇ f (xk),

por otro lado, sabemos que

sk = −B−1k ∇ f (xk),

con esto, se tiene que

dk = A−1sk,

así, tenemos que

yk+1 = yk + dk

= A−1(xk − v) + A−1sk

= A−1(xk − v + sk)


= A−1(xk − vxk+1 − xk)

= A−1(xk+1 − v),

es decir,

yk+1 = A−1(xk+1 − v).

Finalmente, sabemos que

Bk+1 = Bk −BksksT

k Bk

sTk Bksk

+(∇ f (xk+1)−∇ f (xk))(∇ f (xk+1)−∇ f (xk))

T

(∇ f (xk+1)−∇ f (xk))Tsk. (6.26)


ˆBk+1 = Bk −BkdkdT

k Bk

dTk Bkdk

+zkzT

k

zTk dk

= AT Bk A−(

ATBk A)

dkdTk

(

AT Bk A)

dTk AT Bk Adk

+(∇h(yk+1)−∇h(yk))(∇h(yk+1)−∇h(yk))

T

(∇h(yk+1)−∇h(yk))Tdk

= AT Bk+1 A− AT (Bk A)(

A−1sk

) (

A−1sk

)T (AT Bk

)

(A−1sk)T

AT Bk A (A−1sk)A

+(∇h(yk+1)−∇h(yk))(∇h(yk+1)−∇h(yk))

T

(∇h(yk+1)−∇h(yk))T (A−1sk)

= AT Bk A− AT BksksTk Bk

sTk Bksk

A

+AT(∇ f (xk+1)−∇ f (xk))(AT∇ f (xk+1)−∇ f (xk))

T

(AT∇ f (xk+1)−∇ f (xk))T A−1sk

= AT Bk A− AT BksksTk Bk

sTk Bksk

A

+ AT (∇ f (xk+1)−∇ f (xk))(∇ f (xk+1)−∇ f (xk))T

(∇ f (xk+1)−∇ f (xk))TskA

= AT

(

Bk −BksksT

k Bk

sTk Bksk

+(∇ f (xk+1)−∇ f (xk))(∇ f (xk+1)−∇ f (xk))

T

(∇ f (xk+1)−∇ f (xk))Tsk

)

A


ˆBk+1 = AT Bk A.

EJERCICIO 6.22. Considere un método de descenso, para el cual, para cada k ∈ N, la direc-

ción de descenso está dada por pk = −B−1k ∇ f (xk), donde, Bk corresponde a la Hessiana en

xk o una aproximación de la misma. Si Bk no es definida positiva es posible hacer la elección

115

Bk + µI en reemplazo de Bk, donde, µ > 0 e I es la matriz identidad. ¿Qué debería satisfacer

µ para que dicho reemplazo garantice una dirección de descenso?

Demostración. Para cada k ∈ N, consideremos

Mk = BkµI,

tenemos que

Mk pk = −∇ f (xk) y ∇ f (xk)T pk < 0,

para todo k ∈ N, de donde, se sigue que

pTk Mk pk = −pT

k∇ f (xk) > 0,

para cada k ∈ N.

Sea (λn, xn)n∈Nun par propio de la sucesión de matrices (Bn)n∈N

, por el ejercicio 6.8, tene-

mos que

Mkxk = (Bk + µI) xk

= Bkxk + µxk

= λkxk + µxk

= (λk + µ)xk,

de donde, (λk + µ) > 0, con esto, obtenemos que

µ > −λk,

para cada k ∈ N, por lo tanto, para obtener una dirección de descenso, necesitamos que

µ > |mınk∈N

λk| o µ > maxk∈N

|λk|.

EJERCICIO 6.23. Considere el siguiente algoritmo Cuasi-Newton de Kleinmitchel:

1. Escoja x0 ∈ Rn, H0 simétrica y definida positiva, σ ∈ ]0, 1/2[ , ρ ∈ ]σ, 1[ , ε > 0 y fije

k = 0.

2. Repetir hasta que ‖∇ f (xk)‖ ≤ ε:


• Calcule Hk pk = −∇ f (xk),

• Calcule el paso αk > 0 mediante la regla de Wolfe - Powell,

• Actualice xk+1 = xk + αk pk,

• Actualice dk = xk+1 − xk, yk = ∇ f (xk+1)−∇ f (xk) y ρk =∇ f (xk+1)

T pk

∇ f (xk)T pk,

• Escoja γk ∈ ]0, 1− ρk[ y calcule

Hk+1 =γk

αk

[

Hk −(yk + γk∇ f (xk))(yk + γk∇ f (xk))

T

γk(1− ρk − γk)∇ f (xk)T pk

]

,

• Actualice k←− k + 1

Si f : Rn → R es continuamente diferenciable y acotada inferiormente, demuestre los si-

guiente:

a) Hk+1dk = yk, para cada k ∈ N,

b) Hkk∈Nes una sucesión de matrices simétricas y definidas positivas,

c) El algoritmo Cuasi-Newton de Kleinmithchel está bien definido.

Demostración. a) Sea k ∈ N, en primer lugar, notemos que

dk = xk+1 − xk = xk + αk pk − xk = αk pk,

con esto, se tiene que

Hk+1dk =γk

αk

[

Hkdk −(yk + γk∇ f (xk))(yk + γk∇ f (xk))

Tdk


]

. (6.27)

Por otro lado, gracias a la definición de ρk, se sigue que

αk(yk + γk∇ f (xk))T pk = αk (∇ f (xk+1)−∇ f (xk) + γk∇ f (xk))

T pk

= αk

(

ρk∇ f (xk)T pk −∇ f (xk)

T pk + γk∇ f (xk)T pk

)

= −αk (1− ρk − γk)∇ f (xk)T pk,

es decir,

αk(yk + γk∇ f (xk))T pk = −αk (1− ρk − γk)∇ f (xk)

T pk, (6.28)

para cada k ∈ N.

117

Ahora, combinando (6.27) y (6.28), obtenemos que

Hk+1dk = γk Hk pk +(yk + γk∇ f (xk)) (1− ρk − γk)∇ f (xk)

T pk

(1− ρk − γk)∇ f (xk)T pk,

= γk Hk pk + yk + γk∇ f (xk),

de donde, dado que

Hk pk = −∇ f (xk),

obtenemos que

Hk+1dk = −γk∇ f (xk) + yk + γk∇ f (xk) = yk,

para cada k ∈ N.

b) Vamos de demostrar que Hkk∈Nes una sucesión de matrices simétricas, por inducción.

Para k = 0, por hipótesis, H0 es simétrica. Supongamos que el resultado es válido para

n = k, es decir, Hk = HTk , vamos a demostrar que el resultado se cumple para n = k + 1,

es decir, debemos probar que

Hk+1 = HTk+1.


HTk+1 =

γk

αk

[

HTk −

(

(yk + γk∇ f (xk))(yk + γk∇ f (xk))T)T


]

=γk

αk

[

Hk −(yk + γk∇ f (xk))(yk + γk∇ f (xk))

T


]

= Hk+1,


HTk+1 = Hk+1,

por lo tanto, podemos concluir que Hkk∈N, es una sucesión de matrices simétricas.

Vamos a demostrar que Hkk∈Nes una sucesión de matrices definidas positivas, esto lo

haremos por inducción. En efecto, dado que H0 es simétrica y definida positiva tenemos

nuestra hipótesis de inducción; ahora, supongamos que el resultado es válido para n = k,

es decir, Hk, es simétrica y definida positiva, vamos a probar que Hk+1, también lo es. Sea

v ∈ Rnr 0 debemos probar que

vT Hk+1v > 0.



vT Hk+1v =γk

αkvT Hkv− vT (yk + γk∇ f (xk))(yk + γk∇ f (xk))

T

αk(1− ρk − γk)∇ f (xk)T pkv

=γk

αkvT Hkv−

(

yk + γk∇ f (xk)Tv)T (

yk + γk∇ f (xk)Tv)

αk(1− ρk − γk)∇ f (xk)T pk

=γk

αkvT Hkv−

∥

∥yk + γk∇ f (xk)Tv∥

∥

2

αk(1− ρk − γk)∇ f (xk)T pk,

es decir,

vT Hk+1v =γk

αkvT Hkv−

∥

∥yk + γk∇ f (xk)Tv∥

∥

2

αk(1− ρk − γk)∇ f (xk)T pk. (6.29)

Finalmente, sabemos que

vT Hkv > 0 y ∇ f (xk)T pk < 0,

y además, dado que γ ∈ ]0, 1− ρk[, tenemos que

1− ρk − γk > 0,

de donde, junto con(6.29), podemos concluir que

vT Hk+1v > 0.

c) El algoritmo Cuasi-Newton de Kleinmithchel está bien definido, debido que f es continua-

mente diferenciable y acotada inferiormente, por lo tanto, existen pasos factibles αk > 0,

para cada k ∈ N.

Además, la sucesión de matrices Hkk∈Nes una sucesión de matrices simétricas definidas

positivas, con esto, garantizamos que la direcciones obtenidas son direcciones de descenso.

CAPÍTULO 7

CÓDIGOS EN MATLAB

Los códigos fueron tomados de las clases de la laboratorio dictadas por el profesor Sergio

González y la profesora Kateryn Herrera.

7.0.1 Caso función cuadrática matricial de R4 en R

Método del descenso con búsqueda lineal de Armijo:

1 % Metodo de d e s c e n s o g e n e r a l con busqueda de a r m i j o para r e s o l v e r f u n c i o n e s

c u a d r a t i c a s de R^4 en R .

2 % Debe m o d i f i c a r f_cuad , f _ c u a d _ g r a d f y f _ h e s s i a n a .

3 % ____________________________________________________________________________

4 % Input :

5 % x : v e c t o r de i n i c i a l i z a c i o n

6 % sigma1 : v a l o r de sigma en l a f u n c i o n c u a d r a t i c a

7 % A: m a t r i z

8 % ____________________________________________________________________________

9 % Output :

10 % e r r o r : v e c t o r de e r r o r e s

11 % i t e r : numero de i t e r a c i o n e s n e c e s a r i a s

12 % ____________________________________________________________________________

13 % I n i c i a l i z a c i o n

14 function [ error , i t e r , x ]= Newton_glob_4 ( x , sigma1 ,A)

15 r e s =1; %r e s i d u o

16 i t e r =0; %i t e r a c i o n

17 t o l =1e−4; %t o l e r a n c i a

18 % ____________________________________________________________________________

19 % P a r a m e t r o s

20 beta =1/2;

21 sigma=1e−4;

22 e r r o r = [ ] ;

23 % ____________________________________________________________________________

24 while res > t o l

25 xprev=x ;

26 i t e r = i t e r +1;

119

120 Códigos en Matlab

27 p=−f _ h e s s i a n a ( x , sigma1 ,A) \f_cuad_gradf ( x , sigma1 ,A) ;

28

29 n=0;

30 armi jo =1;

31 %% % % % % % % % % % % % % % % % % % % % % % % % % %

32 % Armijo l i n e s e a r c h

33 %% % % % % % % % % % % % % % % % % % % % % % % % % %

34 while armijo >0

35 alpha =( beta ) ^(n ) ;

36 armi jo=f_cuad ( x+alpha∗p , sigma1 ,A)−f_cuad ( x , sigma1 ,A)−sigma∗alpha∗

f_cuad_gradf ( x , sigma1 ,A) ’∗p ;

37 n=n+1;

38 end

39

40 x=x+alpha∗p ’ ;

41 r e s=norm ( f_cuad_gradf ( x , sigma1 ,A) ) ;

42 e r r o r ( i t e r ) = r e s ;

43 end

7.0.2 EJERCICIO 4.2

1 c l e a r a l l ;

2 c l c ;

3 x=input ( ’ ingrese x0= ’ ) ;

4 t o l =sqr t ( eps ) ;

5 gradf=gradf_opt ( x ) ;

6 ngf=norm ( gradf ) ;

7 rho1 = 0 . 5 ;

8 roh2 = 0 . 9 ;

9 e r r = [ ] ;

10 i f ( ngf < t o l )

11 f p r i n t f ( ’ t o l e r a n c i a alcanzada ’ ) ;

12 end

13 i t e r =0;

14 ngf0=ngf ;

15 while ( ngf > t o l )

16 i t e r = i t e r +1;

17 gf=gradf_opt ( x ) ;

18 Hf=hess f_opt ( x ) ;

19 d=−Hf\gf ;

20 gd=gf ’∗d ;

21 minr=min ( rho1 , roh2∗norm ( d , 1 ) ) ;

22 i f (−gd>=minr∗norm ( d ) ^2)

121

23 p=d ;

24 else

25 p=−gf ;

26 end

27 [ arm , i t e r a r ]= armi jo_opt ( x , p ) ;

28 x=x+arm∗p ;


30 ngf=norm ( gradf/ngf0 ) ;

31 e r r ( i t e r ) =ngf ;

32 end

33

34 x1=x ( 1 )

35 x2=x ( 2 )

36 f igure ( 1 )

37 semilogy ( e r r ) ;

38 xlabel ( ’ I t e r a c i o n e s ’ ) ;

39 ylabel ( ’ Error ’ ) ;

40 t i t l e ( ’ x1^2−x1∗x2+2∗x2^2−2∗x1+exp ( x1+x2 ) ’ ) ;

41

42 x a s t =[ x1 , x2 ] ;

43 gradiente = gradf_opt ( x a s t ) ;

44 hess iana = hess f_opt ( x a s t ) ;

7.0.3 EJERCICIO 6.3

1 % Eva luador de f u n c i o n e s

2 function f =f_cuad ( x , sigma ,A)

3 % Funcion c u a d r a t i c a

4 f =(1/2)∗x∗x ’ + ( 1 / 4 ) ∗sigma ∗ ( x∗A∗x ’ ) ^2;

5 end

1 % G r a d i e n t e de l a f u n c i o n c u a d r a t i c a

2 function gf=f_cuad_gradf ( x , sigma ,A)


4 gf= x ’ + sigma∗x∗A’∗ x ’∗A’∗ x ’ ;

5 end

1 % H ess i a na de l a f u n c i o n c u a d r a t i c a

2 function gf=f _ h e s s i a n a ( x , sigma ,A)

3 I = speye ( 4 ) ;


5 gf= ( I +3∗sigma∗A∗x ’∗ x∗A) ;

6 end


1 % R e s u e l v a e l p rob l ema min f ( x )

2 % f ( x ) = ( 1 / 2 ) x ’ x + ( 1 / 4 ) s igma ( x ’ Ax ) ^2

3

4 % Codigo ( g r a f i c a s y t a b l a s ) :

5 x1 =[ cos ( 7 0 ) , sin ( 7 0 ) , cos ( 7 0 ) , sin ( 7 0 ) ] ;

6 x2 =[ cos ( 5 0 ) , sin ( 5 0 ) , cos ( 5 0 ) , sin ( 5 0 ) ] ;

7 A=[5 1 0 1/2; 1 4 1/2 0 ; 0 1/2 3 0 ; 1/2 0 0 2 ] ;

8 sigma1 = 1 ;

9 sigma2 = 10^(4) ;

10 [ err_11 , i t e r _ 1 1 , x_11 ] = Newton_glob_4 ( x1 , sigma1 ,A) ;




14

15 f igure ( 1 )

16 hold on

17 plot ( err_11 )

18 plot ( err_21 )

19 hold o f f

20 legend ( ’ x1 = [ cos ( 7 0 ) , s i n ( 7 0 ) , cos ( 7 0 ) , s i n ( 7 0 ) ] ’ , ’ x2 = [ cos ( 5 0 ) , s i n ( 5 0 ) , cos

( 5 0 ) , s i n ( 5 0 ) ] ’ )

21 t i t l e ( ’ sigma1 = 1 ’ )

22

23 f igure ( 2 )

24 hold on

25 plot ( err_12 )

26 plot ( err_22 )

27 hold o f f

28 legend ( ’ x1 = [ cos ( 7 0 ) , s i n ( 7 0 ) , cos ( 7 0 ) , s i n ( 7 0 ) ] ’ , ’ x2 = [ cos ( 5 0 ) , s i n ( 5 0 ) , cos

( 5 0 ) , s i n ( 5 0 ) ] ’ )

29 t i t l e ( ’ sigma2 = 10^4 ’ )

30 i t 1 = 1 : 8 ;

31 i t 2 = 1 : 1 9 ;

32 t_sigma1= t a b l e ( i t 1 ’ , err_11 ’ , err_21 ’ ) ;

33 t_sigma1 . P r o p e r t i e s . VariableNames = ’ i t e r a c i o n e s ’ , ’ x1 ’ , ’ x2 ’ ;

34 t_sigma2= t a b l e ( i t 2 ’ , err_12 ’ , err_22 ’ ) ;

35 t_sigma2 . P r o p e r t i e s . VariableNames = ’ i t e r a c i o n e s ’ , ’ x1 ’ , ’ x2 ’ ;

7.0.4 EJERCICIO 6.4


2 function f =f_opt ( x )

123

3 x1=x ( 1 ) ;

4 x2=x ( 2 ) ;

5 % Funcion

6 f =(1/2) ∗ ( x1^2+x2 ^2)∗exp ( x1^2−x2 ^2) ;

7 end

1 % G r a d i e n t e de l a f u n c i o n c u a d r a t i c a

2 function gf=gradf_opt ( x )

3 x1=x ( 1 ) ;

4 x2=x ( 2 ) ;

5 % Def in imos e l g r a d i e n t e

6 df1 = exp ( x1^2−x2 ^2)∗x1 ∗ ( x1^2+x2 ^2+1) ;

7 df2 = exp ( x1^2−x2 ^2)∗x2∗(1−x1^2−x2 ^2) ;

8 gf =[ df1 ; df2 ] ;

9 end

1 % H ess i a na de l a f u n c i o n c u a d r a t i c a

2 function Hf=hess f_opt ( x )

3 x1=x ( 1 ) ;

4 x2=x ( 2 ) ;

5 % Def in imos l a h e s s i a n a

6 H11=exp ( x1^2−x2 ^2) ∗ (2∗ x1^4+2∗x1^2∗x2^2+5∗x1^2+x2 ^2+1) ;

7 H12=x1∗exp ( x1^2−x2 ^2)∗(−2∗x1^2∗x2−2∗x2 ^3) ;

8 H21=exp ( x1^2−x2 ^2)∗x2∗(−2∗x1^3−2∗x1∗x2 ^2) ;

9 H22=exp ( x1^2−x2 ^2) ∗ (2∗ x2^4+2∗x1^2∗x2^2−5∗x2^2−x1 ^2+1) ;

10 Hf=[H11 H12 ; H21 H22 ] ;

11 end


2 % f ( x ) = ( 1 / 2 ) ∗ ( x1^2+x2 ^2)∗ exp ( x1^2−x2 ^2) ;

3

4 c l e a r a l l ;

5 c l c ;

6 x=input ( ’ ingrese x0= ’ ) ;

7 I = eye ( 2 ) ;

8 t o l =sqr t ( eps ) ;

9 %g r a d f = g r a d f _ o p t ( x ) ;

10 gradf=gradf_opt ( x ) +3∗ I ;

11 ngf=norm ( gradf ) ;

12 rho1 = 0 . 5 ;

13 roh2 = 0 . 9 ;

14 e r r = [ ] ;

15 i f ( ngf < t o l )

16 f p r i n t f ( ’ t o l e r a n c i a alcanzada ’ ) ;


17 end

18 i t e r =0;

19 ngf0=ngf ;

20 while ( ngf > t o l )

21 i t e r = i t e r +1;


23 Hf=hess f_opt ( x ) ;

24 d=−Hf\gf ;

25 gd=gf ’∗d ;

26 minr=min ( rho1 , roh2∗norm ( d , 1 ) ) ;

27 i f (−gd>=minr∗norm ( d ) ^2)

28 p=d ;

29 else

30 p=−gf ;

31 end

32 [ arm , i t e r a r ]= armi jo_opt ( x , p ) ;

33 x=x+arm∗p ;


35 ngf=norm ( gradf/ngf0 ) ;

36 e r r ( i t e r ) =ngf ;

37 end

38

39 x1=x ( 1 )

40 x2=x ( 2 )

41 ezsur f ( ’ (1/2) ∗ ( x1^2+x2 ^2)∗exp ( x1^2−x2 ^2) ’ ,[−x1−1,x1 +1] ,[−x2−1,x2 + 1 ] )

42 hold

43 plot ( x1 , x2 , ’ o ’ ) ;

44

45 f igure ( 2 )

46 semilogy ( e r r ) ;

47 xlabel ( ’ I t e r a c i o n e s ’ ) ;

48 ylabel ( ’ Error ’ ) ;

49 t i t l e ( ’ (1/2) ∗ ( x1^2+x2 ^2)∗exp ( x1^2−x2 ^2) ’ ) ;

7.0.5 EJERCICIO 6.2


2 function f =f_opt ( x )

3 x1=x ( 1 ) ;

4 x2=x ( 2 ) ;

5 % Funcion

6 f =x1^2+2∗x1∗x2−x2^3+2∗x2 ^2;

7 end

125

1 % G r a d i e n t e de l a f u n c i o n

2 function gf=gradf_opt ( x )

3 x1=x ( 1 ) ;

4 x2=x ( 2 ) ;

5 % Def in imos e l g r a d i e n t e

6 d1f = 2∗x1+2∗x2 ;

7 d2f = 2∗x1−3∗x2^2 +4∗x2 ;

8 gf =[ df1 ; df2 ] ;

9 end

1 % H ess i a na de l a f u n c i o n

2 function Hf=hess f_opt ( x )

3 x1=x ( 1 ) ;

4 x2=x ( 2 ) ;

5 % Def in imos l a h e s s i a n a

6 H11f = 2 ;

7 H12f = 2 ;

8 H21f = 2 ;

9 H22f = −6∗x2 +4;

10 Hf=[H11 H12 ; H21 H22 ] ;

11 end

1 % Para g r a f i c a r l a f u n c i o n

2 function [ f g r a f ]= f _ o p t _ g r a f ( x )

3 f g r a f = ’ x1^2+2∗x1∗x2−x2^3+2∗x2^2 ’ ;

4 end


2 % f ( x ) = x1^2+2∗x1∗x2−x2^3+2∗x2 ^2;

3 c l e a r a l l

4 c l c

5

6 f g r a f =f _ o p t _ g r a f ( x ) ;

7

8 x=input ( ’ ingrese vec tor i n i c i a l = ’ ) ;

9

10 t o l =0 .00000001 ;

11

12 Bf=eye ( 2 , 2 ) ;


14 ngf=norm ( gradf , 2 ) ;

15

16 i f ngf < t o l


17 f p r i n t f ( ’ t o l e r a n c i a alcanzada ’ )

18 end

19

20 i t e r =0;

21 ngf0=ngf ;

22 e r r = [ ] ;

23

24 while ngf > t o l

25 i t e r = i t e r +1;


27 p=−Bf\gf ;

28 [ arm , i t e r a r ]= wolfe_opt ( x , p ) ;

29 d=arm∗p ;

30 x1=x+d ;

31 gf1=gradf_opt ( x1 ) ;

32 y=gf1−gf ;

33 t =(2/(d ’∗y ) ) ∗ ( f_opt ( x )−f_opt ( x1 ) +(d ’∗ gf1 ) ) ;

34 i f t <0.01

35 t = 0 . 0 1 ;

36 e l s e i f t >100

37 t =100;

38 end

39

40 Bf=Bf+ t ∗ (1/( y ’∗d ) ) ∗ ( y∗y ’ ) −(1/(d ’∗ Bf∗d ) ) ∗ ( Bf ∗ (d∗d ’ ) ∗Bf ) ;

41

42 ngf=norm ( gf1 ) %/ ngf0

43 e r r ( i t e r ) =ngf ;

44 vf ( i t e r ) =f_opt ( x ) ;

45 x=x1 ;

46 end

47

48 %

49 % G r a f i c o s de f y d e l punto o p t i m a l

50 %

51 f igure ( 1 )

52 x1=x ( 1 ) ;

53 x2=x ( 2 ) ;

54

55 ezsur f ( f g r a f , [ x1−1,x1 + 1 ] , [ x2−1,x2 + 1 ] )

56 t i t l e ( ’ Gra f i cos de f y del punto optimal ’ )

57 hold

58 plot ( x1 , x2 , ’ or ’ )

59 %

60 % C o n v e r g e n c i a

127

61 f igure ( 2 )

62 semilogy ( e r r )

63 xlabel ( ’ I t e r a c i o n e s ’ )

64 ylabel ( ’ Error ’ )

65 t i t l e ( ’ Convergencia del e r r o r ’ )

7.0.6 Algoritmo: Paso de Wolfe

1 function [ arm , i t e r ]= wolfe_opt ( x , p )

2


4 gfp=gf ’∗p ;

5

6 fx=f_opt ( x ) ;

7

8 i t =1e4 ;

9

10 a =0;

11 b i n f =1e10 ;

12 a l f a =1;

13

14 i t e r =0;

15

16 while i t e r > i t

17 i t e r = i t e r +1;

18 x1=x+ a l f a ∗p ;

19 fx1=f_opt ( x1 ) ;

20 gf1=gradf_opt ( x1 ) ;

21 gfp1=gf1 ’∗p ;

22

23 i f fx1 >fx +(1 e−4)∗ a l f a ∗gfp

24 b= a l f a ;

25 a l f a = 0 .5∗ ( a+b ) ;

26 e l s e i f gfp1 <(1 e−4)∗gfp

27 a= a l f a ;

28 i f b==b i n f

29 a l f a =2∗a ;

30 else

31 a l f a = 0 .5∗ ( a+b ) ;

32 end

33 else STOP

34 end

35 end


36

37 arm= a l f a ;

Documents

OPTIMIZACIÓN I - Alephsub0...2 Deﬁniciones y Teoremas c) Si D