Численное моделирование (методы оптимизации)
Не перебирай все варианты, будь спецом по оптимизации!
Состав курса
4 курс специалитета ФКИ, И.А. Самыловский.
Осень 2023-2024 гг., Пятница, 13:00-14:35, дистант (а всё, закрыт)
По ссылкам - папки с материалами.
Обсуждаем, чем будем заниматься, классифицируем задачи оптимизации, рассказываем про два дуболомных метода - метод прямого поиска и метод дихотомии.
Рассказываем, что метод дихотомии - только пример класса многоточечных методов, а также рассказываем про метод золотого сечения, метод Фибоначчи и метод Пауэлла!
Обсуждаем, как может выглядеть C++/Qt-based приложение для тестирования методов минимизации скалярных унимодальных функций, а также говорим про метод ломаных для поиска минимума функций липшицевых!
Продолжаем разговор про метод ломаных, проверяем его сходимость. Приводим пример из астродинамики, который подходит под поиск минимума липшицевой функции.
Применяем методы дихотомии, золотого сечения и Фибоначчи к различному и сравниваем результаты
Разбираем методы покрытий: равномерного перебора, последовательного перебора, модификацию метода перебора с отсечением части сетки. Смотрим, в каких случаях они не работают и что означает "не работают" (спойлер: означает, что, задав точность, мы всего лишь не подберемся к точной нижней грани функции на эту точность). И смотрим, какие еще липшицевы функции одной переменной может нам предоставить астродинамика.
Обсуждаем метод, не требующий предварительного определения константы Липшица и работающий быстрее, чем методы покрытий. Метод Стронгина!
Применяем рассмотренные методы поиска экстремума липшицевых функций к функциям из астродинамики!
Ведём "разбор полётов" по лабораторкам, создаем примеры фукнций, на которых есть менее "приятное" поведение первой и второй производных (и все - из астродинамики и немного ПВО / ПКО), и начинаем обсуждать задачи с ограничениями. И понимаем, что логично начинать их рассмотрение с задачи линейного программирования.
Для тех, кто: а) хочет дослать материалы по лабораторкам б) материалы сдал, но хочет продемонстрировать, как его программа работает с новыми функциями: дистанция между КА на орбитах с большой разницей эксцентриситетов, дистанция от КА до маневрирующей боевой ракеты, угловая скорость локатора, следящего за маневрирующей боевой ракетой
Как и обещали, начинаем задачи линейного программирования. Рассматриваем общую постановку задачи, задачу "каноническую" и "стандартную" и учимся заменой переменных переводить задачи одного типа в задачи другого типа (по факту - "убиваем" либо ограничения-равенства, либо ограничения-неравенства) и формулируем утверждение о "равносильности" задач таких типов.
См. предпоследний слайд, ждем до 12:00 вторника, 7.11.2023. Как обычно - папка с ФИО и группой, внутри - .tex и .pdf файл с описанием преобразований
Рассматриваем угловые точки множества, тренируемся их определять и заодно вспоминаем линейную алгебру и аналитическую геометрию. На слайдах 12-14 -- описание лабораторки.
ПО для отображения линейных ограничений и перемещения прямой, задающей функционал + работа с угловыми точками. Как обычно, папка с ФИО и группой, по угловым точкам - .tex и .pdf файлы.
Знакомимся с симплекс-методом, который позволяет не перебирать все угловые точки множества. И даже приводим пример, в котором за три итерации находим оптимальное решение. А основное время тратим на разлиновку симплекс-таблиц.
Приводим пример антициклина - правила, позволяющего избежать зацикливания симплекс-метода (а он может зацикливаться, т.е. выйдя из угловой точки, мы через некоторое количество шагов вернемся в неё же, но это количество шагов - не "1"). И заодно формулируем ЗЛП на космическую тематику.
Говорим об условиях существования решения ЗЛП в терминах двойственных задач. Изучаем связь между задачей "прямой" и двойственной и понимаем, что двойственность связана с "переводом" на язык ЗЛП общей формы необходимых условий экстремума. Говорим про функцию Лагранжа и даже про условия дополняющей нежесткости.