Self-concordant functions for optimization on smooth manifolds

摘要

This paper discusses self-concordant functions on smooth manifolds. In Euclidean space, this class of functions are utilized extensively in interior-point methods for optimization because of the associated low computational complexity. Here, the self-concordant function is carefully defined on a differential manifold. First, generalizations of the properties of self-concordant functions in Euclidean space are derived. Then, Newton decrement is defined and analyzed on the manifold that we consider. Based on this, a damped Newton algorithm is proposed for optimization of self-concordant functions, which guarantees that the solution falls in any given small neighborhood of the optimal solution, with its existence and uniqueness also proved in this paper, in a finite number of steps. It also ensures quadratic convergence within a neighborhood of the minimal point. This neighborhood can be specified by the the norm of Newton decrement. The computational complexity bound of the proposed approach is also given explicitly. This complexity bound is O(- ln(/spl epsi/)), where a is the desired precision. An interesting optimization problem is given to illustrate the proposed concept and algorithm.