Учебно-методический комплекс «Ньютоновские методы для задач оптимизации и вариационных задач»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное образовательное учреждение

высшего профессионального образования

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
Факультет вычислительной математики и информатики

УТВЕРЖДАЮ

Декан факультета ВМК

____________________Е.И. Моисеев

«______»__________________2013
Учебно-методический комплекс

«Ньютоновские методы для задач оптимизации и вариационных задач»
Направление подготовки

010400_Прикладная математика и информатика

Интегрированный магистр
Профиль бакалавриата:

2 поток «Математические методы обработки информации

и принятия решений»
Специализация:

«Исследование операций и актуарная математика»

Квалификация (степень) выпускника

Бакалавр
Форма обучения

очная

Москва

2013

Рецензент:
Рабочая программа дисциплины «Ньютоновские методы для задач оптимизации и вариационных задач».

Составитель: профессор кафедры исследования операций факультета ВМК МГУ

А.Ф. Измаилов.

Рабочая программа предназначена для преподавания дисциплины «Ньютоновские методы для задач оптимизации и вариационных задач» из блока вариативных профессиональных дисциплин (ВПД) студентам очной формы обучения по направлению подготовки «010400.62 Прикладная математика и информатика», профилю «Математические методы обработки информации и принятия решений», специализации «Исследование операций и актуарная математика», в 7 семестре.

Рабочая программа составлена с учетом Федерального государственного образовательного стандарта высшего профессионального образования по направлению подготовки, утвержденного приказом Министерства образования и науки Российской Федерации от "8" декабря 2009 г. № 712, а также образовательного стандарта МГУ интегрированный магистр по направлению «010400.62 Прикладная математика и информатика». Дисциплина является обязательной для студентов специализации «Исследование операций и актуарная математика».

Составитель:

____________________ А.Ф.Измаилов
1. Цели освоения дисциплины
Целью освоения дисциплины является ознакомление слушателей с современным состоянием важнейших областей численной оптимизации.
«Ньютоновские методы для задач оптимизации и вариационных задач» - краткий курс численных методов оптимизации, основное внимание в котором уделено методам общего назначения, ориентированным на решение гладких задач математического программирования и вариационных задач без какой-либо специальной структуры. Излагаются как «классические» методы, важные в идейном отношении, так и более изощренные «новые» алгоритмы, привлекающие в настоящее время наибольшее внимание специалистов и пользователей.

2. Место дисциплины в структуре ООП бакалавриата

Дисциплина относится к блоку вариативных профессиональных дисциплин (ВПД). Она предназначена для профессиональной подготовки студентов, обучающихся по направлению подготовки «010400 Прикладная математика и информатика» (1 ступень –бакалавриат - двухуровневой программы интегрированный магистр, непрерывной подготовки), профилю «Математические методы обработки информации и принятия решений».

Изучение опирается на предварительно полученные знания в рамках курсов: математического анализа и линейная алгебры.

Знания, полученные в ходе освоениядисциплины, могут быть использованы при изучении дисциплин модулей «Теория игр и ее приложения», «Теория игр и исследование операций», курсов по методам оптимизации и математической экономике.

3.Компетенции обучаемого, формируемые в результате освоения дисциплины
Процесс изучения дисциплины направлен на формирование (элементов) следующих компетенций в соответствии с ФГОС ВПО по данному направлению:

а) общенаучные (ОНК): владение методологией научных исследований в профессиональной области (ОНК-4); владение фундаментальными разделами математики и информатики, необходимыми для решения научно-исследовательских и практических задач в профессиональной области (ОНК-6);

б) профессиональных (ПК): способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат (ПК-2).
В результате освоения дисциплины студент должен:

знать основные принципы, лежащие в основе современных подходов к численному решению задач оптимизации и вариационных задач;

уметь применять на практике методы оптимизации для решения задач соответствующих классов;

понимать и применять на практике методы линейного и нелинейного программирования;

уметь осуществлять сравнительный анализ и настройку оптимизационных алгоритмов с целью выбора наиболее подходящих в той или иной прикладной ситуации;

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

4. Структура дисциплины и ее место в учебном плане
Общая трудоемкость дисциплины «Ньютоновские методы для задач оптимизации и вариационных задач» составляет 2 зачетные единицы (72 часа). Лекции – 36 часов, самостоятельная работа – 36 часов. Экзамен в 7 семестре.
За дисциплину отвечает кафедра исследования операций.

4.1. Тематический план учебной дисциплины

№	Название темы	Аудиторные занятия (часы)		Самостоятельная работа студента
		Лекции	Семинары
7-ой семестр
1	Введение. Предварительные сведения	4	0	4
2	Элементы теории оптимизации и вариационные задачи	4	0	4
3	Начальные сведения о численных методах для задач оптимизации и вариационных задач	4	0	4
4	Методы для задач безусловной оптимизации и нелинейных уравнений	8	0	8
5	Методы для задач условной оптимизации и комплементарных задач	12	0	12
6	Стратегии глобализации сходимости	4	0	4
	Итого:	36	0	36
	Всего (часы) (аудиторные занятия и самостоятельная работа):	72

4.2. Структура дисциплины по видам работ

№	Раздел дисциплины	Семестр	Неделя семестра	Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)			Формы текущего контроля успеваемости (по неделям семестра) Форма промежуточной аттестации (по семестрам)
				Лекц.	Сем.	Сам.
1	Введение. Предварительные сведения	7	1	4		4
2	Элементы теории оптимизации и вариационные задачи	7	2-3	4		4
3	Начальные сведения о численных методах для задач оптимизации и вариационных задач	7	4	4		4
4	Методы для задач безусловной оптимизации и нелинейных уравнений	7	5-8	8		8
5	Методы для задач условной оптимизации и комплементарных задач	7	9-14	12		12
6	Стратегии глобализации сходимости	7	15-16	4		4	Экзамен

5. Формы контроля знаний
По курсу «Ньютоновские методы для задач оптимизации и вариационных задач»: устный экзамен в 7 семестре. Требуется продемонстрировать понимание основных принципов, лежащих в основе изучаемых алгоритмов, а также умение проводить сравнительный анализ достоинств и недостатков различных алгоритмов.

6. Содержание дисциплины
Элементы теории оптимизации и вариационные задачи. Постановка и классификация задач оптимизации. Достаточные условия существования глобального решения. Условия первого порядка оптимальности в задаче оптимизации на выпуклом множестве. Условия первого и второго порядков оптимальности в задаче безусловной оптимизации, в задаче с ограничениями-равенствами (принцип Лагранжа), в задаче со смешанными ограничениями (условия Каруша-Куна-Таккера). Вариационные задачи.
Начальные сведения о сведения о численных методах для задач оптимизации и вариационных задач. Классификация методов. Понятия сходимости. Оценки скорости сходимости. Правила остановки.
Методы для задач безусловной оптимизацию оптимизации и нелинейных уравнений. Методы спуска. Метод Ньютона, квазиньютоновские методы.
Методы для задач условной оптимизации и комплементарных задач. Методы для задач оптимизации с простыми ограничениями (методы проекции градиента, условного градиента, условные методы Ньютона). Методы для задач оптимизации c ограничениями-равенствами (ньютоновские методы для системы Лагранжа, метод квадратичного штрафа, модифицированные функции Лагранжа). Методы решения задач со смешанными ограничениями и коплементарных задач (последовательное квадратичное программирование, метод Джозефи-Ньютона, полугладкий метод ньютона для комплементарных задач и системы Каруша-Куна-Таккера, идентификация активных ограничений, штрафы, модифицированные функции Лагранжа).
Стратегии глобализации сходимости. Одномерный поиск. Методы доверительной области. Глобализация сходимости методов последовательного квадратичного программирования.
7. Образовательные технологии, используемые в аудиторных занятиях
Преподавание курса «Ньютоновские методы для задач оптимизации и вариационных задач» осуществляется посредством компьютерных презентаций.

8. Оценочные средства для текущего контроля успеваемости и аттестации студентов
Экзаменационные вопросы, 7 семестр
1. Постановка и классификация задач оптимизации. Достаточные условия существования глобального решения.

2. Прямые необходимые условия оптимальности. Необходимые условия первого порядка оптимальности в задаче оптимизации на выпуклом множестве.

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

4. Необходимые и достаточные условия первого и второго порядков оптимальности в задаче с ограничениями-равенствами.

5. Необходимые и достаточные условия первого и второго порядков оптимальности в задаче со смешанными ограничениями.

6. Постановки вариационных задач.

7. Классификация методов. Понятия сходимости. Оценки скорости сходимости. Правила остановки.

8. Методы спуска для задач безусловной оптимизации.

9. Метод Ньютона для уравнений и задач безусловной оптимизации. Квазиньютоновские методы.

10. Метод проекции градиента.

11. Метод условного градиента. Условные методы Ньютона.

12. Ньютоновские методы для системы Лагранжа.

13. Метод квадратичного штрафа для задач c ограничениями-равенствами.

14. Метод модифицированных функций Лагранжа для задач c ограничениями-равенствами

15. Метод Джозефи-Ньютона

16. Методы последовательного квадратичного программирования.

17. Полугладкий метод Ньютона для комплементарных задач и системы Каруша-Куна-Таккера.

18. Идентификация активных ограничений.

19. Методы штрафа для задач со смешанными ограничениями.

20. Метод модифицированных функций Лагранжа для задач cо смешанными ограничениями.

21. Стратегии глобализации сходимости: одномерный поиск, методы доверительной области.

22. Глобализация сходимости методов последовательного квадратичного программирования.

9. Учебно-методическое и информационное обеспечение дисциплины
Основная литература
1. Измаилов А.Ф., Солодов М.В. Численные методы оптимизации. 2-е изд., перераб. и доп. М.: Физматлит, 2008.

2. Измаилов А.Ф. Чувствительность в оптммизации. М.: Физматлит, 2006.
Дополнительная литература
1. Бертсекас Д. Условная оптимизация и методы множителей Лагранжа. М.: Радио и связь, 1987.

2. Васильев Ф.П. Методы оптимизации. М.: Факториал Пресс, 2002.

3. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1988.

4. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985.

5. Деннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. М.: Мир, 1988.

6. Мину М. Математическое программирование. Теория и алго

ритмы. М.: Наука, 1990.

7. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986.

8. Карманов В.Г. Математическое программирование. М.: Физматлит, 2000.

9. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.

10. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М.: Наука, 1975.

10. Материально-техническое обеспечение дисциплины
Требуется компьютер, проектор и проекционный экран.