scoresvideos
Nonlinear Optimization
Table of Contents
Unit 5 Overview: Newton's Method
5.1 Classical Newton's method
5.2 Modified Newton methods
5.3 Convergence analysis and implementation issues

Newton's method is a powerful optimization tool, but it has limitations. Modified Newton methods address these issues, improving stability and efficiency. They tweak the classic approach, making it more practical for real-world problems.

Damped and quasi-Newton methods are key modifications. They introduce step size control and Hessian approximations, respectively. These changes help tackle tricky functions and cut down on computational costs, making optimization more accessible and reliable.

Damped and Quasi-Newton Methods

Damped Newton Method and Its Advantages

  • Damped Newton method modifies traditional Newton's method to improve convergence
  • Introduces a step size parameter α to control the magnitude of each iteration
  • Update formula: xk+1=xk−αk[∇2f(xk)]−1∇f(xk)x_{k+1} = x_k - α_k [∇^2 f(x_k)]^{-1} ∇f(x_k)
  • Helps prevent overshooting in regions where the function is highly nonlinear
  • Improves stability and convergence rate in challenging optimization problems
  • Utilizes line search techniques to determine optimal step size α_k at each iteration
  • Can handle functions with irregular curvature or multiple local minima more effectively

Quasi-Newton Methods: BFGS and DFP

  • Quasi-Newton methods approximate the Hessian matrix to reduce computational cost
  • Avoid explicit calculation of second derivatives, making them more efficient for large-scale problems
  • Update the approximate Hessian or its inverse at each iteration using gradient information
  • BFGS (Broyden-Fletcher-Goldfarb-Shanno) method updates the inverse Hessian approximation
  • BFGS update formula: Bk+1=Bk+ykykTykTsk−BkskskTBkskTBkskB_{k+1} = B_k + \frac{y_k y_k^T}{y_k^T s_k} - \frac{B_k s_k s_k^T B_k}{s_k^T B_k s_k}
  • DFP (Davidon-Fletcher-Powell) method updates the Hessian approximation directly
  • DFP update formula: Hk+1=Hk+ykykTykTsk−HkskskTHkskTHkskH_{k+1} = H_k + \frac{y_k y_k^T}{y_k^T s_k} - \frac{H_k s_k s_k^T H_k}{s_k^T H_k s_k}
  • Both methods maintain positive definiteness of the approximation, ensuring descent directions
  • BFGS generally performs better in practice due to its superior numerical stability
  • Quasi-Newton methods strike a balance between computational efficiency and convergence speed

Trust Region and Gauss-Newton Methods

Trust Region Methods: Concept and Implementation

  • Trust region methods define a region around the current point where the quadratic model is trusted
  • Solve a subproblem to find the step within the trust region that minimizes the quadratic model
  • Trust region subproblem: min⁡pqk(p)=fk+gkTp+12pTBkpsubject to∥p∥≤Δk\min_{p} q_k(p) = f_k + g_k^T p + \frac{1}{2} p^T B_k p \quad \text{subject to} \quad \|p\| \leq \Delta_k
  • Adjust the trust region radius Δ_k based on the agreement between the model and the actual function
  • Provide robust convergence properties, especially for ill-conditioned problems
  • Can handle non-convex optimization problems more effectively than line search methods
  • Dogleg method offers an efficient approach to solving the trust region subproblem

Gauss-Newton and Levenberg-Marquardt Methods for Nonlinear Least Squares

  • Gauss-Newton method specializes in solving nonlinear least squares problems
  • Designed for minimizing sum of squared residuals: f(x)=12∑i=1mri(x)2f(x) = \frac{1}{2} \sum_{i=1}^m r_i(x)^2
  • Approximates the Hessian using the Jacobian of the residuals: ∇2f(x)≈J(x)TJ(x)\nabla^2 f(x) \approx J(x)^T J(x)
  • Update formula: xk+1=xk−[J(xk)TJ(xk)]−1J(xk)Tr(xk)x_{k+1} = x_k - [J(x_k)^T J(x_k)]^{-1} J(x_k)^T r(x_k)
  • Levenberg-Marquardt method combines Gauss-Newton with trust region ideas
  • Adds a damping term to the approximated Hessian: [J(xk)TJ(xk)+λkI][J(x_k)^T J(x_k) + \lambda_k I]
  • Damping parameter λ_k adjusts between Gauss-Newton and gradient descent behavior
  • Provides improved stability and convergence for ill-conditioned or highly nonlinear problems
  • Widely used in curve fitting, parameter estimation, and computer vision applications

Secant Method

Secant Method: Principles and Implementation

  • Secant method serves as a root-finding algorithm, applicable to optimization by finding zeros of the gradient
  • Approximates the derivative using two previous points instead of computing it directly
  • Update formula: xk+1=xk−f(xk)(xk−xk−1)f(xk)−f(xk−1)x_{k+1} = x_k - \frac{f(x_k)(x_k - x_{k-1})}{f(x_k) - f(x_{k-1})}
  • Converges superlinearly with a rate of approximately 1.618 (golden ratio)
  • Requires two initial points to start the iteration process
  • Can be extended to multidimensional optimization problems (Broyden's method)
  • Offers a balance between the simplicity of the bisection method and the fast convergence of Newton's method
  • Particularly useful when the derivative is difficult or expensive to compute
  • Can be combined with other methods to create hybrid algorithms with improved performance