Методы оптимизации

Кафедра информатики и автоматизации научных исследований

Специальность: Прикладная информатика

Преподаватель: Коротченко А.Г.

Целями освоения дисциплины (модуля) «Методы оптимизации»  являются ознакомление студентов с вопросами построения оптимизационных математических моделей для конкретных предметных областей, обучение студентов основным понятиям теории нелинейной оптимизации и методам решения экстремальных задач. В  курсе изучаются условия оптимальности в задачах математического программирования, элементы выпуклого анализа и теории оптимального управления, методы решения задач безусловной и условной оптимизации.

В курс включены основные понятия, изучаемые в таких дисциплинах как математический анализ, алгебра и геометрия дифференциальные уравнения, математические основы информатики.  К дисциплинам, для которых освоение данной дисциплины необходимо как предшествующее, относится дисциплина базовой части  математического и естественнонаучного цикла «Теория систем и системный анализ».

В результате освоения дисциплины обучающийся должен:

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

Уметь:  применять условия оптимальности для анализа экстремальных задач из различных классов, доказывать основные теоремы теории нелинейной оптимизации.

Владеть: представлениями  (навыками)   в решении нелинейных задач оптимизации (методы нулевого порядка, сопряженных градиентов, условного градиента, методы штрафов, методы решения многоэкстремальных задач).

Содержание

1. НЕЛИНЕЙНЫЕ ОПТИМИЗАЦИОННЫЕ МОДЕЛИ. ЗАДАЧА БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ И КЛАССИЧЕСКАЯ ЗАДАЧА НА УСЛОВНЫЙ ЭКСТРЕМУМ. Понятие о задачах оптимизации. Примеры оптимизационных задач. Схема вычислительного эксперимента. Теоремы существования решения задач поиска экстремума. Необходимые и достаточные условия оптимальности в задаче безусловной оптимизации. Классическая задача на условный экстремум. Функция Лагранжа. Теоремы о необходимом условии оптимальности первого  и второго порядка. Достаточные условия оптимальности.

 

2.ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА. УСЛОВИЯ ОПТИМАЛЬНОСТИ В ЗАДАЧАХ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ. ЭЛЕМЕНТЫ ТЕОРИИ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ. Выпуклые множества и выпуклые функции. Примеры. Внутренние операции в классе выпуклых функций. Выпуклая задача оптимизации и ее основные свойства. Дифференциальные критерии выпуклости. Сильно выпуклые функции и критерии сильной выпуклости. Теорема существования и единственности решения выпуклой задачи с сильно выпуклой целевой функцией. Проекция точки на множество. Теорема о разделяющей гиперплоскости и теорема об опорной гиперплоскости. Теорема отделимости. Теорема Фана. Необходимые условия оптимальности в терминах направлений. Дифференциальное условие оптимальности в задаче минимизации функции на выпуклом множестве. Конкретизация дифференциального условия оптимальности в задаче минимизации функции на выпуклом множестве для случаев, когда допустимое множество является гиперпараллелепипедом и неотрицательным октантом. Задача математического программирования. Необходимые условия оптимальности в задаче математического программирования (принцип Лагранжа). Условия регулярности в задаче математического программирования. Достаточные условия оптимальности, определяемые принципом Лагранжа, для регулярной задачи выпуклого программирования. Теорема Куна-Таккера. Достаточные условия оптимальности в общей задаче математического программирования.  Вектор Куна-Таккера. Теорема существования вектора Куна-Таккера, Основные теоремы теории двойственности. Теорема Куна-Таккера в форме двойственности. Формулировка принципа максимума. Простейшая задача оптимального быстродействия. Задача вариационного исчисления.

3. ОПТИМАЛЬНЫЕ АЛГОРИТМЫ ПОИСКА ЭКСТРЕМУМА. МЕТОДЫ ОПТИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ. Унимодальные функции. Оптимальный пассивный метод поиска минимума унимодальных функций. Метод Фибоначчи. Метод золотого сечения. Оптимальный пассивный метод поиска минимума липшицевых функций. Точная нижняя миноранта для функций, удовлетворяющих условию Липшица. Свойства точной нижней миноранты. Метод ломаных. Метод кусочно-линейной аппроксимации.

4. КЛАССИЧЕСКИЕ ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ БЕЗУСЛОВНОЙ И УСЛОВНОЙ ОПТИМИЗАЦИИ. НЕКОТОРЫЕ МЕТОДЫ РЕШЕНИЯ МНОГОЭКСТРЕМАЛЬНЫХ ЗАДАЧ. Начальные сведения о численных методах оптимизации функций многих переменных. Сходимость и скорость сходимости методов оптимизации. Условия остановки. Направление убывания. Выбор длины шага в методах спуска. Градиентный метод. Сходимость в случае невыпуклой минимизируемой функции. Сходимость и оценка скорости сходимости в случае сильно выпуклой минимизируемой функции. Обсуждение метода. Примеры. Метод Ньютона и его модификации. Квазиньютоновские методы. Примеры. Понятие сопряженных направлений и их свойства. Методы сопряженных направлений. Метод сопряженных градиентов. Метод сопряженных направлений нулевого порядка. Метод Хука-Дживса. Метод Нелдера-Мида. Примеры. Метод проекции градиента. Теорема сходимости. Обсуждение метода. Метод условного градиента и его сходимость. Конечный метод решения задач квадратичного программирования. Метод линеаризации. Сходимость метода штрафных функций. Оценки скорости сходимости. Простейший алгоритм метода штрафов. Примеры. Метод параметризации целевой функции. Методы, основанные на редукции размерности. Методы, основанные на априорной информации о минимизируемой функции.

Лабораторный практикум

1.Построение нелинейных оптимизационных моделей. Задача безусловной оптимизации. Классическая задача на условный экстремум.

2. Выпуклые множества и выпуклые функции. Критерии выпуклости и сильной выпуклости. Выпуклая задача оптимизации. Теорема существования и единственности. Условие оптимальности в задаче минимизации функции на выпуклом множестве. Задача математического программирования. Принцип Лагранжа. Условия регулярности в задаче математического программирования. Теорема Куна - Таккера в дифференциальной форме.

3. Метод Фибоначчи. Метод золотого сечения. Оптимальный одношаговый метод в классах, определяемых априорной информацией о минимизируемой функции. Метод ломаных.

4. Градиентный метод. Квазиньютоновские методы. Методы сопряженных направлений. Метод проекции градиента. Метод условного градиента. Метод линеаризации. Методы штрафов.

Литература

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

  1. Васильев Ф.П. Численные методы решения экстремальных задач. – М.: Наука, 19801.
  2. Васильев Ф.П. Методы решения экстремальных задач. – М.: Наука, 1981
  3. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. – М.: Наука, 1986
  4. Карманов В.Г. Математическое программирование. – М.: Наука, 1986

 

б) дополнительная литература

  1. Хедли Дж. Нелинейное и динамическое программирование. – М.: Мир, 1967
  2. Зангвилл У.И. Нелинейное программирование. Единый подход. – М.: Советское радио, 1973
  3. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф.
  4.  Математическая теория оптимальных процессов. - М.: Наука, 1976
  1. Стронгин Р.Г. Численные методы в многоэкстремальных задачах. – М.: Наука, 1978
  2. 5.. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. – М.: Наука, 1978
  1. Черноусько Ф.Л., Меликян А.А. Игровые задачи управления и поиска. – М.: Наука, 1978
  2. Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979
  3. Ашманов С.А. Линейное программирование. – М.: Наука, 1981
  4. 9.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982
  1. Розен В.В. Цель- оптимальность- решение: математические модели принятия оптимальных решений. – М.: Радио и связь, 1982
  2. Батищев Д.И. Методы оптимального проектирования. – М.: Радио и связь, 1984
  3. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. – М.: Высшая школа, 1986
  4. Банди Б. Методы оптимизации. Вводный курс. – М.: Радио и связь, 1988
  5. Коротченко А.Г. Методические указания для самостоятельной работы студентов специальности «прикладная математика» при изучении темы «Методы поиска экстремума функций одной переменной» в курсе «Моделирование выбора решений». – Изд. ГГУ, Горький, 1990
  6. Батищев Д.И., Коган Д.И. Вычислительная сложность экстремальных задач переборного типа. – Изд. ННГУ, Н.Новгород, 1994
  7. Коротченко А.Г., Тихонов В.А. Методические указания (сборник задач) по курсу «Модели и методы принятия решений». – Изд. ННГУ, Н.Новгород, 2000
  8. Коротченко А.Г., Сморякова В.М., Кучина О.М., Малаховская Д.А. Методическая разработка по курсу «Системы принятия решений». – Фонд компьютерных изданий ННГУ, www.unn.ru/syst _ pr.doc,2010
  9. Коротченко А.Г., Сморякова В.М., Кучина О.М., Малаховская Д.А. Методическая разработка (сборник задач) по курсу «Системы принятия решений». – Фонд компьютерных изданий ННГУ, www.unn.ru/task_ pr.doc,2010

Отчетность

  • Семестр 5: Зач
  • Семестр 6: Экз