Trust region Newton method. If ∇2f(x) is singular (or very ill-conditioned), the Newton step Δxnt=−∇2f(x)−1∇f(x) is not well defined. Instead we can define a search direction Δxtr as the solution of
minimizesubject to(1/2)vTHv+gTv∥v∥2≤γ,
where H=∇2f(x), g=∇f(x), and γ is a positive constant. The point x+Δxtr minimizes the second-order approximation of f at x, subject to the constraint that ∥(x+Δxtr)−x∥2≤γ. The set {v∣∥v∥2≤γ} is called the trust region. The parameter γ, the size of the trust region, reflects our confidence in the second-order model.
Show that Δxtr minimizes
(1/2)vTHv+gTv+β^∥v∥22,
for some β^. This quadratic function can be interpreted as a regularized quadratic model for f around x.