Методы оптимизации. Курс

1.

Курс «Методы оптимизации»
Лектор – Черноруцкий Игорь Георгиевич
( [email protected] ) - можно обращаться по всем личным
вопросам
Должность – профессор ВШПИ
Ученая степень – доктор технических наук
Ученое звание – профессор

2.

Для справки:
• Должности бывают – ассистент, преподаватель (старший
преподаватель), доцент, профессор
• Ученые степени – без степени, кандидат наук (например,
технических), доктор наук
• Ученые звания – доцент, профессор
Как правило, должность профессора занимает доктор наук,
имеющий звание профессора. Иногда на должность
профессора назначают д.т.н. со званием доцента. Должности
доцента обычно занимают к.т.н. со званием доцента.

3.

4.

5.

6.

Основная литература

7.

Основные разделы курса
1. Постановка общей задачи принятия решений как задачи выбора
вариантов. Примеры задач принятия решений. Их особенности
(численные оценки исходов, многокритериальность и т.д.).
2. Классификация проблем принятия решений. Принятие решений в
условиях определенности и неопределенности.
3. Проблема минимизации функционала в контексте общей
проблемы выбора. Что такое функция, функционал, оператор?
4. Две постановки задачи оптимизации. Минимизаторы и
минимизирующие последовательности. Некорректные задачи
минимизации. Разрешимость задач оптимизации. Сходимость по
аргументу и по функционалу. Практические аспекты (на
примерах).

8.

5. Терминологические замечания: конечномерные и бесконечномерные задачи,
математическое программирование. Нелинейное программирование, линейное
программирование, квадратичное программирование, динамическое программирование.
Принцип параметризации. Задача о наборе высоты. Принцип оптимальности Беллмана.
6. Задача безусловной оптимизации и ее важность. Метод штрафных функций для
ограничений – равенств. Параболоиды и их основные свойства. Структуры поверхностей
уровня параболоидов.
7. Метод оптимизации как генератор минимизирующей последовательности. Критерии
сравнения методов оптимизации. Тесты, таймер-программы, горнеры. Роль параболоидов.
8. Метод циклического покоординатного спуска. Заклинивание. Овражность для
квадратичного случая.
9. Алгоритм GZ1, метод вращения осей Розенброка.
10. Критерий минимального запаса работоспособности. Сглаженный вариант критерия
минимального запаса работоспособности. Зачем нужна процедура сглаживания?

9.

11. Общая структура программного комплекса оптимизации. Критерии
окончания процесса оптимизации, в том числе содержательные критерии.
12. Методы обобщенного покоординатного спуска. Алгоритм и реализация.
Методы вычисления производных.
13. Многокритериальная оптимизация. «Инженерный» подход и его
ограниченность. Множество Парето как решение многокритериальной задачи.
14. Принцип Парето. Свойства множеств Парето и множеств Слейтера.
Геометрические иллюстрации.
15. Численные методы построения множеств Парето. Метод линейной
свертки – последовательность действий и геометрические иллюстрации.
Свойства получаемых решений. Роль невыпуклости границы множества
достижимости.
16. Метод максиминной свертки. Свойства решений и геометрические
интерпретации. Метод главного критерия.
17. Метод Джоффриона. Лексикографическая оптимизация.
18. Матричные градиентные методы. Анализ сходимости метода простого
градиентного спуска. Вектор ошибки. Разностное уравнение для вектора
ошибки. Множители затухания. Сходимость в условиях большого разброса
собственных чисел. Геометрические иллюстрации.

10.

19. Методы ускорения сходимости для процедуры градиентного спуска. Метод
«утюга» Люстерника. Метод «оврагов», партан методы. Методы параллельных
касательных.
20. Понятие функции релаксации и ее роль в задачах анализа и синтеза. Требования к
функциям релаксации. Функции релаксации метода простого градиентного спуска,
метода Ньютона, метода Левенберга как регуляризованной формы метода Ньютона.
21. Методы с экспоненциальной релаксацией, их особенности и реализация.
Вычислительная схема метода. МЭР как «оптимальный» градиентный метод,
обобщающий классические процедуры.
22. Построение метода по его функции релаксации. Методы с чебышевскими
функциями релаксации. Особенности построения, применения и реализации.
23. Методы учета ограничений: методы штрафных функций, замены
переменных, модифицированных функций Лагранжа.
24. Методы декомпозиции. Метод аппроксимации и реализации. Метод
вспомогательных частных критериев.
25. Методы оптимизации в условиях неопределенности.
26. Генетические алгоритмы.

11.

Практические занятия
Общие положения
Цель практических занятий (ПЗ) – закрепление лекционного
материала и овладение практическими навыками решения
оптимизационных задач. Подготовка к осознанному применению
стандартных пакетов оптимизации типа «Матлаб» или «NAG»
(Numerical Analysis Group). Таких пакетов сейчас много.
Основной упор делается на «ручное» выполнение заданий для
уяснения существа дела и понимания того, что же делают стандартные
программы. При успешном выполнении практических заданий и их
обсуждении есть возможность получить автомат и по экзамену.

12.

Формы проведения ПЗ
самостоятельное выполнение задания в аудитории. Обычно у каждого свое
задание
контрольные работы по теме
обсуждения выполненных самостоятельных и контрольных работ.
Решение типовых примеров студентами в диалоге с преподавателем
теоретические коллоквиумы – ВРБ (вопросно-развивающие беседы)
консультации и обсуждение лекционного материала
заключительное занятие – работа с задолжниками, выставление
автоматических зачетов студентам, успешно выполнившим необходимые
задания

13.

Темы обсуждаемые на ПЗ
Динамическое программирование (ДП). Поиск минимального пути на
графе методом ДП
Линейное программирование (ЛП). Графическое решение задач ЛП.
Решение реальной «задачи о красках» (5 вариантов)
Задача безусловной оптимизации (unconstrained optimization problem).
Параболоиды.
Построение линий уровня «своего» параболоида
Покоординатные стратегии. Построение траекторий спуска методом
ЦПС из заданной начальной точки для параболоида
Построение траекторий спуска методом вращения осей Розенброка
Построение траекторий спуска методом обобщенного
покоординатного спуска (ОПС)

14.

Промежуточный итог. Защита выполненных работ. Коллоквиум по
покоординатным стратегиям. Заклинивание (jamming)
Градиентные стратегии. Построение траектории спуска методом
наискорейшего градиентного спуска. Сделать один шаг методом Ньютона.
Функции от матриц. Построение заданных функций от матрицы Гессе
«своего» параболоида:
h
1
t , sin t ,
e d (h 0.1)
t
0
Для матрицы
sin A
проверить равенство
f ( A)u f ( i )u
i
i

15.

По заданной функции релаксации построить градиентный метод. Привести
график функции релаксации
1 h
R
, h 0.1
1 h
Градиентные методы с экспоненциальной релаксацией. Построить
траекторию спуска (3 звена) методом с экспоненциальной релаксацией (МЭР)
Шаг = 0.1
Промежуточный итог. Коллоквиум
Решение реальной задачи. Оптимизация ТТЛ схемы (транзисторнотранзисторная логика)
Многокритериальные задачи. Построение множеств Парето в пространстве
оценок (лекции плюс практика)