Методы оптимизации 20/21 — различия между версиями
A maminov (обсуждение | вклад) (→О курсе) |
A maminov (обсуждение | вклад) (План лекций) |
||
| Строка 35: | Строка 35: | ||
=== Лекции === | === Лекции === | ||
| + | Примерный план лекций: | ||
| + | |||
| + | '''1. Общие сведения о задачах оптимизации''' | ||
| + | |||
| + | Постановка задачи оптимизации, классификация задач оптимизации. Локальный и глобальный оптимум. Условный экстремум. Теорема Куна-Таккера, необходимые и достаточные условия оптимальности. Двойственность и ее применение в оптимизации. | ||
| + | |||
| + | '''2. Методы безусловной непрерывной оптимизации''' | ||
| + | |||
| + | Методы поиска минимума функции одной переменной. Методы, не использующие производных (“нулевого порядка”). Методы градиентного спуска и сопряженных градиентов. | ||
| + | Метод Ньютона. Квазиньютоновские методы (LBFGS). | ||
| + | |||
| + | '''3. Методы условной непрерывной оптимизации''' | ||
| + | |||
| + | Методы штрафных функций. Барьерные методы. Метод проекции градиента. | ||
| + | |||
| + | '''4. Методы поиска глобального экстремума''' | ||
| + | |||
| + | Точные методы, основанные на интервальном анализе. Липшицева оптимизациия. Генетические алгоритмы. Популяционные алгоритмы. Поиск с запретами. | ||
| + | |||
| + | '''5. Комбинаторная оптимизация''' | ||
| + | |||
| + | Задача о ранце. Жадные алгоритмы. Метод ветвей и границ для задачи о ранце. Методы динамического программирования для задачи о ранце. Задача об упаковке контейнеров: приближенные и точные методы решения. Приложение: управление ресурсами в распределенных системах. | ||
| + | |||
| + | '''6. Линейное программирование''' | ||
| + | |||
| + | Постановка задачи линейного программирования, различные формы задания. Прямая и двойственная задача ЛП. Прямой симлекс-метод. Двойственный симплекс-метод. Приложение: транспортная задача. Общая задача целочисленного линейного программирования. Метод ветвей и границ для ЦЛП. Метод отсечений Гомори. | ||
| + | |||
| + | '''7. Многокритериальная оптимизация''' | ||
| + | |||
| + | Понятие оптимальности по Парето и Слейтеру. Свертка критериев. Основные алгоритмы аппроксимации множества эффективных решений. Приложение: инженерная оптимизация на примере оптимизации робота. | ||
=== Семинары === | === Семинары === | ||
Версия 13:21, 25 января 2021
Содержание
О курсе
Курс читается для третьекурсников в 3-4 модулях.
Лектор: Посыпкин Михаил Анатольевич
Лекции проходят онлайн по пятницам онлайн на 5 паре (16:20 - 17:40)
Ссылка на конференцию: https://zoom.us/j/99788550952?pwd=bDFVQXJMcmVRNGg3dFlPK1V3RnRGUT09
Семинары:
| Группа | Преподаватель | Время | Аудитория |
|---|---|---|---|
| 183 | Игнатов А.Д. | Среда 09:30 - 10:50 | Zoom конференция |
| 184 | Игнатов А.Д. | Понедельник 09:30 - 10:50 | Zoom конференция |
| 185 | Коновалов Е. В. | Вторник 16:20 - 17:40 | Zoom конференция |
| 186 | Коновалов Е. В. | Вторник 14:40 - 16:00 | Zoom конференция |
| 187 | Маминов А.Д. | Понедельник 09:30 - 10:50 | Zoom конференция |
| 188 | Маминов А.Д. | Понедельник 11:10 - 12:30 | Zoom конференция |
Полезные ссылки
Телеграм-чат курса: https://t.me/joinchat/Rn4TWP5kEJw1d38y
План курса
Лекции
Примерный план лекций:
1. Общие сведения о задачах оптимизации
Постановка задачи оптимизации, классификация задач оптимизации. Локальный и глобальный оптимум. Условный экстремум. Теорема Куна-Таккера, необходимые и достаточные условия оптимальности. Двойственность и ее применение в оптимизации.
2. Методы безусловной непрерывной оптимизации
Методы поиска минимума функции одной переменной. Методы, не использующие производных (“нулевого порядка”). Методы градиентного спуска и сопряженных градиентов. Метод Ньютона. Квазиньютоновские методы (LBFGS).
3. Методы условной непрерывной оптимизации
Методы штрафных функций. Барьерные методы. Метод проекции градиента.
4. Методы поиска глобального экстремума
Точные методы, основанные на интервальном анализе. Липшицева оптимизациия. Генетические алгоритмы. Популяционные алгоритмы. Поиск с запретами.
5. Комбинаторная оптимизация
Задача о ранце. Жадные алгоритмы. Метод ветвей и границ для задачи о ранце. Методы динамического программирования для задачи о ранце. Задача об упаковке контейнеров: приближенные и точные методы решения. Приложение: управление ресурсами в распределенных системах.
6. Линейное программирование
Постановка задачи линейного программирования, различные формы задания. Прямая и двойственная задача ЛП. Прямой симлекс-метод. Двойственный симплекс-метод. Приложение: транспортная задача. Общая задача целочисленного линейного программирования. Метод ветвей и границ для ЦЛП. Метод отсечений Гомори.
7. Многокритериальная оптимизация
Понятие оптимальности по Парето и Слейтеру. Свертка критериев. Основные алгоритмы аппроксимации множества эффективных решений. Приложение: инженерная оптимизация на примере оптимизации робота.
Семинары
Семинар 1
Презентация Семинар 1
| Группа | Преподаватель | Материалы семинара |
|---|---|---|
| 183 | Игнатов А.Д. | |
| 184 | Игнатов А.Д. | |
| 185 | Коновалов Е. В. | |
| 186 | Коновалов Е. В. | |
| 187 | Маминов А.Д. | Записи с семинара 1 |
| 188 | Маминов А.Д. | Записи с семинара 1 |
Семинар 2
Презентация Семинар 2
| Группа | Преподаватель | Материалы семинара |
|---|---|---|
| 183 | Игнатов А.Д. | |
| 184 | Игнатов А.Д. | |
| 185 | Коновалов Е. В. | |
| 186 | Коновалов Е. В. | |
| 187 | Маминов А.Д. | Записи с семинара 2 |
| 188 | Маминов А.Д. | Записи с семинара 2 |
Домашние задания
Домашние задания направлены на реализацию различных методов оптимизации и решению задач. Основной язык данного курса будет Python.
Планируется 5 домашних заданий. За каждое задание вы получите оценку, среднее по всем домашним заданиям будет составлять 0.5 от итоговой оценки.
Экзамен
Итоговая оценка за курс
Итог = 0.5 * ДЗ + 0.5 * ЭКЗ
ДЗ - средняя оценка за домашние задания
ЭКЗ - оценка за экзамен
