Conic Approximations and Collinear Scalings for Optimizers

TLDR

Many optimization algorithms update quadratic approximations to their objective functions. This paper proposes generalizing quadratic approximations to conic approximations—ratios of quadratics with squared denominators—to better match objective function values and gradients and improve minimizer estimates, and it presents general features of algorithms using these approximations and collinear scalings. The authors achieve this by extending affine domain scalings to collinear scalings, \(S(w)=x_0+Jw/(1+h^T w)\), which makes the Hessian of the composed function \(fS\) more constant and better conditioned. The resulting conic approximations and collinear scalings are invariant under affine scalings and under the broader group of invertible collinear scalings, encompassing Newton–Raphson and variable metric algorithms.

Abstract

Many optimization algorithms update quadratic approximations to their objective functions. This paper suggests a generalization from quadratic to conic approximations, defined as ratios of quadratics whose denominators are squares, $(\alpha + \alpha ^T x)^2 $, These can better match the values and gradients of typical objective functions, and hence give better estimates for their minimizers. Equivalently, affine scalings, $S(w) = x_0 + Jw$, of the domain of objective functions f are generalized to collinear scalings, $S(w) = x_0 + Jw/(1 + h^T w)$, to make the Hessian of the composition $fS$ more nearly constant as well as better conditioned. Certain general features of optimization algorithms using conic approximations and collinear scalings are presented. These are not only invariant under affine scalings, along with Newton–Raphson and variable metric algorithms, but they are also invariant under the larger group. of invertible collinear scalings.