Laboratory of Structural Methods of Data Analysis in Predictive
Modeling Moscow Institute of Physics and Technology
ENG
Логин:
Пароль:

Huge-scale problems

Описание направления:

В последнее десятилетие наблюдается стремительный рост размерности решаемых задач оптимизации и статистики, сильно опережающий темпы роста доступных вычислительных мощностей. Это во многом обусловлено взрывным ростом Интернета, а также существенными прорывами в медицине. «Большие данные» (Big Data) стали основным трендом и богатым источником задач в оптимизации, статистике и многих других областях.

 

Для решения оптимизационных и статистических задач огромной размерности требуется разработка новых методов, сложность которых слабо зависела бы от размерности решаемых задач. Сотрудники магистерской программы являются признанными специалистами в области разработки алгоритмов для задач огромной размерности.

Публикации:

Primal-Dual Subgradient Method for Huge-Scale Linear Conic Problems

In this paper we develop a primal-dual
subgradient method for solving huge-scale
Linear Conic Optimization Problems.
Our main assumption is that the primal cone is
formed as a direct product of many small-dimensional convex cones, and that the matrix A
of corresponding linear operator is
uniformly sparse.
In this case, our method can
approximate the primal-dual optimal solution with accuracy ε in O(1/ε^2) iterations.
At
the same time, complexity of each iteration of this scheme does not exceed O(rq log_2 n) operations, where r and q are the maximal numbers of nonzero elements in the rows and
columns of matrix A, and n is the number variables.

Преподаватели: Нестеров Юрий Евгеньевич, Шпирко Сергей Валерьевич, 30 декабря 2014

Random walk based web page ranking functions learning with gradient-free optimization methods

In this paper we consider a problem of web page relevance to a search query. We are working in the framework called Semi-Supervised PageRank which can account for some properties which are not considered by classical approaches such as PageRank and BrowseRank algorithms. We introduce a graphical parametric model for web pages ranking. The goal is to identify the unknown parameters using the information about page relevance to a number of queries given by some experts (assessors). The resulting problem is formulated as an optimization one. Due to hidden huge dimension of the last problem we use random gradient-free methods to solve it. We prove the convergence theorem and give the number of arithmetic operations which is needed to solve it with a given accuracy.

Преподаватели: Гасников Александр Владимирович, Двуреченский Павел , Максим Жуковский, 27 декабря 2014

Методы оптимизации для задач с неточным оракулом в гильбертовом пространстве

В работе обсуждается применение прокс-методов конечномерной оптимизации с неточным оракулом для задач оптимизации в Гильбертовом пространстве. Даются оценки погрешностей предлагаемых алгоритмов.

Преподаватели: Гасников Александр Владимирович, Двуреченский Павел , 27 декабря 2014

Операторы Минковского и их применение в дифференциальных играх

В работе предложен алгоритм для поиска квазиоптимальных стратегий в нелинейных дифференциальных играх на плоскости с целевым множеством. Даны оценки погрешности алгоритма.

Преподаватели: Двуреченский Павел , Иванов Григорий Евгеньевич, 27 декабря 2014

Об универсальности энтропии, как функции Ляпунова и функции, описывающей экспоненциальную концентрацию инвариантной меры, в распределенной системе химических реакций

Преподаватели: Гасников Александр Владимирович, Двуреченский Павел , 27 декабря 2014

Прошедшие мероприятия:

19.05.2014

20.05.2014

21.05.2014

22.05.2014

Invited Plenary Talk (title TBA)

SIAM (Society for Industrial and Applied Mathematics)

15.05.2014

16.05.2014

Advances in Optimization and Statistics

Institute of Information Transmission Problems of RAS (Kharkevich Institute)

21.02.2014

PreMoLab 2014 - I

Institute of Information Transmission Problems of RAS (Kharkevich Institute). Конференция пройдет в Институте проблем передачи информации РАН (ИППИ РАН), к.615

26.12.2013

New trends in Predictive Modeling

Institute of Information Transmission Problems of RAS (Kharkevich Institute). All talks take place at Institute for Information Transmission Problems (B. Karetny, 19).

26.12.2013
Moscow Institute of Physics and Technology

Защита докторской диссертации Ю.Е. Нестерова

Члены лаборатории:
Spokoiny Vladimir
Должность: Руководитель
Polyak Boris
Должность: Ведущий научный сотрудник
Shpirko Sergei
Должность: Ведущий научный сотрудник
Gasnikov Alexander
Должность: Ведущий научный сотрудник
Dvurechensky Pavel
Должность: Ведущий научный сотрудник
Maximov Yury
Должность: Младший научный сотрудник
Nazin Alexander
Должность: Ведущий научный сотрудник