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

РГб од

- 6 СЕН 70ПЭ

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

БУРМИСТРОВА Любовь Владимировна

АНАЛИЗ И ИСПОЛЬЗОВАНИЕ АДАПТИВНЫХ МЕТОДОВ АППРОКСИМАЦИИ ВЫПУКЛЫХ ТЕЛ МНОГОГРАННИКАМИ

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

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

Москва - 2000

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

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

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

доцент Лотов Александр Владимирович

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

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

профессор Никольский Михаил Сергеевич

кандидат физико-математических наук Голиков Александр Ильич Ведущая организация:

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

Защита диссертации состоится 2000 г. в ч. на засе-

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

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

чу<игаи2ооо Г.

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

Новикова Наталья Михайловна

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

Построение аппроксимации выпуклых множеств многогранниками явля-гя классической проблемой. Стандартный подход к построению аппрокси-[рующих многогранников основан на расчете значений опорной функции проксимируемого множества на заданной сетке направлений. Показано, о использование заранее заданных (так называемых неадаптивных) сеток правлений не позволяет эффективно аппроксимировать многомерные мно-ютва (Д. Зонневенд, 1983). Для эффективной аппроксимации многомерных :ожеств в 80-х годах была выдвинута концепция адаптивной итеративной проксимации выпуклых множеств многогранниками и предложен первый тод такого типа — метод уточнения оценок (метод УО) (В. А. Бушенков и В. Лотов, 1982). В этом методе направления, для которых осуществляется счет опорной функции аппроксимируемого множества, формируются с пользованием описания уже построенного аппроксимирующего многогранни-. Разработка устойчивой численной схемы метода УО (О. Л. Черных, 1987)

позволила реализовать математическое обеспечение, предназначенное д: аппроксимации выпуклых множеств с использованием метода УО. До п следнего времени метод УО являлся единственным методом аппроксимац! выпуклых множеств многогранниками, используемым в рамках МДЦ.

С середины 80-х годов ведется теоретический анализ адаптивных итер тивных методов аппроксимации выпуклых множеств многогранниками. Д; анализа адаптивных методов выдвинута концепция хаусдофовых методов а проксимации выпуклых компактных тел многогранниками и показано, ч: методы, являющиеся хаусдофовыми, оптимальны по порядку скорости сх димости для гладких тел (Г. К. Каменев, 1992). В 1994 г. Г. К. Каменев док зал, что метод УО является хаусдорфовым и потому оптимален по поряд! скорости сходимости. Анализ практического использования метода УО пок зал, что его недостатком является то, что на каждой итерации используют« многократные расчеты значений опорной функции аппроксимируемого тел Каждый расчет значения опорной функции в практических задачах сложен требует значительного времени, что приводит к существенным затратам вр мени на построение и аппроксимацию множества достижимых значений кр: териев с помощью метода УО. Эта проблема особенно остро стоит при мн гократпой аппроксимации, которая необходима при исследовании практич ских задач поиска эффективных решений многокритериальных проблем.

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

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

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

Результаты, выносимые на защиту, состоят в следующем.

1. Разработан новый хаудорфов адаптивный метод аппроксимации выпук-»IX компактных тел многогранниками — модифицированный метод сближа-щихся многогранников.

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

3. Проведено экспериментальное изучение разработанного метода на осно-данных аппроксимации многомерных эллипсоидов, получены оценки его

имптотических характеристик и выработаны рекомендации по применению ¡тода для аппроксимации гладких тел.

4. Разработана и реализована (совместно с А. В. Лотовым, В. А. Бушен-вым и Р. В. Ефремовым) система поддержки поиска эффективных страте-й улучшения качества воды в бассейнах крупных рек. В систему включена намическая библиотека, реализующая построение аппроксимации множе-ва достижимых значений критериев или его оболочки Эджворта-Парето

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

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

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

Практическая ценность работы заключается в том, что предложе] ный в ней метод, возможность использования которого для аппроксимаци любых выпуклых тел обоснована теоретически, реализован в виде динам] ческой библиотеки Windows. Выработаны рекомендации по выбору знач! ний параметра метода, влияющего на процесс аппроксимации. Это позв( лило эффективно использовать метод в практических задачах исследовани многокритериальных проблем принятия решений. Динамическая библиот ка является частью математического обеспечения системы поддержки пои« эффективных стратегий улучшения качества воды в крупных реках, разр; ботанной в рамках Федеральной целевой программы "Возрождение Волги" применяемой специалистами проектной организации "Союзводпроект". Ря результатов диссертации использован в работе по проектам РФФИ N 95-0 00968 и N 98-01-00323.

Апробация работы. Основные результаты диссертации докладывалис на 2-й Московской международной конференции по исследованию операцг (Россия, Москва, 17-20 ноября 1998 г.), на семинарах Международной летн« математической школы (Италия, Перуджиа, 25 июля-31 августа 1999 г.), i заседаниях XXVII школы-семинара "Математическое моделирование в npi блемах рационального природопользования" (Россия, Ростов-на-Дону, 13-1 сентября 1999 г.), на XV международной конференции "Принятие решею при многих критериях" (Турция, Анкара, 10-14 июля 2000 г.), на научнь семинарах Вычислительного центра РАН и факультета Вычислительной м тематики и кибернетики МГУ им. М. В. Ломоносова.

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

Публикации. По материалам диссертации опубликовано пять печатнь работ, одна работа опубликована в сети Интернет.

Структура и объем работы. Диссертация состоит из введения, тр( глав, заключения, трех приложений и списка литературы. Содержит >19 страниц, включая список литературы из 75 наименований, "f^ иллюстрацг и шесть таблиц.

Содержание работы Во введении обоснована актуальность выбора темы диссертации, сформированы цели работы, показана научная новизна результатов диссер-,ции и дано краткое описание содержания диссертации по главам. Вве-шие содержит математическую постановку задачи аппроксимации выпук->1х компактных тел (ВКТ) многогранниками. Задача состоит в построении »следовательностей выпуклых телесных многогранников Рп из евклидова юетранства аппроксимирующих множества С из класса ВКТ С из К1* в ;трике Хаусдорфа <?(-, •) с любой степенью точности, т.е. таких многогран-гков, что НпЗп^оо <У(Р", С) = 0. Для решения задачи используется возмож->сть аппроксимации любого С £ С на основе расчета значений его опорной ункции д{и\С) таХуес < и, у > для различных направлений и € 5й, ,е 42 {и е Ж'' : ||и|| = 1}. Для С £ С в работе рассматриваются два :па аппроксимирующих С многогранников: вписанные в С многогранники, внутренние многогранники, все вершины которых принадлежат границе , и описанные многогранники, т.е. внешние многогранники, все гипергра-[ которых касаются границы С. Эти многогранники могут быть построены , основе расчета значения опорной функции С: для некоторого направле-[я и* б может быть рассчитана граничная точка р* тела такая, что и*,р* >= д(и*\С), которая может быть использована в качестве вершины исанного многогранника Р, и значение опорной функции д(и*\С), вместе с определяющее гипергрань {у € :< и*,у >< д(и*|С)} описанного мно-гранника ф. Введение содержит также основные определения и описание вестных метода УО и метода сближающихся многогранников. В работе используются следующие понятия итеративных и адаптивных тодов аппроксимации ВКТ.

Определение 1. Итеративным назовем метод аппроксимации ВКТ мно-гранниками, в котором строятся последовательности телесных многогран-ков Р°, Р1, • • •, Рп, ■ • •, причем на каждой итерации п последующий мно-гранник Р™ строится на основе предыдущего за счет добавления к сово-пности его вершин единственной новой вершины.

Определение 2. Итеративный метод аппроксимации назовем адаптив-ш, если на каждой итерации метода для выбора новой вершины, наряду шформацией об аппроксимируемом теле, используется информация об ап-оксимирующем многограннике, построенном на предыдущей итерации. Примером адаптивного метода является метод УО, в котором ВКТ ап-оксимируется вписанными в него многогранниками. Для выбора очеред-й точки, присоединяемой к уже построенному аппроксимирующему миого-

граннику Рп, на (п+1)-й итерации используется представление многограш; ка Рп в виде множества решений системы линейных неравенств. Выбирает такое направление и*, на котором достигается максимум разности значен: опорной функции аппроксимируемого тела и многогранника Рп по всем в правлениям внешних нормалей гиперграней Р". К многограннику Рп прис единяется такая граничная точка р* тела, что < и*,р* >= д(и*\С). Альте нативным адаптивным методом является метод сближающихся многогра ников (метод СМ) (Г. К. Каменев, 1986), в котором ВКТ аппроксимирует парами вписанных и описанных многогранников. В качестве очередного в правления уточнения многогранников выбирается направление и*, на кот ром достигается максимум разности значений опорной функции описанн го и вписанного аппроксимирующих многогранников по всем направленш внешних нормалей гиперграней вписанного многогранника, а соответству] щая направлению и* граничная точка аппроксимируемого тела использует в качестве очередной вершины, присоединяемой к вписанному многогранн ку. К недостаткам метода СМ относятся отсутствие доказательства его ха> дофовости, сложность реализации метода и низкое качество многограннике получаемых на ранних этапах аппроксимации негладких тел.

В главе 1 предложен адаптивный метод аппроксимации выпуклых ко пактных тел многогранниками — модифицированный метод сближающи ся многогранников (метод МСМ) и проведено теоретическое исследован свойств этого метода. В 1.1 изложено описание метода МСМ. Схема работ метода состоит в следующем. Пусть аппроксимируется С £ С. Считаете что известен метод расчета значений опорной функции д(и\С) тела С, за/: но значение параметра метода /3,0 < /3 < 1, а также заданы в виде мно» ства решений системы линейных неравенств вписанный многогранник Р° . описанный многогранник <5°. Пусть на гг-й итерации метода построены вп санный многогранник Рп и описанный многогранник Пусть Л{Рп) — в нечное множество единичных внешних нормалей гиперграней многогранни Рп 1 число расчетов опорной функции С на п-й итерации метода. Тог,

(п+1)-я итерация метода состоит в следующем. Пусть дп+1 = 0 и = Я Шаг 1: а) находим и* £ II(Р71):

<?№„+1) - 9(и*\Рп) = итахп){д(и\(Э1+1) - д{и\Рп)}.

Если д(и*|(2£п+1) - д{и*\Р"') = 0, то останавливаем работу метода, иначе г реходим к п. б) шага 1;

б) для направления и*, найденного в п. а) шага 1, вычисляем Дп+1(и<)

д(и'\С) - д(и*\Рп)

в) строим 4i+1 следующим образом

Ql+i+1 = Ql+i П ь € Md :< и*, у >< fl(u*|£7)}

i увеличиваем qn+1 на единицу;

г) если An+i(u*) < /3, возвращаемся к п. а) шага 1, иначе переходим к г. а) шага 2.

Шаг 2: а) находим точку р* границы тела С такую, что < и*,р* >= i{u*\C); б) берем Рп+1 = сопу{р*, Рп}, где conv обозначает выпуклую обо-ючку; в) берем Qn+X = • На этом (гг-f 1)-я итерация метода завершена.

В отличие от метода УО, на каждой итерации метода МСМ с /? < 1 ис-юльзуется малое число расчетов опорной функции аппроксимируемого тела. 1ри ,0 = 0 метод МСМ представляет собой метод СМ, а при /3 > 0 метод /ГСМ, в отличие от метода СМ, отсеивает направления, использование кото-)ых не приводит к существенному улучшению точности аппроксимации.

В 1.2 проведен теоретический анализ скорости сходимости последователь-юстей вписанных многогранников, порождаемых методом МСМ при /3 > 0 [ри аппроксимации С 6 С2, т.е. ВКТ с дважды непрерывно дифференцируемой границей и положительными главными кривизнами. Поскольку в итера-ивных методах число вершин вписанного многогранника и номер итерации тличаются на постоянную величину — число вершин многогранника началь-:ой аппроксимации Р°, то скорость сходимости итеративного метода можно зучать как зависимость отклонения S(Pn,C) от номера итерации п, так и :ак зависимость отклонения от числа вершин вписанного многогранника Р". & дальнейшем изучается зависимость отклонения от числа вершин вписан-ого многогранника. При анализе скорости сходимости метода МСМ в 1.2 спользованы свойства хаусдорфовых последовательностей многогранников.

Определение 3. Последовательность многогранников {Р"}л=од,-1 э.п-роксимирующих С £ С, называется хаусдорфовой с константой 7, ес-и существует константа 7 > 0 такая, что S(Pn,Pn+1) > 7<5(Р™,С) для . = 0,1,....

В 1.2.1 показано, что благодаря наличию п. г) шага 1 метода, последова-ельности вписанных многогранников, порождаемые методом для С £ С ри 0 < /3 < 1, являются хаусдорфовыми. Следствием этого является

Теорема 2. Пусть СЕ С2 и0<(3<1. Пусть {Рп}п=од,... — после-ователъностъ вписанных многогранников, порождаемая методом МСМ с араметром Д для С. Тогда для V е > 0 3 п£ такой, что при п>пЕ

5{Рп, С) < (1 + е)---оТПГ~у\' где (!)

eQ3,C) = fW-V pmin(C) - минимальный padi

кривизны поверхности С, ст(С) — площадь поверхности С, В — единичн шар в с центром в начале координат, па — объем шара В и mt(Pn) число вершин многогранника Рп.

Известно, что для любого С Е С и любого номера т > d + 1 существ} многогранник наилучшей аппроксимации (МНА) в метрике Хаусдорфа I такой, что ¿(ГГ", С) = infp^v^c) С), где Т'п(С) — множество вписашл в С многогранников из Md, число вершин которых не превышает т. Д С ЕС доказано (R. М. Dudley, 1974, Е. М. Бронштейн и JI. Д. Иванов, 191 существование константы Const > 0 такой, что

6<!Г,0< Const

m2/(d-l) ■

Известно (R. Schneider, 1981, Р. М. Gruber, 1992), что для С ЕС2 существу константа const > 0 такая, что

COnSt < <5(IT", С), (

mVid~ D

а также выполняется

lim П&^ЩТГ, С) = А(С), (

m-ioo

где величина А(С) называется аппроксимируемостью С Е С2; она являет теоретической характеристикой возможностей приближения тела вписанн ми многогранниками с заданным числом вершин. Поскольку ни одна nocj довательность вписанных многогранников с последовательно возрастающ! числом вершин не может обеспечить лучшую точность аппроксимации, 4i последовательность а Для метода УО порядок числа верш:

равен 2f(d— 1) (Г. К. Каменев, 1994), то порядок 2/(d— 1) является опт мальным для итеративных методов. В 1.2.2 показано, что при аппроксиы ции С Е С2 метод МСМ с ß > 0 оптимален по порядку числа вершин. В 1.2 для сравнения с МНА последовательностей вписанных многогранников, г рождаемых методом МСМ, используется понятие асимптотической эффе тивности г]({Рп}) последовательности многогранников {Pn}n=o,i,-i где

» ^ 8(рп,С) • (

Из (5) следует, что асимптотическая эффективность любой последователь!) сти, не оптимальной по порядку числа вершин, равна нулю. В 1.2.3 свойст

саусдорфовых последовательностей использовапы для доказательства положительности эффективности последовательностей {.Рга}п=о,1,-, порождаемых методом при /3 > 0 для С € С2, а также при выводе оценок (6) эффективности последовательностей, порождаемых для С 6 С3

г,{{П) > А-М (б)

4 { {а + 1)й ) Ртах[су ^

'де — плотность покрытия М^ единичными шарами, ртах(С) — максимальный радиус кривизны поверхности С.

В 1.3 проведен теоретический анализ зависимости отклонения 5(Рп,С) >т числа расчетов опорной функции аппроксимируемого тела С Е С2, вы-юлняемых методом при /? < 1. При поведении анализа применена техни-са вычисления оценок суммарного изменения объемов аппроксимирующих лногогранников на итерациях метода. Показана сходимость пар вписанных I описанных многогранников в метрике Хаусдорфа и получены сформули-юванные ниже оценки сходимости этих пар в метрике Хаусдорфа и метрике )бъема симметрической разности 53(•,•), где (^(Са, С2) = ^(СхДСг), ц(-) — *ера объема в Си С2 е С и С, Д С2 = (СДС2) и (С2\С1).

Теорема 7. Пусть СеС2иО</3<1. Пусть {{Рп, <2п)}„=од,... - последовательность пар многогранников, порождаемая для С методом МСМ : параметром /?. Тогда для V е > 0 3 пе такой, что при п > пе

5(Р\ СГ) < (1 + е)-1 (7)

5\Рп,Яп) < (1 + е)-1 п, где

^ — число расчетов опорной функции С на п итерациях метода,

ЫАО - (I - (-—^^тТ''* ^

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

опорной функции при увеличении числа вершин на единицу. Из (2) и (3) еда дует, что порядок числа расчетов опорной функции для этого метода раве 2/{d — 1). Поскольку при аппроксимации С G С2 ни один итеративный mi тод не может использовать меньшего числа расчетов опорной функции, че этот гипотетический метод, то следствием оценки (7) является оптимад] ность метода МСМ при /3 < 1 по порядку числа расчетов опорной функци для С 6 С2. Существование оценки (7) отличает метод МСМ от метода УС для которого теоретические оценки числа расчетов опорной функции, нео( ходимого для достижения некоторой точности, не получены.

В 1.4 проведен теоретический анализ метода МСМ с /? > 0 при annpoi симации любых С 6 С, в том числе и негладких. В 1.4.1 показана прина; лежность последовательностей вписанных многогранников {-Pn}n=o,i,-> ш рождаемых методом МСМ при /3 > 0, подклассу класса хаусдорфовы последовательностей, введенному Г. К. Каменевым (1999).

Определение 4. Последовательность многогранников {Pn}n=o,i,-I ai проксимирующих С G С, называется H\{f, С)-последовательностью, есл существует константа 7 > 0 такая, что для любого п = 1,2, • ■ • и гранично точки рп тела С такой, что Pn+l — conv{p„, Рл}, существует направлени ипе{и 6 Sd :< и,рп >= д{и\С)} такое, что д{ип\С) - g(tt„|Pn) > у5{Рп, С

Теоретические оценки скорости сходимости #1(7, С)-последователыюсте использованы при анализе скорости сходимости метода для С ЕС, благодар чему получена теорема 13.

Теорема 13. Пусть С £ С иО < fî < 1. Пусть {Р"}п=од,... — последов! телъность вписанных многогранников, порождаемая для С методом MCI с параметром (3. Тогда для V е > 0 3 пе такой, что при п>п£

АсЫ [т'(Рп)]2

где 7i = f3/a(C), а(С) — асферичность С и Ас{7) = min{vli(7),/l2(7)

= ^ fef^ Ml) = i , R - M,;

внешнего для С шара.

Как видно, порядок числа вершин в оценке (8) совпадает с порядком числ вершин в оценке (2) для МНА. В 1.4.2 получены оценки числа расчете опорной функции С 6 С, выполняемых методом МСМ при /3 < 1.

Теорема 15. Пусть СеСыО</3<1. Пусть {(Pn, Q")};=0,i,... - m

следователъностъ пар многогранников, порождаемая для С методом MCI

параметром /3. Тогда для V е > О 3 п6 такой, что при п> пг

(а(С)2 - 1)~1/2а(С)«'/(1-'0.

Оценки, аналогичные (9), получены в 1.4.2 и для 53{Рп,Оп). Таким образом, метод МСМ является единственным адаптивным методом аппрокси-тции ВКТ многогранниками, для которого показана как оптимальность по юрядку числа вершин и числа расчетов опорной функции аппроксимируе-гого тела С б С2, так и получены оценки числа вершин при аппроксимации 7 е С, совпадающие по порядку с оценками для МНА.

В главе 2 описаны методика проведения и результаты экспериментально-о исследования метода МСМ. Экспериментальное исследование необходимо, :оскольку при проведении теоретического анализа свойств метода не полу-:ены точные значения констант, характеризующих зависимость отклонения (Рп,С) от числа вершин вписанных многогранников т1{Рп) и числа расче-ов опорной функции аппроксимируемого тела, а экспериментальные данные озволили получить оценки этих констант и изучить зависимость оценок от войств аппроксимируемого тела. Кроме того, удалось провести сравнитель-ый анализ качества аппроксимации при разных значениях параметра ¡3 и ыработать рекомендации по выбору /3 в зависимости от свойств аппрокси-[ируемого тела. Экспериментальное исследование проведено на основе ап-роксимации многомерных эллипсоидов.

В 2.1 рассмотрены вычислительные аспекты проведения численных экс-ериментов по аппроксимации эллипсоидов и описана методика анализа дан-ых экспериментов. Реализован предложенный Г. К. Каменевым (1986) спо-об приближенного вычисления Л(С) и 5(П"\С) для С = Н{ах,..., а^), где

1(а,\, • • •, а<0 = {х е К«* : < 1}, щ > 0, » = !,-••, Л. Для эл-

ипсоида Н(й1, ■ ■ •, а/) вычисление А (И) сводится к численному интегриро-анию в обобщенных сферических координатах по некоторой прямоугольной бласти, после чего для расчета <5(Пт, Я) используется (4). Реализованный пособ вычисления А(Н) и £(Пт,#) позволил сформировать совокупность ллипсоидов где ^(3) = 201 и N(4) = 91, поверхностный объ-

м элементов которой совпадает с поверхностным объемом единичного шара ? С Ж^, а аппроксимируемость элементов имеет равномерное распределе-ие на полуинтервале (0,Л(В)]. Такой способ формирования совокупности позволил изучить влияние А (С) на качество работы метода.

Методика анализа данных включает:

1) методику исследования скорости сходимости метода МСМ. Поскольку теоретические оценки отклонения в метрике Хаусдорфа, свидетельствующш об оптимальности порядка числа вершин, имеют асимптотический характер оценки констант, характеризующих зависимость отклонения от числа вершин, можно получить на основе экспериментальных данных только в тоь случае, если число вершин достаточно велико для проявления асимптотических свойств метода. Для проверки этого применяются методы простой линейной регрессии. На основе (1) предполагается наличие линейной связ? -1п5р*{Рп,Н{) « — ЪА*(Н{) + ш*(Щ) 1пш'(Рп) и по методу наименыпю квадратов вычисляется экспериментальный порядок числа вершин

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

' где — 2/ (с? — 1) и изучается влияние Л(Я,-) на это отношение. Для эллипсоидов ^ с близкими а>(с2) и а/(Яг) по методу наименыпю квадратов вычисляется экспериментальная константа скорости сходимости к сравнивается с Л(Я,-);

2) методику исследования зависимости отклонения от числа расчетоЕ опорной функции, аналогичную методике из п. 1);

3) методику исследования эффективности метода МСМ, основанную на вычислении эффективности метода на п-й итерации г?„(Я,-) и изучении ее асимптотического поведения;

4) методику исследования отношения Д„+1(и*), где и* — направление, с которым на (п 4- 1)-й итерации метода МСМ осуществлен переход на шаг 2, Соотношение между Ап+1(щ*) и параметром /? характеризует степень влияния значения /3 на процесс уточнения вписанного многогранника Рп\

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

По описанной выше методике проведено также исследование метода УО и метода СМ, что позволило экспериментально сравнить свойства этих методов со свойствами метода МСМ.

В 2.2 описаны результаты экспериментального исследования метода МСМ для й — 4. Исследование зависимости отклонения 6(Р", С) от числа вершин т1[Рп) показало, что можно выделить широкий класс эллипсоидов (к нему относятся эллипсоиды Я такие, что Л (Я) > 0.5), для которых при любых значениях параметра /3 порядок числа вершин вписанных многогранников, построенных в эксперименте, близок к оптимальному. Эллипсоиды Я такие, что А[Н) < 0.5 обладают большой асферичностью (а(Я) > 60), чем и

ожно объяснить то, что для этих эллипсоидов метод выходит на оптималь-ые теоретические характеристики только при очень большом числе вершин, ревосходящем число вершин многогранников, построенных в эксперименте, [сследование констант, характеризующих зависимость отклонения от числа ершин показало, что для любого элемента Н^ скорость сходимости последо-ательносгей вписанных многогранников, порождаемых методом МСМ, не олее чем в 2.5 раза уступает скорости сходимости МНА. Ближе всего к 1НА по скорости сходимости находятся методы с параметром /3, близким

единице, при работе которых выполняется большое число расчетов опорой функции аппроксимируемого тела — их скорость сходимости всего в 1.5 аза уступает скорости сходимости МНА. Очень важно, что к этим мето-ам близки по скорости сходимости методы с /3 < 0.3, для которых число асчетов опорной функции относительно мало. При любых значениях пара-етра /3 отношение экспериментальной и теоретической констант практиче-ш не зависит от аппроксимируемости тела для Л,- таких, что Л(#,) > 1.0, е. эллипсоидов с асферичностью не превосходящей 15, и наблюдается его езначительный рост для эллипсоидов Д- таких, что 0.5 < А(Щ) < 1.0, го свидетельствует об отклонении скорости сходимости метода от скорости содимости МНА при увеличении асферичности.

Исследование числа расчетов опорной функции аппроксимируемого тела, эшолняемых методом МСМ, показало, что можно выделить широкий класс 1липсоидов (к нему относятся эллипсоиды Н такие, что Л(Н) > 0.5), для эторых характер зависимости отклонения от числа расчетов опорной функ-яи зависит от параметра /3 таким образом, что при увеличении параметра /? г нуля до единицы монотонно увеличивается число расчетов опорной функ-яи, необходимое для достижения некоторой точности аппроксимации. Уже гся значений /3 > 0.7 выход на асимптотические свойства метода требует роведения значительного числа расчетов опорной функции, которое пре-зсходит число расчетов, выполненное в эксперименте. Исследование кончит, характеризующих зависимость отклонения от числа расчетов опорой функции для метода МСМ при /3 < 0.7 показало, что независимо от шроксимируемости тела число расчетов опорной функции, выполняемых етодом, не более чем в 3.5 раза превосходит число расчетов, необходимое гаотетическому оптимальному методу. По сравнению с методом УО метод ^СМ позволяет значительно уменьшить число расчетов опорной функции шроксимируемого тела, что особенно заметно при увеличении размерности та увеличении точности аппроксимации.

Исследование эффективности метода МСМ показало, что асимптотиче-сая эффективность метода зависит от значения параметра /3 и при любых

/3 практически не зависит от аппроксимируемости тела. Для каждого эле мента Hi совокупности наибольшие значения (близкие к 0.65

эффективность принимает для метода УО и метода МСМ при /3 — 0.9£ уменьшается при уменьшении 0, принимая для /3 = 0.5 минимальные значе ния, а затем возрастает и при /3 < 0.2 приближается к 0.6.

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

Обобщением результатов исследования метода МСМ являются рекомен дации по его использованию.

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

Параграф 3.1 содержит описание системы, созданной диссертантом сов местно с А. В. Лотовым, В. А. Бушенковым и Р. В. Ефремовым. В 3.1.1 дан; математическая формулировка МДЦ. МДЦ разработан для анализа много критериальных проблем принятия решений, в его рамках обеспечиваются аппроксимация и визуализация множества достижимых значений критери ев /(X), где / : V/ — отображение, действующее из пространств!

решений IV в критериальное пространство Ж**, & X С \У — множество до пустимых решений. В модели, описывающей исследуемую проблему улучше ния качества воды, IV является линейным конечномерным пространством, ^ — выпуклым многогранным множеством, а / — линейным отображением. I описываемой системе вместо /(X) строится более широкое множество ¡*(Х) имеющее ту же эффективную границу. Это множество, называемое оболоч кой Эджворта-Парето (ОЭП) множества /(X), представляет собой множе ство f{X), дополненное доминируемыми им критериальными точками, т.е /*(Х) = 1(Х) -Ь где — неотрицательный ортант в Ж^. Аппроксимацш ОЭП используется в процессе визуального изучения эффективной границь множества /(X), в результате которого пользователь выбирает некоторо( достижимое недоминируемое сочетание значений критериев (достижимук целевую точку); далее выполняется расчет решения х 6 X, реализация ко торого приводит к достижению выбранной целевой точки.

В 3.1.2 описана интегрированная линейная модель, используемая в систе ме для описания проблемы улучшения качества воды. Модель адаптирован; к бассейну реки Ока. Она включает 539 переменных, более 500 ограничена

состоит из трех компонент:

1) модели выброса загрязнителей, разработанной специалистами Инсти-ута водных проблем РАН;

2) упрощенной модели переноса загрязнителей, которая представляет со-ой матрицу влияния, связывающую выброс загрязнителей и их конценгра-ию в каждом из створов реки; модель сформирована специалистами проект-ой организации "Союзводпроект" на основе компьютерных экспериментов системой М1КЕ11, разработанной Датским гидравлическим институтом и оделирующей перенос и распад загрязняющих веществ;

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

В 3.1.3 описаны подсистемы, реализующие основные этапы МДЦ для про-лемы улучшения качества воды, а именно:

1) подсистема подготовки исходных данных, представляющая собой ге-ератор задач линейного программирования, используемых в системе при ппроксимации множества 1(Х) или его ОЭП;

2) подсистема для выбора критериев из числа переменных интегриро-1нной линейной модели (характеристик загрязненности, финансирования т.п.) и назначения ограничений на значения переменных;

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

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

5) подсистема расчета стратегии улучшения качества воды, соответству-щей выбранной целевой точке;

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

В 3.1.4 рассмотрен пример использования системы для исследования про-гемы улучшения качества воды в реке Ока. В 3.2 описаны результаты использования метода МСМ при аппроксима-га негладких ВКТ, возникающих в проблемах, изучаемых в рамках инте-»ированной линейной модели планирования качества воды в реке Ока. Про-

ведено сравнительное изучение работы метода УО и метода MGM при разнь значениях параметра ¡3 для типичных задач анализа, сформулированнь специалистами Института водных проблем РАН и проектной организащ "Союзводпроект". Исследование показало, что использование метода МС в рассмотренных задачах позволяет сократить, по сравнению с методом У( время, необходимое для аппроксимации ОЭП. Например, в типичной пят: критериальной задаче достижение точности аппроксимации 1% требует пр использовании метода МСМ в 4 раза меньше времени, чем при использ вании метода УО. Проведен анализ проблемы выбора значения параметр /3 и показано, что в зависимости от предпочтений пользователя, значен! параметра /3 должно выбираться из диапазона [0.1,0.5].

Приложения 1-3 содержат графические материалы экспериментально] исследования метода МСМ.

Основные результаты диссертации опубликованы в работах:

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

2. Лотов А. В., Бурмистрова Л. В., Бушенков В. А., Ефремов Р. В., Б; бер А. Л., Брайнин Н. А., Максимов А. В. Интегрированная система д.1 поиска эффективных стратегий улучшения качества воды // Сб. тез. док. XXVII школы-семинара "Математическое моделирование в проблемах рац) онального природопользования". Ростов-на-Дону, 1999. С. 110-113.

3. Bourmistrova L. V. Algorithm for approximation of feasible sets in criteric space in linear problems with a large number of decision variables // Тез. док. 2-й моек, междунар. конф. по иссл. операций. М.: ВЦ РАН, 1998. С. 5.

4. Lotov А. V., Bourmistrova L. V., and Bushenkov V. A. Efficient Strategie An Application in Water Quality Planning // Decision Support Systems f< Sustainable Development. Boston etc: Kluwer Acad. Pubis, 1999. P. 145-166.

5. Lotov A., Bourmistrova L., Efremov R., Bushenkov V. Environment application of the feasible goals goals method: screening of water qualil improvement strategies // Abstr. of the 15th Intern, conf. on multiple criter decision making. Ankara: Middle East Technical University, 2000. P. 99.

6. Lotov A., Bourmistrova L., Bushenkov V., Efremov R.; Buber A., Braini N., Maksimov A. MIKE 11 and Interative Decision Maps: joint application in D£ for Water Quality Planning // The 3d Software Conference. Helsingor: Danis Hydraulic Institute, 1999. http://www.dhi.dk/softcon/papers/027/027.htm.

Введение

1 Теоретический анализ сходимости и эффективности модифицированного метода сближающихся многогранников

1. Описание метода.

2. Скорость сходимости и эффективность метода при аппроксимации гладких выпуклых компактных тел.

2.1. Скорость сходимости метода.

2.2. Оптимальность метода по порядку числа вершин.

2.3. Эффективность метода по числу вершин.

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

4. Свойства метода при аппроксимации выпуклых компактных тел общего вида.

4.1. Скорость сходимости метода.

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

5. Анализ оценок скорости сходимости метода для гладких выпуклых компактных тел.

2 Экспериментальный анализ адаптивных методов аппроксимации выпуклых компактных тел многогранниками в классе эллипсоидов

1. Методика проведения экспериментального анализа.

1.1. Методика построения совокупности эллипсоидов.

1.2. Методика исследования асимптотических свойств методов

1.3. Методика изучения методов при малом числе вершин

2. Результаты экспериментального анализа методов.

2.1. Анализ асимптотических свойств методов.

2.2. Анализ методов при малом числе вершин

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

1. Описание системы поддержки поиска эффективных стратегий улучшения качества воды в бассейнах крупных рек.

1.1. Основы метода достижимых целей.

1.2. Математическая модель планирования качества воды в реке

1.3. Основные подсистемы и их назначение.

1.4. Использование системы для планирования качества воды и распределения финансирования в бассейне реки Ока.

2. Сравнительный анализ результатов использования адаптивных методов

2.1. Методика проведения сравнительного анализа методов

2.2. Анализ результатов использования методов в системе

2.3. Применение метода разумных целей для исследования проблемы выбора значения параметра ß.

Математическое моделирование является признанным средством поиска эффективных решений сложных проблем. При использовании математических моделей для поиска эффективных решений важную роль играют методы многокритериальной оптимизации [45], позволяющие учесть противоречивые требования, предъявляемые к рассматриваемым решениям. Одним из методов многокритериальной оптимизации является метод достижимых целей (МДЦ), предложенный в [26] и нашедший в последнее время широкое распространение в практике поддержки принятия решений. В рамках МДЦ осуществляется аппроксимация и визуализация многомерных множеств достижимых значений критериев оценки качества решений (так называемых множеств достижимых целей). МДЦ помогает изучить как возможные значения критериев, так и взаимозависимости между их недоминируемыми сочетаниями, что способствует поиску и изучению разумных компромиссных решений (см. [28]). Применение МДЦ для поиска эффективных решений экономических задач началось еще в семидесятых годах [8], [61]. С середины восьмидесятых годов МДЦ используется для поиска эффективных стратегий улучшения состояния окружающей среды [49], [50], [59], [64]. В начале девяностых годов, когда возник интерес к изучению проблем регулирования рыночной экономики, МДЦ использовался для поиска стратегий государственного регулирования экономики [32]. Другими важными областями применения МДЦ являются изучение возможных вариантов технических систем на предпроектной стадии процесса проектирования, анализ задач бизнеса, в том числе разработка стратегий развития фирм, финансовое планирование и т.д.

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

Построение аппроксимации выпуклых множеств многогранниками является классической проблемой, нахождение способов решения которой представляет большой теоретический и практический интерес, поскольку задача аппроксимации выпуклых множеств возникает во многих приложениях: при аппроксимации множеств достижимости динамических систем ([21]-[23], [25], [34], [40], [41], [60]), в математическом программировании ([10], [31], [73]), в теории многокритериальной оптимизации [45], в кодировании изображений, дизайне и др. Стандартный подход к построению многогранников, аппроксимирующих выпуклые множества, основан на расчете значений опорной функции аппроксимируемого множества на некоторой заданной сетке направлений. В [75] показано, что использование заранее заданных (так называемых неадаптивных) сеток направлений не позволяет эффективно аппроксимировать многомерные множества. Для эффективной аппроксимации многомерных множеств была выдвинута концепция адаптивной итеративной аппроксимации выпуклых множеств многогранниками и предложен первый метод такого типа — метод уточнения оценок (метод УО) [7], в котором направления для расчета значения опорной функции аппроксимируемого множества формируются с использованием описания уже построенного аппроксимирующего многогранника. Разработка устойчивой численной схемы метода УО [42] позволила реализовать математическое обеспечение, предназначенное для построения аппроксимации выпуклых множеств при помощи этого метода. До последнего времени метод УО являлся единственным методом аппроксимации выпуклых множеств многогранниками, используемым в рамках МДЦ.

С середины 80-х годов ведется теоретический анализ адаптивных методов аппроксимации выпуклых множеств многогранниками ([10], [11], [14]-[20], [75]). Для анализа адаптивных методов выдвинута концепция хаусдор-фовых методов аппроксимации выпуклых компактных тел многогранниками и показано, что методы, являющиеся хаусдорфовыми, оптимальны по порядку скорости сходимости для гладких тел [16]. Было показано, что метод У О является хаусдорфовым и потому оптимален по порядку скорости сходимости [18]. Однако анализ практического использования метода УО показал, что его недостатком является необходимость использования многократных расчетов значения опорной функции аппроксимируемого тела на каждой итерации. Каждый расчет значения опорной функции в практических задачах сложен и требует значительного времени, что приводит к существенным затратам времени на построение и аппроксимацию множества достижимых значений критериев с помощью метода УО. Эта проблема особенно остро стоит при многократной аппроксимации тел в диалоговом режиме, а такой способ исследования используется в компьютерных системах поддержки поиска эффективных решений многокритериальных проблем.

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

Целями диссертационной работы являются:

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

2) обоснование оптимальности разработанного метода;

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

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

Математическая постановка задачи аппроксимации выпуклых компактных тел (ВКТ) многогранниками, методы решения которой разрабатываются и исследуются в диссертации, выглядит следующим образом. Рассматривается евклидово пространство где d > 2, со скалярным произведением <•,•>, расстоянием d(-, •) и нормой || • ||. Пусть С — класс ВКТ в Rd и с>(-, •) — метрика Хаусдорфа в классе С (см., напр., [24]), т.е. для Ci, С2 € С

Ci, С2) max < sup d(x, C2), sup d(x, C\) > .

UeCi xeC2 J

Пусть некоторое С 6 С задано методом расчета значений своей опорной clef clef функции д(и\С) = max{< и,х >: х е С}, где и £ Sd = {и Е Rd : ||u|| = 1}. Для заданного таким образом С, т.е. для С, заданного методом расчета значений своей опорной функции, нужно построить последовательность выпуклых телесных многогранников Рп С аппроксимирующих его с любой степенью точности, т.е. таких многогранников Рп, что lim 5(Рп, С) = 0. (1)

71—lOO

Идея, на которой основана аппроксимация ВКТ многогранниками, состоит в том, что любое С £ С можно аппроксимировать многогранниками на основе расчета значений его опорной функции д(и\С) для различных направлений и € Чаще всего для С ЕС рассматриваются два типа аппроксимирующих тело С многогранников из вписанные в тело С многогранники, т.е. внутренние для С многогранники, все вершины которых принадлежат границе С (их совокупность обозначим через Тг(С)), и описанные многогранники, т.е. внешние для С многогранники, все гиперграни которых касаются границы С (их совокупность обозначим через Vе(С)). В результате расчета значения опорной функции С для некоторого направления и* Е находится граничная точка р* тела такая, что < и*,р* >= д(и*\С), которая может быть использована в качестве вершины вписанного многогранника Р, аппроксимирующего С, а также значение опорной функции д(и*\С), определяющее вместе с направлением ад* гипергрань {у Е К6' :< и*, у >< д(и*\С)} описанного многогранника ф, аппроксимирующего С.

Методы построения многогранников, аппроксимирующих ВКТ, за исключением классического метода Минковского [68], можно разделить на две группы:

1) методы, в которых построение аппроксимирующих многогранников основано на построении асимптотически оптимальных покрытий поверхности аппроксимируемого тела ([31], [67], [71], [72]);

2) итеративные методы аппроксимации ([6], [7], [9], [10], [19], [47], [74]).

К первой группе относятся методы из [57], [71], [72], не предлагающие конкретных способов построения аппроксимирующих многогранников для ВКТ С 6 когда ¿>2. Метод из [67] также предназначен исключительно для аппроксимации плоских фигур, а метод из [31] — для оптимизации значения некоторой функции и аппроксимация в этом методе осуществляется попутно.

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

Для исследования итеративных методов аппроксимации, в которых последовательность аппроксимирующих многогранников Рп принадлежит Vх {С) или 7>е(С), в [16] введены понятия аппроксимирующих схем восполнения и отсечения.

Определение 2. Итеративный метод аппроксимации реализует схему восполнения, если для любого С ЕС последовательность порождаемых этим методом многогранников Рп принадлежит классу Тг(С), а на каждой итерации метода выбирается некоторая граничная точка р тела С и очередной многогранник Рп+1 строится в виде РП+1 = сопу{р, Рп}, где сопу обозначает выпуклую оболочку множества точек, в данном случае выпуклую оболочку точки р и вершин многогранника Рп.

Определение 3. Итеративный метод аппроксимации реализует схему отсечения, если для любого С Е С последовательность порождаемых этим методом многогранников О"1 принадлежит классу Vе(С), а на каждой итерации метода выбирается направление и Е и очередной многогранник С}п+ строится в виде <2п+1 = ЯпГ\ {у ЕЕ!1 :< у,и >< д(и\С)}.

Поскольку

1) практика и теоретические оценки показывают (см., напр., оценки из [55]), что сложность описания аппроксимирующего многогранника, характеризуемая прежде всего числом его вершин, возрастает с увеличением точности аппроксимации или увеличением размерности пространства с?;

2) в практических приложениях каждый эксперимент с объектом [46], осуществляемый в процессе работы метода аппроксимации (например, расчет значения опорной функции аппроксимируемого тела) обычно сложен и требует значительного времени, то для использования методов аппроксимации ВКТ многогранниками в практических приложениях необходимо знание теоретических оценок отклонения от аппроксимируемого тела последовательностей многогранников, порождаемых этими методами, через такие характеристики, как:

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

С, т.е. оценок вида 5(Рп, С) < const/(Ln)a, где Ln — число расчетов опорной функции тела С, выполненных методом на п итерациях, и а — некоторое положительное число;

2) сложность описания аппроксимирующих многогранников, например, число вершин аппроксимирующих многогранников Рп, порожденных методом для тела С, т.е. оценок вида 5(Рп, С) < const/(т*(Рп))а, где п — номер итерации метода, a mt(Pn) — число вершин многогранника Рп, построенного на n-й итерации.

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

При изучении качества аппроксимации в метрике Хаусдорфа последовательностями многогранников, порождаемыми итеративными методами, получаемые теоретические оценки скорости сходимости последовательностей многогранников сравнивают с оценками для многогранников наилучшей аппроксимации (МНА). Существование МНА для метрики Хаусдорфа доказано теоретически, а вводятся МНА следующим образом. Пусть Тгт{С) — множество тех многогранников из Vl(C): число вершин которых не превосходит т, где т > d + 1 и пусть 5{7)1п, С) определено как

5(Vlm,C)= inf 6(Р,С).

PeV^C) J

Классическим результатом теории выпуклых множеств ([54], [70]) является существование для любого С G С и любого т > d + 1 такого многогранника Пт G Vlm{C), что

6(П.т,С) = 6(Гт,С). (2)

Многогранник Пт, для которого выполняется (2), называется многогранником наилучшей аппроксимации для тела С. Каждому номеру т соответствует свой МНА Пт. Образованная таким образом последовательность называется последовательностью многогранников наилучшей аппроксимации. Следует сразу отметить, что методы построения МНА известны лишь для некоторых тел из R2. Известно ([3], [53], [55]), что МНА для тела С в метрике Хаусдорфа сходятся к этому телу, т.е. lim ¿(Пт, С) = 0.

То—»00

Также известно ([3], [53]), что для любого С 6 С существует такая константа Const > 0, которая в общем случае может зависеть от свойств тела С, что для любого т > d + 1 выполняется п-. о * (з)

Пусть С2 — класс выпуклых компактных тел с дважды непрерывно дифференцируемой границей и положительными главными кривизнами. Известно ([58], [70]), что для С € С2 существует константа const > 0 такая, что для любого т > d, + 1 справедливо да^.С). (4)

Поскольку, в силу определения МНА, ни одна последовательность вписанных многогранников с последовательно возрастающим числом вершин не может обеспечить лучшую точность аппроксимации, чем последовательность {Hm}m=d+i,d+2,., и существуют итеративные методы (напр., методы из [7] и [19]), для которых порядок числа вершин равен 2/(с? — 1), порядок 2/(d—l) является оптимальным порядком числа вершин для итеративных методов аппроксимации. Итеративные методы аппроксимации ВКТ многогранниками, обеспечивающие построение многогранников Рп таких, что const

5{Рп, С) < mt(pn)y/(d-i)' где const > О1^- некоторая константа, называются оптимальными по порядку числа вершин.

Анализ методов аппроксимации ВКТ многогранниками с точки зрения числа расчетов опорной функции, выполняемых этими методами, также основан на сравнении с МНА, и использует гипотетический метод, вводимый следующим образом. Для любого т > d + 1 при переходе от МНА Пш к МНА jjm+i числ0 вершин увеличивается не более чем на единицу, т.е. т*(Пт+1) - т\Пт) < 1.

Рассмотрим гипотетический метод, порождающий последовательность МНА и выполняющий при переходе от Пт к Пт+1 лишь mt(Пт+1) — т*(Пш) расчет опорной функции аппроксимируемого тела, т.е. использующий лишь один расчет опорной функции при увеличении числа вершин на единицу. Ясно, что ни один итеративный метод не может для построения многогранника с менее чем (га + 1)-й вершиной (т > d+ 1) использовать меньшее число расчетов значения опорной функции, чем необходимо такому гипотетическому методу для получения Пт. Для С £ С2 из оценок (3) и (4) следует, что для введенного гипотетического метода выполняется

C°nSt (5) g)2/(d-l) - ^ ' - (¿m)2/(d-l)' где L™ — число расчетов опорной функции С, необходимых методу для получения Пт. Ясно, что ни один реальный метод не может иметь лучшую оценку. С другой стороны, существует метод [19], для которого получена оценка отклонения 5(Рп, С) вида

6) ьс где Lc — число расчетов опорной функции тела С, выполненных методом для построения Рп, и consti > 0 — некоторая константа. Поэтому методы, для здесь и далее const обозначает некоторую положительную константу, которая может зависеть от аппроксимируемого тела С которых получены оценки вида (6), называются оптимальными по порядку числа расчетов опорной функции для С Е С2.

Как уже говорилось, в соответствии с подходом, используемым для выбора направлений расчета значений опорной функции, большинство итеративных методов аппроксимации ВКТ многогранниками можно отнести к одному из двух типов: неадаптивных и адаптивных методов. Неадаптивные методы основаны на использовании априорно заданной сетки на сфере направлений 5й. К неадаптивным относятся, в частности, методы из [21], [40] и [69], возникшие при решении задачи аппроксимации выпуклых множеств достижимости динамических систем. В этих методах ВКТ приближается описанными вокруг тела многогранниками. Направления нормалей гиперплоскостей аппроксимирующего многогранника выбираются из числа направлений априорно построенной сетки, из-за чего не всегда бывает известна гарантированная точность аппроксимации построенным многогранником. Подобного недостатка лишен неадаптивный метод, описанный в [10] и [11]. В этом методе, исходя из требуемой точности аппроксимации и априорной информации о принадлежности аппроксимируемого тела шару известного радиуса, с помощью равномерной сетки в сферических координатах строится е-сеть на поверхности сферы Такой же метод построения сетки направлений применяется в [38], где также предлагается эвристический прием для отбрасывания гиперграней, несущественных для достижения требуемой точности. В [38] представлены также экспериментальные данные о сходимости неадаптивных методов при аппроксимации некоторых двух- и трехмерных тел.

Второй тип итеративных методов аппроксимации ВКТ многогранниками составляют адаптивные методы.

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

Адаптивные методы аппроксимации более эффективны, чем неадаптивные методы. Возможности адаптивных и неадаптивных методов аппроксимации ВКТ исследованы теоретически в [75], где показано, что для любой априорной сетки направлений можно найти такое тело С Е С, что полученные с использованием этой сетки аппроксимирующие многогранники будут сходиться к С лишь со скоростью порядка l/(d— 1), т.е. будет выполняться лишь 5(Рп,С) < const/{mt(Pn))1^d~1\ в то время как наилучшим, как было указано выше, является порядок 2/{d— 1). В [16] приведены экспериментальные данные, подтверждающие сформулированное выше утверждение.

Рассмотрим сначала некоторые адаптивные методы построения аппроксимирующих многогранников, реализующие схему отсечения. Такие методы предложены в [15] и [74]. В методе из [74] очередное направление и Е Sd выбирается адаптивно из узлов априорно заданной регулярной сетки на Sd с учетом теоретической оценки локального отклонения уточняемого многогранника от аппроксимируемого тела. Показано, что для С Е С из M.d при d = 2,3 и С Е С2 из Rd, d > 3 метод из [74] обеспечивает сходимость в метрике Хаусдорфа со скоростью logn), где п — номер итерации метода, отличающийся на постоянную величину от числа гиперграней описанного аппроксимирующего многогранника. Появление множителя logn в оценке скорости сходимости метода из [74] может быть обусловлено априорным выбором сетки направлений на В методе 3 из [15] для уточнения описанного аппроксимирующего многогранника предлагается использовать направление u G на котором достигается максимальное отклонение многогранника в метрике Хаусдорфа от аппроксимируемого С Е С. Этот метод является скорее теоретической конструкцией, поскольку требует вычисления расстояния по Хаусдорфу между двумя компактными множествами.

В адаптивных методах, реализующих схему восполнения, выбор очередного направления и Е Sd адаптирован к форме аппроксимируемого тела С в той мере, в какой уже построенный методом многогранник Рп аппроксимирует это тело. Впервые адаптивный метод, реализующий схему восполнения, предложен в [51] для аппроксимации части границы двумерного выпуклого тела. Этот метод основан на идее уточнения вписанного в тело аппроксимирующего многогранника в направлении нормали той его гиперграни, для которой достигается его наибольшее отклонение от аппроксимируемого тела. В [7] предложен метод уточнения оценок (метод УО), который использует ту же идею уточнения многогранника, но может использоваться и для аппроксимации многомерных выпуклых тел. Метод УО состоит в следующем. Пусть аппроксимируется С € С и пусть перед началом работы метода задан многогранник начального приближения Р° 6 Тг(С) в виде множества решений системы линейных неравенств и в виде совокупности вершин. Пусть на п-й итерации построен Рп е Т%{С) как в виде множества решений системы линейных неравенств, так и в виде совокупности своих вершин, и пусть построено и(Рп) — множество единичных внешних нормалей гиперграней многогранника Рп. Следует отметить, что множество II (Рп) можно считать заданным, если многогранник Рп построен в виде множества решений системы линейных неравенств. Очередная (п + 1)-я итерация метода УО состоит в следующем.

Шаг 1: а) находим направление и* € II (Рп) такое, что д(и*\С) - д(и*\Рп) = итшп){д{и\С) - д(и\Рп)}.

Если д(и*\С) — д(и*\Рп) = 0, то останавливаем работу метода, иначе переходим к п. б). б) находим точку р* границы тела С такую, что для направления и*, найденного в п. а) шага 1, выполняется < и*,р* >= д(и*\С).

Шаг 2: в качестве очередного многогранника Рп+1 берем

Рп+1 = сопу{р\ Рп}, при этом многогранник Рп+г строим в виде множества решений системы линейных неравенств.

Схема работы метода УО в Ж2 представлена на рис.2. Рис. 2 и другие графические материалы, используемые в дальнейшем при изложении, расположены в приложениях диссертации. В [12] и [14] содержатся результаты экспериментального исследования метода УО.

В [16] для анализа адаптивных методов аппроксимации ВКТ многогранниками введено понятие хаусдорфового метода аппроксимации.

Определение 5. Адаптивный метод аппроксимации ВКТ, реализующий схему восполнения или отсечения, называется хаусдорфовым с константой 7 для С £ С, если он порождает последовательность многогранников {Рп}п=од,., для которой существует константа 7 > 0 такая, что:

5(Рп,Рп+1) > 7<5(Рп,С), п = 0,1,---

В [16] доказана сходимость к аппроксимируемому телу С € С последовательностей многогранников, порождаемых хаусдорфовыми методами в метриках Хаусдорфа и объема симметрической разности. Также показано, что для С 6 С2 порядок числа вершин многогранников последовательностей, порождаемых хаусдорфовыми методами, совпадает с порядком числа вершин МНА, т.е. хаусдорфовы методы оптимальны по порядку числа вершин. В [18] доказано, что для С £ С метод УО принадлежит классу хаусдорфовых методов и поэтому для С 6 С2 оптимален по порядку числа вершин.

В [20] для анализа адаптивных методов аппроксимации ВКТ, реализующих схему восполнения, введен подкласс Н\ класса хаусдорфовых методов аппроксимации ВКТ.

Определение 6. Метод, реализующий схему восполнения, принадлежит классу #1(7,(7) методов, если для последовательности многогранников {Рп}п=о,1,.1 порожденной методом для С £ С, существует константа 7 > 0 такая, что для любого номера п = 1,2,. существует направление ип £ {и £ :< и,рп >= д{и\С)}: д(ип\С)-д(ип\Рп)>у5(Рп,С), где точка рп границы тела (7 такова, что: Рп+1 = сопу{рп, Рп}.

В [20] для С (Е С показана сходимость методов из #1(7, С) со скоростью S(Pn,C) < const/mt(Pn)2/(d~1\ т.е. получена оценка скорости сходимости, порядок числа вершин которой совпадает с порядком оценки (3) для МНА. Также в [20] показано, что метод УО принадлежит подклассу Hi, поэтому полученные для методов из Hi оценки скорости сходимости последовательностей многогранников, порождаемых этими методами, распространяются и на метод УО.

В [42] и [43] предложен алгоритм, реализующий рассмотренную в [35] схему "под-над" построения выпуклой оболочки точки и многогранника в виде множества решений системы линейных неравенств, и являющийся устойчивым при проведении приближенных вычислений. Благодаря разработке и исследованию этого алгоритма стала возможной реализация метода УО, выполняющая аппроксимацию тела, заданного своей опорной функцией, в автоматическом режиме без участия пользователя. Метод УО реализован в виде программного обеспечения персональных компьютеров, работающих под управлением операционной системы Windows, и используется в рамках МДЦ в компьютерных системах поддержки принятия решений.

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

В [15] предложен альтернативный адаптивный метод аппроксимации ВКТ — метод сближающихся многогранников (метод СМ). В этом методе одновременно строятся вписанный и описанный аппроксимирующие многогранники, а для их уточнения выбирается направление нормали гиперграни вписанного многогранника, в котором достигается максимальное отклонение в метрике Хаусдорфа вписанного многогранника от описанного. Схема работы метода СМ состоит в следующем. Пусть аппроксимируется С 6 Си пусть перед началом работы метода заданы многогранники начального приближения Р° € Vl(C) и Q0 £ Vе(С) в виде множества решений системы линейных неравенств. Пусть на п-й итерации метода построены в виде множества решений систем линейных неравенств многогранники Рп 6 Vl{C) и Qn £ -pe^j и построено множество U(Pn), тогда (п + 1)-я итерация метода состоит в следующем.

Шаг 1: а) находим направление u* € U(Pn), на котором достигается g(u*\Qn) ~ d{u*\Pn) = max \g{u\Qn) - д{и\Рп)}. иеи(Рп)

Если g(u*\Qn) — д{и*\Рп) = 0, то останавливаем работу метода, иначе переходим к п. б). б) находим точку р* границы тела С такую, что < и*,р* >= д(и*\С).

Шаг 2: а) в качестве очередного многогранника Рп+1 берем

Pn+1 =conv{p*,Pn}, причем Рп+1 строим в виде множества решений системы линейных неравенств; б) в качестве очередного многогранника Qn+1 берем qu+1 = Qn n ^ е Rd ;< ^ у д(и*\С)}.

На этом (п + 1)-я итерация метода завершена. Отметим, что на каждой итерации метода СМ расчет опорной функции аппроксимируемого ВКТ выполняется лишь один раз. Схема работы метода в М2 представлена на рис.3.

В [19] доказана оптимальность метода СМ по порядку числа вершин вписанного аппроксимирующего многогранника и по порядку числа расчетов опорной функции для С £ С2. Также получены верхние оценки скорости его сходимости для С £ С вида 6(Рп, С) < сог^В [4] и [48] метод СМ исследован на основе данных, полученных в результате проведения численных экспериментов по аппроксимации трех- и четырехмерных эллипсоидов и получены экспериментальные оценки его асимптотической эффективности.

Недостатки метода СМ состоят в том, что теоретически не доказана его принадлежность классу хаусдорфовых методов, теоретические оценки его скорости сходимости для негладких тел имеют порядок 1/ (с£ — 1), в то время как для МНА справедливо (3). Также недостатком метода СМ является то, что при относительно малом числе итераций для негладких тел этот метод строит многогранники с избыточным числом вершин [15], что приводит к значительному снижению скорости их визуализации. В связи с наличием указанных недостатков возникла идея модификации метода СМ. В [15] предложены некоторые способы его модификации, которые не привели однако к разработке хаусдорфовых методов аппроксимации ВКТ.

В главе 1 предложен новый хаусдорфов адаптивный метод аппроксимации ВКТ многогранниками — модифицированный метод сближающихся многогранников (метод МСМ). Этот метод предназначен для решения задачи (1) в условиях, когда не задано аналитическое представление опорной функции д(и\С) аппроксимируемого тела С и более того, каждый расчет значения опорной функции требует значительного времени. Глава 1 содержит результаты теоретического исследования свойств метода МСМ при аппроксимации С £ С и С £ С2.

В 1.1 дано описание метода МСМ. В методе МСМ последовательности аппроксимирующих многогранников формируются с использованием значения параметра метода /3, задаваемого до начала работы метода. Также в 1.1 проведено сравнение схемы работы метода МСМ со схемами работы методов

УО и СМ. В 1.2 показана принадлежность метода МСМ классу хаусдорфо-вых методов, на основе чего для С £ С2 получены оценки отклонения от аппроксимируемого тела вписанных многогранников, порождаемых методом при аппроксимации С, как функции числа их вершин. Показана оптимальность метода МСМ по порядку числа вершин, а также исследована эффективность метода с точки зрения числа вершин вписанных многогранников из порождаемых им последовательностей. В 1.3 техника измерения изменения объемов аппроксимирующих многогранников на итерациях метода МСМ использована для получения для С £ С2 оценок, выражающих отклонение многогранников, порождаемых методом, от аппроксимируемого тела через число расчетов опорной функции вида 6(Р, С) < cons где L — число расчетов опорной функции аппроксимируемого тела С, выполненных для построения Р. Существованием подобных оценок метод МСМ отличается от метода УО, для которого оценок, связывающих отклонение с числом расчетов опорной функции аппроксимируемого ВКТ, не существует. В 1.4 показана принадлежность метода МСМ подклассу Hi методов, благодаря чему для С £ С получены оценки отклонения 5(Рп, С) как функции числа вершин аппроксимирующих многогранников Рп, порожденных методом, и показано, что для любых С £ С метод МСМ обеспечивает сходимость в метрике Хаус-дорфа со скоростью 5(Рп,С) < const/mt(Pn)2^d~1\ т.е. со скоростью, оптимальной по порядку. Также в 1.4 получены оценки, связывающие отклонение многогранников, порождаемых методом МСМ, с числом расчетов опорной функции аппроксимируемого тела С 6 С. В 1.5 проведен анализ трех различных оценок, которые полученны для С £ С2 в 1.2, 1.3 и 1.4 и связывают отклонение 5(Рп, С) с числом вершин вписанных многогранников Рп.

В главе 1 при проведении теоретического анализа свойств метода получены грубые оценки значений констант, характеризующих зависимость отклонения от числа вершин и числа расчетов опорной функции. В главе 2 на основе экспериментальных данных, полученных при аппроксимации многомерных эллипсоидов, получены более точные эмпирические оценки констант, характеризующих зависимость отклонения 5(Рп, С) от числа вершин вписанных многогранников mt(Pn) и от числа расчетов опорной функции аппроксимируемого тела, изучена их зависимость от свойств аппроксимируемого тела, проведен сравнительный анализ качества аппроксимации при разных значениях параметра /3 и выработаны рекомендации по выбору значения /3 в зависимости от свойств аппроксимируемого тела.

В главе 3 описана компьютерная система поддержки поиска эффективных стратегий улучшения качества воды в бассейнах крупных рек, созданной диссертантом совместно с А.В.Лотовым, В.А.Бушенковым и Р.В.Ефремовым. В рамках этой системы осуществлено экспериментальное использование метода МСМ, а также выработаны рекомендации по выбору значений параметра метода /3 для его использования в этой системе. Параграф 3.1 содержит описание системы, в рамках которого дана математическая формулировка МДЦ, описана интегрированная математическая модель, используемая в системе для описания проблемы улучшения качества воды в реке, а также охарактеризованы подсистемы компьютерной системы. Также в 3.1 рассмотрен пример использования системы для исследования проблемы улучшения качества воды в реке Ока. В 3.2 описаны результаты исследования свойств метода МСМ при аппроксимации негладких ВКТ, возникающих в проблемах, изучаемых в рамках интегрированной математической модели планирования качества воды в реке Ока. Проведено сравнительное изучение работы метода УО и метода МСМ при разных значениях параметра /3 для типичных задач анализа. Выработаны рекомендации по выбору значения параметра /3 и применению методов УО, СМ и МСМ в системе.

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

Приложения 1-3 содержат графические материалы экспериментального исследования метода МСМ.

По теме диссертации опубликовано пять печатных работ: [4], [27], [48], [64], [66], одна работа опубликована в сети Internet [65], и одна работа принята к публикации [5].

22

Основные результаты диссертации докладывались на 2-й Московской международной конференции по исследованию операций (Россия, Москва, 17-20 ноября 1998 г.), на семинарах Международной летней математической школы (Италия, Перуджиа, 25 июля-31 августа 1999 г.), на заседаниях XXVII школы-семинара "Математическое моделирование в проблемах рационального природопользования" (Россия, Ростов-на-Дону, 13-18 сентября 1999 г.), на XV международной конференции "Принятие решений при многих критериях" (Турция, Анкара, 10-14 июля 2000 г.), на научных семинарах Вычислительного центра РАН и факультета Вычислительной математики и кибернетики МГУ им. М. В. Ломоносова.

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

Заключение

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

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

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

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

4. Разработана и реализована (совместно с А. В. Лотовым, В. А. Бушен-ковым и Р. В. Ефремовым) система поддержки поиска эффективных стратегий улучшения качества воды в бассейнах крупных рек. В систему включена динамическая библиотека, реализующая построение аппроксимации множества достижимых значений критериев и его оболочки Эджворта-Парето по разработанному методу. Система создана в рамках Федеральной целевой программы "Возрождение Волги". Проведен сравнительный анализ использования предложенного метода и метода уточнения оценок в задачах, изучаемых при помощи системы, и выработаны рекомендации по их применению.

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

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

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

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

5. Бурмистрова Л. В. Исследование нового метода аппроксимации выпуклых компактных тел многогранниками // Ж. вычисл. матем. и матем. физ. 2000. Т. 40. N 10. С. 1476-1491.

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

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

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

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

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

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

12. Кейн Э. Экономическая статистика и эконометрия. Вып. 1. М.: Статистика, 1977. 255 с.

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

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

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

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

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

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

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

20. Кириллова Л. С. Общая задача терминального управления в линейных системах // Автоматика и телемехан. 1965. N12. Т. 26. С. 2120-2130.достижимости для нелинейных управляемых систем //Ж. вычисл. ма-тем. и матем. физ. 1990. Т. 30. N 4. С. 483-490.

21. Красовский Н. П., Субботин А. И. Позиционные дифференциальные игры. М.: Наука, 1974.

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

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

24. Лотов А. В. Один подход к перспективному планированию экономики в условиях отсутствия критерия // Тр. конф. "Системный анализ и перспективное планирование". М: ВЦ АН СССР, 1973.

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

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

27. Муртаф Б. Современное линейное программирование. М.: Мир, 1984. 224 с.

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

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

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

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

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

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

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

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

36. Формальский А. М. Построение области управляемости систем с ограниченными ресурсами управления // Автоматика и телемехан. 1968. N 3. С. 21-29.

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

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

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

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

41. Штойер Р. Многокритериальная оптимизация: теория, вычисления, приложения. М.: Радио и связь, 1992.дач математического программирования // Экономика и матем. методы. 1976. Т.12. Вып.1. С. 128-142.

42. 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.

43. Bourmistrova L. V. Algorithm for Approximation of Feasible Sets in Criterion Space in Linear Problems with a Large Number of Decision Variables // Тез. докл. 2-й Московской международной конференции по исследованию операций. М.: ВЦ РАН, 1998. 5 с.

44. Bushenkov V., Kaitala V., Lotov A., Pohjola М. Decision and negotiation support for transboundary air pollution control between Finland, Russia and Estonia // Finnish Economic Papers. V.7, N.l, Spring 1994. P. 69-80.

45. Bushenkov V. A., Ereshko F. I., Lotov A. V., de Mare L. Application of the GRS method to water resources problems in Southwestern Skane, Sweden. WP82-120. International Institute for Applied Systems Analysis. Laxemburg, Austria. 1982.

46. Cohon J.L. Multiobjective programming and planning. N.Y.: Acad. Press, 1978.

47. Dorfman R. Formal models in the design of water resource systems // Water Resources Research, 1965, 1(3).

48. Dudley R. Metric entropy of some classes of sets with differentiable boundaries// J. Approximation Theory. 1974. V. 10. P. 227-236.

49. Gruber P. M., Kendrov P. Approximation of convex bodies by polytopes // Rendiconti Circolo mat. Palermo. Ser. 2. 1982. T. 31. N 2. P. 195-225.

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

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

52. Gruber P. M. Asymptotic estimates for best and stepwise approximation of convex bodies // I, II Forum. Math., 1992.

53. 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. Laxemburg, Austria. 1986.

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

55. Lotov A. V., Chernykh 0. L., Hellman O. Multiple objective analysis of long-term development strategies for a national economy // European Journal of Operational research. 1992. V. 56. N.2.

56. Лотов А. В., Бушенков В. А., Каменев Г. К. Метод достижимых целей. Lewiston etc.: The Edwin Mellen Press, 1999. 400 c.

57. Lotov A., Bushenkov V., Chernov A., Gusev D and Kamenev G. Internet, GIS and Interactive Decision Maps // Journal of Geographical information and decision analysis, 1997, 1(2).

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

59. Minkowski H. Volumen und Oberfläche // Math. Ann. 1903. Bd.57. P. 447495.

60. Pecsvaradi T., Narendra K. S. Reachable sets for linear dynamic systems // Information and Control. 1971. V. 19. N. 4. P. 230-248.

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

62. Schneider R. Zur optimalen Approximation konvexer Hyperflächen durch Polyeder // Math. Ann. 1983. Bd. 256. N 3. P. 289-301.

63. Schneider R. Polyhedral approximation of smooth convex bodies //J. Math. Analys. and Applic. 1987. V. 128. N 2. P. 470-474.

64. Sonnevend G. On optimization of algorithms for function minimization //J. Comput. Math. Math. Physics. 1973. T. 17. C. 591-609.

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

66. Sonnevend G. An optimal sequential algorithm for the uniform approximation of convex functions on 0,1.2 // Applied mathematics and optimization. 1983. V.10. P. 127-142.