Descent Dynamics Slides Numerical Optimization // Module 01
DESCENT DYNAMICS
First-order methods and the critical role of step-size selection in non-linear landscapes.
GRADIENT DESCENT & LINE SEARCH
The Blindfold Challenge
Imagine you are blindfolded on a rugged mountain range. Your goal is to reach the lowest point in the valley.
You can only feel the slope beneath your feet.
Which direction do you move?
How large of a step do you take before feeling the slope again?
Objective Function \( f(x) \)
Gradient Descent Algorithm
The fundamental iterative approach for first-order optimization.
\[ x_{k+1} = x_k - \alpha_k \nabla f(x_k) \]
Descent Direction
\( p_k = -\nabla f(x_k) \)
The direction of steepest decrease.
Step Size
\( \alpha_k \)
The learning rate or step length.
Update
\( x_{k+1} \)
The next candidate solution.
The Goldilocks Problem of \( \alpha \)
Too Large
The algorithm overshoots the minimum, potentially leading to divergence or chaotic oscillation.
Too Small
The algorithm converges extremely slowly, requiring excessive computational resources and iterations.
Just Right
Efficient descent with rapid convergence while maintaining stability. How do we find this?
Solving for \( \alpha \)
Exact Line Search
Find \( \alpha \) that minimizes:
\[ \min_{\alpha > 0} f(x_k + \alpha p_k) \]
Computationaly expensive for complex \( f(x) \). Mostly used for theoretical analysis or simple quadratics.
Inexact Line Search
Find \( \alpha \) that satisfies "sufficient decrease".
Typically uses conditions like the Armijo Condition or Wolfe Conditions.
Balance between progress and computational effort.
Armijo Condition
To ensure stability, the reduction in the function value must be at least proportional to the gradient and the step size.
\[ f(x_k + \alpha p_k) \le f(x_k) + c_1 \alpha \nabla f(x_k)^T p_k \]
Where \( c_1 \in (0, 1) \), often \( 10^{-4} \)
Search Direction \( p_k \)
Visualizing the Descent Envelope
Current Point \( x_k \) Armijo Limit
Implementation: Backtracking
// Initialize
Given \( \alpha > 0 \), \( \rho \in (0, 1) \), \( c_1 \in (0, 1) \)
// Iteratively shrink alpha until Armijo is met
While \( f(x_k + \alpha p_k) > f(x_k) + c_1 \alpha \nabla f(x_k)^T p_k \):
\( \alpha \leftarrow \rho \alpha \)
// Terminate
Return \( \alpha \)
Line Search Logic Worksheet Line Search Logic
Course: Numerical Optimization // Unit 01
Student Name:
Date:
The Objective
In this exercise, you will manually perform an iteration of Gradient Descent with an **Exact Line Search** and then analyze a **Backtracking (Inexact) Line Search** using the Armijo condition.
Objective Function: \( f(x) = x_1^2 + 10x_2^2 \)
Starting Point: \( x_0 = (10, 1)^T \)
1.1 Calculate the Gradient \( \nabla f(x_0) \) and the Descent Direction \( p_0 = -\nabla f(x_0) \).
1.2 Express the function value along the search direction: \( \phi(\alpha) = f(x_0 + \alpha p_0) \).
Hint: Substitute \( x_1 = 10 + \alpha p_{0,1} \) and \( x_2 = 1 + \alpha p_{0,2} \)
1.3 Find the exact optimal step size \( \alpha^* \) by solving \( \phi'(\alpha) = 0 \).
Backtracking & Sufficient Decrease
The Armijo Condition:
\( f(x_k + \alpha p_k) \le f(x_k) + c_1 \alpha \nabla f(x_k)^T p_k \)
2.1 Using the same function and starting point from Problem 1:
Assume parameters: \( \bar{\alpha} = 1 \) (initial guess), \( \rho = 0.5 \) (shrink factor), \( c_1 = 0.1 \).
Trial \( \alpha \) \( f(x_0 + \alpha p_0) \) Armijo Bound (RHS) Satisfied? 1.0 0.5 0.25
2.2 Discussion: Sensitivity
If we set \( c_1 = 0.9 \) instead of \( 0.1 \), how would that change the requirement for a step to be "acceptable"? Would the algorithm likely take larger or smaller steps?
© OPTIMIZATION METHODS LAB ALGORITHMIC BLUEPRINT SERIES // NO. 01
Line Search Answer Key Instructor Resource
Line Search Logic Answer Key
Course: Numerical Optimization // Unit 01 Solutions
1. Exact Line Search Solutions
1.1 Gradient & Direction
\( \nabla f(x) = [2x_1, 20x_2]^T \)
At \( x_0 = (10, 1)^T \): \( \nabla f(x_0) = [20, 20]^T \)
Direction: \( p_0 = -\nabla f(x_0) = [-20, -20]^T \)
1.2 Univariate Function \( \phi(\alpha) \)
\( x(\alpha) = x_0 + \alpha p_0 = \begin{bmatrix} 10 - 20\alpha \\ 1 - 20\alpha \end{bmatrix} \)
\( \phi(\alpha) = (10 - 20\alpha)^2 + 10(1 - 20\alpha)^2 \)
Expansion (optional): \( \phi(\alpha) = 100 - 400\alpha + 400\alpha^2 + 10(1 - 40\alpha + 400\alpha^2) \)
\( \phi(\alpha) = 4400\alpha^2 - 800\alpha + 110 \)
1.3 Optimal Step Size \( \alpha^* \)
\( \phi'(\alpha) = 8800\alpha - 800 = 0 \)
\( \alpha^* = \frac{800}{8800} = \frac{1}{11} \approx 0.0909 \)
2. Backtracking Solutions
2.1 Backtracking Table
Trial \( \alpha \) \( f(x_0 + \alpha p_0) \) Armijo Bound (RHS) Satisfied? 1.0 3710 30 (Calculation below) NO 0.5 820 70 NO 0.0625* ~77 ~105 YES
*Note: Initial alpha of 1 requires multiple shrinks for this quadratic. At \( \alpha = 1 \), RHS is \( 110 + 0.1(1)(-800) = 30 \).
2.2 Discussion: Sensitivity
Setting \( c_1 = 0.9 \) makes the condition **much stricter**. It requires the function to decrease by 90% of the predicted decrease from the tangent line. This forces the algorithm to take **smaller, more conservative steps** to ensure "sufficient" decrease is met. Conversely, \( c_1 \approx 0 \) accepts almost any descent.
INTERNAL USE ONLY ALGORITHMIC BLUEPRINT SERIES // NO. 01 KEY
Newton Speed Slides Numerical Optimization // Module 02
SECOND ORDER SPEED
Mastering Newton's Method and the power of Hessian-based quadratic convergence.
NEWTON'S METHOD &
The Curvature Advantage
Gradient descent only uses local slope information. Newton's method uses curvature.
Gradient (1st Order)
"Which way is down?"
Hessian (2nd Order)
"How is the slope changing? How curvy is the surface?"
Quadratic Approximation
The Newton Update
\[ x_{k+1} = x_k - [ \nabla^2 f(x_k) ]^{-1} \nabla f(x_k) \]
Finding the root of the derivative by approximating \( f(x) \) as a parabola.
The Hessian
\[ \nabla^2 f(x_k) \]
Matrix of second-order partial derivatives.
Newton Direction
\[ p_k^N = -H_k^{-1} g_k \]
The jump directly to the minimum of the quadratic approximation.
Convergence Performance
Linear Convergence
Error decreases by a constant factor in each step.
\( \|x_{k+1} - x^*\| \le C \|x_k - x^*\| \)
Example: Gradient Descent
Quadratic Convergence
The number of correct digits doubles in each step.
\( \|x_{k+1} - x^*\| \le C \|x_k - x^*\|^2 \)
Example: Newton's Method
The Hidden Price
01
Hessian Construction
Requires calculating \( n^2 \) second derivatives at every single iteration.
02
Matrix Inversion
Solving \( Hx = g \) typically costs \( O(n^3) \). Prohibitive for large-scale problems.
03
Positive Definiteness
If the Hessian is not positive definite, the algorithm can move towards a maximum or saddle point.
Hessian Analysis Worksheet Hessian Analysis
Course: Numerical Optimization // Unit 02
Student Name:
Second-Order Strategy
Newton's method finds the minimum by creating a quadratic approximation of the local surface. In this worksheet, you will derive the Hessian for a non-linear function and calculate a single Newton step to observe the "jump" behavior.
// Objective Function
\( f(x) = \log( e^{x_1} + e^{-x_1} ) + x_2^2 \)
// Start Point
\( x_0 = (1, 1)^T \)
1. Calculate the Gradient Vector \( \nabla f(x) \).
Show your work for both partial derivatives \( \frac{\partial f}{\partial x_1} \) and \( \frac{\partial f}{\partial x_2} \).
2. Construct the Hessian Matrix \( H(x) = \nabla^2 f(x) \).
Verify if the Hessian is diagonal for this specific function.
3. Calculate the Newton Step \( p_0^N = -H(x_0)^{-1} \nabla f(x_0) \).
Evaluate the components at \( x_0 = (1, 1)^T \).
Convergence Analysis
4. Convergence Comparison
Compare the descent direction you found with a standard Gradient Descent step \( p_0^{GD} = -\nabla f(x_0) \). How does the Hessian scaling change the search direction and step length?
5. Singular Hessians
What happens to the Newton algorithm if the function is locally linear (e.g., in a flat region)? Why does the Hessian matrix become problematic in this scenario?
© OPTIMIZATION METHODS LAB ALGORITHMIC BLUEPRINT SERIES // NO. 02
Hessian Analysis Answer Key Instructor Resource
Hessian Analysis Answer Key
Course: Numerical Optimization // Unit 02 Solutions
1. Step-by-Step Derivations
1. Gradient Vector \( \nabla f(x) \)
\( f(x) = \log( e^{x_1} + e^{-x_1} ) + x_2^2 \)
Partial x1:
\( \frac{\partial f}{\partial x_1} = \frac{e^{x_1} - e^{-x_1}}{e^{x_1} + e^{-x_1}} = \tanh(x_1) \)
Partial x2:
\( \frac{\partial f}{\partial x_2} = 2x_2 \)
\( \nabla f(x) = [\tanh(x_1), 2x_2]^T \)
2. Hessian Matrix \( H(x) \)
Mixed partials are zero because variables are separable.
\( H_{11} = \frac{\partial}{\partial x_1}(\tanh(x_1)) = \text{sech}^2(x_1) \)
\( H_{22} = \frac{\partial}{\partial x_2}(2x_2) = 2 \)
\( H(x) = \begin{bmatrix} \text{sech}^2(x_1) & 0 \\ 0 & 2 \end{bmatrix} \)
3. Newton Step at \( x_0 = (1, 1)^T \)
Evaluate Gradient: \( \nabla f(x_0) = [\tanh(1), 2]^T \approx [0.7616, 2]^T \)
Note: \( \text{sech}^2(1) = 1 - \tanh^2(1) \approx 1 - 0.58 = 0.42 \)
Hessian at \( x_0 \): \( H_0 \approx \begin{bmatrix} 0.42 & 0 \\ 0 & 2 \end{bmatrix} \implies H_0^{-1} \approx \begin{bmatrix} 2.38 & 0 \\ 0 & 0.5 \end{bmatrix} \)
\( p_0^N = -H_0^{-1} \nabla f(x_0) \approx -[1.81, 1]^T \)
Analysis Questions Solutions
4. Convergence Comparison
The gradient descent direction is \( [-0.76, -2]^T \). The Newton direction is \( [-1.81, -1]^T \). Notice how the Hessian **scales** the components: the step in the \( x_1 \) direction (where the curvature is small) is significantly lengthened, while the step in the \( x_2 \) direction (where curvature is large) is shortened. Newton's method accounts for the "flatness" of the log-sum-exp term.
5. Singular Hessians
If the function is locally linear, the second derivatives (and thus the Hessian elements) go to zero. The Hessian becomes singular (determinant = 0) or nearly singular, making its inverse undefined or numerically unstable. This causes the Newton step to blow up to infinity, illustrating why Newton's method requires local curvature to function.
INTERNAL USE ONLY ALGORITHMIC BLUEPRINT SERIES // NO. 02 KEY
Quasi Newton Slides Numerical Optimization // Module 03
QUASI NEWTON
Approximating curvature for high-dimensional efficiency: The BFGS Algorithm.
Hessian Approximation & BFGS
The Best of Both Worlds?
We want the speed of Newton's method without the O(n³) price of inversion.
Gradient Descent
Cheap per step, but converges slowly (linear).
Newton's Method
Fast convergence (quadratic), but steps are expensive.
Quasi-Newton
Cheap per step AND fast convergence (superlinear).
THE IDEA
"Don't calculate the Hessian from scratch. Accumulate curvature information by observing how the gradient changes as we move."
The Secant Condition
The Requirement
\[ B_{k+1} s_k = y_k \]
\( s_k = x_{k+1} - x_k \) (Change in position)
\( y_k = \nabla f(x_{k+1}) - \nabla f(x_k) \) (Change in gradient)
\( B_{k+1} \) is our approximation of the Hessian.
The Secant Equation ensures that our approximated Hessian \( B \) behaves like the true Hessian along the most recent search direction.
Since many matrices satisfy this, we pick the one "closest" to our previous approximation.
BFGS
Broyden–Fletcher–Goldfarb–Shanno
Inverse Update Formula
\[ H_{k+1} = (I - \rho_k s_k y_k^T) H_k (I - \rho_k y_k s_k^T) + \rho_k s_k s_k^T \]
Rank-2 Update
Maintains positive definiteness and symmetry.
Direct Inverse
Updates the inverse \( H \approx \nabla^2 f^{-1} \).
Cost: \( O(n^2) \)
Matrix-vector multiplication only. No inversion!
BFGS Characteristics
Stability
Strongly self-correcting. Even if the initial approximation is poor, BFGS recovers.
Efficiency
Achieves superlinear convergence—much faster than GD, close to Newton.
Memory
For huge \( n \), use L-BFGS to avoid storing the full matrix.
BFGS Update Handout BFGS BLUEPRINT
Algorithm Reference // Quasi-Newton Methods
Core Philosophy
"Approximate the inverse Hessian matrix directly using only gradient information, avoiding the \( O(n^3) \) computational bottleneck of matrix inversion."
Superlinear Convergence
Efficient \( O(n^2) \) Updates
Guaranteed Symmetry Preservation
The Secant Variables
Change in Position (\( s_k \))
\( s_k = x_{k+1} - x_k \)
Change in Gradient (\( y_k \))
\( y_k = \nabla f(x_{k+1}) - \nabla f(x_k) \)
Scaling Factor (\( \rho_k \))
\( \rho_k = (y_k^T s_k)^{-1} \)
The Inverse Hessian Update
\[ H_{k+1} = (I - \rho_k s_k y_k^T) H_k (I - \rho_k y_k s_k^T) + \rho_k s_k s_k^T \]
Where \( H_k \approx (\nabla^2 f(x_k))^{-1} \)
01. Search
Compute direction and step size:
\( p_k = -H_k \nabla f(x_k) \)
\( x_{k+1} = x_k + \alpha_k p_k \)
02. Evaluate
Calculate gradient differences:
\( s_k = x_{k+1} - x_k \)
\( y_k = g_{k+1} - g_k \)
03. Update
Refine the Hessian approximation:
Apply the BFGS formula to get \( H_{k+1} \). Initial \( H_0 \) is often set to the Identity matrix \( I \).
Implementation Note
The update remains stable only if \( y_k^T s_k > 0 \). This "curvature condition" is guaranteed if the line search satisfies the **Wolfe Conditions**.
© OPTIMIZATION METHODS LAB ALGORITHMIC BLUEPRINT SERIES // REF. 03
Quasi Newton Practice Worksheet Quasi-Newton Practice
Course: Numerical Optimization // Unit 03
Student Name:
Part 1: The Secant Equation
Suppose we are optimizing a function \( f(x) \). At iteration \( k \), we move from \( x_k \) to \( x_{k+1} \). Observe the following values:
Positions
\( x_k = \begin{bmatrix} 0 \\ 0 \end{bmatrix} \), \( x_{k+1} = \begin{bmatrix} 2 \\ 1 \end{bmatrix} \)
Gradients
\( g_k = \begin{bmatrix} -1 \\ -1 \end{bmatrix} \), \( g_{k+1} = \begin{bmatrix} 3 \\ 1 \end{bmatrix} \)
1.1 Calculate the displacement vector \( s_k \) and the gradient change vector \( y_k \).
1.2 Show that for a purely quadratic function \( f(x) = \frac{1}{2}x^T A x + b^T x \), the true Hessian \( A \) satisfies \( A s_k = y_k \).
Derive this using the definition of the gradient for a quadratic.
1.3 Find a diagonal matrix \( B = \text{diag}(b_1, b_2) \) that satisfies the secant equation \( B s_k = y_k \).
Part 2: Symmetric Rank-1 (SR1)
The SR1 update formula is simpler than BFGS but less stable: \( B_{k+1} = B_k + \frac{(y_k - B_k s_k)(y_k - B_k s_k)^T}{(y_k - B_k s_k)^T s_k} \).
2.1 conceptual Analysis
Why is the SR1 update considered a "rank-1" update? Look at the structure of the numerator. How many independent rows/columns does that matrix have?
2.2 BFGS Comparison
BFGS is a "rank-2" update. Based on your understanding, why might a rank-2 update be more desirable than a rank-1 update when approximating a symmetric positive-definite Hessian?
© OPTIMIZATION METHODS LAB ALGORITHMIC BLUEPRINT SERIES // NO. 03 PRACTICE
Non Convex Landscapes Slides Numerical Optimization // Module 04
NON-CONVEX CHAOS
Navigating local minima, saddle points, and the high-dimensional traps of non-linear surfaces.
Momentum, Stochasticity &
Convexity
One global minimum.
Any local min is global.
Convergence is guaranteed.
Non-Convexity
Many local minima.
Plateaus and saddle points.
Sensitivity to initial conditions.
Saddle Points
In high dimensions, saddle points (stationary points where the Hessian has both positive and negative eigenvalues) are more common than local minima.
The Problem:
"The gradient is zero, so our algorithm stops. But we haven't found a minimum!"
Eigenvalue Sign Mismatch
Hessian Indefiniteness
Building Momentum
The Logic
Treat the optimization as a heavy ball rolling down a hill. The ball accumulates velocity in directions of consistent descent, allowing it to "roll over" small local minima and flat plateaus.
// Update Rule
\( v_{k+1} = \beta v_k + (1-\beta) \nabla f(x_k) \)
\( x_{k+1} = x_k - \alpha v_{k+1} \)
\( \beta \in [0, 1) \) is the friction/momentum coefficient.
Shake the Box
Adding noise to the gradient can bump the algorithm out of shallow local traps.
\( g_{noisy} = \nabla f(x) + \epsilon, \quad \epsilon \sim \mathcal{N}(0, \sigma^2) \)
Why Noise Helps
1
Prevents getting stuck in plateaus where the gradient is exactly zero.
2
Acts as a regularizer, forcing the algorithm to find wider, more stable minima.
3
Fundamental to **Stochastic Gradient Descent (SGD)** in Machine Learning.
Stochastic Momentum Activity Landscape Escape
Course: Numerical Optimization // Unit 04
Scenario Analysis
Navigating Complexity
Theoretical convergence is easy on a parabola. Real-world surfaces are non-convex, filled with shallow local minima and flat saddle points. In this activity, you will analyze how momentum and stochastic noise change the behavior of descent algorithms.
Scenario A: The Shallow Trap
An algorithm is at point \( x_k \) on a slope leading to a shallow local minimum. The gradient \( \nabla f(x_k) \) points toward this trap.
Case 1: Vanilla Gradient Descent
The step size is small. Describe the likely outcome as the algorithm approaches the shallow local minimum.
Case 2: Heavy-Ball Momentum
The algorithm has high momentum from a previous steep descent. How does this help "overcome" the local trap?
Scenario B: The Saddle Dead-End
The algorithm has reached a saddle point where \( \nabla f(x^*) = 0 \). Along one axis, the function increases; along another, it decreases.
1. Why does standard BFGS or Newton's Method get "stuck" here?
2. How does adding Gaussian noise \( \epsilon \sim \mathcal{N}(0, \sigma^2) \) to the gradient calculation help the algorithm find the direction of decrease?
Part 2: Parameter Tuning
Designing an Optimizer
You are designing an optimizer for a function with many narrow valleys and occasional sharp peaks. You must pick values for the learning rate (\( \alpha \)) and momentum (\( \beta \)).
Problem A: High Oscillation
Your algorithm is zig-zagging wildly across a valley but making very little progress toward the minimum. Which parameter should you adjust first, and in what direction (increase/decrease)? Explain why.
Problem B: Premature Convergence
Your algorithm stops after 5 iterations, claiming it found a minimum, but the value is clearly sub-optimal compared to known benchmarks. How could introducing a **Learning Rate Scheduler** (decaying \( \alpha \) over time) or **Stochasticity** improve the final result?
© OPTIMIZATION METHODS LAB ALGORITHMIC BLUEPRINT SERIES // NO. 04 ACTIVITY
Implementation Challenge Guide Black Box Minima
Capstone Project: Algorithmic Implementation Challenge
Project Code
OPTI-CORE-05
The Mission
You are tasked with developing a robust optimization library capable of minimizing an unknown "black box" function. Your library must implement at least two major algorithms (Gradient Descent and BFGS) and include automated step-size selection (Backtracking Line Search).
Target Environment
"The function \( f(x) \) and its gradient \( \nabla f(x) \) are provided as callable objects. Your code must find the global minimum \( x^* \) to within a tolerance of \( \epsilon = 10^{-6} \) in fewer than 500 iterations."
Technical Specs
Dim: \( n \in [2, 10] \)
Max Eval: 2000
Line Search: Armijo
Functional Requirements
1. Descent Core
Implement a generic iterator that accepts a search direction \( p_k \) and computes the update \( x_{k+1} \).
2. Step Selection
Implement Backtracking Line Search with configurable parameters \( \rho \) and \( c_1 \).
3. BFGS Update
Implement the inverse Hessian update formula. Ensure symmetry and positive definiteness are maintained.
4. Convergence Monitor
Your library must track and log: \( \| \nabla f(x) \| \), function value \( f(x) \), and step length \( \alpha \).
5. Stopping Criteria
Stop when the gradient norm falls below \( \epsilon \) OR when the change in \( f(x) \) is negligible over 5 steps.
6. Comparative Analysis
Generate convergence plots comparing Gradient Descent and BFGS on the provided test functions.
Project Deliverables
Optimization Source Code
A clean, documented implementation (Python/NumPy or MATLAB) of your library.
Performance Report
A brief PDF showing convergence plots and a discussion on why one algorithm outperformed the other for specific functions.
© OPTIMIZATION METHODS LAB ALGORITHMIC BLUEPRINT SERIES // NO. 05 GUIDE
Optimization Rubric Optimization Rubric
Project: Black Box Minima // Course Assessment
100 PTS
Criterion Performance Standards Weight Algorithmic Correctness
|
Exemplary: BFGS and Gradient Descent are implemented without error, including correct matrix symmetry preservation and inverse updates.
Incomplete: Formulas have sign errors or logic gaps in the update sequence.
| 30 pts |
|
Line Search Robustness
|
Exemplary: Armijo condition is implemented correctly. The line search handles potential infinite loops and correctly adjusts step size to ensure descent.
Incomplete: Algorithm overshoots or fails to converge due to fixed step size or faulty backtracking logic.
| 25 pts |
|
Performance Analysis
|
Exemplary: Convergence plots clearly show the relationship between iterations and gradient norm. Student provides deep insight into why BFGS outperforms GD (or vice versa) for specific surfaces.
Incomplete: Plots are missing labels or analysis is purely descriptive without technical reasoning.
| 25 pts |
|
Code Quality & Style
|
Exemplary: Code is modular, documented with docstrings, and utilizes vectorization (NumPy/Matrix operations) for efficiency.
Incomplete: Code relies on nested loops for matrix operations or lack comments explaining the mathematical steps.
| 20 pts |
Instructor Feedback
© OPTIMIZATION METHODS LAB ALGORITHMIC BLUEPRINT SERIES // NO. 05 RUBRIC
