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

Primal-dual subgradient methods

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

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

В таких приложениях полезными оказываются прямо-двойственные методы. Разработка эффективных прямо-двойственных методов первого порядка – важное направление исследований сотрудников магистерской программы. 

Публикации:

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

Алгоритм зеркального спуска для минимизации средних потерь, поступающих пуассоновским потоком

Для стохастической системы, функционирующей в непрерывном времени, рассматривается задача минимизации ожидания интегральных потерь на заданном горизонте. Потери происходят в моменты скачков пуассоновского процесса и являются непрерывной выпуклой функцией управляющего параметра, значения которого образуют выпуклый компакт в конечномерном пространстве. В моменты скачков оракул выдает стохастически зашумленные субградиенты функции потерь, ограниченные в среднеквадратическом; шум аддитивный, несмещенный. Предлагается стратегия управления, порожденная алгоритмом зеркального спуска. Для нее доказана явная верхняя граница превышения ожидания интегральных потерь над минимумом. Рассмотрен пример, в котором эта стратегия применена к модели массового обслуживания.

Преподаватели: Назин Александр Викторович, Anulova, SV, Tremba, AA, 17 ноября 2014

Адаптивные алгоритмы зеркального спуска в задачах выпуклой стохастической оптимизации

Рассматривается задача выпуклой стохастической оптимизации и метод зеркального спуска (МЗС) как в «классической», так и в «адаптивной» постановке, когда последовательность обобщенной температуры не определена априори и настраивается в процессе наблюдений градиента и итеративного оценивания оптимальной точки. Доказана соответствующая адаптивная верхняя граница ошибки (относительно оптимизируемой функции) в предположении известного ограничения нормы градиента с вероятностью 1. Это является своеобразной платой за адаптивность метода по сравнению с более слабым ограничением в среднем в неадаптивной постановке.

Преподаватели: Назин Александр Викторович, 17 ноября 2014

Primal-dual methods for solving infinite-dimensional games

Преподаватели: Спокойный Владимир Григорьевич, Нестеров Юрий Евгеньевич, Двуреченский Павел , 17 ноября 2014

On the Three-Stage Version of Stable Dynamic Model

In this paper we propose a new model of the traffic assignment problem. This model joints the entropy model, flow decomposition and the Stable Dynamic model. All parameters in use have a direct physical meaning and interpretations. We show that this model reduces to a non-smooth convex optimization problem that admits natural primal-dual formulation. For completeness, we present and criticize the standard static traffic assignment models. In particular, we prove that the Beckmann model reduces to the Stable Dynamic Model as a result of some limiting process.

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

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

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

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

11.12.2013

Extension of a saddle point mirror descent algorithm with application to robust PageRank

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