Лекции 66 часов Экзамен 5,6 семестр практические занятия 66 часа Диф зачет нет самостоятельная работа 20 часов



Скачать 122.88 Kb.
Дата25.11.2012
Размер122.88 Kb.
ТипЛекции


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

МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ

(ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)


УТВЕРЖДАЮ

Проректор по учебной работе

Д.А. Зубцов

22 июня 2012 г.

П Р О Г Р А М М А



курса по выбору МЕТОДЫ ОПТИМИЗАЦИИ

по направлению 010900

факультет ФУПМ

кафедра математических основ управления

курс III

семестр 5,6

Трудоёмкость: базовая часть – 0 зач. ед.

вариативная часть – 5 зач. ед.

по выбору студента – 0 зач. ед.

лекции – 66 часов Экзамен – 5,6 семестр

практические занятия – 66 часа Диф. зачет – нет

самостоятельная работа – 20 часов

ВСЕГО ЧАСОВ – 132

Программу составили:


д.ф.-м.н., проф., В.Г. Жадан,

к.ф.-м.н., доцент А.Г. Бирюков,

к.ф.-м.н. доцент Р.В. Константинов,

к.ф.-м.н. О.С. Федько,

ассистент П.Е. Двуреченский,

ассистент А.А. Орлов
Программа принята на заседании

кафедры математических основ управления

15 июня 2012 года

Заведующий кафедрой С. А. Гуз

Часть I. Элементы теории

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

  2. Выпуклые множества. Пересечение и линейная комбинация выпуклых множеств, их свойства. Конус, выпуклый конус. Аффинное множество, две формы представления аффинного множества. Выпуклая, неотрицательная и аффинная комбинация точек. Выпуклая, коническая и аффинная оболочки множеств. Их связь с комбинациями точек.

  3. Относительная внутренность и относительная граница множества. Свойства относительной внутренности выпуклого множества.

  4. Отделимость множеств. Свойства отделимости выпуклых множеств. Опорная гиперплоскость. Существование опорной гиперплоскости. Проекция точки на множество. Свойства проекций.

  5. Сопряженное множество. Второе сопряженное множество. Их свойства. Сопряженный конус и сопряженное линейное подпространство. Конус, двойственный к сумме конусов, и конус, сопряженный к пересечению конусов.

  6. Многогранные множества, полиэдры. Множество, сопряженное к многогранному множеству.

  7. Системы линейных равенств и неравенств. Теоремы об альтернативах. Лемма Фаркаша. Линейные матричные неравенства.

  8. Выпуклые, строго выпуклые и сильно выпуклые функции. Определения, примеры, свойства. Множество уровня выпуклой и сильно выпуклой функции. Эпиграф функции, свойства эпиграфа выпуклой функции.

  9. Непрерывность и дифференцируемость по направлению выпуклой функции. Дифференциальные критерии выпуклой (сильно выпуклой) функции.

  10. Субдифференциал функции. Существование и свойства субдифференциала. Теорема о субдифференциале суммы выпуклых функций.


  11. Индикаторная функция множества. Субдифференциал индикаторной функции выпуклого множества. Субдифференциал выпуклой  функции на выпуклом множестве. Опорная функция множества.

  12. Сопряженные и полярные функции, их свойства. Неравенства Юнга–Фенхеля и Минковского–Малера. Примеры сопряженных и полярных функций.

  13. Теорема Вейерштрасса и её следствия. Выпуклая задача минимизации. Теорема о глобальном экстремуме. Условия оптимальности выпуклых задач минимизации в терминах субдифференциалов.

  14. Касательное направление, касательный конус. Конус возможных направлений. Их свойства. Теорема о необходимом условии экстремума в терминах производных по касательному направлению. Необходимое и достаточное условие экстремума для выпуклой задачи в терминах производных по направлению.

  15. Необходимое и достаточное условия экстремума дифференцируемой функции на выпуклом множестве. Вариационное неравенство. Необходимые и достаточные условия экстремума для задачи безусловной минимизации (БМ).

  16. Необходимые и достаточные условия оптимальности для задач математического программирования. Условия Каруша–Куна–Таккера. Достаточные условия второго порядка. Условия регулярности ограничений. Необходимые и достаточные условия оптимальности для выпуклой задачи математического программирования. Регулярная и нерегулярная задачи математического программирования.

  17. Функция Лагранжа для задач математического программирования и ее свойства. Седловая точка функции Лагранжа.

  18. Теория двойственности для задач математического программирования. Задача линейного программирования и двойственная к ней. Собственные и несобственные задачи математического программирования. Двойственность для несобственных задач линейного программирования.

Часть 2. Численные методы

  1. Понятие о численных методах оптимизации. Сходимость и условия остановки численных методов.

  2. Унимодальные функции одной переменной. Методы одномерной минимизации (метод дихотомии, метод золотого сечения, метод Фибоначчи).

  3. Численные методы решения задачи БМ. Способы выбора шага в методах. Наискорейший спуск. Правило Армихо, правило Голдстейна. Градиентный метод и метод Ньютона решения задачи БМ. Свойства их сходимости. Квазиньютоновские методы.

  4. Сопряженные направления. Метод сопряженных градиентов для минимизации квадратичных функций. Метод сопряженных градиентов для решения общей задачи БМ.

  5. Задача линейного программирования (ЛП). Общая, каноническая и другие формы задачи ЛП. Угловые точки в задаче ЛП. Алгебраический критерий угловой точки.

  6. Симплекс-метод решения задачи ЛП. Табличная форма СМ. Модифицированный СМ решения задачи ЛП. Двухфазный симплекс-метод. М-задача.

  7. Методы решения задач с простыми ограничениями. Метод проекции градиента. Метод условного градиента.

  8. Метод возможных направлений и метод линеаризации. Различные варианты вспомогательных задач для выбора возможных направлений.

  9. Общая схема метода штрафных функций. Метод внешних штрафных функций. Метод внутренних штрафных функций (барьерных функций). Свойства сходимости методов штрафных функций.

  10. Методы параметризации целевых функций (метод внешних центров). Метод внешних центров для задач выпуклого программирования.

  11. Модифицированные функции Лагранжа для задач с ограничениями типа равенства. Их обобщение на задачи с неравенствами. Методы последовательного квадратичного программирования.

  12. Мультипликативно-барьерные методы для задач ЛП. Аффинно-масштабирующий метод и метод Кармаркара для задачи ЛП. Прямо-двойственный метод центрального пути для ЛП и КП.

  13. Задачи многокритериальной оптимизации. Понятие оптимальности в многокритериальной оптимизации. Оптимальные по Слейтеру и Парето решения задач многокритериальной оптимизации. Модификация метода внешних центров для задач многокритериальной оптимизации.

  14. Методы глобальной оптимизации. Построение нижних аппроксимаций для липшицевых функций. Метод секущих и метод покрытий.

Литература

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

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

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

  4. Бирюков С.И. Оптимизация. – М.: МФТИ, 2003.

  5. Бирюков А.Г. Методы оптимизации. Условия оптимальности в экстремальных задачах. – М.: МФТИ, 2010.

  6. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. – М.: Наука, 1978.

  7. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. – М.: Наука, 1982.

  8. Измайлов А.Ф., Солодов М.В. Численные методы оптимизации. – М.: Физматлит, 2003.

  9. Жадан В.Г. Численные методы линейного и нелинейного программирования. Вспомогательные функции в условной оптимизации. – М.: ВЦ РАН, 2002.

  10. Галеев Э.М. Тихомиров В.М. Оптимизация. Теория. Примеры. Задачи. – Эдиториал УРСС, 2000.

  11. Ю.Е. Нестеров. Введение в выпуклую оптимизацию. МЦНМО, 2010.

  12. Ляшенко И.Н., Карагодова Е.Н., Черникова Н.В., Шор Н.З. Линейное и нелинейное программирование. – Киев, 1975.

ЗАДАНИЕ № 1

  1. Используя геометрические интерпретации, решить следующие экстремальные задачи:

Указать, какие из решений этих задач являются локальными, глобальными, строгими, острыми.

  1. Решить задачу:



  1. Найти экстремумы в следующей задаче:



  1. Решить задачу:



  1. Пусть



  1. Найти опорные гиперплоскости ко множеству G в точках экстремума для задачи:



1) Пусть замкнутое множество, Найти множество Рассмотреть случаи выпуклого и невыпуклого множеств

2) Пусть даны и выпуклый конус .

Пусть Найти множества



3) Пусть - замкнутые множества и единственная точка. Каким условиям удовлетворяют множества , если:

а)

б)

  1. 1) Показать, что конусом, сопряженным к конусу



является конус



2) Найти



  1. Определить расстояние между множествами и а также уравнения двух разделяющих гиперплоскостей, одна из которых является опорной ко множеству , другая – ко множеству в точках, для которых расстояние минимально

Соответствующую задачу оптимизации решить методом множителей Лагранжа.

  1. а) Пусть даны матрицы





Рассмотреть частные случаи:

1)

Здесь единичные матрицы порядка m и n соответственно. Для всех случаев найти где число

б) Пусть даны матрицы



Доказать, что

Рассмотреть частный случай, когда

ЗАДАНИЕ № 2

  1. а) Пусть выпуклая функция. Доказать, что для всех Для функций и найти

б) Найти опорную функцию для множеств:



  1. Найти функции

на множестве



  1. Показать, что экстремальная задача регулярна: min f(x),



  1. Решить экстремальную задачу



если

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

  1. Решить задачу



для чего найти точки ,

где ,и выяснить, какие из них являются точками локального и глобального, строгого и острого экстремума.

  1. Решить задачу БМ:



  1. Решить задачу



  1. Решить методом множителей Лагранжа задачу:



  1. Построить задачу, двойственную к следующей:



  1. Найти функции, сопряженные к функциям:







  1. Для задачи min, где

найти седловую точку, решая задачу «в лоб», а именно:

а) считая множители Лагранжа параметрами, найти из решения задачи

б) найти из решения задачи



в) сравнить решения с решением, полученным из условия оптимальности ККТ.

  1. В выпуклой задаче



а) найти множество стационарных точек:



б) решить двойственную задачу:



в) найти седловую точку функции Лагранжа.

ЗАДАНИЕ № 3

1. Найти стационарные точки и точки экстремума функции

.

Сделать по одному шагу методом наискорейшего спуска (НС) из начальных точек

.

Оценить значение коэффициента скорости сходимости в методе НС для итерационных процессов, для которых



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

2. Для решения задачи при условии с e-точностью методами дихотомии, золотого сечения и Фибоначчи найти число вычислений функции для e = 10–7и e = 10–10.

3. Какую скорость сходимости к точке минимума имеет метод Ньютона при минимизации функций если



где –симметричная положительно определенная матрица,

  1. Пусть векторы – линейно независимы, Построим систему векторов



при этом система такова, что

Доказать, что векторы , сопряжены относительно матрицы А, а также справедливо соотношение

(*)

Используя формулу (*), решить систему линейных уравнений (**), когда система





предварительно симметризовав её.

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

.

6. Определить скорость сходимости метода Ньютона и метода наискорейшего спуска и окрестность, из которой эти методы сходятся к оптимальному решению следующей задачи:



Замечание: При решении задачи замену переменных не использовать.

7. Найти минимум функции методом Ньютона и методом сопряженных градиентов, где



8. Найти при условиях: методом множителей Лагранжа. Построить для данной задачи двойственную и решить ее. Сравнить решения этих задач.

9. Для задачи непрерывно дифференцируемая функция, сформулировать необходимые условия экстремума, если



Сформулировать для указанных задач достаточные условия экстремума первого порядка, второго порядка, достаточные условия острого экстремума. Сформулировать для задачи математического программирования необходимые и достаточные условия оптимальности первого и второго порядков.

10. Рассмотрим задачу № 1 (КЗ) и задачу № 2 (МП):



где функции – непрерывно дифференцируемые. Представим задачу МП в следующем виде:



Используя для задачи № 3 теорему о необходимом условии оптимальности для задачи № 1 (метод множителей Лагранжа для К 3; теор. 1.5, глава 1), доказать следующую теорему для задачи МП (см ).

Теорема (ККТ). Пусть в задаче МП функции f и непрерывно дифференцируемы в окрестности некоторой допустимой точки линейно независимы.
Тогда если решение задачи МП, то существует единственный вектор такой, что

– множество индексов активных ограничений.

ЗАДАНИЕ № 4

1. Для задачи ЛП



построить двойственную задачу, решить её, после чего решить прямую задачу.

2. Найти решение задачи



зависящее от параметров

3. Следующую задачу линейного программирования решить табличным симплекс-методом :


Найти решение соответствующей двойственной задачи.

Указание. Конкретные значения параметров A и B получить у своего преподавателя.

  1. Пусть матрица Методом внешних штрафных функций решить задачу 1: при условии Методом внутренних штрафных функций решить задачу 2: при условии .

5. Решить методом точных внешних штрафных функций задачу: найти



6. Методом условного градиента решить задачу: найти

при условиях Начальная точка x0 = (0, 1). Длина шага a вдоль направления h определяется из условия одномерной максимизации.

  1. Методом проекции градиента (схема № 2) решить задачу при условиях:

  1. Начальная точка

Методом возможных направлений решить следующую задачу: при условиях: Начальная точка

9. Методом модифицированных функций Лагранжа решить задачи.





Найти предельное значение множителя Лагранжа Оценить коэффициенты скорости сходимости последовательностей

Указание. При необходимости воспользоваться формулами из задачи № 11, задание № 1.

10. Методом параметризации целевой функции решить задачу при условии

11. Найти барьерно-проективным методом расстояние от начала координат до выпуклой оболочки точек

Указание. Свести задачу к задаче условной минимизации на симплексе.

Подписано в печать 29.06.2012. Формат 60 ´ 84.

Усл. печ. л. 0,25. Тираж 125 экз. Заказ № 184

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

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

«Московский физико-технический институт

(государственный университет)»

Отдел оперативной полиграфии «Физтех-полиграф»

141700, Московская обл., г. Долгопрудный, Институтский пер., 9

E-mail: rio@mail.mipt.ru


Похожие:

Лекции 66 часов Экзамен 5,6 семестр практические занятия 66 часа Диф зачет нет самостоятельная работа 20 часов iconЛекции 50 часов Экзамен 8 семестр практические занятия 50 часов Диф зачет нет самостоятельная работа 20 часов
Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления....
Лекции 66 часов Экзамен 5,6 семестр практические занятия 66 часа Диф зачет нет самостоятельная работа 20 часов iconЛекции 32 часа Экзамен нет практические (семинарские ) занятия 32 часа Диф зачет 4 семестр
Асимптотические обозначения (O, Ω, θ, o, ω) и их свойства (транзитивность, рефлексивность, симметричность, обращение)
Лекции 66 часов Экзамен 5,6 семестр практические занятия 66 часа Диф зачет нет самостоятельная работа 20 часов iconЛекции 32 часа Экзамен 8 семестр практические (семинарские) занятия 16 часов Диф зачет нет
Базовый вероятностный метод. Задача Эрдеша о свойстве в гиперграфа. Простейшая оценка снизу для величины m(n), равной наименьшему...
Лекции 66 часов Экзамен 5,6 семестр практические занятия 66 часа Диф зачет нет самостоятельная работа 20 часов iconЛекции 34 часа Экзамен нет практические ( семинарские ) занятия 34 часа Диф зачет 7 семестр
Микроскопическое (динамическое и статистическое) и макроскопическое (гидродинамическое и феноменологическое) описание физических...
Лекции 66 часов Экзамен 5,6 семестр практические занятия 66 часа Диф зачет нет самостоятельная работа 20 часов iconЛекции 18 часов, практические занятия 18 часов, самостоятельная работа 36 часов
Трудоемкость (в зачетных единицах) – 2;аудиторных – 36 часов, лекции – 18 часов, практические занятия 18 часов, самостоятельная работа...
Лекции 66 часов Экзамен 5,6 семестр практические занятия 66 часа Диф зачет нет самостоятельная работа 20 часов iconЛекции 32 часа Экзамен нет практические (семинарские) занятия 32 часа Диф зачет II семестр
Примеры групп. Циклические группы. Аддитивная группа вычетов по модулю n. Группа перестановок (симметрическая группа). Цикловое разложение...
Лекции 66 часов Экзамен 5,6 семестр практические занятия 66 часа Диф зачет нет самостоятельная работа 20 часов iconЛекции 36 часов 20 Практические занятия 36 8 Индивидуальная работа 84 3 Самостоятельная работа 70 51 Зачет нет нет
Охватывает продолжительный отрезок времени с 40 тыс лет и до современности. Но основное внимание обращается эпохе формирования современных...
Лекции 66 часов Экзамен 5,6 семестр практические занятия 66 часа Диф зачет нет самостоятельная работа 20 часов iconЛекции 50 часов Экзамен 8 семестр семинары 50 часов Зачет нет лабораторные занятия нет
Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления....
Лекции 66 часов Экзамен 5,6 семестр практические занятия 66 часа Диф зачет нет самостоятельная работа 20 часов iconЛекции 34 часа Экзамен 9 семестр практические (семинарские) занятия 34 часа Зачет нет
Одномерные решетчатые системы. Теорема об отсутствии фазовых переходов при в системах малой размерности (одномерных и двумерных)...
Лекции 66 часов Экзамен 5,6 семестр практические занятия 66 часа Диф зачет нет самостоятельная работа 20 часов iconЛекции 34 часа Экзамен нет семинары 34 часа Зачет с оценкой 3 семестр лабораторные занятия нет
Программа обсуждена на заседании кафедры математических основ управления 15 мая 2011 г
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org