Projected gradient descent accumulates at Bouligand stationary points

Abstract

This paper considers the projected gradient descent (PGD) algorithm for the problem of minimizing a continuously differentiable function on a nonempty closed subset of a Euclidean vector space. Without further assumptions, this problem is intractable and algorithms are only expected to find a stationary point. PGD generates a sequence in the set whose accumulation points are known to be Mordukhovich stationary. In this paper, these accumulation points are proven to be Bouligand stationary, and even proximally stationary if the gradient is locally Lipschitz continuous. These are the strongest stationarity properties that can be expected for the considered problem.

References in corpus (7)

• Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms
• Optimality conditions for disjunctive programs based on generalized differentiation with application to mathematical programs with equilibrium constraints
• Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy
• On the complexity of finding a local minimizer of a quadratic function over a polytope
• The effect of smooth parametrizations on nonconvex optimization landscapes
• Regularity Properties of Non-Negative Sparsity Sets
• On estimating the regular normal cone to constraint systems and stationarity conditions

Cited by in corpus (3)

• Low-rank optimization methods based on projected projected-gradient descent that accumulate at Bouligand stationary points
• Eigengap Sparsity for Covariance Parsimony
• The tangent cone to the real determinantal variety: various expressions and a proof