A gradient sampling method on algebraic varieties and application to nonsmooth low-rank optimization

Abstract

In this paper, a nonsmooth optimization method for locally Lipschitz functions on real algebraic varieties is developed. To this end, the set-valued map <em>ε</em>-conditional subdifferential <em>x</em> &#8594; ∂<em>^N_εf</em>(<em>x</em>) := ∂<em>_εf</em>(<em>x</em>) + <em>N</em> (<em>x</em>) is introduced, where ∂<em>_εf</em>(<em>x</em>) is the Goldstein-<em>ε</em>-subdifferential and <em>N</em> (<em>x</em>) is a closed convex cone at <em>x</em>. It is proved that negative of the shortest <em>ε</em>-conditional subgradient provides a descent direction in <em>T</em> (<em>x</em>), which denotes the polar of <em>N</em> (<em>x</em>). The <em>ε</em>-conditional subdifferential at an iterate <em>x_&#8467;</em> can be approximated by a convex hull of a finite set of projected gradients at sampling points in <em>x_&#8467;</em> + <em>ε_&#8467;B_{T(x_&#8467;)}</em> (0, 1) to <em>T</em>(<em>x_&#8467;</em>), where <em>T</em>(<em>x_&#8467;</em>) is a linear space in the Bouligand tangent cone and <em>B_{T(x_&#8467;)}</em>(0, 1) denotes the unit ball in <em>T</em>(<em>x_&#8467;</em>). The negative of the shortest vector in this convex hull is shown to be a descent direction in the Bouligand tangent cone at <em>x_&#8467;</em>. The proposed algorithm makes a step along this descent direction with a certain step-size rule, followed by a retraction to lift back to points on the algebraic variety &Mellintrf;. The convergence of the resulting algorithm to a critical point is proved. For numerical illustration, the considered method is applied to some nonsmooth problems on varieties of low-rank matrices <em>M</em>≤<em>r</em> of real <em>M</em> × <em>N</em> matrices of rank at most <em>r</em>, specifically robust low-rank matrix approximation and recovery in the presence of outliers.