他組織イベント案内

2018-05-14 最適化,数値解析セミナー

投稿者:  中務 佑治(国立情報学研究所)
会場: 国立情報学研究所1208室
概要: Andre Uschmajew (Max Planck Institute Leipzig) 講演

日程 2018年 5月14日(月) 15:00-16:00
会場 国立情報学研究所1208室
本文 Dr. Andre Uschmajewによるセミナーのご案内をお送りいたします. 是非ご参加ください. 講演者はテンソルや最適化問題の第一人者です.
講演者 Andre Uschmajew (Max Planck Institute Leipzig)
https://www.mis.mpg.de/tensopt/publications/andre-uschmajew.html
タイトル Gradient sampling for nonsmooth optimization on manifolds and varieties
概要 Gradient sampling (GS) is a conceptually simple method for minimization of locally Lipschitz functions. The idea is to approximate the subdifferential at a given point by a convex hull of randomly sampled nearby gradients. We consider generalizations of this approach to optimization problems posed on Riemannian manifolds or algebraic subvarieties admitting an a-regular stratification. The latter scenario is motivated by optimization problems on low-rank matrices or tensors. The main theoretical task is to prove that the minimum norm element in a convex hull of vectors, which are obtained by transporting gradients from nearby points to the current tangent space, is a descent direction (w.r.t. a retraction), provided that the number of sampled gradients is larger than the dimension of the manifold/variety. For varieties it is further necessary to discuss what should happen in the singular points. Under reasonable assumptions, we can prove that with probability one the limit points of our proposed GS algorithms are Clarke stationary points relative to their strata. When the dimension of the manifold is too large, the full GS approach can be computationally expensive, but our numerical experiments, which concern the sparse vector problem on a sphere and robust low-rank matrix approximation, illustrate that a small number of gradient samples can be sufficient in practice.
Joint work with Seyedehsomayeh Hosseini.

References:
1. S. Hosseini, A. Uschmajew: A gradient sampling method on algebraic varieties and application to nonsmooth low-rank optimization, preprint. URL: http://www.mis.mpg.de/fileadmin/uschmajew/uschmajew_aGradientPreprint.pdf
2. S. Hosseini, A. Uschmajew: A Riemannian gradient sampling algorithm for nonsmooth optimization on manifolds, SIAM J. Optim., 27 (2017) 1, p. 173-189. URL: http://dx.doi.org/10.1137/16M1069298
問い合わせ先 中務 佑治
e-mail: nakatsukasaseparatornii.ac.jp
詳細 web https://www.nii.ac.jp/en/event/2018/0514.html