ME/AER 647 Systems Optimization I

---

Trust Region Methods

Instructor: Hasan A. Poonawala

Mechanical and Aerospace Engineering
University of Kentucky, Lexington, KY, USA

Topics:
What they are
Quadratic Models and Regions

General Framework

• Approximate $f$ near $\mathbf{x}_k$ using a model function $m_k$
• Minimize $m_k$ near $\mathbf{x}_k$ by solving $$\begin{align} \min_{p} & m_k\left(\mathbf{x}_k+p\right)\\ \text{s.t.} & \mathbf{x}_k+p \in \text{Trust region}\\ & \text{Original Constraints} \end{align}$$

Quadratic Case

The optimization problem becomes¹: $$\begin{align} \min_{p} & m_k\left(\mathbf{x}_k+p\right) = f_k + p^T \nabla f_k + \frac{1}{2}p^T F_k p\\ \text{s.t.} & \| p\|_2 \leq \Delta_k \end{align}$$

We’ve seen how to work through the KKT conditions to find a solution:

• If $\nabla f_k ^T F_k^{-1} \nabla f_k \leq \Delta_k^2$, then $p_k = -F_k^{-1} \nabla f_k$, assuming $F_k$ is PSD
• Otherwise, need to find $\mu >0$ such that $\nabla f_k ^T ( F_k + \mu I)^{-1} \nabla f_k = \Delta_k^2$ and $F_k +\mu I$ is PSD. If found, then $$p_k = -(F_k+\mu I)^{-1} \nabla f_k$$

1. $f_k = f(\mathbf{x}_k)$, $\nabla f_k = \nabla f(\mathbf{x}_k)$, $F_k = \nabla^2 f(\mathbf{x}_k)$

Trust Region Size

• How big should $\Delta_k$ be?

• Define $$\rho_k = \frac{f(x_k) -f(x_k + p_k)}{f(x_k) - m(p_k)}$$

  • $\rho_k <0$ implies objective increased, reject step
  • $\rho_k \approx 1$ means model $m_k$ was good over trust region
  • $\rho_k \ll 1$ implies model was not good over trust region

• Use $\rho_k$ to modulate $\Delta_k$

Trust Region Algorithm

Given $\hat \Delta >0$, $\Delta_0 \in (0,\hat \Delta)$, and $\eta \in [0,\frac{1}{4})$, evaluate the following loop:

1. Solve for $p_k$
2. Evaluate $\rho_k$
   • If $\rho_k < \frac{1}{4}$: $\quad$ $\Delta_{k+1} = \frac{1}{4} \Delta_k$
   • Else
     • If $\rho_k > \frac{3}{4}$ and $\|p_k\| = \Delta_k$: $\quad$ $\Delta_{k+1} = \min(2 \Delta_k,\hat \Delta)$
     • Else: $\quad$ $\Delta_{k+1} = \Delta_k$
3. Update $x_{k+1}$:
   • If $\rho_k > \eta$: $\quad$ $x_{k+1} = x_k + p_k$
   • Else : $\quad$ $x_{k+1} = x_k$

Trust Region Method Approximations

• For large problems, prefer to approximately solve for $p_k$
  • No point getting an expensive exact solution to an approximate problem
• Two ideas
  • Cauchy Point: Line search along gradient.
    • Basically steepest descent with a max step size
  • Dogleg method
    • Best when $F_k$ is positive definite
    • Unconstrained minimum of $m_k$ is $p_k^B$ (full step), minimum of line search along $\nabla f_k$ is $p^U$
    • On a two-line-segment path from $x_{k} \to p^U \to p_k^B$, $m_k$ decreases while the point gets further away from $x_k$ (Lemma 4.2 in NW)
    • Find the point on this path where $\|p_k\| = \|\Delta_k\|$