A gradient sampling method on algebraic varieties and application to nonsmooth low-rank optimization
A gradient sampling method on algebraic varieties and application to nonsmooth low-rank optimization
Dokument öffnen (805.3KB)Datum der Veröffentlichung
10.2016Verlag / herausgebende Einrichtung
Institut für Numerische Simulation (INS)Verlagsort
BonnMetadaten
Zur Langanzeige
Zitierbarer Link (Handle URI) 
https://hdl.handle.net/20.500.11811/11861
Inhalt
In this paper, a nonsmooth optimization method for locally Lipschitz functions on real algebraic varieties is developed. To this end, the set-valued map ε-conditional subdifferential x → ∂Nεf(x) := ∂εf(x) + N (x) is introduced, where ∂εf(x) is the Goldstein-ε-subdifferential and N (x) is a closed convex cone at x. It is proved that negative of the shortest ε-conditional subgradient provides a descent direction in T (x), which denotes the polar of N (x). The ε-conditional subdifferential at an iterate xℓ can be approximated by a convex hull of a finite set of projected gradients at sampling points in xℓ + εℓBT(xℓ) (0, 1) to T(xℓ), where T(xℓ) is a linear space in the Bouligand tangent cone and BT(xℓ)(0, 1) denotes the unit ball in T(xℓ). The negative of the shortest vector in this convex hull is shown to be a descent direction in the Bouligand tangent cone at xℓ. 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 ℳ. 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 M≤r of real M × N matrices of rank at most r, specifically robust low-rank matrix approximation and recovery in the presence of outliers.
Schlagwörter
Lipschitz function, descent direction, Clarke subdifferential, algebraic varieties, Riemannian manifolds, robust low-rank matrix recovery
Klassifikation (DDC)
510 Mathematik 518 Numerische AnalysisErstpublikation
https://ins.uni-bonn.de/publication/preprintsZugehörige Publikation(en)
https://doi.org/10.1137/17M1153571Reihe, Nummer
INS Preprints ; 1624Hosseini, Seyedehsomayeh; Uschmajew, André: A gradient sampling method on algebraic varieties and application to nonsmooth low-rank optimization. In: INS Preprints, 1624.
Online-Ausgabe in bonndoc: https://hdl.handle.net/20.500.11811/11861
Online-Ausgabe in bonndoc: https://hdl.handle.net/20.500.11811/11861
@unpublished{handle:20.500.11811/11861,
author = {{Seyedehsomayeh Hosseini} and {André Uschmajew}},
title = {A gradient sampling method on algebraic varieties and application to nonsmooth low-rank optimization},
publisher = {Institut für Numerische Simulation (INS)},
year = 2016,
month = oct,
INS Preprints},
volume = 1624,
note = {In this paper, a nonsmooth optimization method for locally Lipschitz functions on real algebraic varieties is developed. To this end, the set-valued map ε-conditional subdifferential x → ∂Nεf(x) := ∂εf(x) + N (x) is introduced, where ∂εf(x) is the Goldstein-ε-subdifferential and N (x) is a closed convex cone at x. It is proved that negative of the shortest ε-conditional subgradient provides a descent direction in T (x), which denotes the polar of N (x). The ε-conditional subdifferential at an iterate xℓ can be approximated by a convex hull of a finite set of projected gradients at sampling points in xℓ + εℓBT(xℓ) (0, 1) to T(xℓ), where T(xℓ) is a linear space in the Bouligand tangent cone and BT(xℓ)(0, 1) denotes the unit ball in T(xℓ). The negative of the shortest vector in this convex hull is shown to be a descent direction in the Bouligand tangent cone at xℓ. 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 ℳ. 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 M≤r of real M × N matrices of rank at most r, specifically robust low-rank matrix approximation and recovery in the presence of outliers.},
url = {https://hdl.handle.net/20.500.11811/11861}
}
author = {{Seyedehsomayeh Hosseini} and {André Uschmajew}},
title = {A gradient sampling method on algebraic varieties and application to nonsmooth low-rank optimization},
publisher = {Institut für Numerische Simulation (INS)},
year = 2016,
month = oct,
INS Preprints},
volume = 1624,
note = {In this paper, a nonsmooth optimization method for locally Lipschitz functions on real algebraic varieties is developed. To this end, the set-valued map ε-conditional subdifferential x → ∂Nεf(x) := ∂εf(x) + N (x) is introduced, where ∂εf(x) is the Goldstein-ε-subdifferential and N (x) is a closed convex cone at x. It is proved that negative of the shortest ε-conditional subgradient provides a descent direction in T (x), which denotes the polar of N (x). The ε-conditional subdifferential at an iterate xℓ can be approximated by a convex hull of a finite set of projected gradients at sampling points in xℓ + εℓBT(xℓ) (0, 1) to T(xℓ), where T(xℓ) is a linear space in the Bouligand tangent cone and BT(xℓ)(0, 1) denotes the unit ball in T(xℓ). The negative of the shortest vector in this convex hull is shown to be a descent direction in the Bouligand tangent cone at xℓ. 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 ℳ. 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 M≤r of real M × N matrices of rank at most r, specifically robust low-rank matrix approximation and recovery in the presence of outliers.},
url = {https://hdl.handle.net/20.500.11811/11861}
}
Die folgenden Nutzungsbestimmungen sind mit dieser Ressource verbunden:
