11
$\begingroup$

In Nocedal & Wright's book on Numerical Optimization, there is a statement in section 2.2 (page 27), "Generally speaking, it is easier to preserve scale invariance for line search algorithms than for trust-region algorithms". In that same section, they talk about having new variables that are scaled versions of the original variables, which can help with both line search and trust region. Another approach is preconditioning. For trust region methods, preconditioning is equivalent to having elliptical trust regions and thus, provides scale invariance. However, a similar intuition is not clear for preconditioning for line search. In what ways is line search better suited for scale invariance? Are there some practical considerations?

Also, I have a question regarding preconditioning for trust region methods. For a highly ill-conditioned problem, will a good preconditioner reduce both the number of outer Newton iterations and inner CG iterations or only the latter? Since, the trust region is ellipsoidal in the original space, a good preconditioner should lead to an ellipsoid that will match the landscape better. I feel this might reduce the number of outer Newton iterations by forcing the algorithm to take better directions. Is this right?

$\endgroup$
2
$\begingroup$

I suppose there could be some difference between how line-search and trust-region methods handle scaling, but I really don't see it bear out in practice as long as we're aware of the scaling. And, to be clear, the Nocedal and Wright book was talking about affine scaling. Nonlinear scaling is somewhat trickier to quantify.

To see why, say we want to minimize $f:X\rightarrow \mathbb{R}$, but we want to scale the variables by some kind of nonsingular, self-adjoint operator $A\in\mathscr{L}(X)$. Define $J:X\rightarrow \mathbb{R}$ as the scaled objective function. Then, \begin{align*} J(x) =& f(Ax)\\ \nabla J(x) =& A\nabla f(Ax)\\ \nabla^2 J(x) =& A\nabla^2 f(Ax) A \end{align*} The real difference in algorithms is what happens to the scaling $A$. In Newton's method, we solve $$ \nabla^2 J(x) \delta x = -\nabla J(x) $$ or $$ A\nabla^2 f(Ax) A \delta x = -A\nabla f(Ax) $$ Assuming the Hessian is nonsingular, we have $$ A \delta x = -\nabla^2 f(Ax)^{-1} \nabla f(Ax) $$ Basically, the scaling cancels out and disappears, so it doesn't affect the direction. That's why we say Newton's method is affine scale invariant.

Alright, so now let's say that we don't have the Hessian. Really, at the end of the day, trust-region methods rely on solving the system $$ H \delta x = -\nabla J(x) $$ for some kind of Hessian approximation $H$. Most of the time, we're going to use Steihaug-Toint truncated-CG because it works well. If we plug back in our scaling, we have $$ H \delta x = -A \nabla f(Ax) $$ If we're throwing CG at this system, that basically means that we have one tool for dealing with the scaling $A$ and that's the Hessian or its approximation $H$. Theoretically, we could change the shape of trust-region, but all that really means is cutting off our step earlier or later. This does affect the step, but I've always found it a pain to control.

In a line-search method, we can view our iterate as applying some kind of magic function $\phi$ to our gradient. Hence, for the scaled direction: $$ \delta x = \phi(-A\nabla f(Ax)) $$ Maybe $\phi$ computes the Newton step. Maybe it $\phi$ computes the BFGS step. Whatever. Certainly, we have some restrictions such as we likely need $\phi$ to produce a descent direction, but it does highlight that there's a great amount of flexibility here. That means that we have a greater amount of tools at our disposal to handle the scaling $A$.

Now, what are these tools and should we be using them? Personally, I think the answer is no. Unless you really know your application and have a specialized algorithm to find the solution, inexact Newton methods work really, really well. By inexact Newton, I mean solving the system $$ \nabla^2 J(x) \delta x = -\nabla J(x) $$ inexactly using CG. This is precisely using Steihaug-Toint in the trust-region setting (p. 171 in Nocedal and Wright) or Newton-CG for line-search (p. 169 in Nocedal and Wright). They work pretty close to the same and they don't care about affine scaling. They also don't require storing the Hessian, only Hessian-vector products are required. Really, these algorithms should be the workhorses for most problems and they don't care about affine scaling.

As far as the preconditioner for the trust-region problem, I don't think there's any easy way to tell apriori if you're going to improve the number of overall optimization iterations or not. Really, at the end of the day, optimization methods operate in two modes. In mode one, we're too far from the Newton's method convergence radius, so we globalize and just force the iterates to insure that the objective goes down. Trust-region is one way. Line-search is another. In mode two, we're in the Newton's method convergence radius, so we try not to mess with it and let Newton's method do it's job. In fact, we can see this in the convergence proofs of things like trust-region methods. For example, look at Theorem 4.9 (p.93 in Nocedal and Wright). Very explicitly, they state how the trust-region becomes inactive. In this context, what's the utility of the preconditioner? Certainly, when we're in the Newton's method convergence radius, we do far less work and the number of CG iterations goes down. What happens when we're outside this radius? It sort of depends. If we calculate the full-Newton step, then the benefit is that we did less work. If we cut off our step early due to truncation from truncated-CG, then our direction will be in the Krylov subspace $$ \{-P\nabla J(x),-(PH)(P\nabla J(x)),\dots,-(PH)^k(P\nabla J(x))\} $$ where $P$ is the preconditioner and $H$ is our Hessian approximation. Is this a better subspace to find a direction in than $$ \{-\nabla J(x),-(H)(\nabla J(x)),\dots,-(H)^k(\nabla J(x))\}? $$ It's hard to tell. Maybe. Maybe not. The theory just tells us that we converge in a finite number of steps.

This doesn't mean that there's not value in defining a good preconditioner. However, I'm not sure how someone defines a preconditioner to assist in the optimization for points away the Newton's method convergence radius. Typically, we design a preconditioner to cluster the eigenvalues of the Hessian approximation, which is a tangible, measurable goal.

tldr; Practically speaking, there are a greater variety of ways for a line-search method to generate an iterate than a trust-region method, so it's possible there's an amazing way to handle affine scaling. However, just use an inexact Newton method and it doesn't matter. A preconditioner does affect the performance of an algorithm away from the Newton's method convergence radius, but it's hard to quantify how, so just design a preconditioner to cluster the eigenvalues of the Hessiasn approximation.

$\endgroup$

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.