Gradient Projection Method on Matrix Manifolds
- PDF / 531,648 Bytes
- 9 Pages / 612 x 792 pts (letter) Page_size
- 69 Downloads / 202 Views
nt Projection Method on Matrix Manifolds M. V. Balashova,* a Trapeznikov
Institute of Control Sciences, Russian Academy of Sciences, Moscow, 117997 Russia *e-mail: [email protected]
Received November 26, 2019; revised December 24, 2019; accepted April 9, 2020
Abstract—The minimization of a function with a Lipschitz continuous gradient on a proximally smooth subset of a finite-dimensional Euclidean space is considered. Under the restricted secant inequality, the gradient projection method as applied to the problem converges linearly. In certain cases, the linear convergence of the gradient projection method is proved for the real Stiefel or Grassmann manifolds.
Keywords: Lipschitz continuous gradient, proximal smoothness, gradient projection method, metric projection, nonconvex optimization problem, restricted secant inequality, Stiefel manifold, Grassmann manifold DOI: 10.1134/S0965542520090079
1. INTRODUCTION AND BASIC NOTATION 1.1. Introduction The gradient projection method (GPM) (also known as the projection-proximal method) for solving the problem
min f ( x) A
(1)
was proposed in [1, 2]. If f ( x) in (1) is a strongly convex function with a Lipschitz continuous gradient and the set A is convex and closed, then the GPM converges with the rate of a geometric progression (or linearly, exponentially). The GPM has been proved to be efficient for various optimization problems [2, 3]. An important nonconvex problem (1) is the minimization of a smooth function f on a matrix manifold A without boundary. For example, A can be the Stiefel or Grassmann manifold [4]. If the set A in problem (1) is a smooth manifold, then versions of the GPM with steps related to local geodesics on the manifold are traditionally used [5–9]. Newton’s method is also applied to solve the problem mainly in the case of quadratic functions or constraints [4, 6]. However, Newton’s method converges locally in the general case and there are few explicit estimates for its convergence domain in the case of nonconvex problem (1). The last is also true for the GPM. In this paper, we formulate the GPM for the minimization of a smooth generally nonconvex function on the real Stiefel or Grassmann manifold. A key point is that the real Stiefel manifold is a proximally smooth set with constant of proximal smoothness 1 and the real Grassmann manifold is also a proximally smooth set with constant 1/ 2. Note that, in view of the compactness assumptions, any compact smooth manifold without boundary is proximally smooth. Thus, the task is to find the best (i.e., largest) constant. Moreover, Theorems 2 and 4 provide sufficient conditions for the linear convergence of the GPM on Stiefel and Grassmann manifolds, respectively. In contrast to the above-mentioned works, the properties of proximally smooth sets make it possible to present a GPM version with a simple explicit convergence estimate. Additionally, the results do not depend on geodesics on manifolds. This is another advantage of the proposed approach. However, problem (1) has to be embedded in Euclide
Data Loading...
