Децентрализованная оптимизация, транспортные задачи, спектральные свойства графов

Квалификация выпускника: бакалавр

Направление подготовки:

Направленность (профиль) образовательной программы:

Программу разработал(а): Александр Рогозин

1. Краткая характеристика дисциплины

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

2. Перечень планируемых результатов обучения

Целью освоения дисциплины является получение студентами представления о транспортных задачах и задачах децентрализованной оптимизации.

Задачами дисциплины являются изучение моделей Бэкмана и стабильной динамики в задачах транспортного моделирования, обзор задач вида multi-commodity flow, изучение задач децентрализованной оптимизации и методов их решения.

Общая характеристика результата обучения по дисциплине

Знания:

Основные модели транспортного моделирования. Симплекс метод, метод Франк-Вульфа, двойственный субградиентный метод.
Децентрализованная оптимизация. Децентрализованные методы первого порядка, консенсус.

Умения:

Составление транспортной модели, реализация численных методов и проведение моделирования с помощью численных методов.

Навыки (владения):

Постановка задачи в транспортном моделировании и децентрализованной оптимизации.
Работа с литературой по численным методам в данных областях.

3. Структура и содержание дисциплины

№ п/п	Наименование раздела дисциплины	Содержание дисциплины по темам
1.	Транспортное моделирование: обзор.	Примеры применения транспортных моделей Парадокс Браесса Понятие о матрице корреспонденции, пропускных способностях ребер графа
2.	Модель Бэкмана.	Зависимость времени проезда по ребру от транспортного потока, BPR функции Метод Франк-Вульфа Двойственный субградиентный метод
3.	Модель стабильной динамики (Нестерова-де-Пальма).	Определение модели стабильной динамики Edge-based подход, решение симплекс методом Path-based подход, решение двойственным субградиентным методом
4.	Задачи о конкурентных потоках.	Задача о максимальном конкурентном потоке Двойственный метод ее решения
5.	Оптимизация сетей.	Задачи с ограниченным бюджетом на пропускные способности. Оптимизация сети для увеличения конкурентного потока. Оптимизация сети относительно метрики.
6.	Децентрализованная оптимизация: обзор.	Задачи, решаемые группой дронов, спутников Федеративное обучение, задачи с ограничениями приватности Управление энергетическими системами
7.	Двойственный подход к децентрализованной оптимизации.	Матрица Лапласа, mixing matrix, консенсусный алгоритм, число обусловленности графа Задача децентрализованной оптимизации как задача с аффинными ограничениями Двойственные методы SSDA, MSDA
8.	Прямой подход к децентрализованной оптимизации.	Методы, использующие консенсусное проектирование Методы, основанные на алгоритме Forward-Backward: PAPC, OPAPC
9.	Нижние оценки сложности в децентрализованной оптимизации.	Обзор нижних оценок в оптимизации: формализация методов первого порядка, “плохие” функции “Плохие” графы, связь числа обусловленности с диаметром Обзор существующих нижних оценок: постоянные графы, меняющиеся и медленно меняющиеся графы

4. Методические и оценочные материалы

Задания для практических занятий:

№ п/п	Наименование раздела дисциплины (модуля)	Перечень рассматриваемых тем (вопросов)
1.	Модель Бэкмана.	Выписать задачу оптимизации, соответствующую модели Бэкмана Реализовать метод Франк-Вульфа для модели Бэкмана Применить этот метод для данных [1] и [2]
2.	Модель стабильной динамики.	Выписать задачу оптимизации, соответствующую модели стабильной динамики, и двойственную ей Реализовать двойственный метод решения задачи стабильной динамики Реализовать симплекс метод или метод внутренней точки для решения задачи стабильной динамики (на базе [3])
3.	Максимальный конкурентный поток.	Вывести двойственную задачу к задаче максимального конкурентного потока Реализовать двойственный метод с переключениями. Применить его к сетям из коллекций [1,2]
4.	Оптимизация сетей.	Сформулировать и решить с помощью методов линейного программирования задачу оптимального распределения бюджета на пропускные способности. Запустить решение на данных [1,2]
5.	Децентрализованная оптимизация.	Реализовать методы SSDA, MSDA [4] Реализовать метод PAPC [5]

[1] https://sndlib.put.poznan.pl/home.action
[2] https://github.com/bstabler/TransportationNetworks
[3] https://www.cvxpy.org/
[4] Scaman, K., Bach, F., Bubeck, S., Massoulié, L., & Lee, Y. T. (2018). Optimal algorithms for non-smooth distributed optimization in networks. Advances in Neural Information Processing Systems, 31.
[5] Drori, Y., Sabach, S., & Teboulle, M. (2015). A simple algorithm for a class of nonsmooth convex–concave saddle-point problems. Operations Research Letters, 43(2), 209-214.

|} Текущий контроль успеваемости обучающихся по дисциплине:

№ п/п	Наименование раздела дисциплины	Форма текущего контроля	Материалы текущего контроля
1.	Модель Бэкмана, модель стабильной динамики.	Защита проекта.	Реализовать метод Франк-Вульфа для модели Бэкмана.
2.	Модель стабильной динамики.	Защита проекта.	Реализовать двойственный метод для задачи стабильной динамики.
3.	Максимальный конкурентный поток.	Защита проекта.	Реализовать двойственный субградиентный метод с переключениями для задачи максимального конкурентного потока.
4.	Оптимизация сети.	Домашнее задание.	Реализовать метод на основе линейного программирования для задачи оптимизации сети при фиксированном бюджете.

Контрольные вопросы для подготовки к промежуточной аттестации:

№ п/п	Наименование раздела дисциплины	Вопросы
1.	Модель Бэкмана.	Выписать задачу оптимизации, соответствующую модели Бэкмана. Выписать метод Франк-Вульфа для оптимизации выпуклой функции на ограниченном множестве.
2.	Модель стабильной динамики.	Выписать задачу оптимизации, соответствующую модели стабильной динамики. Дать определение задачи линейного программирования. Дать определение двойственной задачи в оптимизации. Дать определение субградиента выпуклой функции, выписать субградиентный метод. Вывести двойственную задачу к модели стабильной динамики.
3.	Максимальный конкурентный поток.	Выписать задачу оптимизации, соответствующую максимальному конкурентному потоку Вывести двойственную к этой задаче.
4.	Оптимизация сети.	Качественно описать схему работы симплекс метода. Выписать линейную программу, соответствующую оптимизации сети при ограниченном бюджете.
5.	Децентрализованная оптимизация.	Выписать общую постановку задачи децентрализованной оптимизации. Дать определение матрицы Лапласа, mixing matrix. Описать консенсусную процедуру. Описать схему вывода двойственного метода децентрализованной оптимизации. Выписать метод Forward-Backward для вариционных неравенств. Переписать задачу децентрализованной оптимизации как вариационное неравенство. Применить к нему метод Forward-Backward и выписать полученный алгоритм.

Вопросы/Задания к промежуточной аттестации в устной/письменной форме:

Метод Франк-Вульфа для минимизации выпуклых функций на ограниченном выпуклом множестве.
Определение субградиента выпуклой функции. Субградиентный метод.
Задача линейного программирования - определение.
Симплекс метод.
Двойственная задача оптимизации.
Алгоритм Forward-Backward для вариационных неравенств.
BPR функция зависимости времени проезда по ребру от загрузки ребра.
Модель Бэкмана.
Модель стабильной динамики.
Максимальный конкурентный поток.
Задачи оптимизации сети при ограниченном бюджете.
Постановка задач децентрализованной оптимизации.
Матрица Лапласа, mixing matrix.
Консенсусная процедура.
Двойственные методы децентрализованной оптимизации SSDA, MSDA.
Прямые методы децентрализованной оптимизации: PAPC.

Перечень учебно-методического обеспечения дисциплины

Список основной литературы:

Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1988). Network flows.
Shahrokhi, F., & Matula, D. W. (1990). The maximum concurrent flow problem. Journal of the ACM (JACM), 37(2), 318-334.
Fleischer, L. K. (2000). Approximating fractional multicommodity flow independent of the number of commodities. SIAM Journal on Discrete Mathematics, 13(4), 505-520.
Scaman, K., Bach, F., Bubeck, S., Massoulié, L., & Lee, Y. T. (2018). Optimal algorithms for non-smooth distributed optimization in networks. Advances in Neural Information Processing Systems, 31.
Drori, Y., Sabach, S., & Teboulle, M. (2015). A simple algorithm for a class of nonsmooth convex–concave saddle-point problems. Operations Research Letters, 43(2), 209-214

Методические указания для обучающихся по освоению дисциплины

Вид учебных занятий/деятельности	Деятельность обучающегося
Лекция	Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
Практическое (семинарское) занятие	При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его. Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.
Устный/письменный опрос	Отвечать, максимально полно, логично и структурировано, на поставленный вопрос. Основная цель – показать всю глубину знаний по конкретной теме или ее части.
Реферат	Поиск источников и литературы, составление библиографии. При написании реферата рекомендуется использовать разнообразные источники, монографии и статьи из научных журналов, позволяющие глубже разобраться в различных точках зрения на заданную тему. Изучение литературы следует начинать с наиболее общих трудов, затем следует переходить к освоению специализированных исследований по выбранной теме. Могут быть использованы ресурсы сети «Интернет» с соответствующими ссылками на использованные сайты. Если тема содержит проблемный вопрос, следует сформулировать разные точки зрения на него. Рекомендуется в выводах указать свое собственное аргументированное мнение по данной проблеме. Подготовить презентацию для защиты реферата.
Эссе	Написание прозаического сочинения небольшого объема и свободной композиции, выражающего индивидуальные впечатления и соображения по конкретному поводу или вопросу и заведомо не претендующего на определяющую или исчерпывающую трактовку предмета. При работе над эссе следует четко и грамотно формулировать мысли, структурировать информацию, использовать основные понятия, выделять причинно-следственные связи. Как правило эссе имеет следующую структуру: вступление, тезис и аргументация его, заключение. В качестве аргументов могут выступать исторические факты, явления общественной жизни, события, жизненные ситуации и жизненный опыт, научные доказательства, ссылки на мнение ученых и др.
Подготовка к промежуточной аттестации	При подготовке к промежуточной аттестации необходимо проработать вопросы по темам, которые рекомендуются для самостоятельной подготовки. При возникновении затруднений с ответами следует ориентироваться на конспекты лекций, семинаров, рекомендуемую литературу, материалы электронных и информационных справочных ресурсов, статей. Если тема вызывает затруднение, четко сформулировать проблемный вопрос и задать его преподавателю.
Практические (лабораторные) занятия	Практические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов.
Самостоятельная работа	Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка видеопрезентации. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
Видеопрезентация	Подготовка видеопрезентаций по курсу. Видеопрезентации могут быть сделаны на любую тему, затронутую в ходе курса. Темы должны быть заранее согласованы с преподавателем. Видеопрезентации продолжительностью около 5 минут (300 секунд) должны быть подготовлены в группах, определяемых преподавателем. Несмотря на то, что это групповая работа, должен явно присутствовать вклад каждого члена группы.
Доклад	Публичное, развернутое сообщение по определенной теме или вопросу, основанное на документальных данных. При подготовке доклада рекомендуется использовать разнообразные источники, позволяющие глубже разобраться в теме. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
Дискуссия	Публичное обсуждение спорного вопроса, проблемы. Каждая сторона должна оппонировать мнение собеседника, аргументируя свою позицию.
Контрольная работа	При подготовке к контрольной работе необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме.
Тестирование (устное/письменное)	При подготовке к тестированию необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме. Основная цель тестирования – показать уровень сформированности знаний по конкретной теме или ее части.
Индивидуальная работа	При выполнение индивидуальной работы необходимо взять задание у преподавателя, ознакомиться с требованиями к выполнению работы, изучить поставленную проблему, найти решение проблемы. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия. Оформить результаты работы.
Разработка отдельных частей кода	Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.
Выполнение домашних заданий и групповых проектов	Для выполнения домашних заданий и групповых проектов необходимо получить формулировку задания от преподавателя и убедиться в понимании задания. При выполнение домашних заданий и групповых проектов необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме.

Методы и технологии обучения, способствующие формированию компетенции

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

BSc: DecentralizedPptimizationTransportProblemsSpectralPropertiesOfGraphs

Contents