RUS  ENG
Полная версия
СЕМИНАРЫ

Межкафедральный семинар МФТИ по дискретной математике
10 ноября 2014 г. 19:00, г. Долгопрудный, Москва, ул. Льва Толстого, д. 16, Яндекс, БЦ «Морозов», ауд. «7.Небо»


Subgradient methods for huge-scale optimization problems

Yu. E. Nesterovab

a Université Catholique de Louvain
b Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow region

Аннотация: We consider a new class of huge-scale problems, the problems with sparse subgradients. The most important functions of this type are piece-wise linear. For optimization problems with uniform sparsity of corresponding linear operators, we suggest a very efficient implementation of subgradient iterations, which total cost depends logarithmically in the dimension. This technique is based on a recursive update of the results of matrix/vector products and the values of symmetric functions. It works well, for example, for matrices with few nonzero diagonals and for max-type functions.
We show that the updating technique can be efficiently coupled with the simplest subgradient methods. Similar results can be obtained for a new non- smooth random variant of a coordinate descent scheme. We present also the promising results of preliminary computational experiments.


© МИАН, 2024