Программа по курсу: Основы выпуклого анализа и линейного программирования по направлению: 511600 факультет

Вид материала

Программа

Содержание лекции: 66 часов ВСЕГО ЧАСОВ: 66

Подобный материал:

• Задачи математического и линейного программирования. Математическая модель задачи использования, 25.82kb.
• Кафедра «Прикладная математика» Экономические приложения линейного программирования, 27.15kb.
• Программа по курсу: современные технологии параллельного программирования (по выбору), 69.72kb.
• К. А. Тимирязева Экономический факультет Кафедра экономической кибернетики Светлов, 241.83kb.
• Программа по курсу: введение в искусственный интеллект (базовый) по направлению: 511600, 68.26kb.
• Задачи линейного программирования Геометрическая интерпретация задач линейного программирования, 132.4kb.
• Задачи линейного программирования Геометрическая интерпретация задач линейного программирования, 38.07kb.
• Темы курсовых работ «Методы оптимизации» Графический метод решения задачи линейного, 11.12kb.
• Рабочей программы дисциплины Автоматизированные информационно-управляющие системы, 23.35kb.
• Ю. А. Самарский 17 июня 2006 г. Программ а по курсу вычислительная математика по направлению, 137.08kb.

Министерство образования и науки Российской Федерации

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

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


УТВЕРЖДАЮ

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

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

«_______» _____________2006 г.

ПРОГРАММА

по курсу: Основы выпуклого анализа и линейного программирования

по направлению: 511600

факультет: ФАКИ

кафедра: вычислительной математики


курс: 3 дифф. зач.: 5 семестр

семестры: 5,6 экзамен: 6 семестр
^

лекции: 66 часов

ВСЕГО ЧАСОВ: 66

Программу составил к.ф.-м.н., доцент Балашов М.В.


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

кафедры вычислительной математики 28 июня 2006 г.


Зав. кафедрой проф. А.С. Холодов

Осенний семестр

1. Выпуклые множества, функции и их связь. Выпуклая оболочка множества. Теорема Каратеодори.
   
2. Непрерывность выпуклых функций. Полунепрерывные снизу функции, их свойства.
   
3. Теоремы об отделимости. Опорные гиперплоскости.
   
4. Сопряженные функции. Теорема Фенхеля-Моро. Индикаторные и опорные функции выпуклых замкнутых множеств и их связь. Описание выпуклых замкнутых множеств с помощью опорных функций.
   
5. Метрика Хаусдорфа. Пространство (выпуклых) компактов в Rⁿ, его полнота и локальная компактоность.
   
6. Поляры.
   
7. Теорема Каратеодори для функций. Случай положительно однородной функции.
   
8. Односторонние производные по направлению выпуклых функций. Субдифференциал. Полунепрерывность субдифференциала сверху. Теорема Моро-Рокафеллара.
   
9. Задача выпуклого программирования. Функция Лагранжа, седловая точка. Необходимые и достаточные условия экстремума.
   
10. Теорема Крейна-Мильмана-Кли для неограниченных множеств. Равенство A=co (extr A)+O⁺A. Задача о максимизации выпуклой функции на выпуклом замкнутом множестве.
    

Весенний семестр

1. Каноническая, основная и общая задачи линейного программирования (ЛП). Сведение основной задачи ЛП к канонической. Сведение общей задачи ЛП к канонической.
   
2. Описание крайних точек множества-ограничения в канонической задаче.
   
3. Алгоритм симплекс-метода (СМ) для канонической задачи. Экономные формулы для пересчета. Модифицированный симплекс-метод. Примеры.
   
4. Зацикливание. Лексикографическое правило избежания зацикливавния (без доказательства).
   
5. М-задача. Эквивалентность М-задачи исходной канонической задаче для больших М (при условии непустоты множества ограничений в канонической задаче).
   
6. Теорема Грюнбаума-Хаммера (без доказательства). Идея метода центрированных сечений. Задача об отыскании шара максимального радиуса, вписанного в многогранник, сведение ее к задаче ЛП.
   
7. Сетка, сеточные операторы и их свойства.
   
8. Оценки погрешности многогранных аппроксимаций на сетке.
   
9. Сильно выпуклые множества с радиусом R. Оценки погрешности многогранных аппроксимаций сильно выпуклых множеств с радиусом R.
   
10. Сильно выпуклые функции. Устойчивость задачи минимизации сильно выпуклой функции на множестве по множеству в метрике Хаусдорфа.
    

Список литературы

1. Рокафеллар Р. Выпуклый анализ. М., Мир, 1973.
   
2. Поляк Б.Т. Введение в оптимизацию. М., Наука, 1983.
   
3. Васильев Ф.П. Численные методы решения экстремальных задач. М., Наука, 1980.
   
4. Половинкин Е.С. Элементы теории многозначных отображений. МФТИ, 1982.
   
5. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М., Наука, 1980.
   
6. Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач. М., Наука, 1974.
   
7. Гольштейн Е.Г., Третьяков Н.В. Модифицированные функции Лагранжа. М., Наука, 1989.