Trust region method

From Glossary

Jump to: navigation, search

The iteration is defined as LaTeX: x' = x + p, where LaTeX: p is the (complete) change determined by a subproblem of the form:

LaTeX: 
\max \{ F(p) : \| p \| \le D \},

where F depends on the iterate and is an approximation of the change in objective function value. The particular norm and the magnitude of D determine the set of admissible change values (p), and this is called the trust region. A common choice of F is the quadratic form using the Taylor expansion about the current iterate, x, as:


LaTeX: 
F(p) = p^T \nabla f(x) + \frac{1}{2} p^T H_f(x) p.


Using the Euclidean norm and applying the Lagrange Multiplier Rule  to the subproblem yields p from the equation:


LaTeX: 
(H_{f(x)} - u I) p = - \nabla f(x) \mbox{ for some } u \ge 0.


Note that for u=0, the iteration is Newton's method, and for very large u, the iteration is nearly Cauchy's steepest ascent.


Views
Personal tools