A gradient method in a Hilbert space with an optimized inner product:
achieving a Newton-like convergence
Academic Article

Overview

Research

View All

Overview

abstract

In this paper we introduce a new gradient method which attains quadratic
convergence in a certain sense. Applicable to infinite-dimensional
unconstrained minimization problems posed in a Hilbert space $H$, the approach
consists in finding the energy gradient $g(\lambda)$ defined with respect to an
optimal inner product selected from an infinite family of equivalent inner
products $(\cdot,\cdot)_\lambda$ in the space $H$. The inner products are
parameterized by a space-dependent weight function $\lambda$. At each iteration
of the method, where an approximation to the minimizer is given by an element
$u\in H$, an optimal weight $\hlambda$ is found as a solution of a nonlinear
minimization problem in the space of weights $\Lambda$. It turns out that the
projection of $\kappa g(\hlambda)$, where $0<\kappa \ll 1$ is a fixed step
size, onto a certain finite-dimensional subspace generated by the method is
consistent with Newton's step $h$, in the sense that $P_u(\kappa
g(\hlambda))=P_u(h)$, where $P_u$ is an operator describing the projection onto
the subspace. As demonstrated by rigorous analysis, this property ensures that
thus constructed gradient method attains quadratic convergence for error
components contained in these subspaces, in addition to the linear convergence
typical of the standard gradient method. We propose a numerical implementation
of this new approach and analyze its complexity. Computational results obtained
based on a simple model problem confirm the theoretically established
convergence properties, demonstrating that the proposed approach performs much
better than the standard steepest-descent method based on Sobolev gradients.
The presented results offer an explanation of a number of earlier empirical
observations concerning the convergence of Sobolev-gradient methods.