Universidad de la República

Facultad de Ingenierı́a
Instituto de Matemática y Estadı́stica ”Rafael Laguardia” (IMERL)

Análisis Comparativo de Métodos de

Descenso
Práctica Obligatoria 2

Autores:
Kevin Verges
Seylen Rodrı́guez

2025
1 Introducción
Este informe documenta la implementación y análisis de tres métodos de optimización
basados en descenso: paso fijo, acelerado de Nesterov y paso decreciente. Se aplican a la
función de Rosenbrock y se comparan en términos de convergencia, eficiencia y robustez.
Además, se incluyen visualizaciones bidimensionales y tridimensionales que ilustran la
topologı́a de la función objetivo.

2 Marco teórico
2.1 Convexidad y Envolvente Convexa
La convexidad juega un papel fundamental en la optimización. Las funciones convexas
tienen la propiedad deseable de que cualquier mı́nimo local es también un mı́nimo global,
y los conjuntos de subnivel {x | f (x) ≤ α} son convexos. La teorı́a de convergencia de
muchos algoritmos, incluidos los estudiados aquı́, es más sólida y ofrece mejores garantı́as
para funciones convexas. Un concepto básico relacionado es la envolvente convexa.
Definiendo un conjunto finito de puntos x1 , . . . , xk ∈ Rn , su envolvente convexa, de-
notada como Conv({x1 , . . . , xk }), es el conjunto de todas las combinaciones convexas de
estos puntos:
k
nX k
X o
C = Conv({x1 , . . . , xk }) = θi xi | θi = 1, θi ≥ 0 para todo i = 1, . . . , k .
i=1 i=1

Este conjunto C es siempre convexo, como se demuestra a continuación.

Demostración (Convexidad de la Envolvente Convexa): P Sean u, vP ∈ C. Entonces

existen coeficientes no negativos {θi }ki=1 y {ϕi }ki=1 tales que ki=1 θi = 1, ki=1 ϕi = 1, y
k
X k
X
u= θi xi , v= ϕi xi .
i=1 i=1

Consideremos un punto w en el segmento de lı́nea que une u y v, es decir, w = tu+(1−t)v

para algún t ∈ [0, 1]. Sustituyendo las expresiones para u y v:
k
X k
X k
X
w=t θi xi + (1 − t) ϕi xi = (tθi + (1 − t)ϕi )xi .
i=1 i=1 i=1

Llamemos ψi = tθi + (1 − t)ϕi . Dado que t ∈ [0, 1], (1 − t) ∈ [0, 1], y θi , ϕi ≥ 0, se tiene
que los nuevos coeficientes ψi son también no negativos (ψi ≥ 0) para todo i. Además, la
suma de estos nuevos coeficientes es:
k
X k
X k
X k
X
ψi = (tθi + (1 − t)ϕi ) = t θi + (1 − t) ϕi = t(1) + (1 − t)(1) = 1.
i=1 i=1 i=1 i=1

Puesto que w se puede expresar como una combinación convexa de los puntos originales
x1 , . . . , xk (coeficientes ψi ≥ 0 que suman 1), se concluye que w ∈ C. Por lo tanto, C es
un conjunto convexo.

1
3 Definición de problemas y funciones
Se consideran dos funciones objetivo para evaluar y comparar los métodos de descenso:

• Función de Rosenbrock: Definida en R2 como:

f (x, y) = (1 − x)2 + 100(y − x2 )2 .

Es una función no convexa clásica, famosa por su valle parabólico largo, estrecho
y de fondo plano (y = x2 ). El mı́nimo global único es f (1, 1) = 0. Su estructura
dificulta la convergencia de muchos optimizadores, ya que el gradiente tiende a
ser casi ortogonal a la dirección que lleva al mı́nimo dentro del valle, provocando
pequeños pasos o zigzags.
• Función Cuadrática Regularizada: Definida en Rm como:

f (x) = ∥Ax − b∥22 + λ∥x∥22 ,

donde x ∈ Rm , A ∈ Rn×m , b ∈ Rn , y λ > 0 es el parámetro de regularización L2

(Tikhonov). Esta función surge en problemas de mı́nimos cuadrados regularizados
(e.g., Ridge Regression). Una propiedad clave es que para λ > 0, f (x) es fuertemente
convexa. Su Hessiano es ∇2 f (x) = 2(AT A + λI), que es definido positivo. Esto
garantiza un único mı́nimo global y tasas de convergencia lineales para GD y AGD.
La constante de fuerte convexidad es µ = 2λmin (AT A + λI) y la constante de
suavidad (Lipschitz del gradiente) es L = 2λmax (AT A + λI).

4 Métodos aplicados
Se implementaron y compararon los siguientes métodos de descenso de primer orden, que
utilizan únicamente información del gradiente ∇f (x):

1. Gradiente Descendente con paso fijo (GD): Es el método más básico. La

actualización sigue la dirección opuesta al gradiente:

xk+1 = xk − α∇f (xk ),

donde α > 0 es el tamaño de paso (tasa de aprendizaje), constante en todas las

iteraciones. La elección de α es crucial: un valor demasiado grande puede causar
inestabilidad o divergencia, mientras que uno demasiado pequeño resulta en con-
vergencia lenta. La teorı́a sugiere α < 2/L para convergencia en funciones L-suaves
y convexas, pero L puede ser difı́cil de calcular, por lo que α a menudo se ajusta
empı́ricamente.
2. Descenso Acelerado de Nesterov (AGD): Introduce un mecanismo de ”mo-
mentum” para acelerar la convergencia, especialmente en problemas convexos mal
acondicionados o con valles.
yk = xk + βk (xk − xk−1 ), (Extrapolación/Momentum)
xk+1 = yk − α∇f (yk ), (Paso de gradiente en punto extrapolado)
Los coeficientes de momentum
√ βk se calculan usando una secuencia auxiliar tk :
1+ 1+4t2
−1
βk = ttkk+1 , con tk+1 = 2
k
y t0 = 1 (se asume x−1 = x0 ). Intuitivamente, yk

2
 anticipa la posición futura usando la dirección del paso anterior (xk − xk−1 ), y el
gradiente se evalúa en este punto ”adelantado”, permitiendo corregir la trayectoria
y acumular velocidad en direcciones consistentes.

3. Gradiente Descendente con paso decreciente: Utiliza un tamaño de paso que

disminuye con las iteraciones:
α0
xk+1 = xk − αk ∇f (xk ), con, por ejemplo, αk = √ .
k+1
Esta estrategia garantiza la convergencia bajoP condiciones
Pmás generales que el paso
2
fijo (e.g., condiciones de Robbins-Monro: αk = ∞, αk < ∞), siendo útil en
optimización estocástica. Sin embargo, para problemas deterministas suaves como
los aquı́ tratados, la convergencia es tı́picamente mucho más lenta que con GD con
paso fijo bien ajustado o AGD. α0 es un parámetro inicial a definir.

5 Tasas teóricas de convergencia

La teorı́a de optimización proporciona las siguientes tasas de convergencia para el error
f (xk ) − f ∗ bajo diferentes supuestos sobre f (L-suavidad y µ-fuerte convexidad):

• GD (paso fijo α ≈ 1/L):

– L-suave y convexa: O(1/k) (sublineal).

– L-suave y µ-fuertemente convexa: O(ρkGD ) con ρGD ≈ (1−µ/L) (lineal/geométrica).

• AGD (paso fijo α ≈ 1/L):

– L-suave y convexa: O(1/k 2 ) (sublineal acelerada).

p
– L-suave y µ-fuertemente convexa: O(ρkAGD ) con ρAGD ≈ (1 − µ/L) (lineal,
más rápida que GD).
√
• GD (paso decreciente αk ∝ 1/ k):

– L-suave y (fuertemente) convexa:

√ Convergencia garantizada, pero tasa sub-
∗
lineal lenta, tı́picamente O(1/ k) o peor para f (xk ) − f , aunque puede ser
O(1/k) para ∥xk − x∗ ∥2 en casos fuertemente convexos. Claramente subóptima
comparada con las tasas anteriores para problemas suaves.

Nota: La función de Rosenbrock no es convexa, por lo que estas tasas no se aplican

globalmente. Sin embargo, la función cuadrática regularizada es L-suave y µ-fuertemente
convexa, por lo que las tasas lineales para GD y AGD son directamente relevantes.

5.1 Función de Rosenbrock

Punto inicial: x0 = (−1.2, 1.0). Criterio de parada: ∥∇f (xk )∥2 < 10−6 o k > 100 000.
Los tamaños de paso se ajustaron por prueba y error:

• GD fijo: α = 10−3 , convergió en 32 077 iteraciones (0.45s).

• Nesterov (AGD): α = 10−3 , convergió en 3 916 iteraciones (0.085s).

3
 √
• Paso decreciente: α0 = 0.1, αk = α0 / k + 1, alcanzó el máximo de 100 000
iteraciones (1.61s) sin cumplir la tolerancia.

Figure 1: Convergencia en Rosenbrock: ∥xk − x∗ ∥ en escala logarı́tmica vs. iteración k.

Figure 2: Trayectorias de los tres métodos sobre curvas de nivel de Rosenbrock.

4
 AGD acelera notablemente la convergencia (8× menos iteraciones que GD) pero mues-
tra oscilaciones pronunciadas. El paso decreciente, aun tras 100000 iteraciones, apenas
reduce el error, evidenciando su lentitud en este valle mal condicionado.

5.2 Función cuadrática regularizada

Punto inicial: x0 = (5.0, −3.0). Parámetro de regularización: λ = 0.1. Estimamos la
constante de Lipschitz como

L = 2 λmax AT A + λI = 2(1 + 0.1) = 2.2,

y tomamos α = 1/L ≈ 0.45.

Los resultados fueron:

• GD fijo: α = 0.45, 120 iteraciones.

• Nesterov (AGD): α = 0.45, 40 iteraciones.

• Paso decreciente: α0 = 0.1, 500 iteraciones.

Figure 3: Convergencia en la función cuadrática regularizada: f (xk ) − f ∗ en escala

logarı́tmica vs. iteración k. Lı́nea continua: GD; lı́nea discontinua: AGD; lı́nea pun-
teada: paso decreciente.

Al ser fuertemente convexa y bien condicionada, tanto GD como AGD presentan lı́neas
rectas en escala log (convergencia
p lineal), observándose una pendiente más pronunciada
en AGD (tasa teórica 1 − µ/L frente a 1 − µ/L). El método de paso decreciente, con
tasa sublineal, requiere muchas más iteraciones para acercarse al mı́nimo.

5
5.3 Análisis de sensibilidad al tamaño de paso α
Para ilustrar la dependencia de cada método respecto al paso α, se evaluaron GD y AGD
con
α ∈ {10−2 , 10−3 , 10−4 , 10−5 },
en ambas funciones (Rosenbrock y cuadrática regularizada). Los gráficos muestran el
error ∥xk − x∗ ∥ en función de la iteración (eje vertical en escala logarı́tmica).

Figure 4: Comparativa de GD (lı́nea continua) y AGD (lı́nea discontinua) para distintos

α.

Rosenbrock:

• Para α ≥ 10−2 , AGD diverge rápidamente; GD aún converge pero con zigzag.

• El mejor compromiso para GD fue α = 10−3 : suficientemente grande para rapidez

pero estable.

• Para α ≤ 10−4 , ambos métodos convergen muy lentamente.

Función cuadrática regularizada:

• Ambos métodos son robustos en el rango [10−2 , 10−4 ].

• La elección teórica α = 1/L = 1 (parte cuadrática) converge en muy pocas itera-

ciones.

• AGD sólo presenta oscilaciones leves con α = 10−2 ; GD es monótono.

Este análisis confirma que el rango óptimo de α varı́a mucho según la función y el método,
y que una única gráfica bien construida (Fig. 4) basta para mostrarlo.
La Fig. 1 muestra que Nesterov converge mucho más rápido que GD con paso fijo
en términos del error ∥xk − x∗ ∥, aunque presenta oscilaciones pronunciadas. GD con
paso fijo converge lentamente de forma monotónica. El método de paso decreciente es
extremadamente lento. Las trayectorias (Fig. 2) ilustran el zigzag de GD en el valle,
mientras Nesterov sigue una ruta más central gracias al momentum. El paso decreciente
apenas avanza.

6
Figure 5: Mapa de calor de la función de Rosenbrock con curvas de nivel superpuestas y
su mı́nimo global

Figure 6: Superficie 3D de la función de Rosenbrock, mostrando claramente el estrecho

valle parabólico.

7
6 Análisis geométrico del Valle de Rosenbrock
Las visualizaciones (Fig. 2, 5, 6) son clave para entender el comportamiento diferencial de
los métodos en la función de Rosenbrock. El problema radica en el mal condicionamiento
efectivo dentro del valle estrecho y curvo.

• GD: El gradiente ∇f apunta predominantemente en la dirección de máxima variación

local, que es casi perpendicular a las paredes del valle. Sin embargo, la dirección
hacia el mı́nimo (1, 1) yace a lo largo del fondo del valle. Como GD sigue −∇f ,
realiza grandes correcciones ortogonales al valle (causando el zigzag) y avanza muy
lentamente a lo largo de él.

• AGD (Nesterov): El término de momentum βk (xk − xk−1 ) actúa como un prome-

dio ponderado de las direcciones de los gradientes pasados. Dentro del valle, las
componentes del gradiente que causan el zigzag tienden a cancelarse entre itera-
ciones sucesivas, mientras que la componente a lo largo del valle se refuerza. Esto
permite a Nesterov ”filtrar” las oscilaciones y acumular velocidad en la dirección
correcta, resultando en un progreso mucho más rápido.

• Paso Decreciente: Su lentitud se debe directamente a que αk → 0. No tiene

un mecanismo para adaptarse a la geometrı́a del problema, simplemente reduce su
agresividad con el tiempo, lo que es ineficiente aquı́.

El Hessiano de Rosenbrock cerca del mı́nimo está mal condicionado (ratio alto entre
valores propios máximo y mı́nimo), lo que explica por qué los métodos que no manejan
implı́cita o explı́citamente esta información de segundo orden (como GD) sufren, mientras
que la aceleración de Nesterov mitiga parcialmente este problema.

7 Conclusiones
La implementación y comparación de GD con paso fijo, AGD (Nesterov) y GD con paso
decreciente en las funciones de Rosenbrock y cuadrática regularizada permite extraer las
siguientes conclusiones:

• Eficiencia Superior de Nesterov: AGD demostró ser el método más eficiente en

ambos escenarios, requiriendo significativamente menos iteraciones para alcanzar la
convergencia, tanto en el problema no convexo y mal condicionado de Rosenbrock
como en el fuertemente convexo cuadrático. Esto valida empı́ricamente las ventajas
teóricas de la aceleración de Nesterov.

• Compromiso de GD Fijo: GD con paso fijo es simple de implementar, pero su

rendimiento depende fuertemente de una buena elección del tamaño de paso α. Es
notablemente lento en el valle de Rosenbrock debido al zigzagging causado por el
mal condicionamiento local.

• Lentitud del√Paso Decreciente: Aunque teóricamente robusto, el paso decre-

ciente αk ∝ 1/ k es muy lento en la práctica para problemas deterministas suaves,
siendo superado ampliamente por los otros dos métodos. Su utilidad principal reside
en contextos estocásticos o con ruido.

8
 • Costo Computacional vs Iteraciones: Dado que el costo por iteración está
dominado por el cálculo del gradiente (similar para los tres métodos), la reducción
en el número de iteraciones lograda por AGD se traduce directamente en una menor
tiempo de ejecución total.

• Importancia de la Visualización: Las gráficas de convergencia (error vs it-

eración) y las visualizaciones geométricas (trayectorias, contornos, superficie 3D) son
herramientas esenciales para comprender y comparar el comportamiento dinámico
de los algoritmos de optimización.

En conclusión, para la optimización de funciones diferenciables donde el cálculo del gradi-

ente es factible, el método Acelerado de Nesterov representa una mejora sustancial sobre el
Gradiente Descendente estándar, ofreciendo convergencia mucho más rápida con un ligero
aumento en la complejidad de implementación. La elección entre ellos y otros métodos
dependerá del problema especı́fico, la disponibilidad de información (Hessiano, etc.) y los
requerimientos de precisión y velocidad.

8 Referencias
• Boyd, S., & Vandenberghe, L. (2004). *Convex Optimization*. Cambridge Univer-
sity Press.

• Nesterov, Y. (1983). A method for solving the convex programming problem with
convergence rate O(1/k 2 ). *Soviet Mathematics Doklady*, 27(2), 372-376.

• Nocedal, J., & Wright, S. J. (2006). *Numerical Optimization* (2nd ed.). Springer.

• Robbins, H., & Monro, S. (1951). A Stochastic Approximation Method. *The

Annals of Mathematical Statistics*, 22(3), 400-407.