Numerical Optimization for Large Scale Problems

What I implemented

For the final project in Numerical Optimization for Large Scale Problems, I implemented two second-order methods rather than calling a library solver. I then compared where they spent their time and how they behaved as the problems grew from classroom-sized examples to N = 100,000 variables.

Algorithms Implemented

• Modified Newton Method: Uses Modified Cholesky Factorization to ensure descent in non-convex regions.
• Truncated Newton (Newton-CG): Approximates the Newton step using Conjugate Gradient — no exact Hessian factorization needed.

Both methods are globalized using a Backtracking Line Search strategy.

Test Problems

• Broyden Tridiagonal Function: Symmetric, pentadiagonal Hessian (bandwidth b=2).
• Banded Trigonometric Function: Diagonal Hessian after algebraic decoupling.

Key Optimizations

• Sparse banded matrix operations (O(N) complexity instead of O(N³)).
• Dynamic τ-perturbation to maintain positive-definiteness of Hessian.
• Adaptive forcing sequence ηₖ for convergence near the optimum.
• Graph Coloring (Stride Strategy) for O(1) exact Hessian computation.

Key Findings

• Modified Newton outperforms on highly structured sparsity — Broyden at N=100,000 solved in ≈ 0.45 seconds.
• Truncated Newton showed numerical instability on the Trigonometric problem due to negative curvature regions.
• Vectorized Finite Differences introduced negligible overhead with h=10⁻⁸ tuning.

Built with

Language: Python 3
Libraries: NumPy, SciPy (sparse, linalg), Matplotlib
Techniques: Modified Cholesky Factorization, Conjugate Gradient, Backtracking Line Search, Graph Coloring, Finite Differences
Authors: Lucio Baiocchi (s360244), Leonardo Passafiume (s358616) — Politecnico di Torino, Jan 2026