Numerical Optimization

Reference: Numerical Optimization by Nocedal and Wright

Categorize your optimization problem

Different optimization problems require different classes of optimization algorithms for efficient solution. Some fundamental decision points: The tree below can serve as a guide for which class of optimization algorithm is appropriate.

We will mainly discuss the optimization of smooth functions, with and without constraints.

Sketch of lecture

• Problem classification

  • Tree

• Concepts

  • Global and local solutions

  • Convex sets and functions

  • Conditions for optima from calculus

  • Iteration algorithms

    \[x_o \rightarrow x_1 \rightarrow \ldots \rightarrow x_k \rightarrow x_{k+1} \rightarrow x_\text{opt}\]

• Gradient free methods

  • Nelder-Mead simplex

• Line search

  \[\min_{\alpha > 0} f(x_k + \alpha p_k)\]

  • Descent condition \(p_k^T \nabla f_k < 0\)

  • Steepest descent \(\nabla f\) (Sensitivity to scaling)

  • Newton direction \((\nabla^2 f)^{-1} \nabla f\) (by minimizing \(m_k\))

  • Conjugate gradient method

  • Quasi-Newton methods (SR1, BFGS)

• Trust regions

  \[ \begin{align}\begin{aligned}\min_{p} m_k(x_k + p)\\where :math:`x_k + p` lie inside the trust region and\end{aligned}\end{align} \]
  \[ \begin{align}\begin{aligned} m_k(x_k + p) = f_k + p^T\nabla f_k + p^T B_k p\\where :math:`B_k \sim \nabla^2 f_k` Secant condition\end{aligned}\end{align} \]
  \[B_{k+1}s_k = y_k\]
  \[s_k = x_{k+1}-x_k = \alpha p_k\]
  \[y_k = \nabla f_{k+1} - \nabla f_k\]

  • Levenberg-Marquadt

• Model formulation

• Objective function \(f\)

• Variables \(x\)

• Constraint functions

  • Equality

  • Inequality