Лекции 66 часа Экзамен 5,6 семестр семинары 66 часа Зачет нет лабораторные занятия нет - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Лекции 32 часа Экзамен нет семинары 32 часа Зачет с оценкой 8 семестр... 1 52.75kb.
Лекции 32 час Экзамен 8 семестр семинары 16 Зачет с оценкой нет лабораторные... 1 27.97kb.
Лекции 34 часа Экзамен IX семестр практические (семинарские) 1 109.21kb.
Лекции 2 часа Практические занятия 52 часа срс 27 часов Всего 81... 1 149.04kb.
Семинары: Стребков Денис Олегович Лекции: 24 часа Семинары: 24 часа 1 332.85kb.
Лекции (64 часа), экзамен в 8-м семестре семинары (64 часа) 1 45.7kb.
Современные проблемы физики рабочая программа 3 347.35kb.
Аннотации примерных программ дисциплин для профиля «Мировая экономика» 1 83.65kb.
Лекции нет; Лабораторные занятия нет Практические занятия 16; 1 29.91kb.
Лекции 18 час. Практические / лабораторные занятия 1 8 час. 1 83.38kb.
Учебная программа дисциплины в. Од. 5 «История эстетических учений»... 1 296.03kb.
Программа введение в оптимизацию 1 36.64kb.
Направления изучения представлений о справедливости 1 202.17kb.

Лекции 66 часа Экзамен 5,6 семестр семинары 66 часа Зачет нет лабораторные занятия - страница №1/1


министерство образования и науки российской федерации


Федеральное агентство по образованию


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

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


УТВЕРЖДАЮ

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

Ю.А.Самарский

июля 2010 г.



П Р О Г Р А М М А



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

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

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

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

курс III

семестр 5,6

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

семинары – 66 часа Зачет – нет

лабораторные занятия – нет

самостоятельная работа – 2 часа в неделю

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

Программу и задание составили:


д.ф.-м.н. В.Г. Жадан,

к.ф.-м.н. А.Г. Бирюков,


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

ассистент А.А. Орлов


Программа утверждена на заседании

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

14 апреля 2010 года

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19. Задача полуопределенного программирования (линейная задача на конусе положительно полуопределенных матриц). Примеры задач полуопределенного программирования. Теория двойственности для задач полуопределенного программирования.



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

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

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

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

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

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

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

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

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

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

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

11. Модифицированные функции Лагранжа и численные методы на их основе.

12. Барьерно-проективные методы для задач с простыми ограничениями. Барьерно-проективные методы для задач линейного программирования.

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

14. Задачи многокритериальной оптимизации. Оптимальные по Парето решения задач многокритериальной оптимизации. Модификация метода внешних центров для задач многокритериальной оптимизации.
Литература
1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. – М.: Наука, 1986.

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

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

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

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

6. Лесин В.В., Лисовец Ю.П. Основы методов оптимизации. – М.: МАИ, 1998.

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

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

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

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


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

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

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

3. Найти экстремумы неявно заданной функции двух переменных:



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



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



6. Пусть








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




8. Обозначим проекция точки а на множество G.

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

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

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



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



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



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



Вычисления провести с относительной точностью

11.


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




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

1)

Здесь – единичные матрицы порядка m и n соответственно.

Для всех случаев найти

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

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



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




ЗАДАНИЕ № 2


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



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

на множестве



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




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

если

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


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

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

где ,

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



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



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



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



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

a)

б)





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

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

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



из решения задачи

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



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



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

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



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

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



ЗАДАНИЕ № 3
1. Найти стационарные точки и точки экстремума функции

.

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



.

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





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

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

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

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


Указание: При необходимости воспользоваться одной из формул:

где

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


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

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



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




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

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

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



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

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

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

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


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

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


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

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

ЗАДАНИЕ № 4


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

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



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

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



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

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


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

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

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

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



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

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

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

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

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



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




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

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

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

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

Подписано в печать 09.07.09. Формат 60 ´ 84. Бумага офсетная.

Печать офсетная. Усл. печ. л.1,25. Уч.-изд. л. 0,9. Тираж 150 экз. Заказ №
Государственное образовательное учреждение

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

«Московский физико-технический институт (государственный университет)»

Отдел автоматизированных издательских систем «ФИЗТЕХ-ПОЛИГРАФ»



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






Если нравится, считайте, что получилось. Леонид Леонидов
ещё >>