1
$\begingroup$

In Numerical Optimization book by Nocedal, page 19, The author describes trust region method as follow:

In the second algorithmic strategy, known as trust region, the information gathered about $f$ is used to construct a model function $m_k$ whose behavior near the current point $x_k$ is similar to that of the actual objective function $f$.

we find the candidate step $p$ by approximately solving the following subproblem: $$\min_p ~~m_k(x_k + p)$$ where $x_k + p$ lies inside the trust region.

The model $m_k$ in is usually defined to be a quadratic function of the form $$ m_k(x_k + p) = f_k + p^\top \nabla f_k + \frac 1 2 p^\top B_k p $$

I have a naive question to ask: Specifically, I understand how to approximate $f$ but not why: we can use Taylor expansion to approximate, but I do not understand why we need approximate at fist place? Is that because we have a simpler system (quadratic form) that we can solve? Note, the approximation (quadratic form) may not be convex, as shown in the example in book page 20.

enter image description here

$\endgroup$
1
$\begingroup$

Yes, a quadratic approximation of the objective function is used, and updated/improved, as the optimization progresses. It is usually a simpler problem to solve than the original, and its solution doesn't require any (possibly long-running) evaluation of the actual objective function. But it's not entirely accurate, that's why the trust region is used to restrict the solution of the trust region problem to a region in which the quadratic approximation is accurate enough so that the actual objective function improves when the solution to the trust region problem is obtained. And if it doesn't improve enough, the trust region problem is re-solved using a smaller trust region. Note that in some cases, such as when the objective function can only be evaluated based on for instance the solution to some differential equations, there isn't even a closed form for the actual objective function, but a quadratic approximation can still be used.

Note that steepest descent and gradient descent also use a quadratic approximation to the objective function, but with the Hessian (quadratic term) always being the identity matrix. Indeed, trust region approach can be used on steepest descent/gradient descent (well, a trust region gradient descent would be called trust region steepest descent), Quasi-Newton, and Newton, with exact or finite difference gradients.

If BFGS Quasi-Newton method is used (damped if constrained), then each quadratic objective approximation can be convex. Using SR1 Quasi-Newton, or the actual Hessian, the quadratic objective approximation may or may not be convex. But each trust region problem does not need to be solved to global optimality, or even local optimality, and they will be bounded due to the trust region.

Finally, note that trust regions can be used for optimization subproblems without the subproblem objective function necessarily being quadratic. You could use a rational approximation, or even a cubic (if you're ready to have some fun with 3rd order tensors).

$\endgroup$
  • $\begingroup$ Thank you very much for such a nice answer! Could you give me an example of "objective function does not have closed form, but quadratic approximation can still be used?" You mentioned "the solution of some differential equations", but I cannot think about a example. $\endgroup$ – hxd1011 Aug 9 '16 at 14:06
  • $\begingroup$ See for example mathworks.com/matlabcentral/answers/… The optimizer can form a quadratic approximation of the objective function, for instance based on a finite-difference gradient, and a Quasi-Newton approximation of the Hessian. In some cases, it is possible to find the gradient directly as the numerical solution to adjoint differential equations rather than requiring use of finite differences. $\endgroup$ – Mark L. Stone Aug 9 '16 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.