Unit 2.4: Conjugate Gradient Method (Fletcher-Reeves)

This method bridges the gap between Steepest Descent (Simple but Slow) and Newton’s Method (Fast but Heavy).

1. Concept

It fixes the "zig-zag" behavior of Steepest Descent without calculating the heavy Hessian matrix.

• It generates search directions that are Conjugate (orthogonal with respect to the matrix A).
• Idea: "Let's not move in a direction that spoils the progress we made in the previous step."

2. Formulas (Fletcher-Reeves)

New Search Direction (Sᵢ): Sᵢ = -∇f(Xᵢ) + βᵢ * S₍ᵢ₋₁₎

Here, we don't just follow the negative gradient. We add a fraction (β) of the old direction (S₍ᵢ₋₁₎) to correct our path.

Calculating βᵢ: βᵢ = |∇f(Xᵢ)|² / |∇f(X₍ᵢ₋₁₎)|² (Ratio of the magnitude of the new gradient squared to the old gradient squared).

3. Algorithm

1. Start: Select X₁.

• For the first step, use Steepest Descent: S₁ = -∇f(X₁).

1. Minimize: Find step size λᵢ to minimize along Sᵢ.
2. Update: X₍ᵢ₊₁₎ = Xᵢ + λᵢ * Sᵢ.
3. Compute Gradient: Calculate new ∇f(X₍ᵢ₊₁₎).
4. Compute β: Use the formula above.
5. New Direction: S₍ᵢ₊₁₎ = -∇f(X₍ᵢ₊₁₎) + β * Sᵢ.
6. Repeat.

4. Pros & Cons

• Pros: Much faster than Steepest Descent; Low memory (doesn't need Hessian); Converges in n steps for a purely quadratic function.
• Cons: More complex logic; Requires a very accurate line search for λ to work correctly.