Лекции 64 часа Экзамен 5,6 семестр семинары 64 часа Зачет нет лабораторные занятия нет



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


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

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

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

УТВЕРЖДАЮ

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

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

24 июня 2011 г.

П Р О Г Р А М М А



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

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

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

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

курс III

семестр 5,6

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

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

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

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

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

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

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

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


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

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

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

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

17 мая 2011 года

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

Часть 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. Бирюков А.Г. Методы оптимизации. Условия оптимальности в экстремальных задачах. – М.: МФТИ, 2010.

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

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

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

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

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

ЗАДАНИЕ № 1

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



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

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



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



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

.

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



6. Пусть



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



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

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



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

а)

б)

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



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



2) Найти



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–7и e = 10–10.

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



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

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



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

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

(*)

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





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

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

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



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

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



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

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



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

10. Пусть функции непрерывно дифференцируемы на . Рассмотрим экстремальные задачи:
А) Найти:



Б) Найти: ,

где

;

.

  1. Доказать, что точка является локальным решением задачи А тогда и только тогда, когда существует точка , где , являющаяся локальным решением задачи Б.

  2. Доказать, что для всех точек задачи А существует , такой, что является стационарной точкой задачи Б.

  3. Верно ли, что для стационарной точки задачи Б точка является стационарной точкой задачи А?


ЗАДАНИЕ № 4


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



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

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


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

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





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

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

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

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



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

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

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



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

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

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





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

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

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

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

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

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

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

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

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

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

Отдел оперативной полиграфии

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



Похожие:

Лекции 64 часа Экзамен 5,6 семестр семинары 64 часа Зачет нет лабораторные занятия нет iconЛекции 34 часа Экзамен нет семинары 34 часа Зачет с оценкой 3 семестр лабораторные занятия нет
Программа обсуждена на заседании кафедры математических основ управления 15 мая 2011 г
Лекции 64 часа Экзамен 5,6 семестр семинары 64 часа Зачет нет лабораторные занятия нет iconЛекции 32 часа Экзамен нет семинары 32 часа Зачет с оценкой 8 семестр лабораторные занятия нет
Охватывает более простые, главным образом «одномерные» методы; третье задание относится к анализу существенно многомерных данных
Лекции 64 часа Экзамен 5,6 семестр семинары 64 часа Зачет нет лабораторные занятия нет iconЛекции 32 часа Экзамен 8 семестр семинары -нет Зачет с оценкой нет лабораторные занятия нет
Некоторые задачи, приводящие к стохастическим аналогам обыкновенных дифференциальных уравнений (стохастические модели, возникающие...
Лекции 64 часа Экзамен 5,6 семестр семинары 64 часа Зачет нет лабораторные занятия нет iconЛекции 32 часа Экзамен нет семинары нет Зачёт с оценкой 4 семестр лабораторные занятия 32 часа
Понятия базы данных, системы баз данных и субд. Требования к субд. Характеристики, функции субд
Лекции 64 часа Экзамен 5,6 семестр семинары 64 часа Зачет нет лабораторные занятия нет iconЛекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет
Алфавиты, конструктивные объекты, их примеры. Понятие алгоритма, вычислимые функции. Формализация понятия алгоритма: частично-рекурсивные...
Лекции 64 часа Экзамен 5,6 семестр семинары 64 часа Зачет нет лабораторные занятия нет iconЛекции 32 часа Экзамен нет практические (семинарские ) занятия 32 часа Диф зачет 4 семестр
Асимптотические обозначения (O, Ω, θ, o, ω) и их свойства (транзитивность, рефлексивность, симметричность, обращение)
Лекции 64 часа Экзамен 5,6 семестр семинары 64 часа Зачет нет лабораторные занятия нет iconЛекции 34 часов Экзамен 11 семестр семинары нет Зачет нет лабораторные занятия нет
Приближенные алгоритмы с гарантированными оценками точности. Анализ точности жадного алгоритма в задачах о покрытии, вершинном покрытии...
Лекции 64 часа Экзамен 5,6 семестр семинары 64 часа Зачет нет лабораторные занятия нет iconЛекции 34 часа Экзамен нет практические ( семинарские ) занятия 34 часа Диф зачет 7 семестр
Микроскопическое (динамическое и статистическое) и макроскопическое (гидродинамическое и феноменологическое) описание физических...
Лекции 64 часа Экзамен 5,6 семестр семинары 64 часа Зачет нет лабораторные занятия нет iconСеминары нет Зачёт нет лабораторные занятия 16 часов самостоятельная работа 2 часа в неделю
Программа утверждена на заседании кафедры математических основ управления 18 марта 2005 г
Лекции 64 часа Экзамен 5,6 семестр семинары 64 часа Зачет нет лабораторные занятия нет iconЛекции 34 часа Экзамен 9 семестр практические (семинарские) занятия 34 часа Зачет нет
Одномерные решетчатые системы. Теорема об отсутствии фазовых переходов при в системах малой размерности (одномерных и двумерных)...
Разместите кнопку на своём сайте:
ru.convdocs.org


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