Документ взят из кэша поисковой машины. Адрес оригинального документа : http://io.cs.msu.ru/UMK.doc Дата изменения: Fri Sep 5 22:34:46 2014 Дата индексирования: Sat Apr 9 22:26:14 2016 Кодировка: koi8-r

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное образовательное учреждение
высшего профессионального образования
«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Факультет вычислительной математики и информатики
УТВЕРЖДАЮ
Декан факультета ВМК
____________________Е.И. Моисеев
«______»__________________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. Материально-техническое обеспечение дисциплины

Требуется компьютер, проектор и проекционный экран.