ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2008, том 48, < 3, с. 397-417
УДК 519.658
ТЕОРИЯ ДВОЙСТВЕННОСТИ ОПТИМАЛЬНЫХ АДАПТИВНЫХ МЕТОДОВ ПОЛИЭДРАЛЬНОЙ АППРОКСИМАЦИИ ВЫПУКЛЫХ ТЕЛ1
© 2008 г. Г. К. Каменев
(119333 Москва, ул. Вавилова, 40, ВЦ РАН) e-mail: kamenev@ccas.ru Поступила в редакцию 02.07.2007 г.
Предлагается аппарат теории двойственного описания итерационных методов полиэдральной аппроксимации выпуклых тел. Рассматриваются различные типы задач аппроксимации, требующие применения теории двойственности. Предложенная теория позволяет конструировать методы аппроксимации тел с двойственным описанием (опорная/дистанционная функции), а также методы, оптимальные с точки зрения двойственных характеристик сложности аппроксимирующих многогранников (вершины/грани). Сформулированы новые оптимальные методы на основе предложенной теории. Библ. 34.
Ключевые слова: выпуклое тело, аппроксимация многогранником, алгоритм, метод аппроксимации, оптимальные методы, оценка сложности, двойственность.
1. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЗАДАЧАХ ПОЛИЭДРАЛЬНОЙ
АППРОКСИМАЦИИ
Аппроксимация многогранниками является традиционным средством исследования выпуклых множеств (см. [1]). Долгое время интерес к задаче был в основном теоретическим (см. [2]). Вместе с тем задача аппроксимации выпуклых компактных тел многогранниками возникает во многих приложениях: в теории оптимального управления (см. [3]), математическом программировании, кодировании изображений и др. Важное практическое значение вычислительные методы полиэдральной аппроксимации (МПА) имеют в задачах принятия решений на основе использования математических моделей (см. [4]-[6]). Для решения этих задач получили развитие теория и практика использования адаптивных методов полиэдральной аппроксимации (АМПА). В частности, был разработан адаптивный итерационный метод "уточнения оценок" (см. историю его создания в [6]), который показал себя практически пригодным для аппроксимации выпуклых тел большой размерности. В рамках этих исследований был предложен в [7]-[9], теоретически обоснован в [7]-[16], экспериментально в [17]-[19] исследован и нашел практическое применение (см. [4]-[6]) класс хаусдорфовых (или Н-) методов полиэдральной аппроксимации, асимптотически оптимальных с точки зрения сложности описания аппроксимирующих многогранников.
Необходимость применения теории двойственности в задачах полиэдральной аппроксимации возникает в следующих случаях:
1) когда при наличии методов, основанных на описании аппроксимируемого тела через опорную (дистанционную) функцию, необходимо разработать МПА для тел с двойственным описанием через дистанционную (опорную) функцию;
2) когда при наличии методов с последовательно растущим числом вершин (гиперграней) необходимо разработать МПА многогранниками с двойственным описанием, т.е. с последовательно растущим числом гиперграней (вершин);
3) при необходимости разработки МПА, оптимальных по числу вычислений опорной и/или дистанционной функции аппроксимируемого тела.
В настоящей статье предлагается аппарат двойственного описания МПА, определенных с помощью схем восполнения и отсечения, затем устанавливается факт двойственности H- и Н1-по-
1)Работа выполнена при финансовой поддержке гранта Президента РФ по государственной поддержке ведущих научных школ (код проекта НШ-5379.2006.1), РФФИ (код проекта 07-01-00472), программы фундаментальных исследований РАН < 14 и программы фундаментальных исследований ОМН РАН < 3.
следовательностей восполнения и отсечения. Далее рассматриваются методы построения двойственных АМПА в задачах аппроксимации в различной постановке.
2. КЛАССЫ АДАПТИВНЫХ МЕТОДОВ ПОЛИЭДРАЛЬНОЙ АППРОКСИМАЦИИ
Рассмотрим евклидово пространство Ed со скалярным произведением (•, •), расстоянием р(-, ■), нормой ||-1| и лебеговой мерой ц. Пусть Br(z) обозначает замкнутый шар радиуса r с центром в z, Bd - единичный шар с центром в начале координат, Sd- 1 - сферу направлений, т.е. границу Bd, и пусть nd := ^(Bd). Для е, 0 < е, и X с E введем обозначения
[X]e := {x е Ed: p(x, X) < е}, (Х)е := {x е Ed: p(x, X) < е}.
Множество K с Ed называется конусом, если для любого x е K и X, 0 < X, справедливо включение
Xx е K. Множество C с Ed называется выпуклым, если (1 - X)x + Xy е C для всех x, y е C и 0 < X < 1.
Выпуклой оболочкой множества X с Ed называется множество convX, являющееся пересечением всех выпуклых множеств, содержащих X. Для двух выпуклых множеств C1 и C2 введем обозначение выпуклого множества
C1 + C2 := {z е Ed: z = x + y, x е C1, x е C2} (сумма по Минковскому). Для X е [R и выпуклого C пусть
XC := {z е Ed: z = Xx, x е C}. Для X > 0 введем внешнее параллельное множество
Cx := C + BX(0) = U Bx( x).
x е C
Ясно, что в нашем случае [C]X = CX, X > 0. Через proj(x, X) обозначим проекцию точки x на множество X, через card X - мощность множества X.
Обозначим через % класс выпуклых компактных множеств с непустой внутренностью, т.е. выпуклых компактных тел (ВКТ). Через dC обозначим границу тела C, через intC - множество его внутренних точек, через ffl(C) - его асферичность (минимальное отношение радиусов концентрических внешнего R(C) и внутреннего r(C) шаров) и через c(C) - его поверхностный объем.
Обозначим через %+ класс ВКТ с дважды непрерывно дифференцируемой границей и положительными главными кривизнами. Через rmin(C) и rmax(C) обозначим минимальный и, соответ-
2
ственно, максимальный радиусы кривизны dC, C е %+ .
Пусть ^ с %, - класс выпуклых телесных многогранников (выпуклых оболочек конечного множества точек, не лежащих в одной гиперплоскости). Для P е ^ через M'(P) обозначим множество его вершин, а через m\P) - число его вершин, через Mf(P) обозначим множество векторов единичных внешних нормалей к его гиперграням (граням максимальной размерности), а через mf(P) - число его гиперграней. Для C е % введем класс &'(C) внутренних многогранников,
вершины которых принадлежат dC (вписанных многогранников), и класс 9?c(C) внешних многогранников, гиперграни которых касаются dC (описанных многогранников). Определим также классы
^m (C) := { P е ^'(C): т( P) < m }, ^ (C) := { P е ^c( C): mf( P) < m }. Рассмотрим традиционную (см. [2]) для рассматриваемой задачи метрику Хаусдорфа
8(C1, C2) := max{sup{p(x, C2): x е C1}, sup{p(x, C1): x е C2}}. В дальнейшем, где это возможно, будем опускать индексные обозначения. Так, через ^m(C) будем обозначать (C) и &cm (C), через ^(C) будем обозначать ^m(C) для любых m > d + 1, че-
рез M(P), m(P) будем обозначать Mt(P), m'(P) для P е ^'(С) и Mf(P), mf(P) для P е ^c(C). Пусть также
8(С, ®m(C)) := inf{8(C, P): P е ^(С)}.
Пусть Eq := Е\{0}, ^o := {С с %: {0} е int С} - класс ВКТ, содержащих внутри себя начало координат, := n ^0(С) := п ^(С).
Для u е Eq введем обозначения опорной функции
g(u, С) := max{<u, x>: x е С},
опорного полупространства
L(u, С) := {x е Ed <u, x> < g(u, С)},
опорной гиперплоскости
l(u, С) := {x е Ed: <u, x> = g(u, С)},
множества точек касания
T(u, С) := {р е дС: <u, р> = g(u, С)} и конуса внешних единичных нормалей в граничной точке р е дС
S(p, С) := {u е Sd- ь <u, р> = g(u, С)}. Для произвольного р е Ed нам будет удобно использовать обозначения
g(u, р) := <u, р>, l(u, р) := {x е Ed: <u, x> = <u, р>},
L(u, р) := {x е Ed: <u, x> < <u, р>},
что, очевидно, не противоречит введенным ранее определениям опорных функции, гиперплоскости и полупространства.
Пусть С е и x е Ed, через
g*(x, С) := min{^ > 0: x е ^С}
обозначим дистанционную (калибровочную или Минковского) функцию для С. Из определения дистанционной функции следует (см. [20, замечание 11.1]), что
g*(x, С) = ||x||/||x01|,
где x0 = [o, x) п дС - точка пересечения луча, исходящего из начала координат и проходящего через x, и границы тела С. Эту точку x0 обозначим через
t(x, С) := x/g*(x, С) е дС, x е Eq .
Пусть ю0(С) - минимальное отношение радиусов внешнего R0(G) и внутреннего г0(С) шаров с центрами в начале координат. Ясно, что ю0(С) > ю(С).
Определим теперь общие аппроксимационные схемы - схему восполнения (см. [21], [17], [8]) и схему отсечения (см. [22], [8]).
СХЕМА ВОСПОЛНЕНИЯ
Пусть построен Pn е 9?1(С). Тогда (n + 1)-я итерация состоит из двух шагов.
Шаг 1. Выбираем рп е дС.
Шаг 2. Кладем Pn + 1 := еопу{рп, Pn}.
Конкретные методы, основанные на схеме восполнения, можно характеризовать способами решения двух задач: способом выбора рп е дС и способом построения Pn + 1 := сопу{рп, Pn} в требуемом виде.
СХЕМА ОТСЕЧЕНИЯ
Пусть построен Рп е 9с(С). Тогда (п + 1)-я итерация состоит из двух шагов. Шаг 1. Выбираем направление ип е - 1. Шаг 2. Кладется Рп + 1 := Рп п Ь(ип, С).
Конкретные МПА, основанные на схеме отсечения, можно характеризовать способами решения задач: способом выбора ип е - 1 и способом построения Рп + 1 := Рп п Цип, С) в требуемом виде.
Поскольку в схеме восполнения (отсечения) Рп е 9'(С) (Рп е 9с(С)), то Рп + 1 е 9'(С) (Рп + 1 е е 9с(С)). Если в некоторой реализации схемы восполнения (отсечения) многогранник начального приближения Р0 принадлежит 9 (С) (9с(С)), то и Рп е 9' (С) (Рп е 9 (С)) для любого п. В этом случае будем говорить, что последовательность многогранников {Рп}п = 0, 1, 2, ... является последовательностью восполнения (отсечения) для С или последовательностью многогранников, порождаемой данной схемой для тела С и многогранника начального приближения Р0 е 9(С).
Приведем теперь определения классов последовательностей вписанных и описанных многогранников, неявно характеризующих классы адаптивных методов полиэдральной аппроксимации (АМПА), порождающие их.
Определение 1. Последовательность многогранников {Рп}п = 1, 2, порождаемую для С е 9 и
Р0 е 9'(С) некоторой реализацией схемы восполнения, будем называть хаусдорфовой, или #(у, С)-последовательностью восполнения, если существует константа у > 0 такая, что для любого п = 0, 1, ... справедлива оценка
5(Рп, Рп + 1) > у5(Рп, С). (1)
Так как
5(Рп, Рп + 1) = р(рп, Рп),
то условие (1) может быть переформулировано в виде
Р(Рп, Рп) > у5(Рп, С).
Определение 2. Последовательность многогранников {Рп}п = 1, 2, пор
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.