Mathematical Optimization for Engineers - Chapter 2

 

๐Ÿงญ 1. Overview of Solution Methods for Unconstrained Optimization

  • Goal: Minimize a function f(x)f(x) without constraints.

  • Two main types:

    • Indirect methods: Solve the optimality condition f(x)=0\nabla f(x) = 0 (e.g., Newton's method).

    • Direct methods: Iteratively improve the function (e.g., line-search, trust region).


๐Ÿ” 2. Indirect Methods

  • Based on solving f(x)=0\nabla f(x) = 0 analytically or numerically.

  • Represent the problem as a nonlinear system of equations.


⬇️ 3. Direct Methods

  • Construct a sequence {xk}\{x_k\} 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 ฮฑk\alpha_k along a descent direction pkp_k.

  • 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: pk=f(xk)p_k = -\nabla f(x_k)


⚙️ 8. Newton’s Method

  • Uses second derivatives (Hessian) for faster convergence.

  • Step: pk=H1f(xk)p_k = -H^{-1} \nabla f(x_k)

  • 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: O(1/ฯต2)O(1/\epsilon^2), Newton’s method: faster with O(1/ฯต3/2)O(1/\epsilon^{3/2}).


๐Ÿ”ฌ 15. Rosenbrock Function Example

  • Used to illustrate convergence behavior of various methods.

  • Demonstrates challenges in optimization like slow convergence for steepest descent.