Выпуклые задачи на многогранниках тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

084693145

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М. В. ЛОМОНОСОВА МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 519.853.3+ 514.177.2+ 519.157

Горская Елена Сергеевна

ВЫПУКЛЫЕ ЗАДАЧИ НА МНОГОГРАННИКАХ

Специальность 01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва, 2010 г.

" 3 ИЮН 2010

004603145

Работа выполнена на кафедре общих проблем управления Механико-математического факультета Московского Государственного Университета имени М. В. Ломоносова.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор Протасов Владимир Юрьевич

доктор физико-математических наук, профессор Осипенко Константин Юрьевич

кандидат физико-математических наук, Балашов Максим Викторович

Центральный экономико-математический институт РАН (ЦЭМИ РАН)

Защита диссертации состоится 4 июня 2010 г. в 16 часов 45 минут на заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М. В. Ломоносова по адресу: РФ, 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ имени М. В. Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета (Главное здание, 14 этаж).

Автореферат разослан 4 мая 2010 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ, доктор физико-математических наук, профессор

А. О. Иванов

Общая характеристика работы

Актуальность темы.

Диссертация посвящена изучению выпуклых экстремальных задач многих переменных и применению методов выпуклой минимизации к классическим задачам дискретной математики. Методы приближённого нахождения минимума выпуклой функции на выпуклом множестве активно разрабатывались, начиная с 40-х годов прошлого века. Интерес к таким задачам возник с рождением линейного программирования. Задача линейного программирования (ЛП) заключается в нахождении экстремума линейной функции на многограннике (задаваемом конечной системой линейных равенств и неравенств). Впервые нетривиальные задачи такого рода появились в исследованиях JI. В. Канторовича в 1939 г. и Дж. Данцига в 1947 г. Развитие линейного программирования, а затем и выпуклой оптимизации в более широком смысле, активно продолжилось в 60-х годах. При этом большое внимание уделялось задачам нелинейного выпуклого программирования, в которых либо минимизируемая функция, либо ограничения, либо и то и другое нелинейны. Этому посвящены работы многих известных математиков: Н. Кармаркара, С. Бойда, Б. Поляка, А. Немировского, Ю. Нестерова, JI. Хачияна и пр.

Термин «выпуклое программирование» появился в 1960-х годах. Можно сказать, что выпуклое программирование (ВП) — это набор методов и алгоритмов для приближённого численного решения задач вида:

fo{x) min, х = (х\,...,хп) G G,

при этом GcR" — выпуклое множество, заданное системой неравенств fi(x) ^ 0, г = 1,..., т, f{ — выпуклые (не обязательно дифференцируемые) функции (г = 0,..., тп). Нужно найти её решение с точностью е, то есть указать такую точку х* £ G, что \minxecfa{x) — /о(^*)| ^ £ (иногда речь идет не об абсолютной погрешности, а об относительной).

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

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

Подход, разрабатываемый в диссертации, основан на приближении надграфиков целевой функции и функций ограничений многогранниками (т.е., множествами, задаваемыми системой линейных неравенств), посредством чего задача выпуклого программирования сводится с некоторой погрешностью к задаче линейного программирования, которую затем можно точно и эффективно решить. Задача приближения выпуклых тел многогранниками в метрике Хаусдорфа исследовалась в литературе ранее, например, в работах следующих авторов: М. Ludwig, С. Schütt, El. Werner2, L. Chen3, M. Lopez, S. Reisner4, J. S. Müller5, P. M Gruber6, R. Schneider7, D. E. McClure, R. A. Vitale8, В. Ю. Протасов9, Г. К. Каменев10. Известно, что число граней приближающего многогранника асимптотически эквивалентно , где п — размерность, е — точность приближения. Эта оценка имеет экспоненциальный рост по размерности п и неулучшаема уже для евклидова шара. В диссертации разрабатывается метод, позволяющий для определённого класса выпуклых тел значительно уменьшить количество граней. Он основан на представлении

'S. Boyd, L. Vandenherghe. Convex Optimization. Cambridge Univ. Press, 2006.

2M. Ludwig, С. Schütt, El. Werner. Approximation of the Euclidean ball by polytopes. Studia Math. 173 (2006), no. 1, 1-18.

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

4M. Lopez, S. Reisner. Hausdorff approximation of convex polygons. Comput. Geom. 32 (2005), no. 2, 139-158.

5J. S. Müller. Step by step approximation of plane convex bodies. Arch. Math. (Basel) 58 (1992), no. 6, G06-610.

6P. 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.

7R. Schncider. Polyhedral approximation of smooth convex bodies. J. Math. Anal. Appl. 128 (1987), no. 2, 470-474.

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

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

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

многогранника в виде проекции другого многогранника более высокой размерности. Идея данного метода была предложена А. С. Немировским и А. Бен-Талем для квадратичных функций11. В диссертации эта идея распространяется на другие классы элементарных функций и на приближение в равномерной метрике.

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

Хроматическим числом х(Х, р, Л) метрического пространства X с метрикой р с множеством запрещённых расстояний А = {ai,..., {щ Е R, а,- > 0) называется величина, равная минимальному количеству цветов, в которые можно покрасить все точки пространства X так, что точки ж, у € X, такие, что р(х, у) S А, не будут одинаково окрашены. Эта проблема была поставлена Э. Нелсоном в 1950 г. для евклидовой плоскости и множества А, состоящего из одного запрещённого расстояния12. До сих пор неизвестно точное значение хроматического числа х в за~ даче Нелсона, а известны лишь оценки: 4 ^ х ^ 7. Для к запрещённых расстояний, следуя П. Эрдешу, рассматривают величину х(Х, р\ к) = = тах^.щ^ р, Л). В диссертации вычисляются нижние асимптотические оценки для к) и /1; к), т. е. вычисляются показатели Cfc и кк в неравенствах (Gt+o(l))n ^ x(Rn,/2; к) и (к* + о(1))п ^ x{Rn,h\ к). А. М. Райгородским и И. М. Митричевой были получены оценки при к = 3,4. Для этого ими был разработан метод, сводящий вычисление показателей 0t и к решению некоторых экстремальных задач13. В диссертации показано, что эти задачи можно свести к семействам выпуклых экстремальных задач на переменной области определения (на поверхности многогранника, зависящего от некоторого параметра), для которых удалось разработать эффективный метод решения. Это позволило улуч-

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

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

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

шить существующие оценки для ^ и при Л; =3,4 и вычислить показатели ^ при к = 5,..., 20 и Кк при к = 5,..., 30.

Цель работы.

Цель диссертации — построение эффективных методов линеаризации выпуклых экстремальных задач, оценка сложности полученных алгоритмов, применение методов выпуклой минимизации к задаче оценки хроматических чисел дистанционных графов и метрических пространств.

Научная новизна.

Результаты диссертации являются новыми и состоят в следующем:

1) Разработаны алгоритмы, сводящие некоторые классы выпуклых экстремальных задач к задачам минимизации линейных функционалов на выпуклых многогранниках и получены оценки их сложности.

2) Охарактеризованы наилучшие приближения выпуклых функций одной переменной кусочно-линейными, получены точные оценки на число узлов.

3) Разработаны методы приближения надграфиков выпуклых функций в равномерной метрике проекциями многогранников большей размерности и получены оценки их сложности.

4) Разработана техника решения специального класса задач выпуклой многомерной минимизации, применённая для получения асимптотических нижних оценок хроматических чисел конечномерного пространства с евклидовой метрикой и с метрикой ¿1 с несколькими запрещёнными расстояниями.

Методы исследования.

В работе применяются методы вариационного исчисления, теории приближений, теории функций, выпуклого анализа, методы выпуклой многомерной минимизации, линейно-алгебраический метод в комбинаторике.

Теоретическая и практическая ценность.

Работа носит теоретический характер. Результаты диссертации могут найти применение при решении выпуклых экстремальных задач большой размерности, при исследовании задач об аппроксимации многомерных выпуклых функций, при изучении задач о хроматических числах дистанционных графов и метрических пространств.

Апробация результатов.

Результаты диссертации докладывались автором на следующих научных семинарах и конференциях:

• Конференция «Ломоносовские чтения» (Москва, 2008 г.)

• Международная научная конференция «Современные проблемы математики, механики и информатики» (Тула, 2009 г.)

• Восьмая международная Казанская научная школа-конференция (Казань, 2009 г.)

• Международная конференция «Оптимизация и аппроксимация» по-свящённая 75-летию проф. В. М. Тихомирова (Москва, 2009 г.)

• Семинар лаборатории численных методов и оптимизации ЦЭМИ п/р проф. Е. Г. Голынтейна (2010 г.)

• Семинар по теории приближения и теории экстремума п/р проф. В. М. Тихомирова в МГУ (2010 г.)

• Семинар по теории функций и экстремальным задачам п/р проф. А. В. Арутюнова в РУДН (2010 г.)

• Семинар «Линейно-алгебраические и вероятностные методы в комбинаторике» п/р доц. А. М. Райгородского в МГУ (2008 г.)

Публикации.

Основные результаты диссертации опубликованы в 6 работах автора. Список этих работ приведён в конце автореферата [1-6].

Структура диссертации.

Диссертация состоит из введения, двух глав и списка литературы из 47 наименований. Общий объём диссертации составляет 110 страниц.

Содержание работы

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

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

Пусть С К", С2 С М*, бз С К' — многогранники, проекции которых приближают надграфики выпуклых функций /1(2), /2(2;) и д(х) на отрезках [а; 6], [а; 6], [01561], с точностями е\, £2, £з> соответственно. Кроме того, пусть [/1(0)5/1(6)] £ [01561] ид — неубывающая. Пусть также с 6 К, с > 0.

Теорема 1. Существуют многогранники

1) Су С Ш.п+к~2, проекция которого приближает надграфик }{х) = = тах{/1(а;), /2(2;)} с точностью е = тах-^ьег} на [а;6];

2) С2 С проекция которого приближает надграфик /(х) = = }\{х) + /2(я) с точностью е = Е\ + £2 на [а; 6];

3) С3 С Кп+г_1, проекция которого приближает надграфик д{/(х)) с точностью е = £1 • |<7'(б1)| + £3 на [а; 6];

4) С4 С К", проекция которого приближает надграфик /1 с точностью £1 на [са;с6];

5) С5 С К", проекция которого приближает надграфик с точно-

с

стью — на [а; 6];

с

При этом количество неравенств, задающих каждый многогранник, не превосходит его удвоенной размерности.

Пусть а 6 К, а > О, Ь € К, Ь > е, т £ N. Тогда

Теорема 2. Существуют многогранники

1) С К.^1, проекция которого приближает надграфик f(x) = х1™ с точностью е на [0;а], при этом

т2 т2т , т , 1

М<Т+21^1па+2Ь21Пв;

2) ¿2 С К^2, проекция которого приближает надграфик /(х) = ех с точностью е на [0; 1], при этом

N2 < ^ 1п2 - + ^ 1п - + 10; 4 £ 2 £

3) Оз С К.^2, проекция которого приближает надграфик /(х) = — 1па; с точностью е на отрезке [0; 1];

4) 64 С К^3, проекция которого приближает надграфик /(х) = —,

р > 1 с точностью £ на

1

при этом

N3 < ^ 1п2 - 4- Сх 1п - + Сг,

2 £ £

где С1 = 31п|- + 2р2 + 13р+ 11, С2 = 13^1п^ + 5(1п2р)2 + 30.

При этом количество неравенств, задающих каждый многогранник, не превосходит его удвоенной размерности.

Далее показано, как для некоторых классов функций многих переменных задачу приближения проекцией многогранника большей размерности можно свести к одномерной задаче. Такое возможно, например, если рассматриваемая функция раскладывается в сумму выпуклых функций

одной переменной, или же когда она представима в виде композиции выпуклой функции одной переменной и выпуклой функции многих переменных, для которых соответствующая задача уже решена.

Разработан метод эффективного решения нелинейных выпуклых задач, приведены численные примеры (в том числе пример А. Ю. Левина о минимизации суммы экспонент).

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

\ß

емых функций.

Предложен алгоритм приближения графика вогнутой функции / кусочно-линейной функцией }£ и доказана его оптимальность по количеству узлов N(fe) ломаной (/ рассматривается на отрезке [0; ¿>], полагаем, что

Д0) = 0).

Теорема 3. Для любой кусочно-линейной функции f£(x), такой, что

|| f£(x) - /(х)||с[0;Ч < е

имеем N{}£) > N(JE).

Из теории сплайн-апроксимации (теорема Лигуна-Сторчая14) следует, что количество шагов этого алгоритма оценивается сверху как Однако, вычисление интеграла f0 \J—f"(x) dx может быть технически сложным для многих функций, кроме того, он может расходиться или не существовать (в случае негладкой функции). Для того, чтобы обойти это затруднение, в работе формулируется и решается соответствующая задача оптимального управления, в результате чего мы находим точную константу в оценке и экстремаль, на которой она

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

достигается. Пусть а = р — корень уравнения ар!пр = р2 — 2р +

¡{Щ

\ — 1пр, если + 1 + ар — а в случае, когда а ф 2 и 7(а) = < р -1

I \/2, если а = 2. Нумерация теорем соответствует нумерации в диссертации.

Теорема 5. Для любой вогнутой функции / общее количество узлов ломаной /£, порождённой алгоритмом, не превосходит

у/е 4\/2 С — абсолютная константа.

Таким образом, для любого значения а можно, предварительно численно решив соответствующее уравнение, вычислить ./(а). Для того, чтобы получить представление о том, насколько велико значение ./(а) для произвольной функции (без численного решения уравнения) мы находим более простую функцию С (а), такую, что •/(«) ^ С {а) для всех

Г 2\Лпа, если а > 2, допустимых значении а. При этом б(а) = < _

[ у/2, если 1 < а < 2

Соответствующее утверждение доказано в теореме 6 диссертации.

Таким образом получаем, что при данной функции /(х) и е —> 0 оценка на количество узлов асимптотически не лучше, чем

А^™, где С0={

2"т(/(6))1, если1^Яб<2,

/'(о) .Л® „„„./'(0)

2~* /{Ь)[пГ-^-Ь

если ,.,. Ь > 2.

т ч ' т

Также в работе показано, как можно свести задачу приближения над-графика выпуклой функции многих переменных проекцией многогранника большей размерности к одномерной задаче линеаризации. Например, такое возможно в случае, когда рассматриваемая функция есть симметричная функция координат, или когда она раскладывается в прямую сумму выпуклых функций одной переменной. Приведены алгоритмы и

оценки их сложности для некоторых многомерных функций, среди которых, например, функция энтропии и ¿р-нормы. В частности, установлен следующий результат о приближении единичного шара пространства R" в метрике Lp: {(ггь..., ип) G К", НР ^ 1}.

Теорема 7. Единичный шар Ьр-нормы приближается с точностью е проекцией многогранника

G' = {и = (uh ...,ип,х 1,..., x2n-i) G К3"-1: |«j| ^ xi:

г = 1,..., п] х £ G; х ^ 0}

заданного не более чем

г 1

. Ш / П\ 8 „ ^,3 1

С(р)-д{ In-J +2п + Сп*£4

неравенствами, где С(р) — константа, зависящая от р.

Аналогичные результаты доказаны для функций энтропии и логарифма от суммы экспонент. Рассмотрены численные примеры.

Во второй главе диссертации методы выпуклой минимизации применяются для нахождения нижних асимптотических оценок хроматических чисел пространства К" с метрикой (обычная евклидова метрика) и пространства R" с метрикой

Из работы А. М. Райгородского и И. М. Митричевой15 следует, что задача вычисления нижних асимптотических оценок хроматических чисел x(№n,h',k) и 1ь к) сводится к решению следующих экстремальных

задач:

1) метрика

х(Шп,12;к) ^ (maxes^ + 0(l))\

где

Sd,k = max ( min f(s) - f{v) . (1)

veA ys£^,(s,b)^h[v) J

10 A. M. Райгородский, И. M. Шитова. О хроматических числах вещественных и рациональных пространств с несколькими вещественными или несколькими рациональными запрещенными расстояниями. Матем. сборник, 199 (2008), Л"«4.

2) метрика l\:

x(RVi;*) ^ (maxe5« + o(l))",

где5Й=тах{5^,5^}и

S'dk = max (plnp+(l-p)ln(l-p)-/(«)-pln(d-l)), (2)

veA ,P<Q

= max (In d+ /(«)). (3)

иеД .p^t1

При этом /(x) = In — функция энтропии (acinar,- = 0 при

Xi = 0), Д = {x S Md: x ^ 0, (x, e) = 1} — единичный симплекс, e = (1,..., 1), b = (0,1,... ,d — l), (x,y) — стандартное скалярное произведение, h(v) — некоторая специальная функция (различная для различных метрик).

То есть, для нахождения оценок в каждой метрике, нужно при каждом d решить экстремальную задачу поиска величин S^* и S^l, а затем максимизировать результат по d. Значение целевой функции в задаче (1) несложно вычисляется при любом v € Д, поскольку минимум берётся от выпуклой функции /(s) на многограннике (пересечении симплекса Д с гиперплоскостью {s G Rd | (s, b) ^ Поэтому минимум вычи-

сляется явно методом множителей Лагранжа. Если бы целевая функция была вогнутой по v, то её максимум Sd.k эффективно вычислялся бы по её значениям. Однако, вогнутой она не является, и может иметь много локальных максимумов. Для таких функций поиск глобального максимума всегда представляет значительные трудности. Все существующие алгоритмы имеют малую эффективность и фактически сводятся к разумному перебору значений функции по узлам некоторой сетки на симплексе Д, с периодическим уменьшением шага сетки. С ростом d время, требуемое на перебор, резко увеличивается, делая невозможным получение точных оценок уже при к = 5. Аналогичные трудности возникают при решении задач (2) и (3).

1) Метрика 1ч. В диссертации показано, что задачу (1) можно свести к семейству экстремальных задач, гладко зависящих от параметра р:

Sdt = max ( min f(s) - min f(v) I ,

0<p^r{d,k) \seA,(s,b)=p юеД,Л(ю)=(/Ы-1)р /

где r(d,k) = minj^-^, ^—To есть, нам нужно найти максимум по

всем р £ [0, r(d, &)] от разности минимумов строго выпуклой функции / на двух множествах. Первое множество — гиперплоскость, минимум на ней ищется явно с помощью правила множителей Лагранжа. Второе — поверхность, задающаяся в Rd уравнением h(v) = (k + i)p. В диссертации показано, что функция h(v) вогнута и кусочно-линейна, следовательно, это поверхность многогранника (также получены в явном виде уравнения, задающие его грани и доказано, что их количество не превосходит Таким образом, мы приходим к задаче поиска минимума выпуклой функции на границе многогранника в Rd, заданного системой линейных неравенств.

В диссертации предложен подход к данной задаче, основанный на следующем простом факте:

Если абсолютный минимум выпуклой функции <р принадлежит внутренности intG выпуклого многогранника G, то минимум iр на его границе 8G равен минимуму этой функции на объединении гиперплоскостей, ограничивающих G.

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

Теорема 10. Для любых d и к выполнено равенство

Sdk = max max [ min f(s) — min f(v) ) i=l,...,2d~l 0<p^r{d,k) \s€A,(s,b)=p ибД,(и,а<)=(*+1)р )

При этом минимум на каждой грани ищется явно. Тогда справедлива следующая теорема

Sd'k = i=r^ (/(W) -/(М.о),

где для каждого i и р через А обозначен единственный положительный корень полинома Рь{г) = 5Zj=oO" — P)z*> а через ц — единственный положительный корень полинома Pa'(z) = (a'j ~ (k + l)p)za'.

Для поиска внутреннего максимума дифференцируем полученное аналитическое выражение по р и приходим к системе уравнений от р, А и /л (соответствующие вычисления проделаны в диссертации).

Данный алгоритм был реализован на компьютере при d sC 20. Для каждого к = 2,..., 20 были найдены наибольшие из величин S^k при d = 2,..., 20. Полученные значения (к при к = 5,..., 20 являются новыми и неулучшаемыми в рамках данного метода, а при к = 3,4 улучшают существующие оценки.

2) Метрика 1\. Аналогичный подход позволил решить задачу нахождения оценок для х(М", 1\\ к). При этом было доказано, что задача по поиску величины S^l = max{Sjk, сводится к семейству экстремальных выпуклых задач с параметром р:

Sdl = Sdk = max

g(p) - min f(v)

v<=A,h(v)=2{k+l)p

где

ri(d, к) =

d и •

если d четно,

4(fc + 1) d2- 1

если d нечётно,

4d{k + lY

и r(d, к) = min {^i, ri(d, /с)}

При этом для каждого значения р нам необходимо найти минимум выпуклой функции / на множестве {г> € A,h(v) = 2(к + 1)р} (функция h(v) соответствует метрике Ii). Доказано, что в этом случае h(v) также является вогнутой и кусочно-линейной, т. е. минимум выпуклой функции ищется на поверхности выпуклого многогранника. Применив подход, использованный для метрики ¿2, получим

S^l = max max [ д(р) - min f(v) a'K J=0,...,d-1 0<p<r(d,it) V «еД,(а',»)=4>

Решая выпуклую задачу для каждой грани, получим Теорема 13. Для любых d и к выполнено равенство

где для каждого j up через ß обозначен единственный положительный корень полинома Pai(z) = Ylt^o (ai ~ При этом V = p(k + 1) — d +

+ 1 +j.

Дифференцируя полученное аналитическое выражение по р, приходим к системе уравнений с неизвестными р и ß. Описанный алгоритм реализован численно: для каждого к = 1,... ,30 мы нашли наибольшее значение величины S^l при всех d — 2,...,40. Найденные константы Кк при к = 5,..., 30 являются новыми и неулучшаемыми в рамках данного метода, а при к = 3,4 улучшают существующие оценки.

Автор выражает глубокую признательность научному руководителю д.ф.-м.н., профессору В. Ю. Протасову за постановку задач и постоянное внимание к работе.

Автор благодарен д.ф.-м.н., профессору В. М. Тихомирову, д.ф.-м.н., профессору О. М. Касим-Заде, д.ф.-м.н., профессору А. Б. Угольнико-ву, д.ф.-м.н., доценту А. М. Райгородскому, к.ф.-м.н. А. С. Кочурову за обсуждение работы. Автор благодарит сотрудников кафедры общих проблем управления за неизменно доброжелательную атмосферу.

Работы автора по теме диссертации

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

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

3. Горская Е. С., Митричева И. М., Протасов В. Ю., Райгородский А. М., Оценка хроматических чисел евклидова пространства методами выпуклой минимизации, Математический сборник, вып. 200 (2009), №6, С. 3-22.

(В этой работе Е. С. Горской принадлежит решение выпуклой экстремальной задачи и окончательные численные результаты.)

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

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

6. Gorskaya Е. S., Mitricheva I. М., Protasov V. J., Raigorodskii А. М., A solution to an extremum problem concerning the chromatic numbers of spaces with several forbidden distances, Abstracts of «Fete of Combinatorics and Computer Science» (Keszthely, Hungary, 2008), P. 110.

(В этой работе E. С. Горской принадлежит решение выпуклой экстремальной задачи и окончательные численные результаты.)

Подписано в печать 30,04.10 Формат 60x88 1/16. Объем 1 п.л. Тираж 100 экз. Заказ № 952 Отпечатано в ООО «Соцветие красок» 119991 г.Москва, Ленинские горы, д.1 Главное здание МГУ, к. А-102

Введение

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. Оценка хроматических чисел Кп в евклидовой метрике ¿2 •

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)

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. Müller, 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, 107146.

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. Ausgewählte einzelprobleme der kombinator-ishen geometrie in der ebene. L'Enseignement Mathématique, 1, (1955), 56-89.Работы автора по теме диссертации

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

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

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

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