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

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

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

УТВЕРЖДАЮ

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

___________

«_______» _____________2006 г.

ПРОГРАММА

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

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

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

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

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

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

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

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

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

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

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

Зав. кафедрой проф.

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

Выпуклые множества, функции и их связь. Выпуклая оболочка множества. Теорема Каратеодори. Непрерывность выпуклых функций. Полунепрерывные снизу функции, их свойства. Теоремы об отделимости. Опорные гиперплоскости. Сопряженные функции. Теорема Фенхеля-Моро. Индикаторные и опорные функции выпуклых замкнутых множеств и их связь. Описание выпуклых замкнутых множеств с помощью опорных функций. Метрика Хаусдорфа. Пространство (выпуклых) компактов в Rn, его полнота и локальная компактоность. Поляры. Теорема Каратеодори для функций. Случай положительно однородной функции. Односторонние производные по направлению выпуклых функций. Субдифференциал. Полунепрерывность субдифференциала сверху. Теорема Моро-Рокафеллара. Задача выпуклого программирования. Функция Лагранжа, седловая точка. Необходимые и достаточные условия экстремума. Теорема Крейна-Мильмана-Кли для неограниченных множеств. Равенство A=co (extr A)+O+A. Задача о максимизации выпуклой функции на выпуклом замкнутом множестве.

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

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

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

1.  Выпуклый анализ. М., Мир, 1973.

2.  Поляк в оптимизацию. М., Наука, 1983.

3.  Васильев методы решения экстремальных задач. М., Наука, 1980.

4.  Половинкин теории многозначных отображений. МФТИ, 1982.

5.  Пшеничный анализ и экстремальные задачи. М., Наука, 1980.

6.  , Тихомиров экстремальных задач. М., Наука, 1974.

7.  , Третьяков функции Лагранжа. М., Наука, 1989.