Rescaling and Asymptotic Acceleration in Unconstrained Quadratic Optimisation

Abstract We investigate the properties of a class of piecewise-fractional maps arising from the introduction of an invariance under rescaling into convex quadratic maps. The subsequent maps are quasiconvex, and pseudoconvex on specific convex cones; they can be optimised via exact line search along admissible directions. We study the minimisation of such relaxed maps via coordinate descents with gradient-based rules, placing a special emphasis on coordinate directions verifying a maximum-alignment property in the reproducing kernel Hilbert spaces related to the underlying positive-semidefinite matrices. In this setting, we illustrate theoretically and empirically that accounting for the optimal rescaling of the iterates can in certain situations substantially accelerate the unconstrained minimisation of convex quadratic maps.