Second order gradient-based method to locally maximize sum of squares

Question

Non-linear least squares algorithms such as Gauss-Newton allow me to (locally) minimize a sum of squares of residuals (the output of some non-linear function). I.e. locally solve: $$ \mathbf{x} = \arg\min_{\mathbf{x}^*} \|\mathbf{f}(\mathbf{x}^*)\|^2, $$ where $\mathbf{x}$ is a vector of variables, and $\mathbf{f}()$ is a function that outputs a vector of residuals. Assume there are more residuals than variables, so the problem is well conditioned.

The nice thing about least squares solvers is that they offer second-order convergence, but only require the first (not second) derivative of residuals ($\mathbf{f}(\mathbf{x})$) to be computed.

Is there a similarly effective (e.g. second-order) algorithm for maximizing a sum of squares, i.e.

$$ \mathbf{x} = \arg\max_{\mathbf{x}^*} \|\mathbf{f}(\mathbf{x}^*)\|^2, $$

given only the residuals and their gradient? This is for the case that the residuals are in a finite range (so the cost doesn't zoom off to infinity), and there are no constraints on the variables being optimized.

Note that, while this can be rephrased as $$ \mathbf{x} = \arg\min_{\mathbf{x}^*} -\|\mathbf{f}(\mathbf{x}^*)\|^2, $$ it's not clear to me what the update step would be in this case, since Gauss Newton can only be used to minimize a sum of squares, not a negated sum of squares.

I need this for an image alignment problem: I have a scalar field, e.g. an intensity image, and want to maximize the sum of squares of intensity at a predetermined set of sample points, subject to some affine warp of the sample points. I want to find the affine warp that maximizes the sum of squares of the scalar field at the sample points. Note that I want to find a local solution, i.e. the solution I'd get if I did gradient descent from a particular starting point, but with a more efficient, second order algorithm.

If it's not possible, is there an intuitive explanation as to why not?

Answer 1

Least squares costs always have a lower bound: zero. They need not have an upper bound in general.

Gauss-Newton approximates the Hessian of a problem with a positive semi-definite matrix, constructed from the Jacobian. This means it can only model quadratics with a minimum. It drops other higher order terms, that might otherwise change the quadratic model to that with a maximum. If you want to maximize the sum of squares, then you need to include those terms, and hope that you then get a negative semi-definite matrix. However, there is no guarantee you will.

In your particular case, you are maximizing costs over a discrete field (pixel values). Locally, the gradients may imply that the cost will continue increasing the further you move, even if the neighbouring samples do not reflect that - indeed they cannot reflect that, since they are bounded. This is problematic.