5
$\begingroup$

Geometrically, scaling and preconditioning seem to address similar challenges in optimization. However, these two concepts are implemented very differently. Take trust region Newton method, as an example. When a problem is poorly scaled, an elliptical trust region is recommended. Is it possible to formulate an equivalent preconditioner based approach such that one works with spherical trust regions?

update: Section 7.5 in Practical Optimization by Gill , Murray & Wright gives a clear connection between variable scaling and preconditioning the hessian.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The ideas are certainly related, at the very least if your preconditioner corresponds to a symmetric and positive definite matrix. This is because in that case, preconditioning simply means using a different inner product, i.e., a different metric. This can be interpreted as saying that what is a very elongated ellipsoid in the usual $l_2$ metric may turn out to be much closer to a sphere in the preconditioner metric. This picture is valid because the application of an SPD preconditioner can be interpreted as a rotation, axis-parallel scaling, and inverse rotation.

The picture becomes much less clear to interpretation if you use preconditioners that correspond to indefinite or non-symmetric matrices since these can then no longer be interpreted as a simple change in metric.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Err, if the preconditioner varies from point to point I'm not sure it's so simple. Then you have a spatially varying inner product (ie., you are optimizing over a non-flat Riemannian manifold diffeomorphic to $\mathbb{R}^n$). Is there an easy transformation of the problem such that a black-box spherical trust region solver would generate the exact same sequence of iterates as a trust region solver with a spatially varying preconditioner? I've been thinking about this and haven't been able to figure it out. $\endgroup$
    – Nick Alger
    Jun 7, 2015 at 18:16
  • 1
    $\begingroup$ I don't know, but you should look for the term "variable metric" optimization methods. I think that there are papers by Deuflhard from the 1980s and 1990s worth reading. $\endgroup$
    – Wolfgang Bangerth
    Jun 7, 2015 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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