Содержание к диссертации
Введение
1. Линеаризация выпуклых экстремальных задач 36
1.1. Многомерная аппроксимация 36
1.1.1. Приближение сумм и композиций 37
1.1.2. Приближение элементарных функций 41
1.1.3. Приближение функций многих переменных 50
1.2. Индуктивная аппроксимация 53
1.2.1. Линеаризация функций одной переменной 54
1.2.2. Линеаризация функций многих переменных 73
1.2.3. Численные примеры 80
2. Оценка хроматических чисел пространства III.п методами выпуклой минимизации 82
2.1. Оценка хроматических чисел Шп в евклидовой метрике 82
2.1.1. Решение экстремальной задачи 83
2.1.2. Алгоритм для реализации метода 90
2.1.3. Численные результаты 94
2.1.4. Некоторые обобщения 95
2.2. Оценка хроматических чисел III.п в метрике 97
2.2.1. Решение экстремальной задачи 97
2.2.2. Численные результаты 103
Список литературы 105
- Приближение функций многих переменных
- Численные примеры
- Алгоритм для реализации метода
- Оценка хроматических чисел III.п в метрике
Введение к работе
Темой диссертации является изучение выпуклых экстремальных задач и их применение к задачам дискретной математики. В первой главе диссертации разработан метод, позволяющий сводить многие выпуклые экстремальные задачи к задаче поиска минимума линейного функционала на многограннике, заданном системой неравенств. При этом под многогранником понимается любая многогранная область, заданная линейными неравенствами (возможно, неограниченная). Во второй главе диссертации существующие методы решения выпуклых экстремальных задач будут применены к решению задачи комбинаторной геометрии по нахождению нижних асимптотических оценок хроматических чисел пространства Rn. Изучаемая область тесно связана с теорией алгоритмов, сложностью алгоритмов, выпуклым анализом.
В сороковые годы прошлого века произошёл всплеск интереса к выпуклым задачам. Он прежде всего был вызван рождением линейного программирования. Задача линейного программирования (ЛП) заключается в нахождении экстремума линейной функции на многограннике (задаваемом конечной системой линейных равенств и неравенств). Впервые нетривиальные задачи такого рода появились в исследованиях Л. В. Канторовича в 1939 г. [1] и Дж. Данцига в 1947 г. [2]. Развитие линейного программирования, а затем и выпуклой оптимизации в более широком смысле, началось в США в конце Второй мировой войны. Это было вызвано как проблемами экономики, так и вопросами, которые ставились военно-промышленным комплексом.
Стремительному развитию линейного программирования способствовали как математики (Л. В. Канторович, Д. фон Нейман, Дж. Данциг), так и экономисты (В. Леонтьев, Т. Купманс). В 1947 году Дж. Данциг предложил метод направленного перебора смежных вершин многогранника в направлении возрастания целевой функции — симплекс-метод, ставший основным при решении задач ЛП. Ему же принадлежит первая фундаментальная монография по линейному программированию [2].
Одновременно с развитием ЛП большое внимание уделялось задачам нелинейного выпуклого программирования, в которых либо минимизируемая функция, либо функции ограничения, либо и то и другое нелинейны. Термин выпуклое программирование появился в 1960-х годах. Можно сказать, что выпуклое программирование — это набор методов и алгоритмов для приближённого численного решения выпуклых задач. Общая задача ВП ставится так: /о (х) -> ram, (1) X == \Xi: . . . , Xjij fc: ijr, при этом GcM" — выпуклое множество, заданное системой неравенств fi (х) ^ 0, г = 1,..., m, fi — выпуклые (не обязательно дифференцируемые) функции (г = 0,... ,га). Нужно найти её решение с точностью є, т. е. указать такую точку х* Є G, что \mmfQ(x) - f0(x*)\ <г (иногда речь идет не об абсолютной погрешности, а об относительной).
Для приближённого решения выпуклых задач разработано достаточно много методов, при этом многие из них разработаны для конкретных классов функций: симплекс-метод, метод центрированных сечений и его модификации, метод эллипсоидов, метод внутренней точки, метод уровней, градиентный метод. В конце введения дан краткий обзор этих методов. Для каждой задачи обычно подбирается наиболее подходящий для неё метод либо создаётся новый, как это произошло с методом центрированных сечений (4).
Особенные трудности вызывают задачи ВП, в которых число переменных п велико. В этом случае возникают сложности со сходимостью алгоритмов для произвольных выпуклых задач. Метод эллипсоидов для некоторых задач работает медленно и плохо сходится уже при п = 20. Кроме того, он требует на каждом шаге хранить и переопределять огромную матрицу. Метод центрированных сечений требует вычисления центров тяжестей выпуклых тел, что даже для многогранников является NP-сложной задачей. Метод внутренней точки полностью разработан лишь для некоторого класса задач (в частности, для задач линейного и квадратичного программирования).
При этом задачи линейного программирования в пространстве большой размерности (даже при п > 105) могут быть эффективно решены симплекс-методом или методом внутренней точки (см., например, [3],
Поэтому следующая идея будет вполне естественной: попытаться свести произвольную задачу выпуклого программирования (1) с некоторой погрешностью к задаче линейного программирования, которую затем можно точно и эффективно решить. Для этого необходимо приблизить выпуклые функции /о и fi кусочно-линейными. Геометрически это означает, что нужно приблизить их надграфики многогранниками. Главный вопрос — как построить приближающий многогранник для данного выпуклого тела. Задача приближения выпуклых тел многогранниками в метрике Хаусдорфа исследовалась в литературе ранее, например, в работах следующих авторов: М. Ludwig, С. Schiitt, 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 переменной, то количество неравенств будет расти как є-^ от точности приближения. Например, если є — 0.1, п = 41, то количество граней многогранника оценивается как СЮ20. При этом константа С зависит от формы приближаемого тела. Кроме того, задача нахождения такого многогранника алгоритмически сложная. Эффективные алгоритмы разработаны лишь при п = 2, для плоских тел (в этом случае идет речь о приближении многоугольником). В работах [7]-[19] постановка задачи отличалась от рассматриваемой в диссертации, поскольку расстояние между выпуклыми телами измерялось в метрике Хаусдорфа, а не в равномерной метрике.
Диссертация состоит из двух глав. В первой главе предлагается метод приближённого решения задач выпуклого программирования, основанный на аппроксимации целевой функции и функций ограничений кусочно-линейными. Таким образом задача выпуклого программирования сводится к задаче минимизации линейного функционала на выпуклом многограннике. Для осуществления подобной аппроксимации надграфик выпуклой функции приближается не многогранником той же размерности, а проекцией многогранника большей размерности. Это осуществляется с помощью добавления новых переменных. В работе представлены алгоритмы построения приближающих многогранников для некоторых классов функций одной переменной, получены оценки размерностей этих многогранников и числа их граней. Затем при помощи индуктивной процедуры данный алгоритм обобщён на функции многих переменных. Также рассмотрен другой подход: когда сначала решается задача приближения надграфика выпуклой функции одной переменной многоугольником, а затем многомерная задача при помощи индукции сводится к решённой одномерной (при этом размерность приближающего многогранника увеличивается в процессе индуктивного перехода). Во второй главе диссертации методы поиска минимума функции на многограннике будут использованы для решения дискретной задачи оценки хроматического числа пространства Rn. Нумерация теорем во введении соответствует нумерации в диссертации.
Кратко опишем структуру диссертации и основные результаты по главам. Диссертация состоит из двух глав. В первой главе разработаны алгоритмы линеаризации выпуклых экстремальных задач и доказаны оценки их сложности. Во второй главе существующие методы решения задач выпуклой оптимизации применяются для решения дискретной задачи получения нижних асимптотических оценок хроматических чисел пространства Ш.п.
Приближение функций многих переменных
В этом параграфе мы рассмотрим задачу приближения надграфика выпуклых функций многих переменных проекцией многогранника большей размерности, а также покажем, как при помощи такого подхода можно эффективно решать нелинейные задачи минимизации. В предыдущих параграфах были приведены алгоритмы построения приближающих многогранников для некоторых элементарных функций одной переменной. В некоторых случаях задачу приближения надграфика выпуклой функции многих переменных можно свести к одномерной. Например, когда рассматриваемая функция раскладывается в прямую сумму выпуклых функций одной переменной, когда она представима в виде суммы выпуклых функций многих переменных, для каждой из которых соответствующая задача решена, или же когда она представима в виде композиции функции одной переменной и функции многих переменных, которые мы можем приблизить проекцией многогранника. Напомним, что в этом параграфе приближающий многогранник G С С Шк, к п для функции /: Rn — R проецируется на подпространство (XI , . . . , Жп, Х} ). Пусть f(xi,..., хп): М.п — R представима в виде суммы двух выпуклых функций многих переменных, для которых соответствующая задача уже решена: f(x\,..., хп) = f\(x\,..., хп) + h{x\, 5хп). При этом многогранники G\ С ЖМі (А\х 61) и Gi С R- 2 (Л2Х 5 62) приближают надграфики /і и /2 на выпуклом множестве V С Rn снизу с точностью Єї и "2 соответственно. Рассмотрим многогранник G С R 1 +ЛГ2-п+і за_ даваемый системой неравенств
Предложение 7. Проекция G приближает надграфик f(x\,..., хп) снизу на множестве V2 — V х У с точностью є = Єї + Є2 Доказательство. 1) Для любой точки (х\,... ,XN1+N2 n+i) Є G верно, ЧТО XNl+No-n+i XN, + XNl+N2-n /l( l, , Хп) -Єі + /2(жі, . . . , Хп) -Є2 = = J \%1 5 5 %П) Є 2) Для любой точки (хі,...:хп,у) Є epif(xi,...,хп) существует прообраз из G. Действительно, пусть у f(xi,...,xn) = fi(xi,...,xn) -f-+ /2( 1, ,%п), тогда можно представить у в виде суммы у = у\ + У2, так, что у\ /i(a?i,..., хп) и у2 /2( 1,..., хп). По условию, существуют набор х = {xn+i,..., ж -і) такой, что А\(х\,..., жП5 я, у\) 6i и набор г = (a;jv1+i,... ,rcjv1+iv2-n-i), такой, что А2(хъ ... ,xn,z,y2) 62- Следовательно, (жь ..., жп, ж, 2/1, г, 2/2,2/) Є G. П Приведём два следствия из этого предложения. Пусть f(xi,... ,хп): W1 —» R представима в виде суммы m выпуклых функций многих переменных, для которых соответствующая задача уже решена: f(xi,..., хп) = ХШі ЖЖЪ жп)- При этом многогранники Gi С МЯі (А ж bi) приближают надграфики fi на выпуклом множестве V С Шп .снизу с точностью ЄІ соответственно (г = 1,..., т). Рассмотрим многогранник G С Ni+-+Nm-{m-\)n+i задаваемый системой неравенств Следствие 3. Проекция G приближает надграфик f{x\,... ,xn) снизу на множестве Vn с точностью є = YHLii Пусть выпуклая функция /: Rn — R представима в виде суммы выпуклых функций одной переменной: / — Y =i fi(xi) Кроме того, пусть многогранники G( С M.Ni приближают надграфики /І(ХІ) на отрезке [а; Ь] снизу с точностью ЄІ, г = 1,...,п. Рассмотрим многогранник G" С +...+ +1 задаваемый системой Следствие 4. Проекция G" приближает надграфик /(жі,... ,#„) снизу на множестве V = [а; 6]п с точностью є = Х)Г=іе # Сформулируем также предложение, позволяющее приближать композицию функции многих переменных и функции одной переменной, для которых задача уже решена. Пусть f(x1:...,xn) : [a;b]n -+ [a ;b ] и g(x) : [aijfcj -» [g(ai)\ g(b{)] — выпуклые функции, д — неубывающая функция и E(f) С D(g). Пусть проекция многогранника G\ сШк (к п, А\х Ь\) приближает надгра-фик f(xi,..., жп) снизу с точностью Єї, проекция многогранника G С М.т (А2Х 62) приближает надграфик д{х) снизу с точностью Єї-
Рассмотрим многогранник G С Rm+fc, задаваемый системой неравенств: Ai(xh...,xk) Ъъ A2(Xk, . . . , Xk+m) &2, Предложение 8. Проекция G приближает надграфик g{f(x\,..., хп)) снизу на множестве [а; Ь]п с точностью є = Є\ sup . j g (:c)l + 2 = = Єї \g (bi)\ +Є2- (g (x) — субдифференциал функции g в точке х.) Доказательство. Обозначим Щ = (жі, ...,ж„), тогда доказательство практически дословно совпадает с доказательством предложения 5, где хі заменяется на Щ, хп на ж&, а хт на Хк+т П Пример 4. Построим многогранник, проекция которого приближает надграфик f(xi,..., жп) = YllLi Ci bi,x\ Ч 0, с точностью є. В этом случае /(ж) = Хльі/г(ж)- При этом каждую из выпуклых функций fi(x) = СІЄ(ЬІ,Х можно приблизить проекцией многогранника Gi С Шкі с точностью є . Пусть п = 40, 6 - 1, сг- 1 (г = 1,... , га, j = 1,..., п). Приблизим надграфик /(я) проекцией многогранника (7 с RN на множестве У = {( ъ ---5 ж4о): \х1 + + ж4о 1}- Из результатов параграфа 1.1.2 и сформулированных выше утверждений следует, что тогда кі ln2 + 71n + 40. Следовательно, размерность N = кі + ... + кт — 40(га — 1) + 1, а точность приближения є = ХХ=і єі В качестве примера того, как можно свести нелинейную задачу выпуклого программирования (1) к задаче линейного программирования, рассмотрим задачу (4) для п = 40. Пусть многогранники Gi С M.Ni (А{Х di) приближают надграфики функций fi на множестве V С Ш40 с точностью є. Тогда задачу (4) можно свести к следующей задаче линейного программирования в пространстве размерности N = NQ + ... + Nk — пк:
Численные примеры
В качестве приложения рассмотрим задачу вычисления расстояния в Lp-норме от точки до многогранника, т. е., задачу вида: Пример 8. Рассмотрим сначала тривиальный пример, выбрав в качестве G единичный симплекс, т. е. множество а в качестве точки а — начало координат. В этом случае ответ вычисляется явно при помощи правила множителей Лагранжа: искомый минимум достигается в точке х = (-,...,-) и равен п р . Приблизив при помощи алгоритма, изложенного в параграфе (1.2.2) надграфик функции Ьр-нормы проекцией многогранника с точностью є, сведём задачу (1.10) к задаче линейного программирования: Пример 9. Для второго примера выберем в качестве а начало координат, а в качестве G рассмотрим множество Далее мы будем использовать следующие обозначения: е = (і,..., і) Є Є M.d, с = -е = (-,...,-), b = (0,1,..., d — і). Через (я, у) обозначим d d d ч стандартное скалярное произведение в M.d с евклидовой метрикой, через Д = [х Є Rd\x 0, (х, е) = 1} — единичный симплекс в M.d. Для данного Л 0 полагаем [Л] = (1, А,..., А -1) Є JRd. Если а = = (ао,..., а -1) — вектор с целыми неотрицательными координатами, то [А]а = „а-\ .в- ( V А"1 -1). Таким образом, [А]а Є А для любого а. В частности, [А]ь = [А], [1] = с. Далее, f(x) = Х)І=О ХІ ПХІ — функция энтропии, при этом полагаем ХІІПХІ = 0 при Х{ = 0. Функция / строго выпукла, поэтому на любом выпуклом компакте она имеет единственную точку минимума. Минимум / на симплексе Д достигается в точке с. Также обозначим h(x) = М(х) — т(х), где х Є А, М(х) и т(х) — функции, определённые во введении. Напомним, что для получения нижних асимптотических оценок на величины х{ Пі fa i к) нам необходимо при каждом d решить экстремальную задачу поиска величины Sd,k: а затем максимизировать результат по d. Тогда Докажем сначала вспомогательный факт о расположении точек минимума энтропийной функции f(v). Лемма 4. Если выпуклый компакт G С А содержит хотя бы одну внутреннюю точку симплекса А, то точка минимума функции f на G также является внутренней точкой А. Доказательство.
Пусть точка х Є G принадлежит внутренности А. Предположим, что минимум функции / на G достигается в некоторой точке z Є 5Д. Не ограничивая общности, считаем, что Z{ — 0 при г = 0,..., q и Zi 0 при г = # + 1,..., d — 1. Частные производные fVi = lnv{ + 1 при г = 0,..., q обращаются в —оо в точке v = z. Производная функции / по направлению вектора х — z равна Y2jZoixi — zi)fvr Поскольку Xi — Zi 0 при і = О,..., q, эта производная также обращается в — оо в точке z. Следовательно, в точках v Є [z, ж], достаточно близких к точке z имеем f(v) f(z): что противоречит предположению. Теперь найдём точку, в которой достигается внутренний минимум в задаче (2.1). Лемма 5. Для любого р минимум функции энтропии f на мно жестве {s Є A(s,b) р} достигается в точке с, а для любого р Є Є (О, ] — в точке [А], где А — единственный положительный корень d-l. полинома Pb{z) = Ylj=oU P)z3 Доказательство. Так как (с,Ь) = , то при р точка с при надлежит упомянутому множеству, а значит минимум / достигается в ней. При р минимум должен достигаться на границе данного множества, причем, в силу леммы 4, не на границе симплекса А. Следовательно, точка минимума лежит в плоскости (s, b) = р. В этой точке выполняется необходимое условие минимума: Cs = 0, где С = f(s) + + Ai((s,b) — р) + Аг((з, е) — 1) — лагранжиан. Таким образом, lnsn + + 1 + Ain + Аг = 0 при п = 0,..., d — 1. Следовательно, sn = СХп, n = 0,..., d — 1, где Л и С — некоторые константы. Из условия (s, е) = 1 получаем С = (5 7=0 ) откуда s = [А], а из условия (s,b) = р получаем, что Л — корень полинома Pb(z). Этот полином не может иметь второго положительного корня Л, в противном случае точка [Л] также будет решением уравнения Cs = 0, а значит, в силу теоремы Каруша-Куна-Таккера [34], также будет давать минимум функции / на множестве s Є А, (s, Ь) = р. Это невозможно в силу строгой выпуклости /. Теперь приступаем к задаче (2.1) по нахождению величины Sd,k-
Для каждого г; Є А с помощью леммы 5 можно вычислить значение целе вой функции. Основная сложность, как уже упоминалось во введении, состоит в том, что эта функция, вообще говоря, не является вогну той, и может иметь много точек локального максимума. Поэтому на хождение её максимума на симплексе А с точностью, например, 0.01, может оказаться неразрешимой на практике задачей уже при d = 5. Для выхода из этой ситуации нам придётся использовать некоторые специальные свойства данной функции. Ключевым является следующее предложение 10, которое превращает задачу (2.1) в семейство выпуклых экстремальных задач, гладко зависящих от параметра р. Для форму лировки результата нам понадобится величина r(d,k), равная миниму му чисел (с, Ь) и Л(с). Заметим, что (с, Ь) = Ef=o Далее, к +1 J d 2 "j и но , о rn(m + l)(2m + l) пользуясь известной формулой 1 + + т = , получаем б i=u d %) = Ей Т - EtJ J- zA = 71 Таким Правом,
Алгоритм для реализации метода
В этом параграфее мы реализуем разработанный метод алгоритмически. Согласно теореме 11, для нахождения величины Sd,k нужно найти максимум правой части равенства (2.8) по всем р Є (0, r(d, к)] и по всем плоскостям {г; Є Д(г;,аг) = (к + 1)р} для г = 1..., 2d_1. Мы разобьём эту задачу на две части: 1) поиск внутреннего максимума в (2.9) по всем р Є (0, r(d, к)] при каждом ц 2) перечисление всех граней и соответствующих векторов а\ г = 1, od-l . } Начнём с первой задачи. Дифференцируя равенства YljZoU Р) — О и j=o(a5 -( + 1)р)ма = 0? получаем: При любом г = 1,..., 2d_1 для нахождения точки р, в которой достигается максимум функции /([А]) — /([/- ] о0 дифференцируем по р: Вычисляя производные функций /([А]) и /([/і]0 )з а затем подставляя и — из (2.10), получим уравнение для нахождения р. dp Более подробно, поскольку /([A]) = Yl srd-l М ІП W-1 w = TO При каждом г = 1,..., 2d_1 возникает, таким образом, своя система уравнений. Это система из трёх уравнений с тремя неизвестными. Решая её численно с помощью компьютера, находим оптимальные параметры р, А и ц для каждого г. Для решения задачи нам нужно перебрать 2 i-i Гранеи многогранника, для каждой грани найти соответствующее р и значение /([А]) — /([д]аі), затем выбрать среди полученных значений наибольшее. Теперь приступим к решению второй задачи: для данного d получить уравнения всех 2d x граней. Для этого запишем m(v) в виде Уравнение каждой грани рассматриваемого многогранника получается при каждом реализуемом способе раскрытии скобок в выражении для т. Запишем слагаемые из этого выражения в виде таблицы: В n-ой строке записаны следующие слагаемые: 2(1 — 2VQ — v\ — v2 —... — -vn_i)+, 2(l-2«o-2ui-«2 «n-i)+, (l-2uo-2vi-2v2 2г;п_і) + . Поскольку г;г- 0, то если какое-либо слагаемое положительно, то положительны и слагаемые, записанные слева и сверху от него. Теперь рассмотрим сетку размера N (см. рис. 12, на боковой стороне расположены N узлов), в каждом узле которой записан 0 или 1. Назовем расстановку нулей и единиц «правильной», если выполняется следующее условие: если в каком-то узле записана 1, то и во всех узлах, в которые можно из него попасть, двигаясь влево и вверх, также записана 1. Заметим, что каждой «правильной» расстановке нулей и единиц в сетке размера d — 1 соответствует грань многогранника и наоборот. Таким образом, для заданного d достаточно перечислить все «правильные» расстановки. Предположим, что мы умеем решать задачу для всех г = 1, ..., N. Покажем, как её решить для N + 1.
Рассмотрим сетку размера Л +1 и обозначим числа, стоящие в узлах нижней строки как 6i, ..., bjv+і- Тогда искомое количество «правильных» расстановок равно Ylj=o - -h гДе Л? — количество «правильных» расстановок при условии, что bi = 1 для і = 1, ...,;и6( = 0 для г = j -f-1, ..., N + 1. Заметим также, что если bi = 1 для і = 1, ..., j: то во всех узлах над ними также записаны единицы, а в узлах, расположенных над bi (г = j+1, ..., iV + 1) может находиться любой «правильный» набор нулей и единиц меньшего размера, чем iV, который мы уже умеем искать. Таким образом, для того, чтобы решить задачу для сетки размера N + 1 нам надо рассмотреть последовательно случаи: 1) hi = О, і — 1, ..., N -j- 1, используем решение задачи для таблицы размера JV; 2) Ь\ = 1, bi = 0, г = 2,..., JV+1. Тогда в первом столбце записаны только единицы, а для того, чтобы найти количество «правильных» расстановок в оставшейся части таблицы используем решение задачи для таблицы размера N — 1; j) bi = 1 для г = 1, ..., j и bi — 0 для г = j + 1, ..., N +1. Тогда в первых j столбцах записаны только единицы, а для того, чтобы найти количество «правильных» расстановок в оставшейся части таблицы используем решение задачи для таблицы размера N — j; N) b{ = 1 для г = 1, ..., N и Ьдг+і = 0. N-f 1) bi = 1 для і = 1, ..., iV + 1, то есть, в таблице записаны одни единицы. ной и той же схеме. Используя алгоритм, изложенный в параграфе 2.1.2, перебираем 2d_1 векторов аг, для каждого вектора численно решаем систему уравнений (2.11), находим значения АИ/І, после чего находим Sd,k как максимальное из чисел /([А]) — /([//]о ) п0 всем г = 1,..., 2d_1. Данный алгоритм может быть реализован на компьютере при небольших значениях d, например, при d 20. Результаты вычислений соберём в следующей таблице. Для каждого к = 2,..., 20 мы нашли величины Sd,k при всех d = 2,..., 20 и записали в таблицу наибольшее из этих чисел. Как показали вычисления, при каждом к функция Sd,k возрастает по d, и максимум по всем d = 2,..., 20 достигается при d — 20. Соответственно, в таблицу занесены только значения при d = 20. С другой стороны, рост Sd,k при d, близких к 20, незначителен и практически стабилизируется. Это позволяет надеяться, что при данных к указанные значения S2o,k и Cfc близки к оптимальным. В таблице выписаны значения параметров р, при которых достигается максимум в (2.9), а также соответствующие параметры точек минимумов Лид при данных р.
Оценка хроматических чисел III.п в метрике
Напомним, что для вычисления показателей / (к Є N) нам необходимо найти Sd,k = max{S$fc, 5J, где To есть, при каждом d нам необходимо найти решение экстремальных задач (2.1) и (2.2), выбрать среди них наибольшее и затем максимизировать полученный результат по d. Далее мы покажем, что max S k = 0, а maxd Sfk 0, то есть, Sd,k = «S и нам достаточно решить экстремальную задачу (2.1). Разберемся с этими двумя случаями последовательно. А) Нам необходимо найти решение экстремальной задачи (2.1). Рассматриваемая функция не является вогнутой, поэтому изначально представляется возможным только способ решения, связанный с перебором значений функции по узлам некоторой сетки на симплексе А, с периодическим уменьшением шага сетки. Однако, с ростом размерности d, время, требуемое на такой перебор, резко увеличивается, что делает невозможным получение точных оценок уже при к = 5. Поэтому используем подход, разработанный в первой части этой главы. Представим задачу (2.1) в виде семейства задач, зависящих от параметра р и покажем, что тогда её решение сводится к поиску минимума выпуклой функции на поверхности некоторого многогранника. Обозначим д(р) = рЫр + (1 — р) 1п(1 — р) — pln(d — 1). Тогда задачу (2.1) можно рассматривать как семейство экстремальных задач с параметром р: При этом для каждого р мы будем искать минимум функции f(v) на множестве точек симплекса, которые соответствуют этому р, то есть на множестве {v Є A, h(v) = 2(к + 1)р}. Докажем, что это множество есть поверхность выпуклого многогранника. Для этого достаточно показать, что h(v) — вогнутая кусочно-линейная функция.
Предложение 13. Функция h(v) — вогнутая на симплексе А, а неравенство h(v) q при любом q равносильно системе из d линейных неравенств (aJ, v) + Р q, j = 1,..., d с целыми неотрицательными векторами а7, не зависящими от q {при этом V — некоторая константа). Доказательство. Положим и ф = Y jZo j- Таким образом, ip(x) = mm{j 0 х Y2i=ovi} — кусочно-постоянная, неубывающая, непрерывная справа функция, принимающая целые значения от 0 до d — 1. Тогда Обозначим через (x)+ — max{0,a;}. Тогда h{v) = 2[m(v) — 2п(г )], где Второе выражение представляет собой сумму d—1 слагаемого, каждое из которых есть неотрицательная часть линейной функции, следовательно, является выпуклой функцией. Таким образом, h(v) есть разность линейной функции и выпуклой функции, то есть h(v) — вогнута. Для любого q 0 неравенство h(г ) q равносильно системе из 2d l линейных неравенств (a?,v) + Р q, соответствующих всевозможным способам раскрытия максимумов в d—1 слагаемом в сумме (2.4). Каждое ИЗ ЭТИХ Неравенств Имеет Целые КОЭффИЦИеНТЫ (при ПеремеННЫХ Vj), поскольку в каждом слагаемом коэффициенты равны ±1. Покажем, что в действительности количество неравенств в системе не превосходит d, т.е., существует не более d способов раскрытия максимумов в сумме (2.4), все остальные случаи не реализуются. Действительно, если для некоторого к слагаемое (— VQ — ... — г & J равно нулю, то все слагаемые с большими значениями к также равны нулю. Назовем последнее ненулевое слагаемое крайним. Тогда каждый способ раскрытия максимумов однозначно определяется своим крайним слагаемым. Поскольку каждое слагаемое может быть крайним, а также крайних слагаемых может совсем не быть, то количество способов раскрытия максимумов в сумме равно (d — 1) + 1 = d. Замечание 14.
Несложно показать, что уравнение, задающую j-ую грань (j = О,..., d — 1) имеет вид (a?, v) — Р, где a? = 2(j — i)-\-l-\-i — d при г = О,..., d — 2 и aj_: = 0, а # = р(к + l) — d + l + j. Таким образом, множество G = {v Є A, h(v) 2(/г + 1)р} есть вы пуклый многогранник, лежащий в симплексе. Центр симплекса с при надлежит внутренности этого многогранника при таких значениях па раметра р, для которых верно неравенство h(с) 2 (к + 1)р. Несложно показать, что при чётных значениях d это неравенство равносильно та кому: р , а при нечётных: р . Обозначим
