Generalized Cauchy Point Calculation

Question

I'm studying Numerical Optimization and I'm using the follow book (Wright, Stephen J., and Jorge Nocedal. "Numerical optimization.") for that. In the chapter about trust region, there is algorithm called (Generalized Cauchy Point Calculation).

Where it says: Find the vector $p_k^s$ that solves

$$ p_k^S = arg \min_{p \in \mathbb{R}^n} f_k + \nabla f_k^Tp \hspace{12pt} s.t \hspace{12pt} ||Dp||\leq \Delta_k\hspace{12pt} (1)$$ where D is a positive definite matrix

Calculate the scalar $\tau k > 0$ that minimizes $m_k(τp^S_k)$ subject to satisfying the trust-region bound, that is,

$\tau k = arg \min_{\tau >0}m_k(\tau p^S_k)$ s.t $||\tau D p^S_k|| \leq \Delta_k;$

$p^C_k= \tau_k p^S_k$

For this scaled version, we find that

$$p^S_k=-\dfrac{\Delta_k}{||D^{-1} \nabla f_k||}D^{-2}\nabla f_k \hspace{12pt} (2)$$

I don't know how to use (1) to get (2).

Thanks for help!

Answer 1

Let's write the Lagrangian for the optimization in (1) by introducing the Lagrange multiplier $\lambda$ for the constraint ( we are going to write the constraint in the quadratic form) \begin{align} \nabla f^Tp + \lambda (p^TD^2p-\Delta^2) \end{align} If we take the gradient of the Lagrangian function and set it to zero we get $p = -\lambda D^{-2} \nabla f$. Now in order to find $\lambda$ we set the constraint with equality and get $\lambda=\frac{\Delta}{\|D^{-1}\nabla f\|}$ which gives us the final result.