ЗАДАЧИ И МЕТОДЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
1.1. Задачи с фиксированным временем начала и окончания. Постановка. Метод рекуррентных уравнений Беллмана (вывод и применение). Принцип Беллмана как необходимое и как достаточное условие (с доказательствами) в задачах с аддитивным критерием и критерием в виде максимума (использовать материалы лабораторной работы). Связь принципа Беллмана с уравнениями Беллмана. Обратные рекуррентные соотношения Беллмана (запись от начала процесса). Пример использования соотношений Беллмана (задача об оптимальном распределении с функцией дохода в виде квадратного корня).
1.2. Задачи с нефиксированной длительностью процесса.
Постановка. Обобщение уравнений Беллмана. Задачи поиска оптимальных путей на графах с неотрицательными весами ребер: метод Дейкстры и его обоснование, связь с принципом Беллмана. Задачи с векторными весами ребер. Оптимальные по Парето и Слейтеру решения, метод сверток (использовать материалы лабораторной работы).
ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА, МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
2.1.Выпуклые множества, выпуклые функции (выпуклость и строгая выпуклость). Проекция точки на множество, две леммы о свойствах проекции. Отделимость точки и множества, строгая и сильная отделимость, две теоремы об отделимости. Свойства выпуклых функций (с доказательствами, кроме свойства непрерывности во внутренних точках), критерии выпуклости. Субрадиент и субдифференциал. Задача выпуклого математического программирования и ее свойства. Использование отсечений при поиске минимума выпуклых функций на выпуклом компакте.
2.2.Функция Лагранжа. Теоремы об условиях экстремума первого порядка в задачах математического программирования: в гладкой задаче с ограничениями–равенствами (теорема Лагранжа), в выпуклых гладких задачах с афинными ограничениями–равенствами (усиленная теорема Лагранжа), в негладкой задаче выпуклого мат.программирования с ограничениями–неравенствами и дополнительным ограничением и виде принадлежности выпуклому множеству (включая теорему о записи условий через седловую точку функции Лагранжа), в гладкой задаче выпуклого, мат.программирования с ограничениями–неравенствами и равенствами (теорема Каруша-Куна_Таккера), в общей гладкой задаче математического программирования (в последнем случае — без доказательства).
Понятие регулярности допустимой области в точке и регулярности области в целом. Достаточные условия регулярности для областей разных типов (условие Слейтера и условия линейной независимости).
2.3. Понятие метода поисковой оптимизации. Априорная и поисковая информация. Пассивные и последовательные алгоритмы. Принцип наилучшего гарантированного результата. Оптимальные и
e–оптимальные алгоритмы. Класс унимодальных функций, правило сокращения интервала. Построение оптимальных и e–оптимальных пассивных N–шаговых алгоритмов, последовательного N–шагового алгоритма (метод Фибоначчи). Неоптимальные алгоритмы: методы золотого сечения и дихотомии. Связь метода Фибоначчи с методом золотого сечения.
Метод поиска минимума выпуклой функции на выпуклом многограннике, основанный на минимизации нижней оценки выпуклой функции. Сведение к последовательности задач линейного программирования.
2.4. Задачи поиска локального экстремума в задачах без ограничений. Общая структура итерационных методов локального поиска. Порядок метода. Линейная, сверхлинейная и квадратичная скорость сходимости. Критерии выбора шагового множителя. Алгоритмы Армихо, Вулфа, одномерной минимизации. Классические методы локального поиска и их свойства: градиентные методы и метод Ньютона. Теоремы сходимости для этих методов, свойства. Методы прямого поиска на примере метода Хука-Дживса.
Общие представления о других методах локальной оптимизации: Ньютона–Рафсона, квазиньютоновские, Флетчера–Рифса (по материалам лабораторной работы, непосредственно в билетах этого вопроса не будет).
2.5. Общие методы решения задач с ограничениями. Метод внешних штрафных функций, степенная функция штрафа. Влияние показателя степени на гладкость функции штрафа. Теорема сходимости.
2.6. Задачи многоэкстремальной оптимизации. Липшицевы функции и их свойства. Метод Пиявского, теорема о свойствах. Версия метода с использованием оценки константы Липшица. Одномерный вариант метода Пиявского — метод ломанных. Информационно–статистический метод.
Многомерные многоэкстремальные задачи. Метод деления на три, теорема о свойствах
(с доказательством — самостоятельно). Обобщение метода деления на три на задачи с ограничениями-неравенствами.
