Теория оптимальных адаптивных методов полиэдральной аппроксимации выпуклых компактных тел и ее применение в задачах принятия решений тема диссертации и автореферата по ВАК РФ 05.13.18, доктор физико-математических наук Каменев, Георгий Кириллович

• Каменев, Георгий Кириллович
• доктор физико-математических наук
• 2004

Оглавление диссертации доктор физико-математических наук Каменев, Георгий Кириллович

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

Введение.

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] были предложены новые методы аппроксимации, в том числе - оптимальные по числу вычислений опорной и дистанционной функций аппроксимируемого тела. Изложению этой теории и посвящена, в основном, настоящая работа.

Список литературы диссертационного исследования доктор физико-математических наук Каменев, Георгий Кириллович, 2004 год

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.Таблицы