Self-concordant functions for optimization on smooth manifolds

摘要

This paper discusses self-concordant functions on smooth manifolds. In Euclidean space, such functions are utilized extensively as barrier functions in interior-point methods for polynomial time optimization algorithms. Here, the self-concordant function is carefully defined on a differential manifold in such a way that the properties of self-concordant functions in Euclidean space are preserved. A Newton decrement is defined and analyzed for this class of functions. Based on this, a damped Newton algorithm is proposed for the optimization of self-concordant functions. Under reasonable technical assumptions such as geodesic completeness of the manifold, this algorithm is guaranteed to fall in any given small neighborhood of the optimal solution in a finite number of steps. The existence and uniqueness of the optimal solution is also proved in this paper. Hence, the optimal solution is a global one. Furthermore, it ensures a quadratic convergence within a neighborhood of the minimal point. This neighborhood can be specified in terms of the Newton decrement. The computational complexity bound of the proposed approach is also given explicitly. This complexity bound is shown to be of the order O(- ln(ε)), where ε is the desired precision. Some interesting optimization problems are given to illustrate the proposed concept and algorithm.