Анализ и использование адаптивных методов аппроксимации выпуклых тел многогранниками тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Бурмистрова, Любовь Владимировна

• Бурмистрова, Любовь Владимировна
• кандидат физико-математических наук
• 2000

Оглавление диссертации кандидат физико-математических наук Бурмистрова, Любовь Владимировна

Введение

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

Список литературы диссертационного исследования кандидат физико-математических наук Бурмистрова, Любовь Владимировна, 2000 год

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.