Trust Region Method

In the Trust Region Method we approximate a given function $f$ by a quadratic model $q_k(p)=f(x_k)+\nabla{f(x_k)}^Tp+\frac{1}{2}p^T\nabla^2{f(x_k})p$. Now, we want to minimize the function within a trusted region so we look at:

$\min q_k(p) \text{ subject to } \|p\|\leq\Delta$,

where $\Delta >0$ is the radius of the trusted region. If we have the case $\|p\|=\Delta$, what does this practically mean?

Thank you for your time!

Solution 1:

Usually the trusted region is dependent on the current step $k$ of the algorithm. So supposing that you mean the varying trust radius $\Delta_k$:

If $\|p_k\| = \Delta_k$ then the increment $p_k$ that minimizes your quadratic approximation of $f$ at step $k$ has reached the maximal radius at which we still trust the model function to accurately represent the function $f$.

We impose this restriction because we only have trust that $q_k$ represents $f$ in a (small) neighbourhood around $x_k$.

For a given $p_k$ to fulfil $\|p_k\| = \Delta_k$ does not have immediate practical significance. It could be that the current guess for the trust region radius is too low if the model quality is good i.e. if

$$\rho_k := \frac{f(x_k) - f(x_k + p_k)}{q_k(0) - q_k(p_k)}$$

is close to $1$, then maybe we could have stepped further. Hence the next step in the algorithm would be to increase the trusted radius such that $\Delta_{k+1} > \Delta_k$.

On the other hand if the quality of the model is bad e.g. if $\rho_k$ is close to $0$ or even negative then the trusted region will be reduced or the step rejected. So in short, the meaning of whether we reach the 'limit of our trust' or not, depends on the accuracy of our current approximation $q_k$ and cannot be interpreted on its own.