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

Темой диссертации является изучение выпуклых экстремальных задач и их применение к задачам дискретной математики. В первой главе диссертации разработан метод, позволяющий сводить многие выпуклые экстремальные задачи к задаче поиска минимума линейного функционала на многограннике, заданном системой неравенств. При этом под многогранником понимается любая многогранная область, заданная линейными неравенствами (возможно, неограниченная). Во второй главе диссертации существующие методы решения выпуклых экстремальных задач будут применены к решению задачи комбинаторной геометрии по нахождению нижних асимптотических оценок хроматических чисел пространства К". Изучаемая область тесно связана с теорией алгоритмов, сложностью алгоритмов, выпуклым анализом.

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

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

Одновременно с развитием ЛП большое внимание уделялось задачам нелинейного выпуклого программирования, в которых либо минимизируемая функция, либо функции ограничения, либо и то и другое нелинейны. Термин выпуклое программирование появился в 1960;х годах. Можно сказать, что выпуклое программирование — это набор методов и алгоритмов для приближённого численного решения выпуклых задач. Общая задача ВП ставится так: о (я) min, (1).

X =. .. , %п) ^ G¦) при этом G с!" — выпуклое множество, заданное системой неравенств fi (х) < 0, г = 1, т, fi — выпуклые (не обязательно дифференцируемые) функции (г = 0,., ш). Нужно найти её решение с точностью е, т. е. указать такую точку х* G G, что тш/о (я-) — /о (ж*)| < г xeG иногда речь идет не об абсолютной погрешности, а об относительной).

Для приближённого решения выпуклых задач разработано достаточно много методов, при этом многие из них разработаны для конкретных классов функций: симплекс-метод, метод центрированных сечений и его модификации, метод эллипсоидов, метод внутренней точки, метод уровней, градиентный метод. В конце введения дан краткий обзор этих методов. Для каждой задачи обычно подбирается наиболее подходящий для неё метод либо создаётся новый, как это произошло с методом центрированных сечений (4).

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

При этом задачи линейного программирования в пространстве большой размерности (даже при п > 105) могут быть эффективно решены симплекс-методом или методом внутренней точки (см., например, [3],.

М).

Поэтому следующая идея будет вполне естественной: попытаться свести произвольную задачу выпуклого программирования (1) с некоторой погрешностью к задаче линейного программирования, которую затем можно точно и эффективно решить. Для этого необходимо приблизить выпуклые функции /о и fi кусочно-линейными. Геометрически это означает, что нужно приблизить их надграфики многогранниками. Главный вопрос — как построить приближающий многогранник для данного выпуклого тела. Задача приближения выпуклых тел многогранниками в метрике Хаусдорфа исследовалась в литературе ранее, например, в работах следующих авторов: М. Ludwig, С. Schutt, El. Werner, L. Chen, M. Lopez, S. Reisner, J. S. Muller, P. M. Gruber, R. Schneider, D. E. Mc-Clure, R. A. Vitale, В. Ю. Протасов, Г. К. Каменев (см. [7] - [19]). В частности, было доказано, что число граней приближающего многогранника асимптотически эквивалентно Сегде п — размерность, е — точность приближения, что очень велико при больших значениях п. Эта оценка неулучшаема уже для евклидова шара. Поэтому, если представлять многогранник в виде решения системы линейных неравенств от п + 1 переменной, то количество неравенств будет расти как еот точности приближения. Например, если s = 0.1, п = 41, то количество граней многогранника оценивается как СЮ20. При этом константа С зависит от формы приближаемого тела. Кроме того, задача нахождения такого многогранника алгоритмически сложная. Эффективные алгоритмы разработаны лишь при п = 2, для плоских тел (в этом случае идет речь о приближении многоугольником). В работах [Т]—[19] постановка задачи отличалась от рассматриваемой в диссертации, поскольку расстояние между выпуклыми телами измерялось в метрике Хаусдорфа, а не в равномерной метрике.

Диссертация состоит из двух глав. В первой главе предлагается метод приближённого решения задач выпуклого программирования, основанный на аппроксимации целевой функции и функций ограничений кусочно-линейными. Таким образом задача выпуклого программирования сводится к задаче минимизации линейного функционала на выпуклом многограннике. Для осуществления подобной аппроксимации надграфик выпуклой функции приближается не многогранником той же размерности, а проекцией многогранника большей размерности. Это осуществляется с помощью добавления новых переменных. В работе представлены алгоритмы построения приближающих многогранников для некоторых классов функций одной переменной, получены оценки размерностей этих многогранников и числа их граней. Затем при помощи индуктивной процедуры данный алгоритм обобщён на функции многих переменных. Также рассмотрен другой подход: когда сначала решается задача приближения надграфика выпуклой функции одной переменной многоугольником, а затем многомерная задача при помощи индукции сводится к решённой одномерной (при этом размерность приближающего многогранника увеличивается в процессе индуктивного перехода). Во второй главе диссертации методы поиска минимума функции на многограннике будут использованы для решения дискретной задачи оценки хроматического числа пространства М". Нумерация теорем во введении соответствует нумерации в диссертации.

Кратко опишем структуру диссертации и основные результаты по главам. Диссертация состоит из двух глав. В первой главе разработаны алгоритмы линеаризации выпуклых экстремальных задач и доказаны оценки их сложности. Во второй главе существующие методы решения задач выпуклой оптимизации применяются для решения дискретной задачи получения нижних асимптотических оценок хроматических чисел пространства Мп.

1. JL В. Канторович. Математические методы организации и планирования производства. Л.: Изд-во ЛГУ, 1939.

2. Дж. Данциг. Линейное программирование, его применения и обобщения. М.: Прогресс, 1966.

3. S. Boyd, L. Vandenberghe. Convex Optimization. Cambridge Univ. Press, 2006.

4. Y. Nesterov, A. Nemirovsky. Interior Point Polynomial Methods in Convex Programming. SIAM, Philadelphia, PA, 1994.

5. Б. С. Половинкин, M. В. Балашов. Элементы выпуклого и сильно выпуклого анализа. М.: ФИЗМАТЛИТ, 2004. 416 с.

6. Е. Г. Голыптейн, А. С. Немировский, Ю. Е. Нестеров. Метод уровней, его обобщения и приложения. Экономика и мат. методы. 1995. Т.31. № 3, 164—180.

7. М. Ludwig, С. Schiitt, El. Werner. Approximation of the Euclidean ball by polytopes. Studia Math. 173 (2006), no. 1, 1−18.

8. L. Chen. New analysis of the sphere covering problems and optimal poly-tope approximation of convex bodies. J. Approx. Theory 133 (2005), no. 1, 134−145.

9. J. Bourgain, J. Lindenstrauss, V. Milman. Approximation of zonoids by zonotopes. Acta Math. 162 (1989), 73−141.

10. В. Ю. Протасов. Обобщённый совместный спектральный радиус. Геометрический подход. Изв. РАН. Сер. матем., 61:5 (1997), 99−136.

11. М. Lopez, S. Reisner. Hausdorff approximation of convex polygons. Com-put. Geom. 32 (2005), no. 2, 139−158.

12. P. M Gruber. Error of asymptotic formulae for volume approximation of convex bodies in Ed. Dedicated to Edmund Hlawka on the occasion of his 85th birthday. Monatsh. Math. 135 (2002), no. 4, 279−304.

13. C. Schiitt, El. Werner. Random polytopes with vertices on the boundary of a convex body. C. R. Acad. Sci. Paris Ser. I Math. 331 (2000), no. 9, 697−701.

14. J. S. Mtiller. Step by step approximation of plane convex bodies. Arch. Math. (Basel) 58 (1992), no. 6, 606−610.

15. R. Schneider. Polyhedral approximation of smooth convex bodies. J. Math. Anal. Appl. 128 (1987), no. 2, 470−474.

16. R. Schneider. Affine-invariant approximation by convex polytopes. Studia Sci. Math. Hungar. 21 (1986), no. 3−4, 401−408.

17. D. E. McClure, R. A. Vitale. Polygonal approximation of plane convex bodies. J. Math. Anal. Appl. 51 (1975), no. 2, 326−358.

18. Г. К. Каменев. Об эффективности хаусдорфовых алгоритмов полиэдральной аппроксимации выпуклых тел. Ж. вычисл. матем. и ма-тем. физ. 33:5 (1993), 796−805.

19. В. Ю. Протасов. Совместный спектральный радиус и инвариантные множества линейных операторов. Фундамент, и прикл. матем., 2:1(1996), 205−231.

20. А. А. Лигун, В. Ф. Сторчай, О наилучшем выборе узлов при приближении сплайнами в Ьр. Матем. заметки, 20 (1976), № 4, 611−618.

21. А. Д. Иоффе, В. М. Тихомиров. Теория экстремальных задач. М., Наука, 1974.

22. A. Ben-Tal, A. Nemirovski. On polyhedral approximations of the second order cone. Math. Oper. Res. 2001, 26. 193−205.

23. А. Ю. Левин. Об одном алгоритме минимизации выпуклых функций., Докл. АН СССР, 160:6 (1965), 1241−1243.

24. А. М. Райгородский. Проблема Борсука и хроматические числа метрических пространств. Успехи Матем. Наук, 56 (2001), № 1, 107 146.

25. А. М. Райгородский. Линейно-алгебраический метод в комбинаторике. Москва, МЦНМО, 2007.

26. А. Сойфер. Хроматическое число плоскости: его прошлое, настоящее и будущее. Матем. просвещение, Вып. 8, 2004.

27. А. М. Райгородский. О хроматическом числе пространства. Успехи Матем. Наук, 55 (2000), № 2, 147−148.

28. D. G. Larman and С. A. Rogers. The realization of distances within sets in Euclidean space. Mathematika, 19 (1972), 1−24.

29. И. M. Шитова. О хроматических числах метрических пространств с двумя запрещёнными расстояниями. Доклады РАН, 413 (2007), № 2, 178−180.

30. А. М. Райгородский, И. М. Шитова. О хроматических числах вещественных и рациональных пространств с несколькими вещественными или несколькими рациональными запрещёнными расстояниями. Матем. сборник, 199 (2008), № 4.

31. Н. Г. Мощевитин, А. М. Райгородский. О раскрасках пространства Мп с несколькими запрещёнными расстояниями. Матем. заметки, 81 (2007), № 5, 733−744.

32. N. G. de Bruijn and P. Erdos. A colour problem for infinite graphs and a problem in the theory of relations. Proc. Koninkl. Nederl. Acad. Wet., Ser. A, 54 (1951), № 5, 371−373.

33. H. Алон, Дж. Спенсер. Вероятностный метод. Бином: Лаборатория знаний, Москва, 2007.

34. Г. Г. Магарил-Ильяев, В. М. Тихомиров. Выпуклый анализ. М. Эди-ториал УРСС, 2000.

35. В. Ю. Протасов. К вопросу об алгоритмах приближённого вычисления минимума выпуклой функции по её значениям. Матем. заметки, 59 (1996), Ж, 95−102.

36. Е. Титчмарш. Теория функций. М. Наука, 1980.

37. J.-H. Kang, Z. Furedi. Distance graphs on Zn with? i-norm. Theoretical Сотр. Sci. 319 (2004), № 3, 357−366.

38. A. M. Райгородский. О хроматическом числе пространства с метрикой lq. Успехи матем. наук, 59 (2004), № 5, 161−162.

39. А. М. Райгородский. О хроматических числах метрических пространств. Чебышевский сборник, 5 (2004), № 1 (9), 175−185.

40. L. Moser, W. Moser. Solution to Problem 10. Can.Math. Bull., 4, (1961), 167−189.

41. H. Hadwiger, H. Debrunner. Ausgewahlte einzelprobleme der kombinator-ishen geometrie in der ebene. L’Enseignement Mathematique, 1, (1955), 56−89.Работы автора по теме диссертации.

42. Б. С. Горская. Об одном алгоритме линеаризации выпуклых экстремальных задач. Математический сборник, вып. 201 (2010), № 4, 3−24.

43. Е. С. Горская. Приближение выпуклых функций проекциями многогранников. Вестн. Моск. ун-та. Сер. 1 Матем. Мех. 2010, № 5.

44. Е. С. Горская. Об одном алгоритме линеаризации выпуклых экстремальных задач. Материалы Восьмой международной научной школы-конференции «Лобачевские чтения-2009», Казань, Казанское математическое общество, 2009, 177−179.

45. Е. С. Горская. Применение выпуклых многогранников в решении выпуклых экстремальных задач. Материалы международной научной конференции «Современные проблемы математики, механики, информатики», Тула, ТулГУ, 2009, 30−31.