Выпуклые задачи на многогранниках

• Автор: Горская, Елена Сергеевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 110 с. : ил.

Содержание
Введение
1. Линеаризация выпуклых экстремальных задач
1.1. Многомерная аппроксимация
.1.1.1. Приближение сумм и композиций
1.1.2. Приближение элементарных функций
1.1.3. Приближение функций многих переменных
1.2. Индуктивная аппроксимация
1.2.1. Линеаризация функций одной переменной
1.2.2. Линеаризация функций многих переменных
1.2.3. Численные примеры
2. Оценка хроматических чисел пространства методами выпуклой минимизации
2.1. Оценка хроматических чисел Мп в евклидовой метрике 12 .
2.1.1. Решение экстремальной задачи
2.1.2. Алгоритм для реализации метода
2.1.3- Численные результаты
2.1.4. Некоторые обобщения
2.2. Оценка хроматических чисел К" в метрике 1
2.2.1. Решение экстремальной задачи
2.2.2. Численные результаты
Список литературы

Введение
Темой диссертации является изучение выпуклых экстремальных задач и их применение к задачам дискретной математики. В первой главе диссертации разработан метод, позволяющий сводить многие выпуклые экстремальные задачи к задаче поиска минимума линейного функционала на многограннике, заданном системой неравенств. При этом под многогранником понимается любая многогранная область, заданная линейными неравенствами (возможно, неограниченная). Во второй главе диссертации существующие методы решения выпуклых экстремальных задач будут применены к решению задачи комбинаторной геометрии по нахождению нижних асимптотических оценок хроматических чисел пространства К". Изучаемая область тесно связана с теорией алгоритмов, сложностью алгоритмов, выпуклым анализом.
В сороковые годы прошлого века произошёл всплеск интереса к выпуклым задачам. Он прежде всего был вызван рождением линейного программирования. Задача линейного программирования (ЛП) заключается в нахождении экстремума линейной функции на многограннике (задаваемом конечной системой линейных равенств и неравенств). Впервые нетривиальные задачи такого рода появились в исследованиях Л. В. Канторовича в 1939 г. [1] и Дж. Данцига в 1947 г. [2]. Развитие линейного программирования, а затем и выпуклой оптимизации в более широком смысле, началось в США в конце Второй мировой войны. Это было вызвано как проблемами экономики, так и вопросами, которые ставились военно-промышленным комплексом.
Стремительному развитию линейного программирования способствовали как математики (Л. В. Канторович, Д. фон Нейман, Дж. Данциг), так и экономисты (В. Леонтьев, Т. Купманс). В 1947 году Дж. Данциг предложил метод направленного перебора смежных вершин многогранника в направлении возрастания целевой функции —- симплекс-метод, ставший основным при решении задач ЛП. Ему же принадлежит первая фундаментальная монография по линейному программированию [2].

Одновременно с развитием ЛП большое внимание уделялось задачам нелинейного выпуклого программирования, в которых либо минимизируемая функция, либо функции ограничения, либо и то и другое нелинейны. Термин выпуклое программирование появился в 1960-х годах. Можно сказать, что выпуклое программирование — это набор методов и алгоритмов для приближённого численного решения выпуклых задач. Общая задача ВП ставится так:
/о (ж) -+ min, (1)
х = (a?i, ...,хп) Е G,
при этом G С Мп — выпуклое множество, заданное системой неравенств /г(ж) ^ 0, г = 1,..., т, fi — выпуклые (не обязательно дифференцируемые) функции (г = 0,... , т). Нужно найти её решение с точностью е, т. е. указать такую точку х* Е G, что
| min/о(ж) - /0(ж*)| < £

(иногда речь идет не об абсолютной погрешности, а об относительной).
Для приближённого решения выпуклых задач разработано достаточно много методов, при этом многие из них разработаны для конкретных классов функций: симплекс-метод, метод центрированных сечений и его модификации, метод эллипсоидов, метод внутренней точки, метод уровней, градиентный метод. В конце введения дан краткий обзор этих методов. Для каждой задачи обычно подбирается наиболее подходящий для неё метод либо создаётся новый, как это произошло с методом центрированных сечений (4).
Особенные трудности вызывают задачи ВП, в которых число переменных п велико. В этом случае возникают сложности со сходимостью алгоритмов для произвольных выпуклых задач. Метод эллипсоидов для некоторых задач работает медленно и плохо сходится уже при п = 20. Кроме того, он требует на каждом шаге хранить и переопределять огромную матрицу. Метод центрированных сечений требует вычисления центров тяжестей выпуклых тел, что даже для многогранников является NP-сложной задачей. Метод внутренней точки полностью разработан лишь для некоторого класса задач (в частности, для задач линейного и квадратичного программирования).
При этом задачи линейного программирования в пространстве большой размерности (даже при п > 105) могут быть эффективно решены

= /о — /q- Новая точка Xk+i определяется как проекция Хк на множество уровня 1к = + ЛАк, т. е., Хк+1 — решение задачи
\x - Tfc||2 -> min, х gG,
fkM < h-
Приближённым решением задачи, найденным после к итераций считается «наилучшая» из точек Xj, j = 1,..., к, т. е., такая точка Хк, что

/о = fo(xk). Метод завершает свою работу, когда Afc ^ е.
При этом для любого е > 0 количество шагов метода Ne не превосходит с(А)—-, где с(А) = ((1 —А)2А(2 —А))^1, D — диаметр многогранника

G, L — константа Липшица функции /о-