๐งญ 1. Overview of Solution Methods for Unconstrained Optimization
-
Goal: Minimize a function without constraints.
-
Two main types:
-
Indirect methods: Solve the optimality condition (e.g., Newton's method).
-
Direct methods: Iteratively improve the function (e.g., line-search, trust region).
-
๐ 2. Indirect Methods
-
Based on solving analytically or numerically.
-
Represent the problem as a nonlinear system of equations.
⬇️ 3. Direct Methods
-
Construct a sequence that converges to an optimal solution.
-
Rely on function evaluations and iterative improvements (no explicit solving of gradient equations).
⏱️ 4. Rate of Convergence
-
Linear: error shrinks by a constant factor.
-
Superlinear: convergence faster than linear.
-
Quadratic: error squares each step (very fast).
๐ 5. Line Search Methods
-
Strategy to find an optimal step length along a descent direction .
-
Use Armijo or Wolfe conditions to ensure sufficient decrease.
๐ 6. Descent Directions
-
Steepest descent: direction of negative gradient.
-
Newton’s method: uses Hessian to take smarter steps.
-
Conjugate gradient and quasi-Newton: alternatives for efficient direction choice.
๐งฎ 7. Steepest Descent Method
-
Simple and guaranteed descent.
-
Can be slow, especially in ill-conditioned problems.
-
Step direction:
⚙️ 8. Newton’s Method
-
Uses second derivatives (Hessian) for faster convergence.
-
Step:
-
Fast but computationally expensive and sensitive to poor Hessians.
๐ฆ 9. Trust Region Methods
-
Use a model function (quadratic approximation) and limit steps to a “trust region.”
-
Adjust the region radius based on agreement between model and true function.
-
More stable than line search for some problems.
๐พ 10. Dogleg Method
-
Efficient strategy within trust-region to combine steepest descent and Newton steps.
๐ง 11. Inexact & Modified Newton Methods
-
Inexact Newton: Approximate solution to Newton's step (e.g., Conjugate Gradient).
-
Modified Newton: Adjusts Hessian when it’s not positive definite.
๐ 12. Quasi-Newton Methods
-
Approximate the Hessian update using previous gradients.
-
Examples: DFP, BFGS.
-
Efficient and widely used in practice.
๐งช 13. Parameter Estimation and Least-Squares
-
Example: Fitting reaction parameters in a chemical process.
-
Problem formulated as minimizing the sum of squared errors (residuals).
-
Solved using Gauss-Newton method — a specialized quasi-Newton technique.
๐ 14. Complexity Analysis
-
Measures computational effort to reach a solution.
-
Analytical complexity: number of oracle queries (e.g., gradients).
-
Arithmetical complexity: number of operations.
-
Steepest descent: , Newton’s method: faster with .
๐ฌ 15. Rosenbrock Function Example
-
Used to illustrate convergence behavior of various methods.
-
Demonstrates challenges in optimization like slow convergence for steepest descent.