автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Теория оптимальных адаптивных методов полиэдральной аппроксимации выпуклых компактных тел и ее применение в задачах принятия решений

На правах рукописи

КАМЕНЕВ Георгий Кириллович

г у о и .......

ТЕОРИЯ ОПТИМАЛЬНЫХ АДАПТИВНЫХ МЕТОДОВ ПОЛИЭДРАЛЬНОЙ АППРОКСИМАЦИИ ВЫПУКЛЫХ КОМПАКТНЫХ ТЕЛ И ЕЕ ПРИМЕНЕНИЕ В ЗАДАЧАХ ПРИНЯТИЯ РЕШЕНИЙ

Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ

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

Москва - 2004

Работа выполнена в Вычислительном Центре . А.А. Дородницына РАН

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

доктор физико-математических наук, член-корр. РАН, профессор

доктор физико-математических наук, профессор

доктор технических наук

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

Институт проблем механики РАН

Павловский Юрий Николаевич

Половинкин Евгений Сергеевич Пропой Анатолий Иванович

Защита диссертации состоится " _" _2005 г. в_ч.

на заседании диссертационного совета Д002.017.04 при Вычислительном центре им А.А. Дородницына РАН по адресу: 119991, Москва ГСП-1, ул. Вавилова, 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан "_" "_" 2004 г.

Ученый секретарь ✓

диссертационного совета Д002.017.04, доктор физико-математических наук

Новикова Н. М.

2.006-4

iU 493*4

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Аппроксимация многогранниками является традиционным средством теории выпуклых множеств. Первые аппроксимаци-онные теоремы восходят к Минковскому. В частности, Минковским было доказано, что для каждого выпуклого компактного тела можно найти сходящуюся последовательность выпуклых полиэдров, аппроксимирующих это тело. Эти утверждения широко использовались для получения результатов, связанных с геометрией выпуклых поверхностей. Однако долгое время интерес к задаче был сугубо теоретическим. На важность практической аппроксимации выпуклых тел многогранниками возможно впервые указал Л.С.Понтрягин в связи с проблемой построения множеств достижимости динамических систем. В настоящее время задача аппроксимации выпуклых компактных тел (ВКТ) многогранниками возникает во многих приложениях: в математическом программировании, кодировании изображений и др.

Важное практическое значение вычислительные алгоритмы полиэдральной аппроксимации выпуклых компактных тел имеют в задачах принятия решений на основе использования математических моделей в методе обобщенных множеств достижимости (ОМД), разрабатываемого в ВЦ РАН начиная с 70-х годов группой исследователей под руководством A.B. Лото-ва. В этом подходе вместо изучения отдельных вариантов решения осуществляется сжатие (агрегирование) информации о всех допустимых вариантах. Агрегирование состоит в построении в явном виде множества всех таких значений показателей качества решения, которые могут быть достигнуты в модели как результат допустимых вариантов решений (управлений). Построенное в явном виде множество достижимых значений показателей - обобщенное множество достижимости - может быть использовано для конструирования различных методов анализа моделей и принятия решений на их основе. В выпуклом случае для построения такого описания необходимо разработать эффективные методы полиэдральной аппроксимации выпуклых тел.

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

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

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

Цель работы. Целью работы является:

1) Разработка теории оптимальных адаптивных методов полиэдральной аппроксимации выпуклых компактных тел. В рамках этой теории:

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

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

2) Разработка методики проверки в численных экспериментах эффективности адаптивных методов при достижимых на практике точностях аппроксимации.

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

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

Научная новизна. Результаты диссертации, полученные автором, являются новыми. Основные из этих результатов следующие:

1. Создана теория оптимальных адаптивных методов полиэдральной аппроксимации выпуклых компактных тел. Введены классы адаптивных методов полиэдральной аппроксимации, основанные на адаптивных схемах восполнения и отсечения. Введено понятие Я-методов отсечения и восполнения и исследованы их свойства. Введено понятие более узкого класса Яг методов отсечения и восполнения с более сильными свойствами. [2], [3], [5], [13], [18]

2. Для Я- и Я!-методов получены верхние оценки скорости сходимости, исследована их эффективность. Доказана оптимальность по порядку числа вершин (методы восполнения) и числа гиперграней (методы отсечения) для гладких (Я-методы) и произвольных (Я)-методы) тел. В гладком случае доказана независимость эффективности Я,-методов восполнения от свойств аппроксимируемых тел (совместно с Р.В.Ефремовым). [3], [5], [7], [13], [18], [16], [17], [26]

3. На основе теории оптимальных адаптивных методов полиэдральной аппроксимации изучены существующие алгоритмы и предложены новые. В частности, для существующего и активно используемого в приложениях метода «Уточнения Оценок» доказана принадлежность к классу оптимальных Я,-методов восполнения, изучена его скорость сходимости и эффективность. [2], [5], [8], [13].

4. Предложен метод «Сближающихся Многогранников», использующий одновременно схему восполнения и схему отсечения. Для этого метода получены оценки скорости сходимости и доказана в гладком случае оптимальность по порядку числа вершин внешнего и гиперграней внутреннего аппроксимирующих многогранников, а также по порядку числа вычислений опорной функции аппроксимируемого тела. [10]

5. Развита теория построения и исследования оптимальных адаптивных методов аппроксимации для тел, заданных своей дистанционной (калибровочной) функцией. Введено понятие двойственных классов адаптивных методов полиэдральной аппроксимации. Доказано, что Я- (Я,-) методы восполнения и отсечения являются двойственными классами. Для известных методов сформулированы двойственные аналоги. [18]

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

7. Получена новая верхняя оценка аппроксимационного числа негладких выпуклых дисков. [15]

8. Разработаны теоретические основы методики экспериментального ис-

следования эффективности адаптивных методов полиэдральной аппроксимации в классе многомерных эллипсоидов. [2]

9. Осуществлено экспериментальное исследование эффективности методов в классах многомерных эллипсоидов (совместно с С.М. Джолдыбае-вой). [4], [6]

10. Разработана методика использования методов полиэдральной аппроксимации в многокритериальных задачах принятия решений, в частности при анализе эколого-экономических проблем (совместно с А.В.Лотовым, В.А.Бушенковым и О.Л.Черных). [1], [14], [11], [12], [23], [24], [25], [28], [29]

11. С помощью оптимальных адаптивных методов полиэдральной аппроксимации исследована сложная эколого-экономическая модель сельскохозяйственного региона (совместно с А.В.Лотовым и ван Вальсумом). [11], [22]

12. Предложена методика анализа многомерной задачи выбора на основе визуализации паретовой границы выпуклой оболочки критериальных точек (совместно с В.А.Бушенковым, Д.И.Гусевым, А.В.Лотовым, и О.Л.Черных). [9], [14], [28], [29]

Практическая ценность. В работе исследованы существующие и разработаны новые эффективные методы полиэдральной аппроксимации выпуклых тел. Проведено исследование этих методов в численных экспериментах. Разработана методика использования рассматриваемых методов в задачах принятия решений. С применением рассматриваемых методов исследована сложная эколого-экономическая система сельскохозяйственного региона (совместная работа с Международным институтом прикладного системного анализа (ИИСА)). Оптимальные адаптивные методы полиэдральной аппроксимации, рассмотренные в работе, были использованы также в системе поддержки поиска эффективных стратегий улучшения качества воды в крупных реках (в рамках Федеральной целевой программы «Возрождение Волги»).

Результаты, изложенные в настоящей работе, получены при финансовой поддержке РФФИ (коды проектов 95-01-00968, 98-01-00323, 01-0100530, 04-01-00662), по программе поддержки ведущих научных школ (коды проектов 00-15-96118, НШ-1843.2003.1), при поддержке программы №3 фундаментальных исследований ОМН РАН «Вычислительные и информационные проблемы решения больших задач» и программы фундаментальных исследований РАН «Математическое моделирование и интеллектуальные системы».

Апробация. Результаты, нашедшие отражение в диссертации, докладывались на следующих совещаниях, конференциях и семинарах: на Всесоюзной конференции «Теория, методология и практика системных

исследований» (Москва, 1985), на конференции «Математические методы управления и обработки информации» (Москва, 1985), на семинаре «Многокритериальные задачи математического программирования» Всесоюзного научно-исследовательского института системных исследования (Москва, 1985), на методологическом семинаре «Методы имитационного моделирования экономических объектов» Центрального экономико-математического института АН СССР (Москва, 1985), на заседаниях школы-семинара ИВЕРСИ-85 «Системные и прикладные аспекты диалога на персональных ЭВМ» (Тбилиси, 1985), на IX Всесоюзном симпозиуме «Системы программного обеспечения решения задач оптимального планирования» (Москва, 1986), на конференции молодых ученых Вычислительного центра АН СССР (Москва, 1988), на Советско-финском симпозиуме "Information technology and economic modeling" (Хельсинки, Финляндия 1992), на международной конференции «Konvexgeometrie» (Обервольфах, ФРГ 1997), на 2-й Московской международной конференции по исследованию операций (Москва, 1998), на научной сессии «Проблемы прикладной математики и информатики» Вычислительного центра РАН (Москва, 2000), на 3-й Московской международной конференции по исследованию операций (Москва, 2001), на научной конференции «Математика, Механика и Информатика 2002», поев. 10-летию РФФИ (Москва, 2002), на научной конференции «Математические модели сложных систем и междисциплинарные исследования», поев. 85-летию академика Н.Н.Моисеева (Москва, 2002), на 58-й Конференции Европейской рабочей группы «Поддержка многокритериального принятия решений» (Москва, 2003), на международной конференции «Математическое моделирование социальной и экономической динамики» (Москва, 2004), на 4-й Московской международной конференции по исследованию операций (Москва, 2004) и на ряде семинаров МГУ (Механико-математический факультет: семинарах кафедр математического анализа, теории чисел и дискретной математики; факультет Вычислительной математики и кибернетики: семинар кафедры оптимального управления), института Проблем механики РАН, Московского физико-технического института, Вычислительного центра РАН им. А.А. Дородницына.

Публикации. Основные результаты диссертации опубликованы в 29 работах, из них четыре книги: [11] в соавторстве с А.В. Лотовым, В.А. Бу-шенковым и O.JI. Черных; [14] главы 1-5 в соавторстве с А.В.Лотовым и В.А. Бушенковым, гл. 8 - самостоятельно; [28] в соавторстве с А.В. Лотовым и В.А. Бушенковым; [29] главы 1-6 в соавторстве с А.В. Лотовым и В.А. Бушенковым, гл. 8 - самостоятельно.

Структура и объем работы. Диссертация состоит из предисловия, введения, шести глав, заключения, списка литературы из 160 наименова-

ний, 17 таблиц и 71 рисунка. Текст диссертации без списка литературы, таблиц и рисунков составляет 361 страницу машинописного текста, общий объем - 420 страниц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении дан обзор существующих теории и методов полиэдральной аппроксимации выпуклых компактных тел.

В § 0.1 дан обзор существующей теории оптимальной полиэдральной аппроксимации выпуклых компактных тел. Центральным понятием теории оптимальной полиэдральной аппроксимации ВКТ является понятие многогранника наилучшей аппроксимации (МНА), на котором достигается наибольшая точность приближения для определенной метрики в заданном классе аппроксимирующих многогранников (например, вписанных с ограниченным числом вершин или описанных с ограниченным числом гиперграней). В параграфе приводятся известные оценки зависимости наилучшей достижимой точности от сложности описания аппроксимируемого многогранника (зависимости отклонения от числа вершин или гиперграней многогранника наилучшей аппроксимации). Оказывается, что, согласно существующей теории, для произвольного выпуклого компактного тела верхняя оценка точности обратно пропорциональна числу вершин (гиперграней) в степени 2/(г/-1), где d - размерность пространства. При этом для широкого класса тел, включающего в себя тела с частично гладкой границей, эта оценка неулучшаема.

Рассматривается евклидово пространство Е1' со скалярным произведением <■,•>, расстоянием р(-,-), нормой ||-|| и Лебеговой мерой /л. Пусть B/z) обозначает замкнутый шар радиуса г с центром в г, и 2Г обозначает единичный шар с центром в начале координат, - сферу направлений, т.е. границу Bf, и пусть nd :=

Обозначим через Т класс выпуклых компактных множеств с непустой внутренностью, т.е. выпуклых компактных тел. В случае d= 2 говорят также о выпуклых дисках. Через дС обозначим границу тела С, через int С -множество его внутренних точек, через а(С) - его асферичность (минимальное отношение радиусов концентрических внешнего R{C) и внутреннего г{С) шаров) и через о(С) - его поверхностный объем. Обозначим через класс ВКТ с ^ раз непрерывно дифференцируемой границей, и пусть -класс ВКТ с s раз непрерывно дифференцируемой границей и положительными главными кривизнами, s > 2. Для s>2 через rmin(C) и rmsx(C) обозначим минимальный и, соответственно, максимальный радиусы кривизны дС, Се ¥'5. Пусть ,у> с - класс выпуклых телесных многогранников. Для Ре.f через М'(Р) обозначим множество его вершин, а через т'(Р) - число

его вершин, через Л/(Р) обозначим множество векторов единичных внешних нормалей к его гиперграням (граней максимальной размерности), а через п/(Р) - число его гиперграней. Для CeV введем класс :У'(С) внутренних многогранников, вершины которых принадлежат дС (вписанных многогранников), и класс -fc(C) внешних многогранников, гиперграни которых касаются дС (описанных многогранников). Определим также классы &JLQ := {Ре Sf'(C)\ т'(Р) < т], ./'„(С) := {Ре а»с(С): п/(Р) < т).

Рассмотрим традиционные для рассматриваемой задачи метрики на 4P. метрику Хаусдорфа (метрику Бляшке)

<^(Ci,C2) := шах {sup{p(x, С2): хеС,}, sup{p(jt, С,): хеС2}} и метрику объема симметрической разности (Никодимову метрику)

где С,АС2 := (С,\С2)и(С2\С,) .

В дальнейшем, где это возможно, будем опускать индексные обозначения. Так, через 8 будем обозначать <5" и через ,fm(C) будем обозначать 3>т(С) и äfcm(C), через ¿f{C) будем обозначать .Ут(С) для любых т > d+\, через М(Р), т(Р) будем обозначать Л/(Р), т'(Р) для Ре./(С) и U(P), п/(Р) для Ре2Рс(С). Обозначим также

:tm(C)) := inf {S(C, Р): Ре .?т(С)}.

Пусть Ео1' := ЕЛ{0}, Гп:={СсК: {0} е int С} - класс ВКТ, содержащих внутри себя начало координат,:= 'fi^rxf, .У0(О := .У>0гл./'(С).

Для и е E0d введем обозначения опорной функции g(u, С) := шах {<м, х>: хеС}, опорного полупространства ¿(и, С) := {хеЕ**: <и, х> < g(u, С)}, опорной гиперплоскости l(u,C) := {хе¥?\ <и, х> = g(u, С)}, множества точек касания

1\u,Q := {редС: <u,p> = g(u, Q} и множества внешних единичных нормалей в граничной точке редС S(p,C) := {ueS^1: <u,p> = g(u, С)}.

Пусть Се % ихеЕ^, через

g*(x, C):=min {Л>0:хеЯС} обозначим дистанционную (Минковского или калибровочную) функцию для С. Из определения дистанционной функции следует, что g*(x, 0=1МИ1*о||» где х0=[о, х)пдС - точка пересечения луча, исходящего из начала координат и проходящего через х, и границы тела С. Эту точку х0 обозначим через

t(x, О x/g*(x, О е дС, xeR0d-

Пусть ®ь(0 есть минимальное отношение радиусов R0(C) внешнего и г0(О внутреннего шаров с центрами в начале координат.

Пусть задано некоторое Cef. Классическим результатом теории выпуклых множеств является тот факт, что для метрики S(т.е. ¿F и в классе -fm(C) (т.е. Ут{С) и :fcm(C)) найдется многогранник Пт, не обязательно единственный, на котором достигается <5(С,Ут(С)). Этот многогранник называется многогранником наилучшей аппроксимации: ¿(С, Пт) = <5(С, äfm{C)). Даже для двумерных тел задача нахождения МНА чрезвычайно сложна (за исключением простейших специальных случаев). Вместе с тем МНА могут служить эталоном полиэдральной аппроксимации ВКТ.

Приведем, прежде всего, верхние оценки скорости сходимости МНА (Dudley 1974; Бронштейн и Иванов 1975):

const c4Ji

¿(С, •/„)<-

/и2'«'-"

Нижние оценки скорости сходимости МНА рассмотрим сначала для достаточно гладких тел. Пусть рассматривается метрика rf1. Тогда для Ce'f1 справедливо (Fejes Töth 1948; Schneider 1981, 1987; Gruber 1993; Böröczky 2000):

\2/(<i-l)

1

Л

lim S" (С, )mm =7 — L*r W"2 da(x)

где 9i есть плотность покрытия пространства Е' шарами фиксированного радиуса, nd := л^2/Г((с//2)+1) - объем единичного шара, к<Ах) - кривизна Гаусса-Кронекера (произведение главных кривизн) в точке хедС и е>(*) -элемент поверхностного объема в точке х. Заметим, что точно известны

только величины i9i=l и

■?2= 2л / л/27 .

Рассмотрим метрику <f, и пусть CeW2. Тогда (Gruber 1988, 1991, 1993; Böröczky 2000) существуют константы deld_| и divd.t (триангуляционные числа Делоне и Дирихле, соответственно), зависящие только от d, такие что

lim ¿4(С,^.)«2*М) = — del^,(f kc(x)4d+]) d*(x)Y+Md

m-n» 2

lim ös(C,ycm)mll(d (x)^daix))"^.

m-> od 2

При этом точно известны только значения delj=l/6, del2=l/(2V3), divi=l/12, div2=5/(18V3).

Таким образом, степень 2!(d-1) в оценках скорости сходимости для Cg Ii2 неулучшаема.

В § 0.2 приводится аппарат, используемый в диссертации для описания сходимости многогранников к выпуклым телам со скоростью, по порядку большей 2/(d-1).

Для характеристики аппроксимационных свойств негладких тел введем следующие понятия. Пусть СеК Пусть s>0. Обозначим

а (С) := lim inf mis" (С, J>m )?, 7 (С) := lim sup ml5" (С, J>m )f.

Для характеристики нижней границы скорости сходимости МНА вводится (Schneider, Wieacker 1981) величина

а(С) := inf{s > 0 :а\С) = 0}, которая названа аппроксимационным числом тела С. Поскольку нас интересуют верхние границы скорости сходимости методов полиэдральной аппроксимации (а значит, как эталона и МНА), то назовем эту величину нижним аппроксимационным числом С. Введем верхнее аппроксимацион-ное число тела С как

а(С) := inf{i >0:7(0 = 0}.

Очевидно, что а(С) < а(С) , и в случае равенства этих величин можно говорить об аппроксимационном числе а(С).

Существует (Schneider, Wieacker 1981) нижняя оценка нижнего аппрок-симационного числа а(С), равная половине хаусдорфовой размерности (dim) множества дальних точек С (ехр* С - экстремальных точек, в которых существует внешняя касательная к телу окружность):

а(С)>^ dim ехр* С.

Определим класс ВКТ, для которого порядок 2/(d-\) является неулуч-шаемым. Для 0 < а < (d-1)/2 обозначим Y(a) := {Се'Р. а(С) =а} и пусть Y'#

я

:= Щс?-1)/2). В частности, V+œ.%. Из С := f|C, е V, С, е Г'+2, также следует,

1-1

что С&Щ. Таким образом, класс % достаточно широк, чтобы охватить ВКТ, аппроксимация которых требуется в приложениях.

В § 0.3 рассматриваются методы полиэдральной аппроксимации, вводится понятие эффективности этих методов и их оптимальности по порядку при аппроксимации как отдельных тел, так и их классов. Пусть Се9?и Pe.f(C). Величину

8{С,Р)

назовем эффективностью аппроксимации тела С многогранником Р (с точки зрения числа вершин или гиперграней соответственно).

Пусть F:={/y'}„-| 2, - сходящаяся к Се У последовательность многогранников из J(C). Величины

n(F) := lim inf rj(P"), rj(F) := lim sup tj(P")

назовем, соответственно, нижней и верхней асимптотической эффективностью аппроксимации тела С последовательностью F Если нижняя и верхняя асимптотическая эффективность совпадают, можно говорить об эффективности аппроксимации тела С. Наконец, под эффективностью метода полиэдральной аппроксимации тела С будем понимать эффективность порождаемой им последовательности многогранников.

Очевидно, что 0 < 77(F) < /7(F) < 1, причем для любого МНА Пш,

m=d+1, d+ 2, ..., эффективность аппроксимации равна единице. Поэтому гипотетический метод построения МНА будем называть оптимальным. Метод полиэдральной аппроксимации, порождающий для тела С последовательность с асимптотической эффективностью, равной 1, будем называть асимптотически оптимальным.

Метод полиэдральной аппроксимации, порождающий для тела С последовательность с нижней асимптотической эффективностью, большей нуля, будем называть асимптотически эффективным. Пусть С&'С и а{С) > 0 . Метод полиэдральной аппроксимации назовем оптимальным по порядку числа вершин (гиперграней) для С, если он порождает последовательность многогранников с тем же порядком скорости сходимости, что и у МНА. Метод будем называть асимптотически эффективным (оптимальным по порядку) для класса если он является асимптотически эффективным (оптимальным по порядку) для каждого Cef*. Нетрудно видеть, что асимптотически эффективный метод является (при условии «(С) > 0) оптимальным по порядку. Вместе с тем заметим, что метод может быть оптимальным по порядку и иметь, в то же время, асимптотическую эффективность, равную 0.

Для СеV+2 понятия асимптотической эффективности и оптимальности по порядку совпадают. Однако для класса они могут уже не совпадать. Заметим, наконец, что для того, чтобы некоторый метод был оптимален по порядку в классе необходимо и достаточно, чтобы для любого тела Се% в порождаемой методом последовательности {Р"}п ол, выполнялось

C0nstr J g

S(C,Pn)<-

m{Pnfi(dX)

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

неявного задания аппроксимируемого тела через алгоритм расчета значений его опорной или дистанционной функции.

Пусть аппроксимируемое тело задано через опорную или дистанционную (калибровочную) функции и аппроксимирующий многогранник Р построен некоторым МПА. Обозначим через ггР(Р) и nf (Р) число вычислений опорной и дистанционной функции тела С, необходимое для построения Р. Ясно, что для построения одной вершины (гиперграни) требуется как минимум один расчет опорной (дистанционной) функции. Поэтому по аналогии с определением оптимальности методов по порядку числа вершин (гиперграней) можно ввести понятие метода полиэдральной » аппроксимации оптимального по порядку числа вычислений опорной (дис-

танционной) функции.

Наконец, в параграфе рассматривается различие между итерационными (step-by-step, sequential) и неитерационными, а также между адаптивными (active) и неадаптивными (passive) методами. В методах адаптивных строится последовательность многогранников, в которой построение описания каждого следующего многогранника существенно зависит от информации об аппроксимируемом теле, полученной на предыдущих итерациях.

В § 0.4 приводится краткий обзор известных методов полиэдральной аппроксимации. Значительная часть из них носит теоретический характер и содержится в доказательствах различных утверждений, касающихся возможностей аппроксимации выпуклых тел многогранниками. В конце параграфа приводится обзор адаптивных методов полиэдральной аппроксимации, в том числе метода «Уточнения Оценок», обобщением которого явилась теория, рассматриваемая в диссертации.

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

В § 1.1 вводятся основные понятия теории итерационных методов полиэдральной аппроксимации. Рассматриваются две основные общие схемы аппроксимации - схема восполнения и схема отсечения, изучаемые в диссертации в дальнейшем.

, Схема восполнения

Пусть построен Р"е.У'(С). Тогда (п+1)-я итерация состоит из двух шагов.

Шаг 1. Выбираем р„едС.

Шаг 2. Кладем Р^1 := conv {р„, Р"}.

Конкретные методы, основанные на схеме восполнения, можно характеризовать способами решения двух задач:

1) способом выбора р„едС;

2) способом построения Р"*1 := сопу {р„, Р"} в требуемом виде. Схема отсечения

Пусть построен Р"еУ*(С). Тогда (и+1)-я итерация состоит из двух шагов.

Шаг 1. Выбирается направление Шаг 2. Кладется := Р"пЬ(ит С).

Конкретные МПА, основанные на схеме отсечения, можно характеризовать:

1) способом выбора »„е^"1;

2) способом построения /угИ := Р"гЛ(и„, С) в требуемом виде.

Если в некоторой реализации схемы восполнения многогранник начального приближения Р° принадлежит (3"с(С)), то и Р"е (Р"е:?с(С)) для любого п. В этом случае будем говорить, что последовательность многогранников {/>"}п=о,1)2, является последовательностью восполнения (отсечения) для С или последовательностью многогранников, порождаемой данной схемой для тела С и многогранника начального приближения Р°еУ{С).

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

Определение 1.2.1. Последовательность многогранников >

порождаемую для СеТ и Р°еЗР'(С) некоторой реализацией схемы восполнения, будем называть хаусдорфовой или Н(у С)-последовательностью восполнения, если существует константа у> 0 такая, что для любого п = О, 1,... справедливо 5Н(Р", /угН) > у8н(Р", С).

Определение 1.2.2. Последовательность многогранников {Р"}^ 1,2, , порождаемую для Се.'в и Р°е:?'(С) некоторой реализацией схемы восполнения, будем называть Н\(у, С)-последовательностью восполнения, если существует константа у> О такая, что для любого п = О, 1, ... для некоторого ип^(Рп, О справедливо С) - Р") > у8н(РС).

Определение 1.2.3. Последовательность многогранников {Р"}п-\,2, , порождаемую для СеЯ и Р°е&,с(С) схемой отсечения, будем называть Н(у, (^-последовательностью отсечения, если существует константа у>О такая, что для любого п = О, 1,... справедливо 3Н(Р", /угН) > у 6Н(Р", С).

Определение 1.2.4. Последовательность многогранников -,

порождаемую для СеУЬ и P°e.f0c(C) схемой отсечения, будем называть Н\(у, (^-последовательностью отсечения, если существует константа у> О такая, что для любого п = О, 1, ... для некоторого рпеТ(ип С) справедливо giun, t(p„, П) - g(K„, Q > yS\P", Q.

Нетрудно видеть, что Нг(у, С)-последовательность восполнения (отсечения), есть, в то же время, Н(у, С)-последовательность восполнения (отсечения).

Определение 1.2.5. Последовательность многогранников {Р"}^0,1,2, » порождаемую для Ce У схемой восполнения (отсечения), будем называть асимптотической Н(у,(^-последовательностью (Нх(у, (^-последовательностью) восполнения (отсечения), если для любого е, 0<s<y, существует номер N такой, что последовательность {PN'"}„. 12, является Н(у-£,С)-последовательностью (#,(;*•£;С)-последовательностыо) восполнения (отсечения).

Итерационную схему аппроксимации будем называть (асимптотической) Я- (#г) схемой для класса тел (с константой у), если для каждого Се'/* она является (асимптотической) Я- (Яг) схемой с одной и той же константой у. Очевидно, что (асимптотическая) Я- (Яг) схема для класса тел У* с константой у\ является Н- {Нг) схемой для класса тел У* с константой у2, где У\>У2-

Далее в параграфе показывается, что Я-схемы существуют для любого класса тел У*с:У. Для доказательства вводятся и используются «базовые» адаптивные методы восполнения (МБВ) и отсечения (Мьо).

Базовый Метод Восполнения (БВ)

Пусть для Се У и F°e./(C) построен Р"&:?'(С). Для построения Ря+| выполняются следующие процедуры:

Шаг 1. Найтир„<=дС\ р(р„, Р") = SH(P",Q.

Шаг 2. Положить Р"+| := conv {р„, Р").

Базовый Метод Отсечения (БО)

Пусть для СеУ и PßeJ'c((7) построен Р"еУс(С). Для построения Р^1 выполняются следующие процедуры:

ШАГ 1. Найти и„ := arg шах {g(u, Р") - g(u, Q: }.

Шаг 2. Положить Р"*х := P"nL(u„, Q.

В § 1.3 рассматриваются примеры методов, которые, как доказывается, относятся к классу хаусдорфовых методов.

Методы, реализующие Я-схемы, будем называть хаусдорфовыми (или Я-) методами. Класс методов, использующих Я-схему восполнения или

отсечения (т.е. порождающих Я-последовательности восполнения или отсечения с константой у для Се У), будем обозначать через !о(у, С). Если необходимо, будем различать класс Н-методов восполнения ¡)'(у, С) и -отсечения С). Очевидно, что при У\>У2 справедливо С)о$э(/2, С). Если для некоторой константы у, некоторого класса ?*с?' и некоторого метода М справедливо Мей(/, С) для любого Се/*, то будем писать Ме?>(Г,

Класс методов, использующих Ягсхемы восполнения или отсечения (т.е. порождающих Я,-последовательности восполнения или отсечения с константой у для тела Се?), будем обозначать через 9) ¡(у С). Если необходимо, будем различать класс Нгметодов восполнения 5)\(у, С) и - отсечения ?>с\(у, С). Если для некоторой константы у, некоторого класса ?*с?' и некоторого метода М справедливо Ме50)(/, С) для любого Се?*, то будем писать Ме#|{у, ?*)■ Если величина константы у в некотором утверждении значения не имеет, класс Я- (Я]-) методов будем обозначать через ^(?*)

ш«*)).

Класс методов, использующих асимптотические Я-схемы восполнения или отсечения (т.е. порождающих асимптотические Я-последовательности восполнения или отсечения с константой / для тела Се?), будем обозначать через "Я(у, С). Если необходимо, будем различать класс асимптотических Н-методов восполнения я$)'(у С) и отсечения "^¡(у, С). Если для некоторой константы у, некоторого класса ?*с?' и некоторого метода М справедливо Ме"Я(у, С) для любого Се?*, то будем писать Ме'Жу, ?*). Совершенно аналогично определим класс асимптотических Н-методов а9)1 (/, С) и обозначение Меа^,(/, ?*). Ясно, что для любых Се?'и / справедливо Ыу, С)с"Жу, С). Если величина константы у в некотором утверждении значения не имеет, класс асимптотических Я- (Яг) методов будем обозначать через "*)(?*) С^и(?*)).

Из свойств «базовых» адаптивные методов, полученных в §§ 1.2-1.3, вытекают:

Следствие 1.3.1. МБВе5У(1, Щ, Мбо^О, ?).

Следствие 1.3.2. *)(],

Следствие 1.3.3. Мвве^О,

Следствие 1.3.4.#,(1, ?)*0.

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

Следующий метод «Уточнения Оценок» (УО) (см. историю его создания в [14], [25] и § 0.4) требует на каждой итерации метода конечного чис-

ла вычислений опорной функции и является в настоящее время основным АМПА, используемым на практике. Метод УО обозначим через МУ0.

Метод Уточнения Оценок (УО)

Пусть для CeW и Р°е.У'(0 построен Р"<=.?'(С) в виде системы линейных неравенств, характеризующих множество м\Р"). Для построения Р">] выполняются следующие процедуры:

Шаг 1. а). Найти и„ := arg max {g(M, С) - g(u, Р"): иеМ\Р")}. b). Найти р„е Т(и„, С).

Шаг 2. Построить описание Р"fl := conv {р„, Р"} в виде системы линейных неравенств, характеризующих множество М\Р

Свойства метода УО определяются следующими результатами:

Теорема 1.3.3. Для любых Се'€ и Р°е&'(С) метод МУ0 порождает H](r/R, С)-последовательность восполнения, где }{Р°, С) := r/R, и B£z)^Pa<zCczBK(z\ ZG int Р°, таким образом Муое Vi(К^ О, О-

Следствие 1.3.6. Для любого Ce'f'u любого Р°е./(С) выполняется Муое^ПС).

Следствие 1.3.7. Муое^О, К2)-

Далее в параграфе приводятся аналоги метода УО, сформулированные в [18] на основе теории двойственности АМПА (см. гл. 3), которые позволяют строить ^-последовательности отсечения.

Первый Метод уточнения Внешних Оценок (уво,)

Пусть для CeV?0 и Р°е:?0с(С) построен Р"е:?0с(С) в виде множества М'(Р"). Для построения Р"*1 выполняются следующие процедуры:

ШАГ 1. а). Найти р„ := arg max {pip, p/g*{p,C)y. peM'(P")}. b). Найти unsS{pn/g*(p№ Q, С).

Шаг 2. Построить описание Р"*1 := Р"глЬ(ип, С) в виде множества

Второй Метод Уточнения Внешних Оценок (УВ02).

Пусть для Се % и Р°е.%с(С) построен Р"&Упс(С) в виде множества М'(Р"). Для построения P"+i выполняются следующие процедуры:

Шаг 1. а). Найти

Рп ■■= arg max {g(u(p), р) - g(u(p), Q: peM'(P"), где u(p)eS(p/g*(p, С), С)}, b). Положить и„ := u(pn)eS(p„/g*(p„, Q, Q.

Шаг 2. Построить описание Р"*1 := Р"глЬ(ию С) в виде множества М\Р"ч).

Метод УВО1 обозначим через MyBoi- Метод УВ02 обозначим через Мувог- Свойства методов УВО определяются следующими результатами:

Теорема 1.3.6. Для любых Се%и с(С) методы MyBOi и Муво2 порождают Н\/а>о(С), С)-последовательности отсечения, т.е.

"Mvboi, MyB02ei5ci(l/fflb(C), С).

Следствие 1.3.9. MyRo26a^ci(1, ЩпК2).

Таким образом, для классов #г методов отсечения справедливо

Следствие 1.3.8.Длялюбого Се%

Следствие 1.3.10.

В § 1.4 приводится пример нехаусдорфового метода - рассматривается предложенный автором метод «Сближающихся Многогранников», сочетающий в себе схемы отсечения и восполнения. Метод СМ обозначим через Мсм-

Метод Сближающихся Многогранников (СМ)

Пусть для Cef и Р°еУ(С), (?е.?с(С) построены Р"е.?'(С) и <2*е.?\С). Для построения Р"*] и Q"*1 выполняются следующие процедуры:

ШАГ 1. а). Найти и„ := arg шах {g(u, <£) - g(u, Р"): ueMf(J>")}.

Ь). Найтирпе1\и„, С).

Шаг 2. Построить Р"*х := conv {рт Р") и := 0"пЦи„, Q.

Заметим, что на каждой итерации метода СМ вычисляется только одно значение опорной функции аппроксимируемого тела. Благодаря такой особенности, метод СМ (см. п. 2.6.4) в гладком случае оказывается оптимальным не только по числу вершин внутреннего и числу гиперграней внешнего многогранников, но и по числу вычислений опорной функции аппроксимируемого тела. В главе 3 на основе теории двойственности АМ-ПА рассмотрены методы отсечения, двойственные к методу СМ (методы СМ* и ДСМ). Эти методы основаны на вычислении дистанционной функции аппроксимируемого множества и обладают достоинствами и недостатками, аналогичными методу СМ. В частности, в гладком случае они оказываются оптимальными не только по числу вершин внутреннего и числу гиперграней внешнего многогранников, но и по числу вычислений дистанционной функции аппроксимируемого тела.

Вторая глава посвящена исследованию скорости сходимости, доказательству оптимальности и расчету эффективности (т.е. сравнению со ско-

ростью сходимости многогранников наилучшей аппроксимации) хаусдор-фовых методов.

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

§ 2.1 - вводный. В § 2.2 излагается метод изменения объема на итерациях, который дает наиболее сильные оценки при исследовании скорости сходимости Я-схем, при исследовании скорости сходимости на начальном этапе аппроксимации, а также при исследовании нехаусдорфовых методов.

В § 2.3 излагается метод упаковок нормалей на внешне-параллельном множестве, который дает наиболее сильные оценки при исследовании скорости сходимости Я)-методов при аппроксимации негладких тел.

В § 2.4 излагается метод «Глубоких Ям», который позволяет получить наиболее сильные результаты для оценки скорости сходимости хаусдор-фовых алгоритмов в гладком случае.

В § 2.5 дана сводка результатов исследования скорости сходимости ха-усдорфовых методов, полученных различными методами, выделены наилучшие оценки и рассмотрен вопрос об эффективности и оптимальности методов из рассматриваемого класса. В частности, показано, что в классе гладких тел асимптотическая скорость сходимости Я,-последовательностей восполнения отличается от асимптотической скорости сходимости многогранников наилучшей аппроксимации на константу, не зависящую от аппроксимируемого тела. Для Я-последовательностей (и порождающих их методов) показано, что они оптимальны по порядку числа вершин (последовательности восполнения) и гиперграней (последовательности отсечения) в классе гладких выпуклых тел. Для Я]-последовательностей (и порождающих их методов) показано, что они оптимальны по порядку числа вершин (последовательности восполнения) и гиперграней (последовательности отсечения) в широком классе выпуклых тел, для которого порядок 2/(d-l) является неулучшаемым. Сходимость хаусдорфовых методов оценивается следующими теоремами.

Теорема 2.2.1. Пусть и и, есть Н(у, С)-последовательность восполнения (отсечения). Тогда для любого в, 0 < е < 1, существует N такое, что при ri>N справедливо

S\P",C)<{\+e)Hy,C)k{n)m-d\ 8\РО < (1+£)Л2(/,СЖ«)1/,,Л где к(п) есть п или т'(Р") (п/{Р")) и

А, О',С) =

}|/(</-1)

©(С).

Теорема 2.3.1 и следствие 2.3.1. Пусть Сег€ и о,1д есть Н\{у, С)-последовательность восполнения (отсечения). Тогда для любого е, 0 < е < 1, существует номер N такой, что при ri>N справедливо ¿V, С) < (1 +£)Мг, О Цп?™, О < (1 +e)Ur, Q<KQ КпГЛ

где к(п) есть п или т'(Р") (rr/iP*)) и

2 d-1

dnd

У

Теорема 2.2.2. Пусть Се®+2 и {/>"}^о,1, есть Н(у, С)-последовательность восполнения (отсечения). Тогда для любого е,0<е< 1, существует N такое, что при справедливо

д\Р", С) < (\+е)Я3(у, С)

6И(р", о < (\+е)Чг, с) тт'"\

где кЦп) есть п или т'(Р") (п/(Р")) и

г" J гт(С) ЯЛУ,с) 4 id+l)d

у< J rmn(C)

Следствия 2.4.4-2.4.6. Пусть f/y'}^o,i, - Q-последовательность восполнения для СеУ+2. Тогда

2f9 л2*'"» lim sup SH(C,P")k(.n)2Kä-n <-\ ^¡xk(:(xyl2da(x)

Ишзир ¿5(С,П*(«)2,(<'"

Г J

где к(п) есть п или т'(Р^).

Полученные оценки на скорость сходимости хаусдорфовых АМПА позволяют сделать следующие выводы об оптимальности по порядку хаусдорфовых АМПА.

Теорема 2.5.1. Путь Ъ*а% и Ме^',(«*) (Ме£с,(«*)). Тогда М оптимален в метриках Хаусдорфа и объема симметрической разности по порядку числа вершин (гиперграней) для класса У*.

Теорема 2.5.2. Путь УСе^2 и Ме^'С^*) (Ме^с(«*)). Тогда М оптимален в метриках Хаусдорфа и объема симметрической разности по порядку числа вершин (гиперграней) для класса

Приведем оценку на эффективность Яг последовательностей. Теорема 2.5.8. Пусть Р:={/у,}^0,1, ~ Н\(У> С)-последовательность восполнения для СеЧ?+2. Тогда

Заметим, что эта оценка асимптотической эффективности в метрике Хаусдорфа не зависит от аппроксимируемого тела (в том числе от его асферичности) и прямо пропорциональна константе у.

Изложенные в параграфе результаты о скорости сходимости, оптимальности по порядку и эффективности носят асимптотический характер. Они естественно распространяются и на случай асимптотических Н-последовательностей и порождающих их АМПА.

В § 2.6 сформулированы основные результаты изучения скорости сходимости и эффективности конкретных методов, введенных в гл. 1. Эти результаты являются приложением теории скорости сходимости в классе хаусдорфовых методов к исследованию конкретных представителей из этого класса (подстановкой в скорости сходимости Н- и Ягпоследова-тельностей значений констант у, соответствующих данному методу и данному классу аппроксимируемых тел, см. § 1.3). В частности, показано, что для любого выпуклого компактного тела методы «Уточнения Оценок» и «Уточнения Внешних Оценок» сходятся не хуже, чем со скоростью, имеющей порядок 2/(^-1). Таким образом, эти методы являются оптимальными по порядку числа вершин (метод УО) и числа гиперграней (методы УВО) в классе тел, для которых этот порядок является неулучшаемым. Кроме того, показано, что указанные методы являются асимптотически эффективными в классе тел с гладкой границей и положительными главными кривизнами, причем достигаемая с их помощью точность асимптотически не более чем в четыре раза хуже точности аппроксимации многогранниками наилучшей аппроксимации с тем же числом вершин или гиперграней.

В заключение параграфа рассматривается скорость сходимости метода «Сближающихся Многогранников». Этот метод, как и хаусдорфовы методы, основан на общих адаптивных схемах восполнения и отсечения. Однако, как уже отмечалось, он не принадлежит к классу Я-методов. Поэтому для его исследования используется аппарат изучения изменения объема на

4

4 1А-1

ч2/(</-1)

^шш (С)

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

Теорема 2.6.32. Пусть {(/*", C?")}»i-o,i, - последовательность пар многогранников, порождаемая методом СМ для Cef', <у(С)* 1. Тогда для любого е,0< е<\, существует N такое, что при n>N справедливо 5\Р", 0") < (\+s)ÄxCM(C)li{n)w-J), ÖH{P», Q") < (\+£)Л{м (С)к(п)т^, где к(п) есть п, т'(Р"), п/{(Г\ trf{P") или rrf(ff) и

Г л l'^4'

4^(0 = 2 -а(С)"\ ЫС)2-\]mco(C)dl^

Оd-X)nd.

¿/"(0 = 2 —4 -о-(0[ [а>(С)2 -\Т1о>(С)а [У- \

Теорема 2.6.33. Пусть {(Р0")}„-о,|, - последовательность пар многогранников, порождаемая методом СМ для Се КД Тогда для любого е, 0<£<1, существует N такое, что при п>№ справедливо д\Р", в") < (\+е)Л3(м(С) Л(и)2/°Л 3"{Р", ОТ) < ( ]+е)Л4гм(С) *(и)2/<'Л где к(п) есть п, т\Р"), »/(0"), т*(Р") или и

Л™(С) =-2А-ег(С)<</+,)/21 —— ,

Г 1 2/(^-1)

'] гтт(С)

Теорема 2.6.34. МСм оптимален в метриках Хаусдорфа и объема симметрической разности по порядку числа вершин внутренних, гиперграней внешних многогранников и по числу задач вычисления опорной функции аппроксимируемого множества для класса К\2.

Теорема 2.6.36. Пусть ?\'-={Р"}п^>,\х есть последовательность внутренних и Р2:={£?"}„=о,1,2, ~~ внешних многогранников, порождаемая для Се V+1 методом СМ. Тогда

4 гт{С) ^ 4" rmax(C)

п" +1 а

\2/(</-!)

41 2 </

2/(</-1)

412 Л

2/(4-1)

В § 2.7 изучена сходимость рассматриваемых в диссертации методов на начальном этапе аппроксимации. Полученные результаты позволяют рассчитывать скорость сходимости этих методов на начальном этапе для любых тел (в том числе и при аппроксимации многогранников).

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

Необходимость применения теории двойственности в задачах полиэдральной аппроксимации возникает в следующих случаях:

- когда при наличии методов, основанных на описании аппроксимируемого тела через опорную (дистанционную) функцию, необходимо разработать МПА для тел с двойственным описанием через дистанционную (опорную) функцию;

- когда при наличии методов с последовательно растущим числом вершин (гиперграней) необходимо разработать МПА многогранниками с двойственным описанием, т.е. с последовательно растущим числом гиперграней (вершин);

- при необходимости разработки МПА, оптимальных по числу вычислений опорной и / или дистанционной функции аппроксимируемого тела. Эта теория устанавливает взаимосвязь между рассматриваемыми в диссертации хаусдорфовыми методами восполнения и отсечения и позволяет разрабатывать новые методы.

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

Пусть Се Г; обозначим С*\={хе№,\ <х, у><],уеС} - полярное множество (поляру) для С (относительно {0}). Пусть уеЕ0а и 1у:= {хеЕ : <х, у>=\}. Под полярой л (у) для точки у (относительно сферы <х, х>=1) будем понимать гиперплоскость 1У, а через п(1})={у] обозначим полюс (относительно сферы <х, х>=1) для гиперплоскости 1У. Пусть Се%, тогда известно, что С*е%, С** г С, полюс каждой (экстремальной) гиперплоскости, опорной к С, есть (экстремальная) граничная точка С*, и поляра каждой (экс-

тремальной) граничной точки С есть (экстремальная) опорная гиперплоскость для С*. В наших обозначениях для ueS?1'1 иредС имеем

*(/(«, С)) =—еЭС*; g(u,C)

я{р) = 1(ир, С*), g(u , С*) = ij,« := f.

И и

Кроме того, опорная и дистанционная (калибровочная) функции полностью "дуальны": g(x, C*)=g*(x, С), и g*(х, C*)=g(x, С). Определенные в гл. 1 аппроксимационные схемы отсечения и восполнения являются двойственными в смысле следующей теоремы.

Теорема 3.1.1. Пусть последовательность многогранников {Р"}п=о,\,2, . где Р"е%, и=0,1,2,... , является последовательностью восполнения (отсечения) для СеТ0. Тогда последовательность многогранников {(Р")*}п=0,1,2, является последовательностью отсечения (восполнения) для С*.

В § 3.2 устанавливается факт двойственности Н- и Я,-последовательностей восполнения и отсечения: последовательность из многогранников, полярных к многогранникам Н- (Нг) последовательности восполнения, оказывается Н- (#г) последовательностью отсечения для полярного тела и наоборот.

Теорема 3.2.1. Пусть {P"}n~o,i, есть (асимптотическая) Н{у, С)-последовательность восполнения для Се¥0, Ь, «=0,1,... . Тогда {(/уг)*}„_о! есть (асимптотическая) Н(уа, С*)-последовательность отсечения, где

Кроме того, {(Р")*}„-o,i, есть асимптотическая Н(у*(у, С), С*)-последовательность отсечения, где

у*(у,С):=-

0О(СУ

Теорема 3.2.2. Пусть {Р"}г0,1, - (асимптотическая) Н(у, С)-последовательность отсечения для , и=0,1,... . Тогда

{(Р")*}п_01 есть (асимптотическая) Н(ус, С*)-последовательность восполнения, где

Гс

Кроме того, {(/*")* },r o.i, есть асимптотическая Н(у*(у, С), С*)-последовательность восполнения, где константа У*(у, С) определена в утверждении теоремы 3.2.1.

Аналогичные утверждения справедливы и для ^-последовательностей восполнения и отсечения.

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

В § 3.4 рассматривается вопрос построения методов, оптимальных по порядку числа решений задач оптимизации на аппроксимируемом теле для негладких тел. В параграфе рассматриваются методы, состоящие одновременно из -метода восполнения (отсечения) и метода отсечения (восполнения) из класса, двойственного к нему. Такие методы мы называем самодвойственными. В параграфе приводится описание двух самодвойственных методов, предложенных автором, получены верхние оценки их скорости сходимости, имеющие порядок 2l(d-\). Показано, что в классе тел, для которых этот порядок является неулучшаемым, они являются оптимальными по порядку числа вершин вписанных, гиперграней описанных аппроксимирующих многогранников, по числу вычислений опорной и дистанционной функций, т.е. числу решений задач выпуклой оптимизации на аппроксимируемом теле.

Приведем описание одного из самодвойственных методов (МсмдО-Пусть задан пороговый параметр метода Л, 0 < А < 1.

Самодвойственный, Метод (СМД,)

Пусть для Се Ко и P°eS0XC), ß°e-<(0 построены Р"е.<(С) и (J'e.fJiC). Для построения и выполняются следующие процедуры:

a). Найти v.eWV) и qnr=T(vm ff), где

v„ := arg шах {g(M, ff) - g(u, P"): иеМ\П}-

b). Найти p„e 1\v„, C).

с). Если

то

иначе

фт Рп) - ¿к, п * л \Ф„, оп - фп, т

построить Р"*[ := сопу {/>„, Р"}, положить О"41 := (¿Г,

найти О, О,

построить := (?пЦи№ С), положить Р"+[ := Р".

Свойства метода СМД] определяются, в частности, следующими утверждениями.

Следствие 3.4.1. Пусть {Р"}„-\,2, и Ш"}п-\,2, ~ подпоследовательности внутренних и внешних многогранников с различными членами, порождаемые методом СМД1 для Се¥0, Р°е.'/0'(С), Тогда они являются асимптотическими Н\(у3, С)-последовательностью восполнения с уг := Я!а(С) и Н\(ус, (^-последовательностью отсечения с ус := (1 -Д)/[<и(С)^ь(С)], соответственно.

Теорема 3.4.2. Пусть {(Р", (?")}„-|,2, - последовательность пар многогранников, порождаемая методом СМД/ для Се'('0, РпеЛЬ'(С), (2°е./о (С). Тогда для любого е,0<£< 1, существует N такое, что при п>Л справедливо

8"(Р<Г) < (1+е)Шсо(0, С) {т\Р"))Щ"'Х\

д\Р", < (\+еШ(\-тсо(С)щ(С)), О (тГ(0")У2/<'1~1\ 8Н(Р", дг) < (1+^(1/40, с)у(л, С) пг,ш\ 8\Г, ОТ) < (1+^)^(1/^0, ОИЯ О кЫ2'ш\ 8Н(Р", (?) < ( \+ё)Ш-Х)КМС)щ{С)), О ыпу1!т\ 8"(Р", <Т) < (\+ё)Ш<*С), С)ЫЛ, С) где кх{п) есть ггР{Р") или /^((У), к2{п) есть пР (Р") или ггР (0"), к3{п) есть тор1(Р") или дгор|((/'), константа С) определена в (3.4.3), и

2

ФА 1-е/ ~

Я 2 +а>о(С) 2 0-Я) 2

¥\(Л,С) :=

(¡-\

¿-1 1 -с1

Я 2 +2а>0 (С) 2 (1 -Я)2

2

Теорема 3.4.3. МСмд| оптимален в метриках Хаусдорфа и объема симметрической разности по порядку числа вершин внутренних многогранников, числа гиперграней внешних многогранников, числа вычислений опорной

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

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

Как уже говорилось выше, про минимальное число вершин многогранника, необходимое для получения аппроксимации с заданной точностью, известно только, что его порядок, аппроксимационное число тела, имеет верхнюю оценку вида (d-1)/2. Т.е. в двумерном случае (d=2) минимально необходимое число вершин оценивается по порядку обратной величиной к корню от требуемой точности и не зависит от свойств гладкости аппроксимируемого тела. Ясно, что в случае, когда аппроксимируемым телом является, например, многогранник, эта оценка является очень грубой. Более тонкие верхние оценки в общем случае отсутствуют. Исследование, приведенное в гл. 4, устанавливает связь между верхней оценкой скорости сходимости многоугольника наилучшей аппроксимации и метрическими свойствами (в частности, размерностью) множества крайних точек аппроксимируемого диска.

В § 4.1 приводятся известные аппроксимационные свойства выпуклых дисков. В § 4.2 приводятся определения, необходимые для описания различных типов сходимости многогранников к выпуклым телам.

Пусть U и А - непустые подмножества метрического пространства R. Множество U называется г-сетью для А, если любая точка А расположена на расстоянии не большем, чем е, от некоторой точки U. Множество U называется ^-различимым, если любые две его различные точки находятся на расстоянии, большем, чем е. Множество А называется вполне ограниченным, если для любого положительного есуществует конечная f-сеть для А.

Для вполне ограниченного А обозначим через А) минимальное число точек е-сети А и через А) - максимальное число точек е-различимого подмножества А. Величины := logW^fi; А) и

<££А) := log Ш(е, А) назовем, соответственно, относительной г-энтропией и ¿•-емкостью А (под log здесь и далее понимается log2). Нижняя метрическая размерность вполне ограниченного множества А определяется как

dm А := lim inf —

= lim inf —

£—>0+

log — £

£-*0+

log-£

Аналогично определяется верхняя метрическая размерность dm А, а при равенстве верхней и нижней - метрическая размерность dm А.

Пусть 0 < а < 2 л такая параметризация S, что для 0 < а < л можно определить

а.(р) := min {or. и = (cos a, sin a)eS(p, С)}; а,(р) := max {ос. и = (cos a, sin a)eS(p, С)}. Обозначим через s.(p) и s (р) граничные векторы S(p, С): s {p) := (cos а.(р), sin а.(р)); s,(p):= (cos а,(р), sin а+(р)).

Обозначим

- средний вектор единичных внешних нормалей в точке р (аналог симметричной производной Шварца). Пусть Z: дС—>д(С+В) такое, что 2(р) := р + s(p),p&dC.

В § 4.3 описывается предложенная автором модификация метода «Уточнения Оценок» - хаусдорфовый метод «Экстремальных Ям». На каждой итерации рассматриваемого метода к множеству вершин аппроксимирующего многоугольника прибавляется наиболее удаленная от него экстремальная точка аппроксимируемого тела (так называемая глубокая яма), что и служит обоснованием названия самого алгоритма.

Метод Экстремальных Ям (ЭЯ)

Пусть eext С и 7, := {/|}. Пусть множество Тп построено и conv Т„) > 0. Тогда 7^, := Т„ u где /„,, eext С и

i, conv Т„) = д(С, conv Т„).

Метод ЭЯ принадлежит к классу хаусдорфовых АМПА аппроксимации многомерных ВКТ, описанному в гл. 1 и исследованному в гл. 2. От метода БВ, описанного в гл. 1 и порождающего Я,-последовательности многогранников с константой 1, алгоритм ЭЯ отличается только конкретизацией выбора присоединяемой вершины t„., обязательно из множества экстремальных точек.

Обозначим Р" := conv Т„, п = 1, 2, .... Следующая теорема, характеризующей скорость сходимости последовательности {Р"}„ - i, 2, к аппроксимируемому телу:

Теорема 4.3.1. Пусть {Р"}„-i,2, - последовательность, порождаемая методом ЭЯ для Cef!. Тогда для любых п > а(С+В) Ñ2, и к 0 < v< S[P", С), справедливо

л/S[P",C)-V

п + \<Ш

- г- , Z(ext С)

1 + л12

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

Теорема 4.4.1. Для Се гс: при п > И0{С) и к, 0 < у< 3(.У„, С), справедливо

Теорема 4.4.1 позволяет дать верхние оценки числа вершин МНА, необходимых для достижения любой заданной точности аппроксимации. Следствие 4.4.1 .Для Cef и любых е и ц 0 < v < е, справедливо

где /У0(С) и Л^С) определены в формулировке теоремы 4.4.1.

Далее, в главе получены следствия из полученной оценки. В § 4.5 показано, что аппроксимационное число (порядок скорости сходимости) тела не превышает половины верхней метрической размерности множества продолженных экстремальных точек.

Теорема 4.5.1. Пусть Се'€. Тогда

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

В § 4.7 в качестве примера использования техники исследования, развитой в четвертой главе, рассматривается один класс двумерных дисков с бесконечным (счетным) числом вершин. В этом случае удается аналитически рассчитать скорость сходимости многоугольников наилучшей аппроксимации и сравнить её с верхней оценкой, получаемой по рассмотренной в главе методике. Показано, что полученные таким образом оценки совпадают.

Определим множество Мх (Я > 0) из класса ^следующим образом. На плоскости Е2 в положительном ортанте рассмотрим четверть окружности Я+:={х2+у2=1: х>0, у>0}. Далее на оси у рассмотрим последовательность точек 0 с координатами (0, пЛ), л=0,1,... . Каждую из вершин соединим отрезком ¿У с точкой В( 1, 0). Точки пересечения отрезков О" с 5+ обозначим Т. И определим, наконец, множество Мл:

где Л^о(С) := 1 + o(C+B)N2 и

min {п: Q<e}< max {N0(Q, Nc^C)},

a(C)<a(C)<

dm Z(ext C) 2

М сопу {О, В,{Т" }"=1}, где О - начало координат (0, 0). Класс тел Мл (Л > 0) обозначим через л.

1

Теорема 4.7.1. а(Мх) =

2Л + 2

1

Теорема 4.7.2. dm Z(ext Мл) <

Л +1

Следствие 4.7.3. Метод ЭЯ оптимален по порядку при аппроксимации тел из класса Л.

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

В § 5.1 рассматриваются задачи и разработанная автором общая методика численного исследования эффективности методов полиэдральной аппроксимации. Она основана на сравнении асимптотических оценок сходимости МНА с эффективностью АМПА, полученных в реальных численных экспериментах по аппроксимации, и состоит из двух основных этапов: 1) исследования порядка скорости сходимости; 2) исследования собственно эффективности.

1) Первый этап состоит в следующем. Будем считать, что гипотетический оптимальный метод (метод построения МНА) для ВКТ С имеет асимптотическую скорость сходимости вида

где а(С) и А(С) - некоторые константы, am- некоторая вычислительная характеристика аппроксимирующего МНА П": число итераций п, число вычислений опорной или дистанционной функции G, число вершин т', число гиперграней mi. После этого можно выделить две части исследования.

а). Обоснование применимости асимптотической теории. Пусть в процессе численной аппроксимации получена последовательность многогранников {Р"}. Проверим гипотезу о том, что асимптотически

8(С Р")*__

где А'(С) и а*(С) - некоторые положительные константы, минимизирующие ошибку интерполяции экспериментальных точек в координатах log <5(С, Р") и log т(Р"). Если разброс точек относительно прямой

log <5(С, Р") = log А'(С) - log т(Р") /a*(Q невелик, гипотезу можно считать справедливой.

б). Сравнение порядка скорости сходимости и аппроксимационного числа. Сравним величины а(С) и а*(С). Их близость говорит о том, что порядок скорости сходимости многогранников, порождаемых исследуемым методом и МНА, один и тот же. В этом случае численные исследования будут подтверждать применимость асимптотической теории для оценки скорости сходимости на конечных итерациях.

Заметим, что для проведения данного этапа экспериментального исследования достаточно знать только величину аппроксимационного числа тела: о(С). Поэтому данный этап исследования может быть применен в отношении, например, любых тел из класса tf, для которых a(Q =(d-\)/2, а также в том случае, когда величина аппроксимационного числа может быть рассчитана специально (см., например, класс тел из § 4.7).

2) Второй этап состоит также из двух частей.

а). Исследование эффективности на итерациях метода.

Пусть Се&и РеУ(С). Эффективность аппроксимации может быть рассчитана как

*/>)•=_т_

[m(P)]Ua(C) S(C,P)

Пусть {Р") „=oi - сходящаяся к Се ^последовательность многогранников, построенная исследуемым методом. Начиная с некоторого номера N0, определим эмпирические величины

7*-(0:= min ЫР"). N0<n<N\}, >7*max(C):= шах {ТКП- No<n<Nt},

1* (Q:= Yn(P")W-NQ + \),

n=N0

где Ni - максимальный достигнутый в эксперименте номер итерации метода. Эти величины характеризуют эффективность метода на рассматриваемом отрезке последовательности {Р*}.

б). Исследование асимптотической эффективности метода.

В случае, если на первом этапе исследования гипотеза о сходимости рассматриваемой последовательности многогранников с оптимальным порядком а* = а(С) считается подтвержденной, начиная с номера N0, то, экстраполируя результаты аппроксимации, получаем, что величины rfmm(C) и 7*шах(0 могут служить эмпирическими оценками для нижней и верхней асимптотической эффективности метода:

Z(C)*r,*ma(Cl п(С)*г}*шп (С).

Заметим, что для проведения данного этапа экспериментального исследования необходимо знать не только величину аппроксимационного числа тела а(С), но и уметь рассчитывать константу аппроксимируемости Л (С):

1 ) 4s(C) = i div^tiicixy^^r^-0.

Поэтому второй этап численного исследования эффективности АМПА может быть проведен только в том случае, когда удается рассчитать поверхностные интегралы либо аналитически (что практически возможно только в простейшем случае шаров), либо приближенно; сведя их вычисление к обычному интегрированию. Именно так мы поступаем в классе многомерных эллипсоидов.

Наконец, с величиной А(С) может быть сравнена экспериментальная константа сходимости А*(С), полученная заменой а*(С) на точное значение апрроксимационного числа а(С):

log т О = log A*(Q - log т(Г) IciC). При этом величина А(С)/А *(С) также, наряду с Т]*(С), может служит мерой эффективности метода аппроксимации.

В § 5.2 в качестве объектов аппроксимации выбраны многомерные телесные эллипсоиды. Важность исследования эффективности алгоритмов в классе эллипсоидов определяется тем фактом, что эллипсоиды являются наиболее сложным объектом при аппроксимации в метрике объема симметрической разности. Кроме того, этому классу принадлежит шар, являющийся наиболее сложным объектом при аппроксимации в метрике Хаусдорфа. Основным результатом данного параграфа является сведение задачи расчета константы аппроксимируемости в классе многомерных эллипсоидов к обычному интегрированию по прямоугольной области. Это позволяет проводить исследование методов в классе эллипсоидов в полном объеме.

В § 5.3 излагаются результаты различных численных исследований метода «Уточнения Оценок» в классе многомерных эллипсоидов. В § 5.4 кратко излагаются результаты исследований других адаптивных методов по разработанной методике.

В § 5.5 рассматриваются численные эксперименты по аппроксимации введенного в § 4.7 класса выпуклых дисков со счетным числом вершин и нетривиальной (лежащей между 0 и Vi) верхней оценкой для аппроксима-ционного числа.

В § 5.5 рассматриваются основные выводы из приведенных в диссертации экспериментальных исследований:

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

2) предложенная в главе методика позволяет исследовать как порядок асимптотической скорости сходимости, так и асимптотическую эффективность;

3) рассматриваемые АМПА (в частности, методы УО, СМ, прямо-двойственный, комбинированный) являются оптимальными по порядку для различных классов тел и метрик, при этом асимптотическая скорость сходимости достигается в большинстве случаев уже при достижимой в экспериментах точности;

4) полученные экспериментальные результаты подтверждают теоретические выводы (см. главы 2, 3 и 4) о скорости сходимости и эффективности оптимальных АМПА, рассматриваемых в диссертации.

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

Глава шестая посвящена вопросам практического применения оптимальных адаптивных методов полиэдральной аппроксимации в задачах принятия решений, главным образом, в рамках метода ОМД.

В § 6.1 приводится математическое описание метода ОМД, рассматриваются некоторые особенности использования в нем адаптивных методов полиэдральной аппроксимации, а также вопросы визуализации аппроксимирующих многогранников в данном подходе. Предлагается разработанный автором (совместно с О.Л. Черных) быстрый алгоритм построения больших серий сечений выпуклых многогранников.

В § 6.2 приводится пример использования описанных в диссертации адаптивных методов полиэдральной аппроксимации для анализа экономических и экологических аспектов проблемы распределения водных ресурсов в регионе с развитым сельским хозяйством. За основу модели, используемой в исследовании, принята модель, разработанная в Международном институте прикладного системного анализа. Отметим, что используемая модель отличается подробным описанием производственных процессов. В связи с этим расчет опорной функции аппроксимируемого ОМД требовал значительного времени, что во многом способствовало раз-

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

В § 6.3 рассмотрена методика многокритериального анализа эколого-экономических проблем методом ОМД в целом и кратко охарактеризованы прикладные исследования, основанные на использовании адаптивных методов полиэдральной аппроксимации в рамках метода ОМД.

В § 6.4 рассматривается применение адаптивных методов полиэдральной аппроксимации в задаче визуализации множества Парето в многомер- • ных задачах выбора из конечного числа альтернатив и кратко описываются примеры использования этого подхода.

§ 6.5 посвящен аппроксимации множеств достижимости динамических ,

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

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

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

В заключении приводятся основные результаты диссертации.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Бушенков В.А., Каменев Г.К., Лотов A.B., Черных О.Л. Использование геометрического метода для анализа эколого-экономических систем // Математическое моделирование: Процессы в сложных экономических и экологических системах / Под ред. H.H. Моисеева, A.A. Петрова и A.A. Самарского. М.: Наука, 1986. С. 240-252.

2. Каменев Г.К. Исследование итерационных методов аппроксимации выпуклых множеств многогранниками М.: ВЦ АН СССР. 1986. - 40 с. »

3. Каменев Г.К. Об одном классе адаптивных схем аппроксимации выпуклых тел многогранниками // Математическое моделирование и дискретная оптимизация. М: ВЦ АН СССР. 1988. С. 3-9.

4. Джолдыбаева С.М., Каменев Г.К. Экспериментальное исследование аппроксимации выпуклых тел многогранниками. М.:ВЦ АН СССР. 1991. -51 с.

5. Каменев Г.К. Об одном классе адаптивных алгоритмов аппроксимации выпуклых тел многогранниками // Ж. вычисл. матем. и матем. физ. 1992. Т.32. № 1.С. 136-152.

6. Джолдыбаева С.М., Каменев Г.К. Численное исследование эффективности алгоритма аппроксимации выпуклых тел многогранниками // Ж. вычисл. матем. и матем. физ. 1992. Т.32. № 6. С.857-866.

7. Каменев Г.К. Об эффективности хаусдорфовых алгоритмов полиэдральной аппроксимации выпуклых тел // Ж. вычисл. матем. и матем. физ. 1993. Т.ЗЗ. № 5. С. 796-805.

8. Каменев Г.К. Исследование одного алгоритма аппроксимации выпуклых тел // Ж. вычисл. матем. и матем. физ. 1994. Т.34. № 4. С. 608-616.

9. Бушенков В.А., Гусев Д.И., Каменев Г.К., Лотов A.B., Черных О.Л. Визуализация множества Парето в многомерной задаче выбора // Доклады Академии наук. 1994. Т.335. № 5. С. 567-569.

Ю.Каменев Г.К. Алгоритм сближающихся многогранников // Ж. вычисл. матем. и матем. физ. 1996. Т.36. № 4. С. 134-147.

11. Компьютер и поиск компромисса. Метод достижимых целей. / Лотов A.B., Бушенков В.А., Каменев Г.К., Черных О.Л. М.: Наука, 1997.-239 с.

12. Каменев Г.К. Визуальный метод идентификации параметров // Доклады Академии наук. 1998. Т.359. № 3. С. 319-322.

13. Каменев Г.К. Эффективные алгоритмы аппроксимации негладких выпуклых тел // Ж. вычисл. матем. и матем. физ. 1999. Т.39. № 3. С. 423127.

14. Лотов A.B., Бушенков В.А., Каменев Г.К. Метод достижимых целей. Математические основы и экологические приложения. The Edwin Mellen Press, Lewiston, NY, USA, 1999. - 400 с.

15. Каменев Г.К. Об аппроксимационных свойствах негладких выпуклых дисков // Ж. вычисл. матем. и матем. физ. 2000. Т.40. № 10. С. 14641474.

16. Каменев Г.К. Аппроксимация вполне ограниченных множеств методом глубоких ям // Ж. вычисл. матем. и матем. физ. 2001. Т.41. № 11. С. 1751-1760.

17. Ефремов Р.В., Каменев Г.К. Априорная оценка асимптотической эффективности одного класса алгоритмов полиэдральной аппроксимации выпуклых тел //Ж. вычисл. матем. и матем. физ. 2002. Т. 42. №1. С.23-32.

18. Каменев Г.К. Сопряженные адаптивные алгоритмы полиэдральной аппроксимации выпуклых тел // Ж. вычисл. матем. и матем. физ. 2002. Т. 42. №9. С. 1351-1367.

19. Лотов А.В., Каменев Г.К., Березкин В.Е. Аппроксимация и визуализация Паретовой границы для невыпуклых многокритериальных задач // Доклады Академии наук. 2002. Т.386. № 6. С. 738-741.

20. Каменев Г.К. Самодвойственные адаптивные алгоритмы полиэдральной аппроксимации выпуклых тел // Ж. вычисл. матем. и матем. физ. 2003. Т. 43. №8. С. 1123-1137.

21. Каменев Г.К. Метод полиэдральной аппроксимации выпуклых тел, оптимальный по порядку числа расчетов опорной и дистанционной функций // Доклады Академии наук. 2003. Т. 388. № 3. С. 309-311.

22. Kamenev G.K., Lotov A.V., van Walsum P.E.V. Application of the GRS Method to Water Resources Problems in the Southern Peel Region of the Netherlands, CP-86-19. International Institute for Applied Systems Analysis. Laxenburg, Austria, 1986. - 55 pp.

23. Lotov A. Bushenkov V., Kamenev G., Chernykh O. Method and software for decision making in public problems // Information technology and economic modeling. A joint Finnish-Soviet symposium Helsinki, Finland. Technical research center of Finland, Espoo, 1992. P. 293-308.

24. Chernykh, O.L., and Kamenev, G.K. Linear algorithm for a series of parallel two-dimensional slices of multidimensional convex polytope // Pattern Recognition and Image Analysis, 1993, 3(2), pp. 77-83.

25. Bushenkov, O.L. Chernykh, G.K. Kamenev, and A.V. Lotov. Multidimensional Images Given by Mappings: Construction and Visualization // Pattern Recognition and Image Analysis, Vol. 5, No. 1, 1995. P. 35-56.

26. Kamenev G.K. One class of effective step-by-step algorithms for polyhedral approximation // Konvexgeometrie. Mat. Forschungsinstitut Oberwolfach, Tagungsbericht. 1997. N 44. P.12-14.

27. Lotov A., Bushenkov V., Kamenev G., Loucks D., Camara A. Water Resource Conflict Resolution Based on Interactive Tradeoffs Display // Restoration of Degraded Rivers: Challenges, Issues and Experiences, ed. by D.P.Loucks, Kluwer Academic Publishers. 1998. P. 447-470.

28. Lotov A., Bushenkov V., Kamenev G. Feasible Goals Method. Search for Smart Decisions. M.: ВЦ PAH, 2001. - 239 c.

29. Lotov A.V., Bushenkov V.A., Kamenev G.K. Interactive decision maps. Approximation and Visualization of Pareto Frontier. Appl. Optimization. V. 89. Kluwer Academic Publishers. Boston, Dordrecht, New York, London. 2004. -310P.

Каменев Георгий Кириллович

Теория оптимальных адаптивных методов полиэдральной аппроксимации выпуклых компактных тел и ее применение в задачах принятия решений

Подписано в печать 09.12.2004

Формат бумаги 60x84 1/16 Уч.-изд.л. 2,3. Усл.-печ.л. 2,25 Тираж 100 экз. Заказ 55

Отпечатано на ротапринтах в Вычислительном центре им. A.A. Дородницына РАН 119991, Москва, ул. Вавилова, 40

i

Î--35Î

РНБ Русский фонд

2006-4 2369

Предисловие.

Введение.

0.1. Многогранники наилучшей аппроксимации.

0.2. Аппроксимируемость и аппроксимационное число выпуклых компактных тел (ВКТ).

0.3. Методы полиэдральной аппроксимации и их эффективность.

0.4. Обзор известных методов полиэдральной аппроксимации.

Глава 1. Адаптивные методы полиэдральной аппроксимации (АМПА).

1.1. Итерационные методы и общие аппроксимационные схемы.

1.2. Хаусдорфовы (Н-) схемы и последовательности.

1.2.1. Я-схемы.

1.2.2. Базовые методы.

1.3. Хаусдорфовы АМПА.

1.3.1. Хаусдорфовы методы.

1.3.2. Метод «Уточнения Оценок».

1.3.3. Методы «Уточнения Внешних Оценок».

1.4. Нехаусдорфовы АМПА.

Глава 2. Теория сходимости АМПА.

2.1. Теоретические основы исследования АМПА.

2.2. Метод изменения объема на итерациях АМПА.

2.3. Метод упаковок нормалей.

2.4. Метод «Глубоких Ям» (МГЯ).

2.4.1. Описание МГЯ.

2.4.2. Скорость сходимости МГЯ.

2.4.3. Эффективность МГЯ.

2.4.4. АМПА, основанные на МГЯ.

2.4.5. Исследование хаусдорфовых АМПА методом

Глубоких Ям».

2.5. Асимптотические оценки скорости сходимости, оптимальность и эффективность АМПА.

2.5.1. Аппроксимация произвольных ВКТ.

2.5.2. Аппроксимация гладких ВКТ.

2.5.3 Оптимальность по порядку хаусдорфовых АМПА.

2.5.4. Эффективность хаусдорфовых АМПА при аппроксимации гладких тел.

2.5.5. Асимптотические оценки скорости сходимости и эффективность асимптотических Я-методов.

2.6. Асимптотические оценки скорости сходимости, оптимальность и эффективность конкретных АМПА.

2.6.1 Базовые методы.

2.6.2. Метод «Уточнения Оценок».

2.6.3. Методы «Уточнения Внешних Оценок».

2.6.4. Метод «Сближающихся Многогранников».

2.7. Оценки скорости сходимости АМПА на начальном этапе.

2.7.1. Оценки скорости сходимости первых членов Н-последовательностей.

2.7.2. Оценки скорости сходимости первых членов Яг последовательностей.

2.7.3. Оценки скорости сходимости конкретных АМПА на начальном этапе.

Глава 3. Теория двойственности оптимальных АМПА.

3.1. Двойственные классы АМПА.

3.2. Двойственность хаусдорфовых АМПА восполнения и отсечения.

3.3. Методы конструирования оптимальных АМПА на основе теории двойственности.

3.3.1. Точные двойственные аналоги.

3.3.2. Двойственные методы.

3.3.3. Точные двойственные аналоги для двойственных методов.

3.3.4. Прямо-двойственные методы.

3.3.5. Комбинированные (двухфазные) методы решения смешанных задач.

3.4. Самодвойственные оптимальные АМПА.

3.4.1. Необходимость разработки самодвойственных методов.

3.4.2. Описание самодвойственных методов.

3.4.3. Скорость сходимости самодвойственных методов.

3.4.4. Оптимальность и эффективность самодвойственных методов

Аппроксимация многогранниками является традиционным средством теории выпуклых множеств. Первые аппроксимационные теоремы восходят к Минковскому [145]. В частности, Минковским было доказано, что для каждого выпуклого тела можно найти сходящуюся последовательность выпуклых полиэдров, аппроксимирующих это тело. Эти утверждения широко использовались (см., например, [1]) для получения результатов, связанных с геометрией выпуклых поверхностей. Однако долгое время интерес к задаче был сугубо теоретическим.

На важность практической полиэдральной аппроксимации, возможно, впервые указал Л.С.Понтрягин в предисловии ко второму изданию классической работы [76] в связи с проблемой построения множеств достижимости динамических систем. Эта концепция была развита в работах [83], [59]-[61]. В настоящее время задача аппроксимации выпуклых компактных тел многогранниками возникает во многих приложениях: в математическом программировании [74], кодировании изображений [159] и др. На целесообразность использования аппроксимации выпуклых компактных тел в многокритериальных задачах принятия решений указывали Н.Н. Моисеев [71] и Г.С. Поспелов [77]. Важное практическое значение вычислительные алгоритмы полиэдральной аппроксимации выпуклых компактных тел имеют в задачах принятия решений на основе использования математических моделей в методе обобщенных множеств достижимости (ОМД), разрабатываемого в ВЦ РАН, начиная с 70-х годов, группой исследователей под руководством А.В. Лотова (обзор этого направления дан в [66], [67], [135], [136]).

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

В отличие от физики (и особенно механики), в которых математические модели являются продуктом многовековых исследований и успешного опыта использования, математические модели экономических систем, особенно экономических систем, порождающих экологические проблемы, описывают реальность недостаточно точно, а зачастую дают и качественно неверные предсказания. «Пока еще нет надежных общих принципов математического описания процессов самоорганизации в экономике, поэтому единственным критерием качества модели остается ее способность воспроизвести данные об эволюции изучаемой экономической системы. Мы не имеем в виду то, что принято называть идентификацией или верификацией модели. В конце концов, обычно модель содержит достаточно параметров, чтобы подогнать ее к конкретному набору данных. Речь идет о том, чтобы в рамках единой теории, основанной на немногих предположениях, адекватно отразить всю совокупность качественных особенностей эволюции изучаемой системы. Только в таком случае появляется уверенность, что наши гипотезы достаточно верно отражают природу вещей. Это обычные стандарты качества, принятые в физике» [75]. Поэтому отношение к результатам моделирования как к чему-то безусловному, столь естественное в механике, недопустимо в системах поддержки принятия решений по эколого-экономическим вопросам. Однако и здесь за последние десятилетия достигнут достаточный прогресс, позволяющий говорить о задачах принятия решений с использованием экономических моделей. «Опыт нам дал уверенность, что системный анализ развивающейся экономики позволяет предсказывать в известных условиях эволюцию экономической системы и оценивать последствия экономических решений» [75].

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

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

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

Важным отличием адаптивных методов полиэдральной аппроксимации от методов приближенного описания с помощью отдельно взятых выпуклых тел (таких, как симплекс, параллелепипед, эллипсоид, цилиндр: см., например, обзоры теории в [109], [112]) является возможность аппроксимации выпуклых компактных тел с любой степенью точности. За это преимущество, однако, приходится платить высокую цену: как показывают теоретические оценки ([103], [6], [157], [118] и др.), а также экспериментальные и прикладные исследования ([81], [33], [21], [22], [128], [7], [9], [25]), сложность описания аппроксимирующего многогранника быстро растет с увеличением точности и ростом размерности аппроксимируемого тела. Тем не менее, в задачах принятия решений необходимо использовать методы, обеспечивающие возможность аппроксимации с любой (заранее не известной) степенью точности в связи с тем, что для исследователя важна форма и конкретное расположение паретовой границы аппроксимируемого множества, а не только область, где это множество находится.

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

До 80-х годов прошлого столетия методы построения полиэдральных аппроксимаций выпуклых тел размерности, большей двух, существовали, в основном, "на бумаге" и вытекали из конструкций, использовавшихся при получении соответствующих оценок в теории оптимальной полиэдральной аппроксимации (см. [145], [144], [103], [6], [153] и более поздние работы этого направления [110], [111], [ИЗ], [114], [140], [141], [94]). В 80-х годах стандартный подход к построению многогранников, аппроксимирующих выпуклые множества, стал основываться на расчете значений опорной функции аппроксимируемого множества на некоторой заданной сетке направлений (см., например, [81], [17]). Было, однако, показано [159], [160], что использование заранее заданных (так называемых неадаптивных) сеток направлений не позволяет эффективно аппроксимировать многомерные множества, особенно в негладком случае.

С 80-х годов в ВЦ РАН в рамках метода ОМД развивались теория и практика адаптивных итерационных методов полиэдральной аппроксимации. В частности, был разработан адаптивный метод «Уточнения Оценок» (см. историю его создания в [66]), который показал себя практически пригодным для аппроксимации выпуклых ОМД большой размерности. С обобщения и исследования этого метода на основе теории оптимальной полиэдральной аппроксимации выпуклых тел и было начато развитие теории оптимальных адаптивных методов полиэдральной аппроксимации, рассматриваемой в настоящей работе.

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

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

Во введении дан обзор существующих теории и методов полиэдральной аппроксимации выпуклых компактных тел.

В § 0.1 дан обзор существующей теории оптимальной полиэдральной аппроксимации выпуклых компактных тел. Центральным понятием теории полиэдральной аппроксимации выпуклых компактных тел является понятие многогранника наилучшей аппроксимации, на котором достигается наибольшая точность приближения для определенной метрики в заданном классе аппроксимирующих многогранников (например, вписанных с ограниченным числом вершин или описанных с ограниченным числом гиперграней). В параграфе приводятся известные оценки зависимости наилучшей достижимой точности от сложности описания аппроксимируемого многогранника (зависимости отклонения от числа вершин или гиперграней многогранника наилучшей аппроксимации). Оказывается, что, согласно существующей теории, для произвольного выпуклого компактного тела верхняя оценка точности обратно пропорциональна числу вершин (гиперграней) в степени 2/(d-\), где d - размерность пространства. При этом для широкого класса тел, включающего в себя тела с частично гладкой границей, эта оценка неулучшаема.

В § 0.2 приводится аппарат, предложенный, главным образом, в [157] и [53] и используемый в диссертации для описания сходимости многогранников к выпуклым телам со скоростью, по порядку большей 2/(d-l).

В § 0.3 рассматриваются методы полиэдральной аппроксимации, вводится понятие эффективности этих методов и их оптимальности по порядку при аппроксимации как отдельных тел, так и их классов. Рассматривается различие между адаптивными и неадаптивными методами.

В § 0.4 приводится краткий обзор известных методов полиэдральной аппроксимации. Значительная часть из них носит теоретический характер и содержится в доказательствах различных утверждений, касающихся возможностей аппроксимации выпуклых тел многогранниками. В конце параграфа приводится обзор адаптивных методов полиэдральной аппроксимации, в том числе метода «Уточнения Оценок», обобщением которого явилась теория, рассматриваемая в настоящей работе.

В первой главе развивается теория адаптивных методов полиэдральной аппроксимации, вводятся классы хаусдорфовых методов, а также приводятся примеры конкретных методов из этих классов. Теория хаусдорфовых адаптивных методов полиэдральной аппроксимации была развита автором в работах [35], [36], [37], [38], [39], [41], [44], [45], [46].

В § 1.1 вводятся основные понятия теории итерационных методов полиэдральной аппроксимации. Рассматриваются две основные общие схемы аппроксимации - схема восполнения и схема отсечения, изучаемые в диссертации в дальнейшем. Эти схемы отличаются тем, что в схеме восполнения на каждой итерации к вписанному аппроксимирующему многограннику добавляется некоторая граничная точка аппроксимируемого тела, а в схеме отсечения на каждой итерации описанный аппроксимирующий многогранник усекается некоторой опорной гиперплоскостью аппроксимируемого тела. Показано, что конкретные методы полиэдральной аппроксимации отличаются, прежде всего, способом выбора присоединяемой точки или отсекающей гиперплоскости.

В § 1.2 на основе схем восполнения или отсечения даются определения классов хаусдорфовых или Я-последовательностей вписанных (описанных) многогранников, неявно характеризующие классы адаптивных методов полиэдральной аппроксимации (Я-схем), порождающих их. Помимо класса Я-последовательностей (методов) вводится класс Н\-последователыюстей (методов) с более сильными свойствами.

В § 1.3 рассматриваются примеры методов, которые, как доказывается, относятся к классу хаусдорфовых методов: метод «Уточнения Оценок» (см. выше) в упрощенной абстрактной формулировке автора [32], [33], [38] и предложенный автором метод «Уточнения Внешних Оценок» [44].

В § 1.4 приводится пример нехаусдорфового метода - рассматривается предложенный автором метод «Сближающихся Многогранников» [39], сочетающий в себе схемы отсечения и восполнения.

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

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

Параграф 2.1 - вводный. В § 2.2 излагается метод изменения объема на итерациях, который дает наиболее сильные оценки при исследовании скорости сходимости Я-методов, при исследовании скорости сходимости на начальном этапе аппроксимации, а также при исследовании нехаусдор-фовых методов.

В § 2.3 излагается метод упаковок нормалей на внешне-параллельном множестве, который дает наиболее сильные оценки при исследовании скорости сходимости Я]-методов при аппроксимации негладких тел.

В § 2.4 излагается метод «Глубоких Ям», который позволяет получить наиболее сильные результаты для оценки скорости сходимости хаусдорфовых алгоритмов в гладком случае, а также имеет самостоятельное значение.

В § 2.5 дана сводка результатов исследования скорости сходимости хаусдорфовых методов, полученных различными методами, выделены наилучшие оценки и рассмотрен вопрос об эффективности и оптимальности методов из рассматриваемого класса. В частности, показано, что в классе гладких тел асимптотическая скорость сходимости Н-последовательностей многогранников отличается от асимптотической скорости сходимости многогранников наилучшей аппроксимации на константу, не зависящую от аппроксимируемого тела. Для Н\-последовательностей (и порождающих их методов) показано, что они оптимальны по порядку числа вершин (последовательности восполнения) и гиперграней (последовательности отсечения) в широком классе выпуклых тел, для которого порядок 2/(d-l) является неулучшаемым. Отметим, что это - единственный известный в настоящее время класс методов с такими свойствами.

В § 2.6 сформулированы основные результаты изучения скорости сходимости и эффективности конкретных методов, введенных в гл. 1. Эти результаты являются приложением теории скорости сходимости в классе хаусдорфовых методов к исследованию конкретных представителей из этого класса. В частности, показано, что для любого выпуклого компактного тела методы «Уточнения Оценок» и «Уточнения Внешних Оценок» сходятся не хуже, чем со скоростью, имеющей порядок 2/{d-\). Таким образом, эти методы являются оптимальными по порядку числа вершин (метод «Уточнения Оценок») и числа гиперграней (методы «Уточнения Внешних Оценок») в классе тел, для которых этот порядок является неулучшаемым. Кроме того, показано, что указанные методы являются асимптотически эффективными в классе тел с гладкой границей и положительными главными кривизнами, причем достигаемая с их помощью точность асимптотически не более чем в четыре раза хуже точности аппроксимации многогранниками наилучшей аппроксимации с тем же числом вершин или гиперграней.

В заключение параграфа рассматривается скорость сходимости метода «Сближающихся Многогранников». Этот метод, как и хаусдорфовы методы, основан на общих адаптивных схемах восполнения и отсечения. Однако, как уже отмечалось, он не принадлежит к классу Я-методов. Поэтому для его исследования используется аппарат изучения изменения объема на итерациях, развитый в § 2.2. В результате этого исследования, в частности, показано, что метод «Сближающихся Многогранников» в классе тел с гладкой границей и положительными главными кривизнами оптимален по порядку числа вершин внутренних, гиперграней внешних многогранников и по числу задач вычисления опорной функции. Оптимальность по числу задач вычисления опорной функции - уникальное свойство этого метода, отличающее его от других методов, рассматриваемых в настоящей работе.

В § 2.7 изучена скорость сходимости рассматриваемых в диссертации методов на начальном этапе аппроксимации. Полученные результаты позволяют рассчитывать скорость сходимости этих методов на начальном этапе для любых тел (в том числе и при аппроксимации многогранников).

В третьей главе излагается теория двойственности для адаптивных методов полиэдральной аппроксимации, развитая автором в [43], [44], [45], [46]. Необходимость применения теории двойственности в задачах полиэдральной аппроксимации возникает, прежде всего, в случае использования двойственного описания аппроксимируемого тела (через опорную / дистанционную функции), при аппроксимации многогранниками с двойственным описанием (гиперграни / вершины). Эта теория устанавливает взаимосвязь между рассматриваемыми в диссертации хаусдорфовыми методами восполнения и отсечения, позволяет разрабатывать новые методы, а также имеет самостоятельное значение.

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

В § 3.2 устанавливается факт двойственности Н- и //рпоследовательностей восполнения и отсечения: последовательность из многогранников, полярных к многогранникам Я- (Яр) последовательности восполнения, оказывается Я- (Яг) последовательностью отсечения для полярного тела и наоборот.

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

В § 3.4 рассматривается вопрос построения методов, оптимальных по порядку числа решений задач оптимизации на аппроксимируемом теле для негладких тел. В параграфе рассматриваются методы, состоящие одновременно из Ярметода восполнения (отсечения) и метода отсечения (восполнения) из класса, двойственного к нему. Такие методы мы называем самодвойственными. В параграфе приводится описание двух самодвойственных методов, предложенных автором [44], [45], [46], получены верхние оценки их скорости сходимости, имеющие порядок 2/(d-l). Показано, что в классе тел, для которых этот порядок является неулучшаемым, они являются оптимальными по порядку числа вершин вписанных, гиперграней описанных аппроксимирующих многогранников, по числу вычислений опорной и дистанционной функций, т.е. числу решений задач выпуклой оптимизации на аппроксимируемом теле.

В главе 4 исследуется наилучшая достижимая точность аппроксимации двумерных выпуклых компактных тел многоугольниками и получена новая оценка скорости сходимости многогранников наилучшей аппроксимации [42].

Как уже говорилось выше, про минимальное число вершин многогранника, необходимое для получения аппроксимации с заданной точностью, известно только, что оно (точнее, его порядок - аппроксимационное число тела) имеет верхнюю оценку вида (d-l)/2. Т.е. в двумерном случае {d=2) минимально необходимое число вершин оценивается по порядку обратной величиной к корню от требуемой точности и не зависит от свойств гладкости аппроксимируемого тела. Ясно, что в случае, когда аппроксимируемым телом является, например, многогранник, эта оценка является очень грубой. Более тонкие верхние оценки в общем случае отсутствуют. Единственным известным (двумерным) результатом в этом направлении можно назвать работу [140], в которой показано, что при аффинной длине границы аппроксимируемого диска, равной нулю, многоугольник наилучшей аппроксимации в метрике объема симметрической разности сходится быстрее, чем с порядком (d-1)/2. Вместе с тем, какой порядок будет в этом случае, работа [140] не указывает. Исследование, приведенное в гл. 4, устанавливает связь между верхней оценкой скорости сходимости многоугольника наилучшей аппроксимации и метрическими свойствами (в частности, размерностью) множества крайних точек аппроксимируемого диска.

В § 4.1 приводятся известные аппроксимационные свойства выпуклых дисков. В § 4.2 развивается аппарат, необходимый для описания различных типов сходимости многогранников к выпуклым телам. В § 4.3 описывается предложенная автором модификация метода «Уточнения Оценок» - хаусдорфовый метод «Экстремальных Ям» [42].

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

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

В § 4.7 в качестве примера использования техники исследования, развитой в четвертой главе, рассматривается один класс двумерных дисков с бесконечным (счетным) числом вершин. В этом случае удается аналитически рассчитать нижнюю скорость сходимости многоугольников наилучшей аппроксимации и сравнить её с верхней оценкой, получаемой по рассмотренной в главе методике. Показано, что полученные таким образом оценки совпадают. Кроме того, впервые показано, что существуют диски, для которых многоугольники наилучшей аппроксимации (и метод «Экстремальных Ям») сходятся с любой, сколь угодно большой полиномиальной скоростью.

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

В § 5.1 рассматриваются задачи и общая методика численного исследования эффективности методов полиэдральной аппроксимации. Собственно методика исследования была разработана в работах [32], [33].

В § 5.2 в качестве объектов аппроксимации выбраны многомерные телесные эллипсоиды. Важность исследования эффективности алгоритмов в классе эллипсоидов определяется тем фактом, что эллипсоиды являются наиболее сложным объектом при аппроксимации в метрике объема симметрической разности. Кроме того, этому классу принадлежит шар, являющийся наиболее сложным объектом при аппроксимации в метрике Хаусдорфа. Основным результатом данного параграфа является сведение задачи расчета константы аппроксимируемости в классе многомерных эллипсоидов к обычному интегрированию по прямоугольной области. Это позволяет проводить исследование методов в классе эллипсоидов в полном объеме.

В § 5.3 излагаются результаты различных численных исследований метода «Уточнения Оценок» в классе многомерных эллипсоидов. В § 5.4 кратко излагаются результаты исследований других адаптивных методов по разработанной методике.

В § 5.5 рассматриваются численные эксперименты по аппроксимации введенного в § 4.7 класса выпуклых дисков со счетным числом вершин и нетривиальной (лежащей между 0 и х/г) верхней оценкой для аппроксимационного числа.

В § 5.5 пятой главы рассматриваются основные выводы из приведенных в диссертации экспериментальных исследований.

Глава шестая посвящена вопросам практического применения оптимальных адаптивных методов полиэдральной аппроксимации в задачах принятия решений, главным образом, в рамках метода ОМД.

В § 6.1 приводится математическое описание метода ОМД, рассматриваются некоторые особенности использования в нем адаптивных методов полиэдральной аппроксимации, а также вопросы визуализации аппроксимирующих многогранников в данном подходе. Предлагается разработанный автором (совместно с O.JI. Черных) [101] быстрый алгоритм построения больших серий сечений выпуклых многогранников.

В § 6.2 приводится пример использования описанных в диссертации адаптивных методов полиэдральной аппроксимации для анализа экономических и экологических аспектов проблемы распределения водных ресурсов в регионе с развитым сельским хозяйством. За основу модели, используемой в исследовании, принята модель, разработанная в Международном институте прикладного системного анализа [148]. Отметим, что используемая модель отличается очень подробным описанием производственных процессов. В связи с этим расчет опорной функции аппроксимируемого ОМД требовал значительного времени, что во многом способствовало развитию существующих и появлению новых методов аппроксимации выпуклых тел, изложенных в первой главе.

В § 6.3 рассмотрена методика многокритериального анализа эколого-экономических проблем методом ОМД в целом и кратко охарактеризованы прикладные исследования, основанные на использовании адаптивных методов полиэдральной аппроксимации в рамках метода ОМД.

В § 6.4 рассматривается применение адаптивных методов полиэдральной аппроксимации в задаче визуализации множества Парето в многомерных задачах выбора из конечного числа альтернатив [20], [13] и кратко описываются примеры использования этого подхода.

Параграф 6.5 посвящен аппроксимации множеств достижимости динамических моделей, описываемых системами управляемых дифференциальных уравнений или дифференциальными включениями. Различные методики построения явного описания этих множеств были предложены А.В. Лотовым (см. § 5.6 работы [66]). В параграфе рассматриваются, главным образом, вопросы использования оптимальных адаптивных методов полиэдральной аппроксимации для аппроксимации множеств достижимости.

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

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

В заключении приводятся основные результаты диссертации.

Результаты, нашедшие отражение в диссертации, докладывались на следующих совещаниях, конференциях и семинарах: на Всесоюзной конференции «Теория, методология и практика системных исследований» (Москва, 1985), на конференции «Математические методы управления и обработки информации» (Москва, 1985), на семинаре «Многокритериальные задачи математического программирования» Всесоюзного научно-исследовательского института системных исследования (Москва, 1985), на методологическом семинаре «Методы имитационного моделирования экономических объектов» Центрального экономико-математического института АН СССР (Москва, 1985), на заседаниях школы-семинара ИВЕРСИ-85 «Системные и прикладные аспекты диалога на персональных ЭВМ» (Тбилиси, 1985), на IX Всесоюзном симпозиуме «Системы программного обеспечения решения задач оптимального планирования» (Москва, 1986), на конференции молодых ученых Вычислительного центра АН СССР (Москва, 1988), на Советско-финском симпозиуме "Information technology and economic modeling" (Хельсинки, Финляндия 1992), на международной конференции «Konvexgeometrie» (Обервольфах, ФРГ 1997), на 2-й Московской международной конференции по исследованию операций (Москва, 1998), на научной сессии «Проблемы прикладной математики и информатики» Вычислительного центра РАН (Москва, 2000), на 3-й Московской международной конференции по исследованию операций (Москва, 2001), на научной конференции «Математика, Механика и Информатика 2002», поев. 10-летию РФФИ (Москва, 2002), на научной конференции «Математические модели сложных систем и междисциплинарные исследования», поев. 85-летию академика

Н.Н.Моисеева (Москва, 2002), на 58-й Конференции Европейской рабочей группы «Поддержка многокритериального принятия решений» (Москва,

2003), на международной конференции «Математическое моделирование социальной и экономической динамики» (Москва, 2004), на 4-й Московской международной конференции по исследованию операций (Москва,

2004), и на ряде семинаров МГУ (Механико-математический факультет: семинарах кафедр математического анализа, теории чисел и дискретной математики; факультет Вычислительной математики и кибернетики: семинар кафедры оптимального управления), института Проблем механики РАН, Московского физико-технического института, Вычислительного центра РАН им. А.А. Дородницына.

Основные результаты диссертации опубликованы в 29 работах: [13], [14], [21], [22], [28], [33], [35]-[46], [66], [67], [97], [101], [120], [124], [135]-[138], из них четыре книги [66], [67], [135], [136]: [67] в соавторстве с А.В. Лотовым, В.А. Бушенковым и O.J1. Черных; [66] главы 1-5 в соавторстве с А.В.Лотовым и В.А. Бушенковым, гл. 8 - самостоятельно; [135] в соавторстве с А.В. Лотовым и В.А. Бушенковым; [136] главы 1-6 в соавторстве с А.В. Лотовым и В.А. Бушенковым, гл. 8 - самостоятельно.

Идеи данной работы получили свое развитие в исследованиях [7]-[10], [24]-[26], [68], [99], [119], [131]-[134] и [158], проведенных на основе методик, разработанных автором.

Работа по настоящей диссертации выполнялась при финансовой поддержке РФФИ (коды проектов 95-01-00968, 98-01-00323, 01-01-00530, 04-01-00662), по программе поддержки ведущих научных школ (коды проектов 00-15-96118, НШ-1843.2003.1), при поддержке программы №3 фундаментальных исследований ОМН РАН «Вычислительные и информационные проблемы решения больших задач» и программы фундаментальных исследований РАН «Математическое моделирование и интеллектуальные системы».

Введение

Во введении будет дан обзор существующих теории и методов полиэдральной аппроксимации выпуклых компактных тел.

0.1. Многогранники наилучшей аппроксимации

Рассмотрим евклидово пространство Ed со скалярным произведением <-,->, расстоянием Д-,-), нормой ||-|| и Лебеговой мерой ju. Пусть Br{z) обозначает замкнутый шар радиуса г с центром в z, в1 - единичныи шар с центром в начале координат, 5й1 - сферу направлений, т.е. границу В1, и пусть 7td := ДЯ*). Для s, 0 <f,HXcErf обозначим

Х\е := {jcgE^: р(х, X) < s), {Х)£ := {xeEd: р(рс, Х)<е}. Множество KaEd называется конусом, если для любого xgK и Я, 0<Я, справедливо АхеК. Множество CczEd называется выпуклым, если (1

Л)х+Лу е С для всех х, уеС и 0<А<1. Выпуклой оболочкой множества ХсШ? называется множество conv X, являющееся пересечением всех выпуклых множеств, содержащих X. Выпуклой конической оболочкой множества XaEd называется множество cone X, являющееся пересечением всех выпуклых конусов, содержащих X. Для двух выпуклых множеств С\ и С2 введем обозначение выпуклого множества

С, + С2 := {zgEd: z=x+y, xgCu xeC2} сумма по Минковскому). Для AeM и выпуклого С обозначим

АС := {zeErf: z= Ах, хеС}. Для Л>0 введем внешнее и внутреннее параллельные множества как СЯ:=С + В№= №(*), C.A:={zeEd:B,(z)aC}. хеС

Ясно, что в нашем случае [СЦ = Сл> Л>0. Через proj (jc, X) обозначим проекцию точки х на множество X, через card Х- мощность множествах

Обозначим через с€ класс выпуклых компактных множеств с непустой внутренностью, т.е. выпуклых компактных тел (ВКТ). В случае d = 2 говорят также о выпуклых дисках. Через дС обозначим границу тела С, через int С - множество его внутренних точек, через со(С) - его асферичность (минимальное отношение радиусов концентрических внешнего R(C) и внутреннего г(С) шаров) и через a(Q - его поверхностный объем (см. [58]). Обозначим через %f класс ВКТ с s раз непрерывно дифференцируемой границей, и пусть %* - класс ВКТ с 5 раз непрерывно дифференцируемой границей положительными главными кривизнами, s > 2. ВКТ из класса W+2 называют иногда «овалоидами». ВКТ из класса мы будем иногда в тексте, для краткости, называть гладкими телами. Для s>2 через Гтт{С) и гтах(С) обозначим минимальный и, соответственно, максимальный радиусы кривизны дС, Cg%'s.

Пусть ff, if а % - класс выпуклых телесных многогранников (выпуклых оболочек конечного множества точек, не лежащих в одной гиперплоскости). Для PgW через Л/(Р) обозначим множество его вершин, а через т'(Р) - число его вершин, через А/(Р) обозначим множество векторов единичных внешних нормалей к его гиперграням (граней максимальной размерности), а через - число его гиперграней. Для Се'ё'введем класс .f\C) внутренних многогранников, вершины которых принадлежат дС (вписанных многогранников), и класс &с(С) внешних многогранников, гиперграни которых касаются дС (описанных многогранников). Определим также классы

Ут(С) := {Pg ,¥(С): т'(Р) < т}, ifm(C) := {Pg У>%С): п/(Р) < т}}

Рассмотрим традиционные для рассматриваемой задачи метрики на св (см. [109], [112]): метрику Хаусдорфа (метрику Бляшке)

С2) := шах {sup{p(x, C2):xeCi}, sup{p(x, Ci):xeC2}}

1 В работах [109]-[116] для класса ,fcm{C) используется обозначение .У>С(т)(С). и метрику объема симметрической разности (Никодимову метрику)

5*(СЬС2) :=/i(C,AC2), где С,ДС2 := (С1\С2)и(С2\С1).

В дальнейшем, где это возможно, будем опускать индексные обозначения. Так, через 5 будем обозначать ё1 и 3s, через &т(С) будем обозначать Ут{С) и &ст{С), через &{С) будем обозначать для любых m>d+1, через М(Р), т{Р) будем обозначать Л/(Р), т'(Р) для Ре^(С) и Л/(Р), п/(Р) для Ре^с(С). Обозначим также

S{С, :UQ) ■= inf Р): Рс У>т{С)}.

Пусть := ЕА{0},

Сс??: {0} е int С} - класс ВКТ, содержащих внутри себя начало координат,:= %Щ(С)

Для и е Eod введем обозначения опорной функции g(u, С) := шах {<и, х>: хеС}, опорного полупространства

L(u, С) := {jcgE^: <и, х> < g(u, С)}, опорной гиперплоскости l(u,C) := <и, x> = g(u, С)}, множества точек касания

Т(и,С) := {редС: <и, р> = g(u, Q} и конуса внешних единичных нормалей в граничной точке редС

S{p,С) := {ueS?'1: <u,p> = g(u, С)}. Для произвольногореК* нам будет удобно использовать обозначения g(u,p):=<u,p>, 1{и, р) := <и, х> = <и, р>},

Ци, р) := <и, х> < <и, р>}, что, очевидно, не противоречит введенным ранее определениям опорных функции, гиперплоскости и полупространства.

Пусть Се.% и через g*(x, C):=min {Л>0: хеЛС} обозначим дистанционную [58] {калибровочную [80] или Минковского) функцию для С. Из определения дистанционной функции следует, что g*(x, СИ|х||/||хо||, где х<у=\о, х)с\дС - точка пересечения луча, исходящего из начала координат и проходящего через х, и границы тела С (см. [58], замечание 11.1). Эту точку хо обозначим через t(x, Q :=x/g*(x, Q е дС, хеЕ</.

Пусть о)о(С) есть минимальное отношение радиусов Rq(C) внешнего и г0(С) внутреннего шаров с центрами в начале координат. Ясно, что <у0 (Q>aKQ.

Пусть С eft. Точку zgC будем называть экстремальной, если она не допускает представления в виде (1 -Л)х+Лу, где х,уеСи0<Л<1. Множество экстремальных точек тела С обозначим через ext С. Точку zeC будем называть экспонированной, если Cn/(u,C)={z} для некоторого ueS(z,C). Множество экспонированных точек тела С обозначим через ехр С. Точку zeC будем называть дальней, если существует шар, описанный вокруг С и содержащий z на своей границе. Множество дальних точек тела С обозначим через ехр* С.

Через constat. будем обозначать положительные константы, зависящие от параметров а,Ь,.

Пусть задано некоторое Cerff. Классическим результатом теории выпуклых множеств (см. [109], [115]) является тот факт, что для метрики 5 (т.е. S1 и Ss) в классе ,%,(С) (т.е. У1т{С) и ^т(С)) найдется многогранник не обязательно единственный, на котором достигается д(С,.гУт(С)). Этот многогранник называется многогранником наилучшей аппроксимации

МНА)2:

S(С, Щ = <5(С,

Даже для двумерных тел задача нахождения МНА чрезвычайно сложна (за исключением простейших специальных случаев) ([110], [112]). Вместе с тем МНА могут служить эталоном полиэдральной аппроксимации ВКТ. Поэтому приведем необходимые нам известные оценки зависимости минимальной неточности аппроксимации Cfm(C)) от числа вершин (гиперграней) МНА т. Прочие сведения о МНА можно почерпнуть из обзоров[110], [112], [115]. Прежде всего, известно, что lim S(C,tfm) = 0. (0.1.1) т—>оо

Впервые этот факт (для внутренних многогранников) доказан, по-видимому, в [145]. Для классов iPlm{C) и Уст(С) это свойство вытекает, например, из следующих верхних оценок, полученных независимо в [103] и [6]:

COnstr J я

0.1.2)

Нижние оценки скорости сходимости МНА рассмотрим сначала для точно гладких те ченнаяв [157] и [118]: достаточно гладких тел. Для Се%-2 справедлива следующая оценка, полуconstr ,/ х

S(c,rfm)> СД*. (0.1.3) т к '

2 Этот результат настолько «классический», что мы нигде не нашли его доказательства. Впрочем, существование МНА нетрудно доказать, перейдя в пространство Emrf и рассмотрев, например, множество C"cEmrf, состоящее из точек с координатами т (^-мерных) точек тела С. Очевидно, что это множество компактно как декартово произведение компактов С. Пусть сеЕ""* и tf. Emd —> Erf есть проекция j-го ^/-мерного картежа координат. Тогда

М{д(С, Р(с)): Р(с)=conv {хи . *«},*,=//с), се С} достигается, так как д{С, Р(с)) непрерывно зависит от с. При этом возможное совпадение точек не выводит из класса Wm(C).

Более того, результаты исследований [153], [154] (метрика S1 и CgK3) [1Ю], [111], [113], [114] (метрика ё1 и условие Се св+ , а также метрика показывают, что для Се г6+2 справедливо более сильное утверждение: constr и х

0.1.4)

При этом из [153] следует, что (0.1.4) справедливо, если граница дС является кусочно-гладкой, т.е. состоит из конечного числа гиперповерхностей класса С3 с положительными главными кривизнами (см. замечание в конце настоящего следующего пункта).

Рассмотрим значения констант из (0.1.4) в асимптотике.

Пусть рассматривается метрика 81 и Cetf. Тогда, согласно [105] (d= 2,3), [153], [154] С^3), [113] (%2) и [94] (<справедливо

1 (ч lim 5й{C,ym)m2l{d-X) =- -t±Lrkc(x?'2 da(x) , (0.1.5) где 19/ есть плотность покрытия пространства Е' шарами фиксированного радиуса (см. [79]), Жа :=

- объем единичного шара, к^х) -кривизна Гаусса-Кронекера (произведение главных кривизн) в точке хедС и о(х) - элемент поверхностного объема в точке х. Заметим, что точно известны только величины «9i=l и

Оценки для остальных величин «9/ могут быть найдены, например, в [54]. Отметим, что члены следующего порядка малости по т в асимптотике вида (0.1.5) рассмотрены для метрики Хаусдорфа, например, в [95].

Рассмотрим метрику и пусть CeW2. Тогда, согласно [110], [111], [114] (%2) и [94] (9?), существуют константы deUi и div^i (триангуляционные числа Делоне и Дирихле-Вороного, соответственно), зависящие только от d, что lim 8s{C^m)m2'^=\del^^^W1^^^^^-^ , (0.1.6) от—>0О lim 8\С,*>ст)т2'^ =|div,1(Lkc{xf^Ua{x))d+md'X). (0.1.7)

И->00 2

При этом точно известны только значения deli=l/6, del2=l/(2V3), divi=l/12, div? =5/(18л/3). Отметим, что члены следующего порядка малости по т в асимптотиках вида (0.1.6)-(0.1.7) рассмотрены для метрики объема, например, в [117].

Таким образом, степень 2/(^-1) в оценках (0.1.2)-(0.1.4) для Се^2 не-улучшаема. Обратимся к нижним оценкам для тел с негладкой границей. Очевидно, что для любого Ре.'справедливо

8(Р, &т(С)) — 0,т> т(Р). (0.1.8)

В случае, когда число экстремальных точек аппроксимируемого тела не является конечным, возможны скорости сходимости промежуточные между (0.1.4) и (0.1.8). Согласно [140], при ch2 для произвольного справедливо lim Ss(Cym)m2 =—(L,kc(x)V2 da(x)f, (0.1.9) /Я—>oo 12 где кривизна kdpc) определена почти везде на границе дС и интеграл рассматривается как Лебегов. Соответственно, при условии jdckc(x)y3da(x) = 0 (0.1.10) мы получаем скорость сходимости со степенью большей, чем 2/(^-1). Однако результат [140] не дает определить эту степень. Существующий аппарат, который позволяет оценивать скорость сходимости МНА в этом случае, вместе с необходимыми для дальнейшего изложения нашими добавлениями излагается в следующем пункте.

0.2. Аппроксимируемость и аппроксимационное число выпуклых компактных тел (ВКТ)

В этом разделе будет изучаться только метрика Хаусдорфа, так как для метрики симметричной разности содержательные результаты в негладком случае отсутствуют. Для характеристики аппроксимационных свойств негладких тел введем следующие понятия. Пусть Се(€. Пусть s>0. Обозначим а\С):= liminfт[зн(С,!Ут)], а*(С)limsupmid"{С,(?„,)[. т^СО /И—>00

В [157] для характеристики нижней границы скорости сходимости МНА введена величина а(С) := inf{s>0:as(C) = 0} и названа аппроксимационным числом тела С. Поскольку нас интересуют верхние границы скорости сходимости методов полиэдральной аппроксимации (а значит, как эталона и МНА), то назовем эту величину нижним аппроксимационным числом С. Введем верхнее аппроксимационное число тела С [42] как а(С) := inf{5 > 0:а\С) = 0}. Очевидно, что а(С)<а(С), и в случае равенства этих величин можно говорить об ашроксимационном числе а(С). Из (0.1.2) следует, что а(С)<^, (0.2.1) причем из (0.1.4) следует, что при С&(€+ справедливо а(С) = (d-l)/2.

Для дальнейшего изложения нам понадобится дать ряд определений из теории размерности Хаусдорфа (см., например, [19], [143]).

Пусть R - пространство с метрикой р. Для UdR через D(U) обозначим диаметр множества

D(U) := sup {р(х, у): х,уе U} (примем, что D(0)=0 и D(Uf= 1). Пусть s - произвольное действительное число, 0 < s < оо. Для ЛсМ ие>0 обозначим mf (А) := infj !£>(£,У : А с= \JE„E, е R, ОД) <

Определим ^-размерную меру Хаусдорфа как supm^(^) = limmf (А). eiO

Определим размерность Хаусдорфа как единственное число dim А, такое что ms(A)=cc при 0 < s < dim А и при dim А.< s < оо. Более формально, dim А := sup{s>0: т5(Л)>0}= sup{s>0: т5(Л)=оо} = = inf{s>0: тХ^)<оо} = inf{s>0: т,(Л)=0}. В [157] получена нижняя оценка нижнего аппроксимационного числа а(0, равная половине хаусдорфовой размерности множества дальних точек С (экстремальных точек, в которых существует внешняя касательная к телу окружность): а(С) > ^ dim ехр* С. (0.2.2)

В работе [157] из (0.2.2), как более общего результата, следует (0.1.3): при Се%2 имеем ехр*С = дС, откуда a(Q =a(Q = (d-1)/2. При этом, как показано в [157], для любого s, 0 < s < 1/2, существует выпуклый диск С, такой что а(С) = s.

Поскольку для нас важны верхние границы скорости сходимости неточности в методах аппроксимации, то в настоящей работе нас будет интересовать верхняя оценка верхнего аппроксимационного числа а(С), для негладких тел более сильная, чем (0.2.1). Для получения верхних оценок использовать аппарат хаусдорфовых мер затруднительно по следующей, например, причине. Пусть имеется счетная совокупность множеств {Ah /=1,2,.} из М. Тогда, согласно, например, [143],

00 dim \J А/ = sup {dim Al: / = 1,2.}. (0.2.3) i=\

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

Для получения верхних оценок сходимости методов полиэдральной аппроксимации нами будет использован аппарат метрической размерности, или размерности Минковского (см. гл. 4 или, например, [53], [143]).

В [42] показано (см. в настоящей работе теорему 4.5.1, а также следствие 4.7.1), что, по крайней мере, в плоском случае верхнее аппроксима-ционное число ВКТ в определенном смысле связано с метрической размерностью его крайних точек. Более подробно этот вопрос обсуждается в главе 4.

Аппроксимационное число недостаточно полно описывает аппрок-симационные свойства выпуклого тела. Например, а(С)=0 при Ce:f, и существуют такие Cer(K'.f, причем строго выпуклые и регулярные, что «(С)=0 [157]. Для характеристики различных способов сходимости величины <5(С, Cfm) к нулю в [157] предлагается использовать множество хаусдорфовых функций Н. Элементами Н являются неотрицательные возрастающие вещественные функции h, определенные на [0, +оо), непрерывные справа и удовлетворяющие условию h(0) = 0. В этом классе определяется аппроксимируемость тела Се с€ как множество функций

A(C):={heH:qh(C)> 0} , где ah(C) := liminf тИ{8{С,^т)). т -»оо

Чем меньше множество А(С), тем лучше тело С может быть аппроксимировано многогранниками. Величину А(С) мы будем называть нижней аппроксимируемостью тела С. Введем также верхнюю аппроксимируемость тела С как

A(C):={heH:ah(C)>0} , где аи (С) := lim sup mh(S(C, )) т—>оо

Очевидно, что A(C)czA(C), и в случае совпадения этих множеств можно говорить об аппроксимируемости А{С).

В [157] дана нижняя оценка множества А(С) для С<=св (через обобщенную хаусдорфову размерность множества ехр*С) и показано, что Се./ тогда и только тогда, когда А(С) = 0. В настоящей работе нас будет интересовать верхняя оценка верхней аппроксимируемости А (С), более сильная для негладких тел, чем (0.2.6), и, в частности, равная пустому множеству в классе

В заключение пункта определим класс ВКТ, для которого порядок 2/(d-l) является неулучшаемым. Для 0 < а< (d-\)/2 обозначим

ВД := {С&Ъ. а(С)=а).

Обозначим -=%(d-\)/2). Из (0.1.3) следует, что %2аЩ. Пусть также с€* := {С&Ъ. dim exp* C = d-1}. Ясно, что Однако из

С [\Ci е Сi е Сб1 /=1 также следует, что CeV*. Действительно, как нетрудно показать, все точки границы будут в этом случае дальними, т.к. в точке на границе пересечения конечного семейства шаров всегда существует внешний касающийся шар. Исходя из (0.2.2), можно показать также, что к с€* принадлежат также множества с точкой, в окрестности которой граница дважды-непрерывно дифференцируема, а главные кривизны - положительны. Такой случай часто встречается в приложениях. В любом случае, для класса из (0.2.1)-(0.2.2) следует, что а(С) = а(С) = а(С) = Се%. (0.2.7)

Поэтому Таким образом, класс % достаточно широк, чтобы охватить ВКТ, аппроксимация которых требуется в приложениях.

Результаты (0.1.2)-(0.1.7) показывают, что относительно класса % известно достаточно много. Гораздо меньше известно о классе г6{а), когда a<(d-1)/2. Ясно, что поскольку 0), то Из нашей работы [42] см. следствие 4.7.1) вытекает также, что в плоском случае (d=2) справедливо Цсё)*0 при любом a, 0<oc<(d-l)/2 (следствие 4.7.2). Результат (0.1.9) работы [140] говорит о том, что в плоском случае в класс Щс1-\)/2) не входят ВКТ с нулевым аффинным периметром (см. условие (0.1.10)). Теория ВКТ из %р) при a<{d-1 )/2 требует своей разработки. Результаты работ [140] и [42] (см. гл. 4) являются только начальным вкладом в эту теорию.

0.3. Методы полиэдральной аппроксимации и их эффективность

Пусть для CeW имеется некоторый метод полиэдральной аппроксимации (МПА), под которым мы будем понимать способ построения последовательности многогранников {Р"}„=o,i,., Р"&У{С) (^'т(С) или №ст(С)), сходящейся к телу С в заданной метрике (такую последовательность мы будем называть аппроксимирующей). Примером может служить гипотетический метод построения МНА с последовательно растущим числом вершин (гиперграней).

Нас, прежде всего, будет интересовать качество аппроксимации с точки зрения числа вершин и/или гиперграней многогранников, получаемых с помощью данного метода. Надо сказать, что теория эффективности МПА долгое время была развита недостаточно. Причиной было отсутствие реальных МПА, порождающих многогранники, близкие по свойствам к МНА. Ниже приводится классификация МПА, развитая в наших работах по теоретическому [37], [38], [42] и экспериментальному [32], [33], [21], [22] исследованию адаптивных МПА.

Пусть CeVи Ревг(С). Величину

S(C,P) назовем эффективностью аппроксимации тела С многогранником Р (с точки зрения числа вершин или гиперграней соответственно).

Пусть V\={Pn}rr=\^,. - сходящаяся к Се ^последовательность многогранников из ,/{С). Величины

77(F) := liminf rj(P"), 77(F) := limsup77(P") п—>00 назовем, соответственно, нижней и верхней асимптотической эффективностью аппроксимации тела С последовательностью F. Если нижняя и верхняя асимптотическая эффективность совпадают, можно говорить об эффективности аппроксимации тела С. Наконец, под эффективностью метода полиэдральной аппроксимации тела С будем понимать эффективность порождаемой им последовательности многогранников.

Очевидно, что 0 < 77(F) < 77(F) < 1, причем для любого МНА П„, m=d+1, d+ 2, ., эффективность аппроксимации равна единице. Поэтому гипотетический метод построения МНА будем называть оптимальным. МПА, порождающий для тела С последовательность с асимптотической эффективностью, равной 1, будем называть асимптотически оптимальным.

МПА, порождающий для тела С последовательность с нижней асимптотической эффективностью, большей нуля, будем называть асимптотически эффективным. Из (0.1.2)-(0.1.3) следует, что для асимптотически эффективной последовательности справедливо constr ,7 х tc,p")< (0.3.1) т(Рп)

Более того, если то constr ,/ х

Пусть Cer<?и а(С) > 0. МПА назовем оптимальным по порядку числа вершин (гиперграней) для С, если он порождает последовательность многогранников с тем же порядком скорости сходимости, что и у МПА. Более формально, МПА назовем оптимальным по порядку числа вершин (гиперграней) для С, если он порождает последовательность {Р"}„=o,i,., в которой для любого 5>0 такого, что j(c,.^)<C0nst^; (0.3.3) т справедливо const'r н * г

S(C,Pn)<-Wil. (0.3.4) m(Pn)s

МПА будем называть асимптотически эффективным (оптимальным по порядку) для класса %*а% если он является асимптотически эффективным (оптимальным по порядку) для каждого Се.%*.

Нетрудно видеть, что асимптотически эффективный МПА является (при условии а(С) > 0) оптимальным по порядку. Вместе с тем заметим, что МПА может быть оптимальным по порядку и иметь, в то же время, асимптотическую эффективность, равную 0. Например, такой случай мо

-а(с) жет иметь место, если а (С) = 0, т.е. limsupm[<^(C,^)]*(C) =0, т—>оо в то время как msupm(Pn)[sH(C;Pn)f(C) >0.

Я—>00

Для понятия асимптотической эффективности и оптимальности по порядку совпадают. Совпадают они и для класса ВКТ с частично гладкой границей (см. замечание после неравенства (0.1.4)). Однако для класса а, следовательно, и для класса они могут уже не совпадать. Заметим, наконец, что для того, чтобы некоторый метод был оптимален по порядку в классе %, необходимо и достаточно, чтобы для любого тела Се% в порождаемой методом последовательности {P"}n=o,i,. выполнялось const CtdtS т(Р"У

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

ВКТ, полиэдральную аппроксимацию которого следует построить, может быть задано следующими основными способами:

1) функцией принадлежности (в случае неявного способа задания аппроксимируемого тела задача ее вычисления сводится к задаче оптимизации с квадратичным функционалом): x,Q'-= {1: хеС; 0: х<£С};

2) аналитически;

3) через опорную или дистанционную (калибровочную) функции, которые могут быть заданы также либо через алгоритм расчета для конкретного аргумента, либо аналитически (сводятся к задаче оптимизации с линейным функционалом);

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

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

Наконец, рассмотрим различие между итерационными (step-by-step [113], [114], [116]; sequential [159], [160]) и неитерационными методами. В итерационных методах шаг за шагом осуществляется уточнение аппроксимации, при этом конечная точность может быть как задана заранее, так и определяться в процессе итераций. Среди итерационных методов выделяются методы адаптивные (active [159], [160]), в которых, в отличие от методов неадаптивных (passive [159], [160]), строится последовательность многогранников, в которой построение описания каждого следующего многогранника существенно зависит от информации об аппроксимируемом теле, полученной на предыдущих итерациях. Так, например, на каждой итерации метода множество вершин (гиперграней) аппроксимирующего многогранника может увеличиваться на одну вершину (гипергрань), причем с учетом информации о близости текущего многогранника к аппроксимируемому телу. Заметим, однако, что гипотетические методы построения МНА не могут принадлежать к классу таких методов, так как множество М(Нт+{) существенно отличается от М(Пт) (все вершины и гиперграни «сдвинуты»). В этом легко убедиться на примере правильных п- и (и+1)-угольников, являющихся МНА для круга.

Иногда ([159], [160]) различают бесконечно продолжимые и конечные итерационные методы. В последних в алгоритме метода существенно используется параметры, связанные с пороговой (конечной) аппроксимацией.

Пусть аппроксимируемое тело задано через опорную или дистанционную (калибровочную) функции и аппроксимирующий многогранник Р построен некоторым МПА. Обозначим через mg(P) и тё*(Р) число вычислений опорной и дистанционной функции тела С, необходимое для построения Р. Ясно, что для построения одной вершины (гиперграни) требуется как минимум один расчет опорной (дистанционной) функции. Пусть теперь Сег<?. По аналогии с определением оптимальности методов по порядку числа вершин (гиперграней) МПА назовем оптимальным по порядку числа вычислений опорной (дистанционной) функции, если он порождает последовательность {Р"}п=о,\,., в которой для любого 5>0 такого, что выполняется (0.3.3), справедливо и

5{С,Р")< co"st c,d,s,s mg(Pn)s

S(C,P")<

0.4. Обзор известных методов полиэдральной аппроксимации

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

1) Классическим примером служит МПА, с помощью которого в [145] была доказана возможность аппроксимации ВКТ многогранниками с любой степенью точности. В этом методе аппроксимируемое тело задается своей характеристической функцией, рассматривается метрическая е-сеть, и в качестве аппроксимации берется выпуклая оболочка тех ее узлов, которые принадлежат аппроксимируемому телу. Нетрудно видеть, что в этом случае для построения полиэдральной аппроксимации с точностью е в метрике Хаусдорфа требуется 0{ёш) вычислений характеристической функции, при этом число вершин может оказаться не меньше 0{s"y^dA)).

2) Примерами асимптотически оптимальных методов служат теоретические конструкции, использованные в [153], [154] и [110], [111], [113], [114] для получения асимптотических оценок, соответственно, (0.1.5) и (0.1.6)-(0.1.7). Для метрики Хаусдорфа они состоят в распределении вершин (точек касания) на поверхности тела, равномерном в смысле минимального покрытия поверхности одинаковыми шарами в метрике II квадратичной формы. Для метрики объема они состоят в распределении вершин (точек касания) на поверхности тела, равномерном в смысле минимизации объема, соответствующего триангуляции Делоне (разбиению Дирихле-Вороного) в метрике II квадратичной формы. Заметим, что конкретный вид таких множеств неизвестен даже для сферы S2.

Единственным асимптотически оптимальным методом, который может использоваться на практике, является метод «баланса ошибок» из работы [144] для аппроксимации гладких выпуклых дисков с аналитически

РОССИЙСКАЯ ГОСУДАРСТВЕННАЯ

БИБЛИОТЕКА ^ заданным вдоль границы интегралом от степенной функции кривизны (в этой работе получен первоначальный, двумерный вариант асимптотических оценок (0.1.5) и (0.1.6)-(0.1.7)). Обобщением этого аналитического подхода в тех же рамках двумерных гладких тел является работа [147], в которой рассматриваются асимптотически эффективные методы. Для метрики объема в случае произвольных двумерных тел метод «баланса ошибок» используется в [140], где получена оценка (0.1.9). Непонятно, однако, насколько эффективным является этот метод в случае выполнения условия (0.1.10) (см. замечание после (0.1.9)).

Для получения в этом «теоретическом» подходе конструктивных многомерных методов в [115], [116] предлагается метод проекции на тело точек, равномерно распределенных на гиперплоскостях, касательных к аппроксимируемому телу. Когда этих гиперплоскостей много и проектируемые точки расположены близко к аппроксимируемому телу, распределение их проекций будет «почти равномерным». Естественно, что этот МПА может быть использован только для аппроксимации тел из класса (62, причем ограниченность его применимости в реальных задачах очевидна.

3) «Конструктивным (well-defined) в некоторых случаях и «почти» конструктивным в других» является, по словам авторов, метод [107], [108], требующий знания (аналитического задания) объема произвольных /мерных, l<d-1, сечений аппроксимируемого тела вдоль соответствующих осей координат. Такой метод сходится для произвольных тел в метрике объема со скоростью 0(m~ll{ftA)), где т - число вершин (гиперграней). При этом константа при т~2/(аЧ) неизвестна, что затрудняет не только оценку эффективности метода, но и контроль над точностью аппроксимации. В работе [128] этот метод применен для аппроксимации эллипсоидов произвольной размерности (в этом случае объем требуемых сечений эллипсоидов задается простой аналитической формулой). К сожалению, по словам авторов, рассматриваемый подход «встретит большие препятствия в случае общих выпуклых тел». Таким образом, этот МПА не может применяться в большинстве приложений.

4) Не являются асимптотически эффективными также стохастические методы аппроксимации (сходимость вида для метрики объема и - для метрики Хаусдорфа, см. [116]). В этом подходе вместо точности аппроксимации рассматривается ее математическое ожидание при аппроксимации выпуклой оболочкой случайных точек, распределенных внутри или на поверхности тела.

3) Из работ [103], [6], в которых получена оценка (0.1.2), можно вывести оптимальный по порядку в классе % неадаптивный МПА. Этот метод основан на «равномерном» распределении точек на поверхности описанного шара и дальнейшем проектировании их на поверхность тел. Он требует нахождения проекции точки на поверхность ВКТ, что не всегда возможно в приложениях. Эффективность такого метода, как нетрудно видеть, зависит от асферичности аппроксимируемого тела3.

4) В ряде работ рассматриваются неадаптивные МПА, основанные на вычислении опорной функции аппроксимируемого тела в узлах сетки, априорно заданной на единичной сфере направлений. После нахождения опорных гиперплоскостей в направлении узлов сетки и соответствующих им точек касания в качестве аппроксимации предлагается брать их пересечение или выпуклую оболочку этих точек. К числу таких работ принадлежат, например, [81] и [17]. При условии «равномерности» выбора узлов сетки направлений (см. сноску к предыдущему пункту) эти МПА являются асимптотически эффективными только в случае аппроксимации тел из класса %.2.

3 Задача «равномерного» распределения точек на поверхности многомерной сферы близка к проблеме минимального покрытия пространства шарами и сводится к построению минимального покрытия сферы поверхностными «кругами» равного диаметра. Эта задача изучается в рамках теории покрытий для сферических кодов (см. [54]). В настоящей работе мы не будем рассматривать эту сложную проблему. Заметим, что рассматриваемые нами АМПА дают, при аппроксимации шара, достаточно хорошее распределение вершин на его поверхности (см. [21], а также лемму 2.4.2).

Как показано в [159], [160], никакой неадаптивный метод аппроксимации, основанный на вычислении опорной функции в узлах сетки направлений, не может быть оптимальным по порядку при аппроксимации негладких тел. Этим указанные методы отличаются от неадаптивных МПА, рассмотренных в предыдущем пункте, в которых вместо вычисления опорной функции использовалась операция проектирования на аппроксимируемое тело.

Если, однако, известно, что аппроксимируемое тело является сильно выпуклым или пересечением сильно выпуклых тел4, то, согласно [17], неадаптивный МПА, основанный на вычислении опорной функции в узлах сетки направлений, оказывается оптимальным по порядку. При этом для оценки точности аппроксимации требуется знать параметр выпуклости, что возможно не во всех приложениях.

5) Промежуточное место между адаптивными и неадаптивными МПА занимает метод [159], в котором рассматривается способ построения аппроксимирующих внешних многогранников. Каждый следующий многогранник образуется из предыдущего путем пересечения его с некоторым опорным к аппроксимируемому телу полупространством. В этом методе направление нормали, задающее это полупространство, выбирается из узлов априорно заданной регулярной сетки на поверхности сферы направлений с учетом теоретической оценки локального отклонения уточняемого многогранника от аппроксимируемого тела. В [160] показано, что метод из [159] является субоптимальным по порядку числа гиперграней аппроксимирующего многогранника и числа вычислений опорной функции аппроксимируемого множества. Под субоптимальностью понимается при этом

4 Пусть С&'С. Назовем С v-выпуклым множеством, если для любых х,уеС справедливо Bv[x-y\n{{x+y)l2)<z.C. Назовем С сильно выпуклым, если оно v-выпукло при некотором v>0. Множество сильно выпуклых компактных тел обозначим через Согласно [17], сильно выпуклыми являются выпуклые тела вида {xeErf: F(x)<0}, FeC^E^), а также пересечения конечного числа тел этого вида. оптимальность с точностью до неустранимого логарифмического мультипликативного фактора, т. е. сходимость в метрике Хаусдорфа вида 0{m2l(dA) log т), где т - число гиперграней. Как нам представляется, появление этого фактора обусловлено априорным выбором сетки направлений, используемой, однако, адаптивно. Субоптимальные свойства метода из [159], [160] справедливы для плоских и трехмерных тел с гладкими и негладкими границами. При размерности пространства большей, чем три, субоптимальность сохраняется только при аппроксимации тел класса

6) Рассмотрим теперь адаптивные методы полиэдральной аппроксимации (АМПА), обобщением которых явился класс методов, рассматриваемый в настоящей работе. В этих методах тело приближается последовательностью внутренних многогранников. В качестве нового аппроксимирующего многогранника выбирается выпуклая оболочка прежнего и не принадлежащей ему точки тела, выбранной из определенных соображений. В [11], [15], [12], [64] построенный многогранник уточняется в направлении той его гиперграни, где достигается наибольшее его отклонение от аппроксимируемого тела. Отметим, что эта идея впервые предложена, по-видимому, в [102], где рассматриваются несколько отличная двумерная задача - построение эффективной границы для выбора решения при двух критериях качества. Подход [102] получил также развитие для трехмерных задач (см. [91]), хотя способ решения не позволяет распространить его на большие размерности. Метод [11], [15], [12], [64] получил в дальнейшем развитии название метода «Уточнения Оценок» (УО) (см. историю этого вопроса в [66]).

В работе [152], вышедшей значительно позже указанных работ, предложено несколько методов, являющихся двумерными вариантами метода УО и метода из [159] и названных автором «сэндвичевыми» (sandwich) алгоритмами. Следует отметить, однако, что в работе [152] рассматриваются и некоторые другие принципы адаптации (чем, например, присоединение дальней точки). Однако эти принципы не могут быть распространены на многомерный случай. Аналогичные «сендвичевым» идеи рассматриваются и в работе [151]. Дальнейшего распространения на аппроксимацию более чем двумерных тел «сэндвичевы» алгоритмы не получили.

7) Метод УО был исследован и обобщен в наших работах [32], [33], [38]. В [35], [36] был введен класс АМПА, характеризуемых через Н-схемы. Теория АМПА из этого класса был развита в работах [35], [36], [37], [41], [42], [44], [45], [46]. Для Я-методов полиэдральной аппроксимации были получены верхние оценки скорости сходимости для произвольных ВКТ, была доказана оптимальность по порядку в классе были получены независящие от тела (в т.ч. от его асферичности) оценки асимптотической эффективности в классе %2. В рамках указанного подхода в [36], [39], [42], [44], [45], [46] были предложены новые методы аппроксимации, в том числе - оптимальные по числу вычислений опорной и дистанционной функций аппроксимируемого тела. Изложению этой теории и посвящена, в основном, настоящая работа.

1. Александров А.Д. Внутренняя геометрия выпуклых поверхностей. М.-JL: Гостехтеориздат, 1948.

2. Бард Й. Нелинейное оценивание параметров. М.: Статистика, 1979.

3. Благодатских В.И., Филиппов А.Ф. Дифференциальные включения и оптимальное управление // Топология, обыкновенные дифференциальные уравнения, динамические системы. Тр. МИАН СССР. М.: Наука, 1985.

4. Бляшке В. Круг и шар. М.: Наука, 1967.

5. Бренстед А. Введение в теорию выпуклых многогранников. М.: Мир, 1988.

6. Бронштейн Е.М., Иванов Л.Д. О приближении выпуклых множеств многогранниками // Сибирский матем. ж. 1975. Т. 26. № 5. СЛ110-1112.

7. Бурмистрова JI.B. Исследование одного алгоритма аппроксимации выпуклых компактных тел многогранниками. М.: ВЦ РАН, 1999.

8. Бурмистрова JI.B. Исследование нового метода аппроксимации выпуклых компактных тел многогранниками // Ж. вычисл. матем. и матем. физ. 2000. Т.40. № 10. С. 1475-1490.

9. Бурмистрова JI.B. Экспериментальный анализ нового адаптивного метода полиэдральной аппроксимации многомерных выпуклых тел // Ж. вычисл. матем. и матем. физ. 2003. Т.43. № 3. С. 328-346.

10. Бурмистрова Л.В., Ефремов Р.В., Лотов А.В. Методика визуальной поддержки принятия решений и ее применение в системах управления водными ресурсами // Известия АН. Сер. Теория и Системы Управления. 2002. № 5. С.89-100.

11. Бушенков В. А. Численный алгоритм построения проекций многогранных множеств // Аэрофиз. и прикл. матем. М.: МФТИ, 1981. С. 108-110.

12. Бушенков В. А. Итерационный метод построения ортогональных проекций выпуклых многогранных множеств // Ж. вычисл. матем. и ма-тем. физ. 1985. Т. 25. № 9. С. 1285-1292.

13. Бушенков В.А., Гусев Д.В., Каменев Г.К., Лотов А.В., Черных O.JI. Визуализация множества Парето в многомерной задаче выбора // Доклады Академии наук. 1994. Т. 335. № 5. С. 567-569.

14. Бушенков В. А., Каменев Г. К, Лотов А. В., Черных О. Л. Использование геометрического метода для анализа эколого-экономических систем // Матем. моделирование. Процессы в сложных экономич. и экологич. системах. М.: Наука, 1986. С. 240-252.

15. Бушенков В. А., Лотов А. В. Методы построения и использования обобщенных множеств достижимости. М.: ВЦ АН СССР, 1982.

16. Бушенков В.А. и Лотов А.В. Анализ потенциальных возможностей региона в межрегиональной межотраслевой модели мировой экономики // Межрегиональные межотраслевые модели мировой экономики (под ред. С.М.Меньшикова), 1983. М.: Наука.

17. Васильев И. С. О неулучшаемых оценках аппроксимации сильно выпуклых тел // Вопр. кибернетики. 1988. Т. 136. С. 49-56.

18. Витушкин А.Г. Оценка сложности задачи табулирования. М.: Гос. Изд-во Физ. Мат. Лит., 1959.

19. Гуревич В., Волмэн Г. Теория размерности. М.: Ин. Литерат., 1948.

20. Гусев Д.В., Лотов А.В. Методы поддержки принятия решений в задаче конечного выбора // Исследование операций. Модели, системы, решения. М.: ВЦ РАН, 1994.

21. Джолдыбаева С.М., Каменев Г.К. Экспериментальное исследование аппроксимации выпуклых тел многогранниками. М.: ВЦ АН СССР, 1991.

22. Джолдыбаева С.М., Каменев Г.К. Численное исследование эффективности алгоритма аппроксимации выпуклых тел многогранниками. // Ж. вычисл. матем. и матем. физ. 1992. Т. 32. № 6. С. 857-866.

23. Егорова Н.Е., Каменев Г.К, Лотов А.В. Использование метода обобщенных множеств достижимости в имитационной системе отраслевого планирования // Методы имитационного моделирования экономических объектов. М.: ЦЭМИ, 1985. С. 3-16.

24. Ефремов Р.В. Оценка эффективности адаптивного алгоритма аппроксимации выпуклых гладких тел в двумерном случае // Вестн. Моск. Ун-та, Сер. 15. Вычисл. матем. и киберн. 2000. № 2, стр. 29-32.

25. Ефремов Р.В. Экспериментальный анализ методов внешней полиэдральной аппроксимации выпуклых тел. М.: ВЦ РАН, 2002.

26. Ефремов Р.В. Априорная оценка эффективности адаптивных алгоритмов полиэдральной аппроксимации выпуклых тел // Ж. вычисл. матем. и матем. физ. 2003. Т. 43. № 1. С. 149-160.

27. Ефремов Р.В. Анализ методов полиэдральной аппроксимации выпуклых тел и их применение в задачах многокритериальной оптимизации. Дис. канд. физ.-матем. наук. М.: ВЦ РАН, 2003.

28. Ефремов Р.В., Каменев Г.К. Априорная оценка асимптотической эффективности одного класса алгоритмов полиэдральной аппроксимации выпуклых тел // Ж. вычисл. матем. и матем. физ. 2002. Т. 42. № 1. С. 23-32.

29. Жиглявский А.А., Жшинскас А.Г. Методы поиска глобального экстремума. М.: Наука, 1991.

30. Зезюлинский Н.В., Каменев Г.К. "Потенциал-2": диалоговая система графического анализа многогранных множеств достижимости // Материалы школы-семинара ИВЕРСИ-85 Тбилиси: ГНИИНТИиТЭИ, 1985. С. 144.

31. Каменев Г.К. Методы аппроксимации выпуклых тел многогранниками и их применение для построения и анализа обобщенных множеств достижимости: Дис. канд. физ.-матем. наук. М.: МФТИ, 1986. 219 с.

32. Каменев Г.К Исследование итерационных методов аппроксимации выпуклых множеств многогранниками. М.: ВЦ АН СССР, 1986.

33. Каменев Г.К Один метод построения обобщенных множеств достижимости // Системы программного обеспечения решения задач оптимального планирования. Тез. докл. 9 Всес. симп. М.: ЦЭМИ АН СССР, 1986. С.138-139.

34. Каменев Г. К. Об одном классе адаптивных схем аппроксимации выпуклых тел многогранниками // Матем. моделирование и дискретная оптимизация. М.: ВЦ АН СССР, 1988. С. 3-9.

35. Каменев Г. К. Об одном классе адаптивных алгоритмов аппроксимации выпуклых тел многогранниками // Ж. вычисл. матем. и матем. физ. 1992. Т. 32. № 1. С. 136-152.

36. Каменев Г.К. Об эффективности хаусдорфовых алгоритмов полиэдральной аппроксимации выпуклых тел // Ж. вычисл. матем. и матем. физ. 1993. Т. 33. № 5. С. 796-805.

37. Каменев Г.К Исследование одного алгоритма аппроксимации выпуклых тел // Ж. вычисл. матем. и матем. физ. 1994. Т. 34. № 4. С. 608616.

38. Каменев Г.К. Алгоритм сближающихся многогранников // Ж. вычисл. матем. и матем. физ. 1996. Т. 36. № 4. С. 134-147.

39. Каменев Г.К Визуальный метод идентификации параметров // Доклады Академии наук. 1998. Т. 359. № 3. С. 319-322.

40. Каменев Г.К. Эффективные алгоритмы внутренней полиэдральной аппроксимации негладких выпуклых тел // Ж. вычисл. матем. и матем. физ. 1999. Т. 39. № 3. С. 446-450.

41. Каменев Г.К Об аппроксимационных свойствах негладких выпуклых дисков // Ж. вычисл. матем. и матем. физ. 2000. Т. 40. № 10. С. 1464

42. Каменев Г.К. Аппроксимация вполне ограниченных множеств методом глубоких ям // Ж. вычисл. матем. и матем. физ. 2001. Т. 41. № 11. С. 1751-1760.

43. Каменев Г.К. Сопряженные адаптивные алгоритмы полиэдральной аппроксимации выпуклых тел // Ж. вычисл. матем. и матем. физ. 2002. Т. 42. №9. С. 1351-1367.

44. Каменев Г.К. Метод полиэдральной аппроксимации выпуклых тел, оптимальный по порядку числа расчетов опорной и дистанционной функций // Доклады Академии наук. 2003. Т. 388. № 3. С. 309-311.

45. Каменев Г.К. Самодвойственные адаптивные алгоритмы полиэдральной аппроксимации выпуклых тел // Ж. вычисл. матем. и матем. физ. 2003. Т. 43. № 8. С. 1123-1137.

46. Каменев Г.К, Кондратьев Д.Л. Об одном методе исследования незамкнутых нелинейных моделей // Матем. моделирование. 1992. N3. С. 105-118.

47. Каменев Г.К, Лотов А.В., Черных О.Л. Геометрический метод в многокритериальных задачах принятия решений // Теория, методология и практика системных исследований. Тез. докл. Всес. конф. М.: ГКНТ, 1985. С. 31-32.

48. Канторович Л.В., Акилов ГЛ. Функциональный анализ. М.: Наука, 1977.

49. Карманов В. Г. Математическое программирование. М.: Наука, 1975.

50. Кини Р.Л., Райфа X. Принятие решений при многих критериях: предпочтения и замещения. М.: Радио и связь, 1981.

51. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. М.: Мир, 1978.

52. Колмогоров А.Н., Тихомиров В.М. if-энтропия и Й-емкость множеств в функциональных пространствах // Успехи мат. наук. 1959. Т. 14. № 2. С. 3-86.

53. Конвей Дж., Слоен Н. Упаковки шаров, решетки и группы. М.: Мир, 1990. Т.1.

54. Кондратьев Д.Л., Лотов А.В. О внешних оценках и построении множеств достижимости для нелинейных управляемых систем // Ж. вычисл. матем. и матем. физ. 1990. Т.30. № 4.

55. Куржанский А.Б. Управление и наблюдение в условиях неопределенности. М.: Наука, 1977.

56. Ларичев О. И. Объективные модели и субъективные решения. М.: Наука, 1987.

57. ЛейхтвейсК. Выпуклые множества. М.: Наука, 1985.

58. Лотов А.В. Численный метод построения множеств достижимости для линейной управляемой системы // Ж. вычисл. матем. и матем. физ., 1972. Т. 12 № 3.

59. Лотов А.В. Численный метод исследования непрерывности времени быстродействия в линейных системах и решения задачи Коши для уравнения Беллмана // Ж. вычисл. матем. и матем. физ., 1973. Т. 13. № 5.

60. Лотов А. В. Численный метод построения множеств достижимости для линейных управляемых систем с фазовыми ограничениями // Ж. вычисл. матем. и матем. физ. 1975. Т. 15. № 1. С. 67-68.

61. Лотов А.В. О понятии обобщенных множеств достижимости и их построении для линейных управляемых систем // Докл. АН СССР. 1980. Т. 250. №5. С. 1081-1083.

62. Лотов А. В. Введение в экономико-математическое моделирование. М.: Наука, 1984.

63. Лотов А.В. Методы анализа математических моделей управляемых систем на основе построения множества достижимых значений показателей качества управления. Дис. на соискан. учен. степ. докт. физ.-мат. наук. М.: ВЦ АН СССР, 1986.

64. Лотов А. В. Компьютерная визуализация множества производственных возможностей в рамках анализа эффективности производственных единиц // Докл. АН СССР. 2003. Т. 388. № 2. С. 171-173.

65. Лотов А.В., Бушенков В.А., Каменев Г.К Метод достижимых целей. Математические основы и экологические приложения. The Edwin Mel-len Press, Lewiston, NY, USA, 1999.

66. Лотов A.B., Бушенков B.A., Каменев Г.К, Черных О.Л. Компьютер и поиск компромисса. Метод достижимых целей. М.: Наука, 1997.

67. Лотов А.В., Бушенков В.А., Черных О.Л. Структура и опыт использования компьютерной системы поддержки поиска водохозяйственных стратегий // Научно-техническая информация, серия 2. Информационные процессы и системы, 1998, N 3.

68. Лотов А.В., Каменев Г.К, Березкин В.Е. Аппроксимация и визуализация паретовой границы для невыпуклых многокритериальных задач // Докл. АН. 2002. Т. 386. № 6. С. 738-741.

69. Моисеев Н.Н. Математические задачи системного анализа. М.: Наука, 1981.

70. Моисеев Н.Н., Александров В.В., Тарко A.M. Человек и биосфера. М.: Наука, 1985.

71. Мостеллер Ф., ТьюкиДж. Анализ данных и регрессия. М., Финансы и статистика, 1982.

72. Мухамедиев Б. М. Приближенный метод решения задачи вогнутого программирования // Ж. вычисл. матем. и матем. физ. 1982. Т. 22. № 3. С. 727-732.

73. Петров А.А., Поспелов И.Г., Шананин А.А. Опыт математического моделирования экономики. М.: Энергоатомиздат, 1996.

74. Понтрягин Л. С, Болтянский В. Г., Гамкрелидзе Р. В., Мищенко Е. Ф. Математическая теория оптимальных процессов. М.: Наука, 1969.

75. Поспелов Г.С., Ириков В.А. Программно-целевое планирование и управление. М.: Советское радио, 1976.

76. Препарата Ф., Шеймос М. Вычислительная геометрия. М.: Мир, 1989.

77. Роджерс К. Укладки и покрытия. М.: Мир, 1968.

78. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973.

79. Самсонов С. Л. Восстановление выпуклого множества по его опорной функции с заданной точностью // Вестн. МГУ. Сер. 15. Вычисл. матем. и кибернетика. 1983. № 1. С. 68-71.

80. Торп Дж. Начальные главы дифференциальной геометрии. М.: Мир, 1982.

81. Черноусько Ф.Л. Оценивание фазовых состояний динамических систем. Метод эллипсоидов. М.: Наука, 1988.

82. Черных О.Л. Построение выпуклой оболочки конечного множества точек при приближенных вычислениях // Ж. вычисл. матем. и матем. физ. 1988. Т. 28. № 9. С. 1386-1396.

83. Черных О.Л. Построение выпуклой оболочки конечного множестваточек на основе триангуляции // Ж. вычисл. матем. и матем. физ. 1991. Т. 31. №8. С. 1231-1242.

84. Черных О.Л. Построение выпуклой оболочки множества точек в виде системы линейных неравенств // Ж. вычисл. матем. и матем. физ. 1992. Т. 32. №8. С. 1213-1228.

85. Черных О.Л. Аппроксимация Парето-оболочки выпуклого множества многогранными множествами // Ж. вычисл. матем. и матем. физ. 1995. Т. 35. № 8.

86. Шананин А.А. Об агрегации функции спроса // Экономика и матем. методы. 1989. Т. 25, № 9. С. 1095-1105.

87. Юдин Д. Б., Немировский А. С. Оценка информационной сложностизадач математического программирования // Экономика и матем. методы. 1976. Т. 12. Вып. 1. С. 128-142.

88. Янко Я. Математико-статистические таблицы. М., 1961.

89. Appino P.A. A solution technique for approximating the non-inferior set of three objective linear programs: Ph. D. Diss. Baltimore, Maryland: Johns Hopkins Univ., 1984.

90. Berezkin V.E., Kamenev G.K., Lotov A. V. Experimental Software of Nonlinear Feasible Goals Method // Тез. докл. 3-й Моск. междун. конф. по исследованию операций. М.: ВЦ РАН, 2001. С. 17-18.

91. Blaschke W. Vorlesungen Uber Differentialgeometrie II. Springer-Verlag. Berlin, 1923.

92. Boroczky K.Jr. Approximation of General Smooth Convex Bodies // Ad-vanc. Math. 2000. V. 153. P. 325-341.

93. Boroczky K.Jr. About the Error Term for Best Approximation with Respect to the Hausdorff Related Metrics // Discrete Comput. Geom. 2001. V. 25. P. 293-309.

94. Brooks I.N., Strantzen J.B. Blaschke's rolling theorem in R" II Mem. Amer. Math. Soc. Providence. 1989. V. 80. № 405. P. 2-5.

95. Bushenkov V.A., Chernykh O.L., Kamenev G.K., Lotov A. V. Multidimensional Images Given by Mappings: Construction and Visualization // Pattern Recognition and Image Analysis. 1995. V. 5, № 1. P. 35-56.

96. Bushenkov V., Ereshko F., Kindler J., Lotov A., de Mare L. Application of the GRS Method to Water Resources Problems in Southwestern Skane, Sweden. WP-82-120. Laxenburg, Austria: International Institute for Applied Systems Analysis, 1982.

97. Bushenkov V., Kaitala V., Lotov A., Pohjola M. Decision and Negotiation Support for Transboundary Air Pollution Control between Finland, Russia and Estonia // Finnish Economic Papers, 1994, v.7, № 1.

98. Button L., WilkerJ.-B. Cutting exponents for polyhedral approximations to convex bodies // Geometriac Dedicata. 1978. V. 7. № 4. P. 417-430.

99. Chernykh, O.L., Kamenev, G.K. Linear algorithm for a series of parallel two-dimensional slices of multidimensional convex polytope // PatternRecognition and Image Analysis, 1993, 3(2), pp. 77-83.

100. Cohort J. Multiobjective programming and planning. N. Y.: Acad. Press,1978.

101. Dudley R. Metric entropy of some classes of sets with differentiable boundaries // J. Approximat. Theory. 1974. V. 10. P. 227-236; Corr., ibid,1979. V. 26. P. 192-193.

102. Efremov R.V., Kamenev G.K. Problem-Independent Estimate of Asymptotic Efficiency for Polyhedral Approximation of Convex Feasible Sets in the Criterion Space // Тез. докл. 3-й Моск. междун. конф. по исследованию операций. М.: ВЦ РАН, 2001. С. 25-26.

103. Fejes Toth L. Approximation by polygons and polyhedra // Bull. Amer. Math. Soc. 1948. V. 54. № 4. P. 431-438.

104. Fejes Toth G., Kuperberg W. Packing and Covering with Convex Sets. In: Handbook of Convex Geometry. Edited by P.M.Gruber and J.M.Wills. Elsevier Sci. Publishers B.V. 1993. Ch. 3.3. P. 799-860.

105. Gordon Y., Meyer M., Reisner Sh. Volume approximation of convex bodies by polytopes a constructive method // Studia Mathematica. 1994. III. № l.P. 81-95.

106. Gordon Y., Meyer M., Reisner Sh. Constructing a Polytope to Approximate a Convex Body // Geometriae Dedicata. Kluver Acad. Publ.: 1995. V. 57. P. 217-222.

107. Gruber P.M. Approximation of convex bodies // Convexity and its Applies. Basel etc.: Birkhauser, 1983. P. 131-162.

108. Gruber P. M. Volume approximation of convex bodies by inscribed polytopes // Math. Ann. 1988. Bd. 281. № 2. S. 229-245.

109. Gruber P.M. Volume approximation of convex bodies by circumscribed polytopes. In: Applied Geometry and Discrete Mathematics. The Victor Klee Festschrift, DIMACS Ser., 1991, Vol. 4 (Amer. Math.Soc., Providence, RI), pp. 309-317.

110. Gruber P.M. Aspects of Approximation of Convex Bodies. In: Handbookof Convex Geometry. Edited by P.M.Gruber and J.M.Wills. Elsevier Sci. Publishers B.V. 1993. Ch. 1.10. P. 321-345.

111. Gruber P.M. Asymptotic estimates for best and stepwise approximation of convex bodies I // Forum Math. 1993. N5. P. 281-297.

112. Gruber P.M. Asymptotic estimates for best and stepwise approximation of convex bodies II. // Forum Math. 1993. N5. P. 521-538.

113. Gruber P.M. Approximation by convex polytopes. In Polytopes: Abstract, Convex and Computational. Kluver Acad. Publ.: 1994, pp. 173-203.

114. Gruber P.M. Comparisons of best and random approximation of convex bodies by polytopes I I Rendiconti Circolo mat. Palermo. Ser. II. 1997. Suppl. 50. P. 189-216.

115. Gruber P.M. Error of Asymptotic Formula for Volume Approximation of Convex Bodies in E? II Monatsh. Math. 2002. V. 135. P. 279-304.

116. Gruber P. M., Kenderov P. Approximation of convex bodies by polytopes // Rendiconti Circolo mat. Palermo. Ser. II. 1982. T. 31. № 2. P. 195-225.

117. Kamenev G.K. One class of effective step-by-step algorithms for polyhedral approximation // Konvexgeometrie. Mat. Forschungsinstitut Oberwol-fach, Tagungsbericht. 1997. № 44. P. 12-14.

118. Kamenev G.K. Essential Covering Method for Visualization of Criterion Tradeoff in Non-Linear Multiple Criteria Decision Problems II Тез. докл. 2-й Моск. междун. конф. по исследованию операций. М.: ВЦ РАН, 1998. С. 17.

119. Kamenev G.K. Dual Algorithm for Polyhedral Approximation of Convex Feasible Sets in Criterion Space // Тез. докл. 3-й Моск. междун. конф. по исследованию операций. М.: ВЦ РАН, 2001. С. 48-49.

120. Kamenev G.K, Lotov A.V. Interactive structured procedure of multiple criteria decision making based on Generalized Reachable Sets method // Многокритериальные задачи математического программирования. Труды семинара М.: ВНИИСИ, 1985. С. 51-54.

121. Koutroufiotis D. On Blaschke's rolling theorems // Arch. Math. 1972. V. 23. P. 655-660.

122. Kurzhanski A.B., Valyi I. Ellipsoidal Calculus for Estimation and Control. Boston: Birkhauser, 1996.

123. Leichtweifi K. Convexity and Differential Geometry. In: Handbook of Convex Geometry. Edited by P.M.Gruber and J.M.Wills. Elsevier Science Publishers B.V. 1993. Ch. 4.1. P. 1045-1080.

124. Lopez M. A., ReisnerSh. Algorithms for Polyhedral Approximation of Multidimensional Ellipsoids // J. Algorithms. 1999. V. 33. P. 140-165.

125. Lotov A.V. Reachable Sets Approach to Multiobjective Problems and its Possible Application to Water Resources Management in the Skane Region, WP-81-145. Laxenburg, Austria: International Institute for Applied Systems Analysis, 1981.

126. Lotov A. V., Bushenkov V.A., Kamenev G.K. Feasible Goals Method Search for Smart Decisions. M.: ВЦ PAH, 2001.

127. Lotov A. V., Bushenkov V.A., Kamenev G.K. Interactive decision maps. Approximation and Visualization of Pareto Frontier. Appl. Optimization. V. 89. Kluwer Academic Publishers. Boston / Dordrecht / New York / London. 2004.-310 P.

128. Lotov A.V., Bushenkov V.A., Kamenev G.K., Loucks D.P., Camara A.S. Water resource conflict resolution based on interactive tradeoffs display // Restoration of Degrad. Rivers: Challenges, Issues and Exper. Kluver Acad. Publ.: 1998. P. 447-470.

129. Ludwig M. A Characterization of Affine Length and Asymptotic Approximation of Convex Discs // Abh. Math. Sem. Univ. Hamburg. 1999. V. 69. P. 75-88.

130. Ludwig M. Asymptotic approximation of smooth convex bodies by general polytopes//Mathematika. 1999. V. 46. P. 103-125.

131. Mankiewicz P., Schtitt C. On the Delone Triangulation Numbers // J. Ap-proxim. Theory. 2001. III. P. 139-142.

132. Mattila P. Geometry of Sets and Measures in Euclidean Spaces. Cambridge Univercity Press. 1995. P. 1-343.

133. McClure D. E., Vitale R. A. Polygonal approximation of plane convex bodies // J. Math. Analys. and Appl. 1975. V. 51. № 2. P. 326-358.

134. Minkowski H. Volumen und Oberflache // Math. Ann. 1903. Bd. 57. P. 447-496.

135. Moran P.A.P. The surface area of an ellipsoid. In: Statistics and Probability. Essays in honor of C.R.Rao. North-Holland, 1982.Wl.Miiller J.S. Step by step approximation of plane convex bodies I I Arch. Math. 1992. V. 58. P. 606-610.

136. Orlovski S.A., van Walsum P.E. V. Water policies: regions with intense agriculture. WP-84-40. Laxenburg, Austria: Int. Inst, for Applied Systems Analysis. 1984.

137. Petty C.M. Affine isoperimetric problems // Ann. New York Acad. 1985. Sci. 440. P. 113-127.

138. Popov V.A. Approximation of convex figures // C.R. Acad. Bulgare. Sci. 1968. V.21.P. 993-995.

139. Richardson T.J. Approximation of Planar Convex Sets from Hyperplane Probes//Discrete Comput. Geom. 1997. V. 18. P. 151-177.

140. Rote G. The Convergence Rate of the Sandwich Algorithm for Approximating Convex Functions. Techn. Univer. Graz. Austria. 1992.

141. Schneider R. Zur optimalen Approximation konvexer Hyperflachen durch Polyeder // Math. Ann. 1981. Bd. 256. № 3, S. 289-301.

142. Schneider R. Polyhedral approximation of smooth convex bodies // J. Math. Analys. and Appl. 1987. V. 128. № 2. P. 470-474.

143. Schneider R. Closed convex hypersurfaces with curvature restrictions. // Proc. Amer. Math. Soc. 1988. V. 103. P. 1201-1204.15в. Schneider R. Convex Bodies: the Brunn-Minkowski Theory. Cambridge, 1993.

144. Schneider R., Wieacker J.A. Approximation of convex bodies by polytopes //Bull. London Math. Soc. 1981. V. 13. P. 149-156.

145. Soloveichik D., Ben-Aderet N., Grinman M., Lotov A. Multiobjective optimization and marginal abatement cost in the electricity sector an Israeli case study // European Journal on Operational Research. 2002, 140 (3), 571-583.

146. Sonnevend G. Asymptotically optimal, sequential methods for the approximation of convex, compact sets in Rn in the Hausdorff metrics // Col-loquia Math. Soc. Janos Bolyai. 1980. V. 35 (2). P. 1075-1089.

147. Sonnevend G. An optimal sequential algorithm for the uniform approximation of convex functions on 0, 1. // Appl. Math, and Optimizat. 1983. № 10. P. 127-142.Таблицы