4.1 Trust-region methods

\[\begin{eqnarray} f(x_{k} + p) = f(x_{k}) + \nabla f(x_{k}) ^{\mathrm{T}} p + \frac{1}{2} p^{\mathrm{T}} \nabla^{2} f(x_{k} + t p)p . \label{equation_04_01} \end{eqnarray}\] \[\begin{eqnarray} m_{k}(p) & := & f(x_{k}) + \nabla f(x_{k})^{\mathrm{T}} p + \frac{1}{2} p^{\mathrm{T}} B_{k} p \end{eqnarray}\]

where $B_{k}$ is some symmetric matrix. We assume that

\[\norm{ f(x_{k} + p) - m_{k}(p) } = O(\norm{p}^{2}) .\]

If $B_{k} = \nabla^{2}f(x_{k})$, then

\[\norm{ f(x_{k} + p) - m_{k}(p) } = O(\norm{p}^{3}) .\] \[\begin{eqnarray} \begin{align} \min_{p \in \mathbb{R}^{n}} m_{k}(p) & & & = f(x_{k}) + \nabla f(x_{k}) ^{\mathrm{T}} p + \frac{1}{2} p ^{\mathrm{T}} B_{k} p \nonumber \\ \mathrm{subject\ to} & & & \norm{p} \ge \Delta_{k}, \nonumber \end{align} \end{eqnarray}\]

where $\Delta_{k} > 0$.

By the first optimal condition,

\[\begin{eqnarray} & & \nabla m_{k}(p_{k}^{B}) = \nabla f(x_{k})^{\mathrm{T}} + B_{k} p_{k}^{B} = 0 \nonumber \\ & \Leftrightarrow & p_{k}^{B} = -B_{k}^{-1} \nabla f(x_{k})^{\mathrm{T}} . \end{eqnarray}\]

If $B_{k}$ is positive definite and $\norm{B_{k}^{-1} \nabla f(x_{k})} \le \Delta_{k}$, $p_{k}^{B}$ is optimal.

Outline of Trust region methods

\[\begin{eqnarray} \rho_{k} := \frac{ f(x_{k}) - f(x_{k}+p_{k}) }{ m_{k}(0) - m_{k}(p_{k}) } . \label{equation_04_04} \end{eqnarray}\]

• The numnerator is called the actual reduction
• The denominator is the predicted reduction
• $\rho_{k}$ is positive since $p_{k}$ is

Algorithms 4.1 Trust Region

• $\hat{\Delta} > 0$,
• $\Delta_{0} \in (0, \hat{\Delta})$,
• $\eta \in [0, 1/4)$,

Step1. $k = 0, 1, 2, \ldots, $,

Step2. Obtain $p_{k}$ by Solving \(\eqref{equation_04_03}\).

Step3. Evaluate $\rho_{k}$ from \(\eqref{equation_04_04}\).

Step4.

• If $\rho_{k} < 1/4$, $\Delta_{k+1} = 1/4 \Delta_{k}$
• else
  • if $\rho_{k} > 3/4$ and $\norm{p_{k}} = \Delta_{k}$, $\Delta_{k+1} = \min(2 \Delta_{k}, \hat{\Delta})$.
  • else $\Delta_{k+1} = \Delta_{k}$.

Step5.

• If $\rho_{k} > \eta$, $x_{k+1} = x_{k} + p_{k}$
• else $x_{k + 1} = x_{k}$.

Step6. Back to Step1

■