Содержание к диссертации
Введение
Глава 1. Теоретический анализ асимптотической эффективности хаусдорфовых методов полиэдральной аппроксимации 23
1.1. Некоторые понятия теории методов полиэдральной аппроксимации ВКТ многогранниками 23
1.2. Формулировка основных результатов главы 28
1.3. Доказательство основных результатов 31
1.3.1. Метрика второй основной квадратичной формы на поверхности ВКТ 31
1.3.2. Вспомогательные утверждения 35
1.3.3. Доказательство основных теорем 50
1.4. Анализ метода Уточнения Оценок 51
1.5. Достижимость полученных оценок асимптотической эффективности 52
Глава 2. Экспериментальный анализ эффективности методов полиэдральной аппроксимации ВКТ 55
2.1. Некоторые определения и результаты теории двойственности методов полиэдральной аппроксимации 56
2.2. Метод внешней полиэдральной аппроксимации, двойственный к методу УО 59
2.2.1. Схема отсечения, реализуемая методом УО* 59
2.2.2. Реализация метода УО 61
2.2.3. Оценка асимптотической эффективности метода УО* 63
2.3. Методика проведения эксперимента 65
2.3.1. План эксперимента 65
2.3.2. Формирование совокупности эллипсоидов, участвующих в эксперименте 65
2.3.3. Расчет аппроксимирующих последовательностей 66
2.3.4. Расчет выборочной эффективности 66
2.3.5. Методика оценки номера многогранника, с которого можно изучать асимптотические свойства в аппроксимирующей последовательности 67
2.3.6. Методика оценки нижней ассимптотической эффективности 69
2.4. Анализ экспериментальных данных 70
2.4.1. Анализ асимптотической эффективности 70
2.4.2. Дополнительные результаты 71
2.5. Выводы из экспериментального исследования 74
Глава 3. Использование методов аппроксимации в системе поддержки поиска эффективных стратегий улучшения качестваводы 77
3.1. Проблема поддержки поиска эффективных стратегий улучшения качества воды 77
3.1.1. Постановка задачи 77
3.1.2. Математическая модель планирования качества воды 79
3.1.3. Использование Метода Разумных Целей 83
3.2. Метод Экономного Описания Аппроксимации 86
3.2.1. Описание метода 86
3.2.2. Экспериментальное исследование метода 88
3.3. Система поддержки поиска стратегий улучшения качества воды 90
3.3.1. Описание системы 90
3.3.2. Пример использования системы 91
3.3.3. Результаты экспериментального использования метода ЭОАв системе 93
Заключение 94
Приложение 96
Литература 105
- Формулировка основных результатов главы
- Достижимость полученных оценок асимптотической эффективности
- Метод внешней полиэдральной аппроксимации, двойственный к методу УО
- Система поддержки поиска стратегий улучшения качества воды
Введение к работе
Математическое моделирование является общепринятым средством поиска эффективных решений сложных проблем. В процессе поиска эффективных решений все более важную роль играют методы многокритериальной оптимизации, позволяющие учесть противоречивые требования, предъявляемые к рассматриваемым решениям. Одним из таких методов является метод достижимых целей (МДЦ) ([1], [2]), в рамках которого осуществляется аппроксимация и визуализация многомерных множеств достижимых векторных критериев оценки качества решений (так называемых множеств достижимых целей). МДЦ дает возможность визуального изучения взаимозависимостей между недоминируемыми сочетаниями достижимых значений критериев (Паретову границу множества достижимых целей), что способствует поиску разумных компромиссных решений.
Применение МДЦ для поиска Парето-эффективных решений экономических задач началось еще в семидесятых годах ([3], [4]). С середины восьмидесятых годов МДЦ используется для поиска Парето-эффективных стратегий улучшения состояния окружающей среды (см., например, [2], [5] - [8]). Другой важной областью применения МДЦ является изучение возможных вариантов технических систем на предпроектной стадии процесса проектирования [2]. Дальнейшее развитие МДЦ связано с его применением в сети Интернет, где метод может быть использован в системах электронной торговли, выбора экологических решений и т.д.
Для построения множеств достижимых значений критериев в случае выпуклых, в том числе и линейных моделей, в рамках МДЦ используются итеративные методы аппроксимации выпуклых множеств многогранниками, которые строятся с помощью расчета зна-
чений опорной функции аппроксимируемого множества. Данная диссертационная работа посвящена изучению методов полиэдральной аппроксимации выпуклых компактных множеств, в частности методов, основанных на понятии двойственности выпуклых множеств.
Математическая задача многокритериальной оптимизации выглядит следующим образом. Пусть задано линейное пространство решений W и пусть критериальное пространство является ^/-мерным линейным пространством К. . Пусть связь между решениями (стратегиями) и значениями критериев выбора решения устанавливается отображением/: W —> Е . Пусть Xс W- множество возможных (допустимых) решений. Будем считать, что лицо, принимающее решение (ЛПР) заинтересовано в уменьшении значений каждого из d критериев. В этом случае, критериальная точка у' є Ж доминирует
другую критериальную точку у є Rd, если У^у, т.е. у\
/=1, ..., d, и У Фу. Не доминируемая по Парето (в дальнейшем, просто недоминируемая) граница множества Y=f(X), определяемая как множество недоминируемых точек у є Y,b этом случае имеет вид P(Y)={y є Y: (У є У.у <у,У Фу) = 0}.
Множество P(Y) характеризует совокупность компромиссов, разумных с точки зрения рассматриваемых критериев и представляет наибольший интерес для ЛПР, заинтересованных в поиске эффективных решений проблемы. Все методы поддержки принятия решения, основанные на многокритериальной оптимизации, так или иначе решают задачу представления информации о множестве P(Y) и дают возможность отбора наиболее интересных вариантов.
Особенностью МДЦ является предварительное построение аппроксимации множества Y и дальнейшая визуализация множества
P{Y) с использованием двумерных сечений аппроксимации. В том случае, если множество достижимых целей выпуклое, осуществляется его полиэдральная аппроксимация. В смысле вычислительных затрат этап аппроксимации - самый трудоемкий в МДЦ, поэтому он требует использования эффективных методов. В дальнейшем рассматриваются методы аппроксимации множества Y, которое предполагается выпуклым, компактным и телесным.
Построение аппроксимации выпуклых компактных множеств многогранниками является классической проблемой, разработка способов решения которой представляет большой теоретический и практический интерес, поскольку задача аппроксимации выпуклых множеств возникает и во многих других приложениях: при аппроксимации множеств достижимости динамических систем, в математическом программировании, в компьютерной графике и других областях.
Задача аппроксимации выпуклых компактных множеств многогранниками ставится следующим образом: в евклидовом пространстве Ш.а для заданного выпуклого компактного тела (ВКТ) нужно построить последовательность выпуклых телесных многогранников, аппроксимирующих его с любой степенью точности. Среди методов полиэдральной аппроксимации ВКТ имеется большая группа методов, в которых построение аппроксимирующих многогранников основано на построении асимптотически оптимальных покрытий поверхности аппроксимируемого тела (см., например, [9] - [13]). Для d> 2 эти методы являются теоретическими конструкциями, посредством которых можно получить свойства задач полиэдральной аппроксимации ВКТ. На практике используются итеративные методы аппроксимации ([14] - [21]).
Под итеративным методом полиэдральной аппроксимации тела С понимают метод, в котором строятся последовательности телесных многогранников Р , Р ,..., Рп,..., сходящиеся к С, причем на каждой итерации п последующий многогранник Р" строится на основе предыдущего за счет добавления к совокупности его вершин (либо к совокупности его гиперграней) единственной новой вершины (гиперграни).
Итеративные методы различаются способом построения последующего многогранника по предыдущему. В данной работе рассматриваются методы, использующие две схемы построения последующего многогранника по предыдущему: схему восполнения и схему отсечения. В схеме восполнения, предположив построенным вписанный в тело С многогранник Рп, (п+1)-ю итерацию реализуют в виде двух шагов: выбора точки рпедС и построения нового вписанного в С многогранника Р"+] := conv{рпиР}. Конкретные методы, основанные на схеме восполнения, можно характеризовать способами решения двух задач: способом выборарпєдС и способом построения conv{p„uP} в требуемом виде. В схеме отсечения предполагается построенным описанный вокруг тела С многогранник Р". Тогда («+1)-я итерация состоит из двух шагов: выбора направления и„е5г' и построения нового описанного вокруг С многогранника рп+ ._ рпП(и^ q^ ГдЄ Ци„, С) - опорное к С гиперпространство, с нормалью ип. Конкретные методы, основанные на схеме отсечения, можно характеризовать способами решения задач выбора направления и„ и построения PnnL{um С) в требуемом виде.
Эти две схемы могут быть реализованы на основе вычисления опорной функции аппроксимируемого тела С, определяемой как
g(u, С) = шах {<и, х>:хєС}, (1)
где и = 1}. Схема восполнения реализу-
ется следующим образом. Пусть дан многогранник Рп, вписанный в С. Тогда для некоторого направления ип єл ' находится такая граничная точка р„ , что <и„,рп>= g(u„, С). Эта точка используется в качестве вершины нового вписанного в С многогранника conv{pnuP"}. В случае схемы отсечения считается, что задан многогранник Р" , описанный вокруг С. Тогда для некоторого направления ияєл рассчитывается значение опорной функции g(u„, С), вместе с и„ определяющее полупространство L = {у є Rd: <ип,у> < g{un, С)}, которое
затем используется для построения нового описанного вокруг С многогранника Рп глЬ. Отметим, что в МДЦ для расчета значения опорной функции (1) множества f(X) требуется решить задачу оптимизации
max {<и, у>: у=/(х), хеХ}. Наиболее эффективными являются адаптивные методы выбора направлений uneSr~ : направление выбирается на основе информации об аппроксимируемом теле, полученной на предыдущих итерациях. Впервые идеи адаптивной аппроксимации тел были предложены в [14] и [15]. В [14] для аппроксимации части границы двумерного выпуклого тела было предложено уточнение вписанного в тело аппроксимирующего многогранника в направлении нормали того ребра, на котором достигается наибольшее отклонение многогранника от аппроксимируемого тела. В [15] предложено аппроксимировать проекцию выпуклого компактного множества последовательностью многогранников. Синтез этих двух идей осуществлен в методе Уточнения Оценок (У О) [18]. Метод У О, использующий схему восполнения, до недавнего времени являлся единственным
адаптивным методом аппроксимации ВКТ многогранниками, используемым на практике.
Метод УО состоит в следующем. Пусть требуется аппроксимировать тело С. Пусть задана желаемая точность аппроксимации є. На п-й итерации должен быть построен вписанный в тело С многогранник Р" в виде как множества решений системы линейных неравенств, так и списка вершин, для которых указана принадлежность к гиперграням многогранника (так называемое двойное описание). Пусть ЩР") - множество единичных внешних нормалей гиперграней многогранника Рп, которое можно считать заданным системой линейных неравенств, описывающей многогранник Р". Тогда и+1-я итерация метода УО состоит в следующем.
На первом шаге для каждого из неравенств описания многогранника Р" (т.е. направлений из U{P")) рассчитываем опорную функцию тела С на основе решения соответствующей задачи оптимизации (1). Выбираем такое направление ueU(Pn), для которого величина g( и, С) - g{ и, Рп) максимальна. Отметим, что в процессе расчета опорной функции для направлений ueU(Pn) находятся и точки р границы тела С, что <и, р> = g(u, С). Если величина max {g( и, С) -g(u, Рп): ueU(Pn)} меньше желаемой точности аппроксимации є, то процесс завершается. В противном случае, строится выпуклая оболочка многогранника Рп и точки р„, соответствующей направлению ип, на котором достигается max {g( и, С) -g(u, Рп): w=U(Pn)}. Сложная операция построения conv{/?„ и Рп} в виде множества решений системы линейных неравенств осуществляется на основе специально разработанного алгоритма, использующего двойное описание многогранника Р" [22]. Множество conv{p„uP"} используется в качестве новой аппроксимации Рп+] множества С.
Для целей анализа качества аппроксимации множества С последовательностью многогранников {P"}n=o.i.2.... удобно использовать описание метода У О в виде схемы восполнения [19], в которой отсутствуют черты метода, важные для его реализации, но имеющие значение для анализа сходимости.
Шаг 1: а) на основе измерения значений опорной функции находим направление ип є U(Pn) такое, что
щ = argmax {g( u,Q-g( и, Рп): ие ЩР")}. Если \g{un, С) - g(u„, Рп)\ < є, то останавливаем работу метода, иначе переходим к п. б).
б) Берем такую точку р„ границы тела С, что для направления и„, найденного в п. а) шага 1, выполняется <ип,рп> = g(w„, С).
Шаг 2: в качестве очередного многогранника РпЛ' берем conv{/7„uP"}.
Разработка численной схемы метода УО [22], устойчивой к ошибкам округления, позволила реализовать программное обеспечение, выполняющее аппроксимацию ВКТ, заданного алгоритмически своей опорной функцией, в автоматическом режиме без участия пользователя.
Теоретические исследования в области полиэдральной аппроксимации ВКТ привели к понятию многогранников наилучшей аппроксимации (МНА) [23], которые доставляют минимум отклонения от аппроксимируемого множества при заданной сложности многогранника, под которой в данной работе понимается число вершин для МНА внутренней полиэдральной аппроксимации или гиперграней для МНА внешней полиэдральной аппроксимации. В [23] исследованы асимптотические свойства МНА и показано, что для тел с дважды непрерывно дифференцируемой границей и поло-
жительными главными кривизнами (для класса таких тел принято обозначение %' ) выполняется
lim S(C,Pm(C))m2/(d~]) =А(С),
m—»о
где через Рт{С) обозначен МНА тела С сложности т, а через А{С) обозначается аппроксимируемость тела С, которая является теоретической характеристикой возможностей приближения тела многогранниками. Способы построения МНА существуют только для некоторых двумерных тел; в общем случае такие методы не известны. Эффективные методы полиэдральной аппроксимации ВКТ должны приводить к построению многогранников, близких, в каком-то смысле, по своим аппроксимирующим свойствам к МНА. Отметим, что в силу определения МНА, ни одна последовательность вписанных (или описанных) многогранников с последовательно возрастающим числом вершин (гиперграней), не может обеспечить лучшую точность аппроксимации, чем последовательность МНА для данного тела. Как оказалось, существуют итеративные методы ([15], [19], [20], [21]), строящие для тел из св последовательности многогранников {Р"}и=о,і,2,..., Для которых при п —> со имеет место
3(С,Р")~о(\/(т(Р"))2/("-])), (2)
где т(Р п) - сложность описания Р п. Поэтому 2l{d-\) является асимптотически оптимальным порядком сложности для итеративных ме-тодов аппроксимации для тел из % . Итеративный метод называют оптимальным по порядку сложности для тела из V , если он строит аппроксимирующую последовательность, для которой выполняется
(2).
Теоретические исследования адаптивных итеративных методов привели к выделению классов методов аппроксимации, для которых доказана оптимальность по порядку сложности аппроксими-
рующих многогранников для тел из %" ([25]). Это, например, хаус-дорфовы методы, введенные в [25]. В частности доказано ([26]) что метод УО является хаусдорфовым и потому асимптотически опти-мален по порядку числа вершин для тел из %' . В связи с этим представляют интерес оценки констант сходимости хаусдорфовых методов.
В процессе исследования констант сходимости методов, асимптотически оптимальных по порядку сложности, в [24] введено понятие эффективности аппроксимации ВКТ С последовательностью многогранников F. Пусть F={P"}n=o,\x... ~~ сходящаяся к С последовательность вписанных или описанных многогранников. Через rj(P) обозначим отношение расстояния (по Хаусдорфу) от тела С до МНА с той же сложностью, что и многогранник Р, к расстоянию от С до Р:
S(C,Pm(P)(Q)
Г]{Р) = .
S(C,P)
Величину
n(F) = limmfr/(Pn) (3)
называют {нижней асимптотической) эффективностью аппроксимации тела С последовательностью F. Под эффективностью метода полиэдральной аппроксимации тела С понимают эффективность порождаемой им последовательности многогранников. Очевидно, что 0 < 77(F) < 1, причем эффективность аппроксимации тела С последовательностью МНА равна 1. Метод полиэдральной аппроксимации, порождающий для тела С последовательность с нижней асимптотической эффективностью, большей нуля, называют асимптотически эффективным для тела С. Согласно [25], хаусдорфовы методы для тел из класса W являются асимптотически эффективными.
В [24] получена оценка эффективности хаусдорфовых методов, которая, однако, значительно уступает результатам, полученным в экспериментах по аппроксимации эллипсоидов, описанным в [19], [27] - [29], и, в частности, зависит от асферичности аппроксимируемого тела. Представляет практический интерес задача построения более точных оценок эффективности хаусдорфовых методов. Эта задача рассматривается в первой главе диссертации.
Все изложенные выше факты, касающиеся хаусдорфовых методов в равной степени справедливы как для итеративных методов, реализующих схему восполнения, так и для методов, реализующих схему отсечения. Однако на практике распространение получили методы, реализующие схему восполнения, и их свойства хорошо изучены экспериментально ([19], [20], [27] - [30]). В частности, отсутствует информация о практической реализации эффективных хаусдорфовых методов внешней полиэдральной аппроксимации, реализующих схему отсечения, и о работах, посвященных их экспериментальному исследованию. В то же время, такие методы могут быть востребованы на практике, например в случае, когда необходимо получить аппроксимацию выпуклого тела многогранником с возможно меньшим числом гиперграней. Методы, реализующие схему восполнения, не решают указанной задачи. В то же время ха-усдорфовы методы полиэдральной аппроксимации, реализующие схему отсечения, асимптотически оптимальны по порядку числа ги-пергранеи для тел из V . Актуальность задачи построения аппроксимирующих многогранников с малым числом гиперграней объясняется в рамках МДЦ тем, что сложность этапа визуализации множества достижимых целей определяется числом гиперграней в аппроксимирующем многограннике.
Некоторые адаптивные итеративные методы внешней полиэдральной аппроксимации предложены в [16], [19], [20], [21]. В методе из [16] очередное направление и є 5Ґ'] выбирается адаптивно из узлов априорно заданной регулярной сетки на 5ий с учетом теоретической оценки локального отклонения уточняемого многогранника от аппроксимируемого тела. В [16] показано, что для С є %' из Ж* при
d=2, ЗиСє^ из R при d> 3 этот метод обеспечивает сходимость
в метрике Хаусдорфа со скоростью 0(п2 log п), где п - номер итерации метода, отличающийся на постоянную величину от числа гиперграней описанного аппроксимирующего многогранника. Появление множителя log п в оценке скорости сходимости метода из [16] может быть обусловлено априорным выбором сетки направлений на Sf*~x. В [19] было предложено два адаптивных метода, в которых строятся последовательности описанных многогранников. Первый метод (Базовый Метод Отсечения) является чисто теоретической конструкцией, поскольку требует вычисления расстояния по Хаус-дорфу между двумя компактными множествами. Второй метод из [19], известный как метод Сближающихся Многогранников (СМ), а также его модификация, предложенная в [20], являются, по сути, методами внутренней полиэдральной аппроксимации, а последовательности описанных многогранников являются в них вспомогательным построением и строятся для того, чтобы уменьшить число вычислений опорной функции на аппроксимируемом теле. В результате построенные внешние многогранники не обладают удовлетворительными оценками асимптотической эффективности.
Один из способов построения методов внешней полиэдральной аппроксимации дается развитой в [21] теорией двойственности методов внутренней и внешней полиэдральной аппроксимации. Она основывается на понятии множества, сопряженного к выпуклому
множеству ([40]), и на том факте, что если F = {Рп}п=олх- является последовательностью многогранников, вписанных в ВКТ С, то сопряженная последовательность многогранников F* — {(Р")*}я=о,і,2,... является последовательностью описанных вокруг сопряженного тела С*. Если прямой метод строит для тела С последовательность F, то двойственный ему метод строит для тела С* последовательность F*. В [21] показано, что методы двойственные к хаусдорфовым методам внутренней полиэдральной аппроксимации будут также хаусдорфо-выми, и, значит, оптимальными по порядку числа гиперграней для тел из %' . Это позволяет строить двойственные методы с априорно известными свойствами сходимости. Поэтому такая методика заслуживает тщательного исследования.
В то же время, теоретические оценки эффективности двойственных методов, полученные в [21], существенно зависят от асферичности аппроксимируемых тел. В связи с этим возникает важный для практики вопрос о том, является ли свойство зависимости оценок двойственных методов от асферичности следствием методики, использованной для их получения, или имеет место в действительности. Ответить на этот вопрос может экспериментальное исследование, направленное на изучение асимптотических свойств двойственных методов. Экспериментальные исследования асимптотических свойств адаптивных методов проводились в [19], [20], [27] -[30]. В качестве объектов эксперимента в этих работах брались многомерные эллипсоиды. Использование эллипсоидов в этих экспериментах основано на том, что для любого эллипсоида Е размерности не больше четырех может быть вычислена его аппроксимируемость А(Е) ([19]). Во второй главе диссертационной работы описаны результаты проведения экспериментов по аппроксимации многомерных эллипсоидов с использованием метода, двойственного
методу УО. Эти эксперименты показали практическую применимость такого метода.
В третьей главе описывается использование методов полиэдральной аппроксимации в проблемах улучшения качества воды. Задача улучшения качества воды состоит в выработке рекомендаций по размещению оборудования, предназначенного для очистки стоков промышленности и жилищно-коммунального хозяйства, и по выбору технологии очистки. Для поддержки выбора эффективных стратегий улучшения качества воды в Вычислительном центре РАН была разработана методика целостного рассмотрения водохозяйственных проблем [7], заключающаяся в использовании интегрированных моделей для описания проблем и применении МДЦ для поддержки их исследования. С середины восьмидесятых годов МДЦ успешно используется для поиска эффективных стратегий улучшения качества воды в бассейнах крупных рек ([2], [6] - [8]). На базе МДЦ создаются системы поддержки поиска эффективных стратегий улучшения качества воды, предназначенные для установки в бассейновых управлениях.
В зависимости от масштаба решаемой проблемы, такие системы адаптируются для бассейна крупной реки в целом или для любого его участка. При этом используется разная детализация в математической модели изучаемой проблемы. Для анализа бассейна в целом используется линейная модель очистки стоков, в рамках которой предприятия группируются в отрасли по принципу схожести состава загрязнения, и к стоку от каждой из отраслей может быть применено несколько технологий в разных пропорциях ([2]). В локальной проблеме задача улучшения качества воды сводится к проблеме с большим конечным числом вариантов решения. При этом метод МДЦ модифицируется в Метод Разумных Целей (МРЦ)
([38]), в котором осуществляется аппроксимация выпуклой оболочки критериальных векторов, соответствующих вариантам решения.
Число возможных вариантов стратегий очистки в задаче улучшения качества воды может оказаться очень большим - порядка нескольких миллионов. При аппроксимации выпуклой оболочки такого большого числа точек методами, реализующими схему восполнения, может быть построен аппроксимирующий многогранник с очень большим числом гиперграней. Надо отметить, что от числа гиперграней аппроксимирующего многогранника зависит скорость визуализации его сечений. Технология Диалоговых Карт Решений (ДКР) с помощью интерактивной анимации цветных карт решений (наборов сечений, в которых от сечения к сечению меняется только один некоординатный критерий) позволяет изобразить Паретову границу для нескольких (до семи) критериев в наглядной форме. Такая наглядность, однако, может быть достигнута только в случае быстрой и стабильной работы программного обеспечения ДКР. Поскольку системы поддержки поиска эффективных стратегий улучшения качества воды планируется устанавливать в бассейновых управлениях, т.е. в учреждениях с, возможно, слабой компьютерной базой, то для надежной работы программного обеспечения МДЦ необходимо разрабатывать методы полиэдральной аппроксимации ВКТ, строящие аппроксимирующие многогранники с небольшим числом гиперграней. Таким образом, возникает задача практического использования эффективных адаптивных методов полиэдральной аппроксимации с малым числом гиперграней, которая решается в главе 3.
Итак, диссертационная работа направлена на дальнейшее развитие методов полиэдральной аппроксимации ВКТ, их исследование и применение к решению практических задач. Цели диссертационной работы
Построение априорных оценок нижней асимптотической эффективности аппроксимации многомерных тел хаусдорфовыми методами внутренней и внешней полиэдральной аппроксимации.
Уточнение теоретических оценок асимптотической эффективности метода внешней полиэдральной аппроксимации, двойственного к методу УО, на основе данных его экспериментального исследования.
Использование методов аппроксимации ВКТ в системе поддержки принятия решений об улучшении качества воды в сегментах бассейнов крупных рек и исследование с ее помощью конкретной природоохранной задачи.
В первой главе проведено исследование нижней асимптотической эффективности хаусдорфовых методов аппроксимации в классе тел СЄ . В разделе 1.1 изложены основные понятия и результаты теории методов аппроксимации выпуклых компактных тел многогранниками, использующиеся в дальнейшем. В разделах 1.2 и 1.3 получены априорные оценки нижней асимптотической эффективности аппроксимации многомерных тел из ft2 последовательностями многогранников, которые строятся хаусдорфовыми методами как внутренней так и внешней полиэдральной аппроксимации. Полученные оценки оказались не зависящими от аппроксимируемого тела. В качестве примера, иллюстрирующего полученные результаты, эти оценки применены к методу УО. В разделе 1.4 показано, что для многомерных тел из %' метод УО позволяет строить вписанные многогранники, асимптотически отличающиеся по точности от много-
гранников наилучшей аппроксимации не более чем в четыре раза. Непосредственные вычисления, проведенные в разделе 1.5 для метода УО при аппроксимации круга, показывают, что полученные оценки достижимы.
Во второй главе диссертационной работы проведено экспериментальное исследование метода внешней аппроксимации УО*, двойственного к методу УО. В разделе 2.1 даны необходимые для дальнейшего изложения сведения из теории двойственности методов полиэдральной аппроксимации ВКТ. В разделе 2.2 на основе использования теории двойственности получено описание метода УО* и теоретически показана его оптимальность по порядку числа гиперграней. В разделе 2.3 описана методика проведения эксперимента, направленного на оценку асимптотической эффективности метода УО*. В разделе 2.4 проведен анализ экспериментальных данных. Анализ показал, что асимптотическая эффективность метода УО* зависит от асферичности аппроксимируемого тела. В то же время показано, что теоретические оценки оказались очень грубыми. В ходе экспериментального исследования метода УО* разработана методика, направленная на выявление асимптотического поведения аппроксимирующих последовательностей. Результаты эксперимента обсуждены в разделе 2.5, где даны рекомендации по поводу применения метода на практике.
В главе 3 методы полиэдральной аппроксимации ВКТ применяются в системе поддержки поиска стратегий улучшения качества воды в бассейне реки. Раздел 3.1. содержит постановку и методику решения задачи. В разделе 3.1.1. описана интегрированная математическая модель целостного рассмотрения проблемы; модель используется для расчета конечной совокупности возможных стратегий улучшения качества воды. В разделе 3.1.2 дана математическая
формулировка Метода Разумных Целей (МРЦ), который позволяет осуществлять отбор природоохранных стратегий с использованием графического представления информации о множестве Парето.
В разделе 3.2. разрабатывается метод Экономного Описания Аппроксимации (ЭОА), предназначенный для аппроксимации многомерной выпуклой оболочки большого числа точек многогранником с небольшим числом гиперграней. Такая задача возникает в связи с тем, что в задачах улучшения качества воды число возможных природоохранных мероприятий может быть очень велико - до нескольких миллионов, а программное обеспечение предназначено для использования в организациях со слабой компьютерной базой.
Метод ЭОА основан на идеях теории двойственности методов полиэдральной аппроксимации. В разделе 3.2.1. дается описание метода. В разделе 3.2.2 свойства метода исследуются экспериментально на основе аппроксимации выпуклых оболочек специально сгенерированных совокупностей точек. В качестве таких точек взяты множества вершин т.н. циклических многогранников ([39]).
Формулировка основных результатов главы
Доказательство теоремы изложено в разделе 1.3.3. В доказательстве будут использованы результаты работ [11, 13], в которых предложен подход к выяснению асимптотического поведения отклонения в метрике Хаусдорфа последовательности МНА от аппроксимируемого гладкого тела, основанный на введении на поверхности аппроксимируемого тела метрики второй основной квадратичной формы. Оказывается, что в асимптотике вершины МНА расположены на поверхности аппроксимируемого тела "достаточно равномерно" ([13]). С другой стороны, можно показать (лемма 7), что вершины многогранников в Н\ -последовательности в асимптотике обладают аналогичным свойством. Сравнение двух "хорошо распределенных" последовательностей точек, основанное на лемме 2, и дает требуемое доказательство. Непосредственно из теоремы 1, свойства (6) и определения (3) вытекает асимптотическая оценка на скорость сходимости Н\-последовательностей восполнения многогранников. Следствие 1. Пусть выполнены условия теоремы 1. Тогда для любого в О существует N, такое что для любого n N выполняется Теперь обратимся к методам более широкого класса И. Теорема 2. (Р.В. Ефремов, Г.К. Каменев) Пусть Сес(? и F = {Рп} „=о,1,... есть Н(у, ( -последовательность восполнения. Тогда Доказательство теоремы приведено в разделе 1.3.3. При у=\ утверждения теоремы 1 и теоремы 2 совпадают. Однако поведение этих зависимостей при у, близком к 1, резко отличается. В
Приложении на рис. 1. представлены графики функций от / в правых частях оценок нижней асимптотической эффективности (13) и (14). Непосредственно из теоремы 2, свойства (6) и определения (3) вытекает асиптотическая оценка на скорость сходимости //-последовательностей многогранников. Следствие 2. Пусть выполнены условия теоремы 2. Тогда для любого є 0 существует N, такое что для любого n N выполняется Идея доказательства близка к доказательству теоремы 2. Отличие состоит в том, что вместо изучения асимптотики расположения вершин внутреннего МНА на поверхности аппроксимируемого тела изучаются точки касания гиперграней внешнего МНА с аппроксимируемым телом, которые оказываются расположенными на его поверхности "достаточно равномерно" в смысле метрики второй основной квадратичной формы поверхности аппроксимируемого тела. Непосредственно из теоремы 3, свойства (6) и определения (3) вытекает асимптотическая оценка скорости сходимости //-последовательностей многогранников. Следствие 3. Пусть выполнены условия теоремы 3. Тогда для любого е
О существует N, такое что для любого п N выполняется Из свойства (10) вытекает Замечание 1. Как уже говорилось при обсуждении равенства (6), в следствиях 1 - 3 вместо т\Рп) (rrr(P")) можно подставить номер итерации п. Сформулируем теперь некоторые понятия и результаты из [11, 13, 51], необходимые для доказательства теорем. Определим, согласно [13], класс ВКТ, с границей, являющейся римановым многообразием. Определение 3. Топологическое пространство М называют d-мерным (Римановым) многообразием класса С с метрикой класса С0, если выполнены следующие свойства: a) для любого реМ существует пара U, h {карта), где U - окрестность/? и h - гомеоморфизм (/на открытый шар в Rd; b) пусть р, q є М, и U, h и V, к - соответствующие карты, такие, что UnV 0 и отображение к-ИЛ: h(UnV) -» k(UnV) есть диффеомор-физм класса С ; c) пусть реМ, и U, h - соответствующая карта. Тогда для любой u&h{U) определена положительно определенная квадратичная форма где функции (метрические коэффициенты) gy{-) на h(U) удовлетворяют условиям gij = gjiW принадлежат классу С0. Пусть М - (і-мерное (Риманово) многообразие класса С" с метрикой класса С. Кривую вМ называют принадлежащей классу С\ если существует параметризация этой кривой х: [а, Щ — М, такая что для любой карты U, h и любого интервала \а, b]cz\a, /?] с х([а, b])c:U функция и = fax: [a, b] — h(U) принадлежит классу С1. Если KCLU, ТО длину К определяют как иначе К разбивают на подходящие кривые и их длины складывают. Для JC, у є М через ju(x, у) обозначим точную нижнюю грань длин кривых класса С из М, соединяющих хну. Так определяется (геодезическая) метрика jU на М. Обозначим через // (А, В) := inf {ju(x, у): х є А, у є В] расстояние между множествами А и В в метрике p.. Утверждение 1. [13, стр. 287] Пусть Я \. Пусть Jcz М, и его замыкание cl (J) компактно. Тогда существуют точкиру, / = /,..., т и соответствующие им карты Ui, hi, окрестности 7/ точек р/ и числа Si О, такие что Пусть Сеъ. Определим структуру многообразия класса С с метрикой класса С0 на дС (по [11]). Пусть редС. Через пс(р) обозначим единичную нормаль к дС в точке р, направленную внутрь С. В 1(-пс(р), С) выберем декартову прямоугольную систему координат.
Вместе с пс(р) она образует декартову прямоугольную систему координат всего 1R . Через h обозначим ортогональную проекцию на 1(-Пс(р), С) точек из IR . Пусть U - окрестность р на дС, такая что h есть гомеоморфизм U на h(U), причем h(U) есть открытый евклидов шар размерности d-1. Так введенные U и h удовлетворяют определению карты точкир&дС (пункт а) определения 3). Если теперь любой точке рєдС сопоставить карту U, h, то можно показать (см. [11], доказательство Леммы 1), что так введенная структура на дС удовлетворяет пункту Ь) определения 3. Определим теперь метрику на дС. Предварительно сделаем одно замечание, касающееся метрических коэффициентов g,y(-) в определении 3. Как видно, метрика ju(x, у) определяется выбором этих коэффициентов. Если в качестве них взять коэффициенты первой основной квадратичной формы поверхности дС, то /л(х, у) будет измерять кратчайший путь на поверхности между точками х и у. Если взять коэффициенты второй основной квадратичной формы (ВОКФ), то f/(x, у)12 измеряет (приближенно) Евклидово расстояние между х и 1{пс{у), С) (также как между у и 1{пс{х), С)); последнее утверждение получает свое математическое выражение в лемме 1. В дальнейшем под //(, ) будем понимать метрику, определенную коэффициентами ВОКФ поверхности дС. Пусть функция//: h{U) -» IR, такая , что любая точка xeU представляется в виде (и, J[u)), где и - h{x). В силу дважды непре-рывной дифференцируемости дС, f -функция из класса С . Тогда коэффициенты ВОКФ выразятся через/,/, , 1 i,j, к d- 1 - первые и вторые частные производные/ следующим образом
Достижимость полученных оценок асимптотической эффективности
Покажем, что существуют хаусдорфовы последовательности многогранников, для которых оценки, полученные в теоремах 1, 2 и 3, выполняются точно.
В [24, стр. 800] приведен пример /7(1, В2) последовательности восполнения F, где В - круг единичного радиуса, и показано, что 77(F) = Л, т.е. оценка (14) достижима. Поскольку 7/(1, ( -последовательность является также Н\{\,С)-последовательностью для любого С є % ([41]), оценка (13) также достижима.
Теперь построим пример, в котором достигается оценка (15). Рассмотрим следующий метод аппроксимации круга В2 описанными многоугольниками. Пусть Ръ - равносторонний треугольник, опи-санный вокруг В . Пусть построен многоугольник Рп. Найдем среди всех точек пересечения окружности д(В ) и отрезков, соединяющих начало координат с вершинами Р", точку рп, наиболее удаленную от соответствующей вершины qn и в качестве нового многоугольника Pn+l возьмем пересечение многоугольника Р" с полуплоскостью, граница которой является касательной к В2 в рп, причем qn не лежит в указанной полуплоскости. Тогда последовательность F = {Р"}п=зл.... является H(1,F)-последовательностью отсечения и (15) даст 77(F) Л. С другой стороны, по аналогии с [24], докажем, что 77(F) - Ул.
Действительно, в последовательности F при п = Ъ-2к, =0,1,..., будут возникать правильные многоугольники, которые являются МНА для В . С другой стороны многоугольник с номером т? = 3-2+1-1 доставляет такую же точность аппроксимации, что и многоугольник с номером п - Ъ-2к, т.е. Преобразуем выражение под знаком предела (61) с учетом того, что Р3 2 ,к = 0,1,..., является МНА для В2:
Задача построения аппроксимирующих многогранников заданной точности с малым числом гиперграней является актуальной в рамках МДЦ, поскольку от числа гиперграней в аппроксимирующем многограннике зависит сложность этапа визуализации множества достижимых целей. Эта задача может быть решена методами полиэдральной аппроксимации, реализующими схему отсечения.
Один подход к построению методов, реализующих схему отсечения, дает развитая в [21] теория двойственности методов внутренней и внешней полиэдральной аппроксимации. В [21] показано, что методы, двойственные к хаусдорфовым методам внутренней полиэдральной аппроксимации, будут также хаусдорфовыми. Это позволяет строить двойственные методы с априорно известными свойствами сходимости. Поэтому такая методика заслуживает тщательного исследования.
В то же время, теоретические оценки эффективности двойственных методов, полученные в [21], существенно зависят от асферичности аппроксимируемых тел. В связи с этим возникает важный для практики вопрос о том, является ли свойство зависимости оценок двойственных методов от асферичности следствием методики, использованной для их получения, или имеет место в действительности. Ответить на этот вопрос может экспериментальное исследование, направленное на изучение асимптотических свойств двойственных методов.
В этой главе проводится экспериментальное изучение метода УО , двойственного к методу У О. Основной целью экспериментального изучения является оценка нижней асимптотической эффективности метода УО . В параграфе 2.1 вводятся некоторые понятия теории двойственности методов полиэдральной аппроксимации ВКТ, в параграфе 2.2 строится и исследуется метод УО . В параграфах 2.3-2.5 описывается методика проведения эксперимента и его результаты.
Теория двойственности схем полиэдральной аппроксимации была развита в [21] на базе теории двойственности выпуклых множеств. Изложим некоторые понятия и утверждения теорий двойственности выпуклых множеств и схем полиэдральной аппроксимации, которые понадобятся нам в дальнейшем.
Для тела Се% определим полярное множество {поляру) С относительно {0} - начала координат в R , как множество {xeRd: х, у \,уеС]. Пусть R0d := КА{0}, % = {Са% \ {0} є int С} - класс ВКТ, содержащих внутри себя начало координат, :/b = %r\:f. Пусть С є %, тогда С е%, С = С ([40], теорема 6.4). Пусть у є М(/ и 1у\= {хєЖ1 . х, у =1}. Под полярой тг(у) для точки (относительно сферы х, х =1) будем понимать гиперплоскость 1У, а через п(1у)={у} обозначим полюс (относительно сферы х, х =1) для гиперплоскости 1у. Пусть С є % тогда для и&5?Л, редС и ир =р/\\р\\ справедливы равенства ([40, 6]):
Метод внешней полиэдральной аппроксимации, двойственный к методу УО
Задачей описываемого эксперимента являлась оценка асимптотической эффективности метода УО . Эксперимент состоял из следующих этапов: 1) выбор совокупности аппроксимируемых множеств; 2) расчет аппроксимирующих последовательностей; 3) расчет выборочной (экспериментальной) эффективности; 4) оценка минимального числа гиперграней, обеспечивающих проявление асимптотических свойств; 5) оценка асимптотической эффективности метода УО . Рассмотрим методику проведения этих этапов. В качестве аппроксимируемых тел были взяты совокупности трех- и четырехмерных эллипсоидов, поскольку для любого эллипсоида Е, размерности не больше четырех, может быть вычислена его аппроксимируемость А(Е) ([19]). Зададимся некоторым натуральным числом N(d) - числом эллипсоидов размерности d в выборке. Разобьем полуинтервал (О, A(Bd)], где A(Bd) - аппроксимируемость d- мерного шара, на N(d) полуинтервалов одинаковой длины. Совокупность эллипсоидов одной размерности сформирована так, чтобы в каждом из полуинтервалов лежал единственный эллипсоид, и чтобы эллипсоиды были изопериметрическими - поверхностный объем каждого совпадал с о(В ). Другими словами, совокупность эллипсоидов изопериметри-ческая и равномерно распределена на полуинтервале изменения аппроксимируемости. В эксперименте участвовали две совокупности эллипсоидов {Edi}i=\t..., N(d) размерностей d= 3, 4; при этом ЛчЗ) = 200, N(4) = 99. Технику расчета аппроксимируемости для эллипсоидов можно найти в [19], [27] - [30]; в данной работе использовались те же совокупности эллипсоидов, что и при проведении экспериментов, описанных в [30]; там же содержится подробная методология построения нужных совокупностей и расчета А{Е)
Согласно численной схеме метода УО , изложенной в разделе методом УО был проведен расчет последовательностей многогранников {Рп}, п - щ(сГ), ..., П], где «о(3) = 6, щ{4) = 8, п\ 1024, а п - число вершин аппроксимирующего многогранника, для сопряженных эллипсоидов, полученных следующим образом. Пусть эллипсоид Е задан своими полуосями Яь..., Xd. Тогда полуоси сопряженного эллипсоида Е имеют вид 1/Аь..., \/Ad, а его опорная функция запишется в виде [40, стр.124]: Как видно, опорная функция Е может быть рассчитана, если известны полуоси исходного эллипсоида Е. Целью этого этапа является получение последовательностей эффективности очередного приближения (выборочной эффективности): где Qn := (Р") , п = no(d), ..., п\, а расчет Р" изложен в разделе 2.3.3. Ясно, что d(ff, Е) Ф О для любого п = щ{сГ), ..., щ. Заметим, что f(Q")- т\Рп).
Согласно численной схеме метода УО , изложенной в разделе 2.2.2, величины д(Е, Qn), п = n0(d), ..., щ, для каждого эллипсоида Е из рассматриваемой совокупности могут быть получены как вычисления S(E, (У) нужно знать Е и многогранник Р" в виде множества решений системы линейных неравенств. Для вычисления р(Е, q) по данным Е и Р", где q - внешняя для Е точка, использовался численный метод модифицированных функций Лагранжа ([43], стр. 248 - 253), в котором для промежуточной оптимизации применялся метод Ньютона с регулировкой шага ([43], стр. 64 - 66). В результате этих расчетов оказываются получены последовательности для всех рассматриваемых эллипсоидов.
Система поддержки поиска стратегий улучшения качества воды
Система была реализована для решения конкретной задачи поиска предпочтительных стратегий улучшения качества воды в районе города Коломна. В этой системе, кроме визуализации паре-товой границы, осуществлялась визуализация состояния рек до и после осуществления мероприятий на основе использования простейшей географической информационной системы (ГИС), специально запрограммированной для данного случая. Система поддержки поиска стратегий состоит из следующих подсистем: 1) подсистемы подготовки таблицы, содержащей атрибуты стратегий, 2) подсистемы визуализации текущего состояния качества воды с помощью ГИС, 3) подсистемы аппроксимации ВОЭП, 4) подсистемы визуализации паретовой границы и выбора разумной цели, 5) подсистемы расчета набора стратегий, близких к выбранной цели, 6) подсистемы визуализации полученных стратегий с помощью ГИС.
Для того, чтобы изучить влияние мероприятий в районе г. Коломны, загрязнение, поступающее из Верхней Оки и р. Москва выше г. Коломны, считалось заданным и не превышающим нормы. Были получены данные о выбросах по восьми предприятиям города Коломны. При этом полагалось, что остальные предприятия выбросов загрязнения не осуществляют.
Данные были разработаны специалистами Института водных проблем РАН и АО Союзводпроект.
Диссертантом в рамках работы над СППР, помимо реализации метода ЭОА, была создана подсистема подготовки исходных данных, в которой осуществляется интеграция исходных файлов о водном балансе реки и ее притоков, о выбросах загрязняющих веществ в разрезе створов, о распаде и переносе загрязнителей между точками выброса, о возможных технологиях очистки стоков, и т.д. В результате создается таблица, строки которой соответствуют стратегиям, а столбцы - атрибутам стратегий, часть из которых может быть выбрана в качестве критериев отбора стратегий. Для этого используется генератор, структура которого соответствует математической модели.
Было рассмотрено четыре критерия: стоимость проекта (cost), измеряемая в миллионах рублей, а также максимальные по району концентрации соединений азота (pi) и фосфора (р2), а также биологическая потребность в кислороде, БПК (рЗ), измеряемые в ПДК. Для каждого из предприятий считался возможным выбор одного из пяти вариантов технологических решений по очистке выбросов, так что всего было рассмотрено 390 625 возможных вариантов проекта очистки выбросов. Последствия всех этих вариантов были оценены на основе использования матрицы влияния. Эта информация была представлена в таблице.
Для строк полученной таблицы была аппроксимирована ВОЭП. Черно-белая копия одной из карт решений, построенной с помощью ВОЭП, приведена на рис. 18. На этом рисунке изображены БПК (по вертикальной оси) и общая стоимость проекта (по горизонтальной оси) для нескольких концентраций соединений азота (pi), заданных цветом на дисплее и оттенками серого на рисунке. Концентрации соединений азота изменяются от 1.05 до 1.25 ПДК с шагом 0.05 ПДК. Из рисунка видно, что БПК изменяется от максимальной концентрации в 1.17 ПДК, которой соответствует нулевая стоимость проекта, до минимально возможной в 1.00 ПДК, для достижения которой необходимо вложение 4.86 млн. рублей. В то же время, из рис. 18 видно, что использование всего лишь 0.35 миллионов рублей приводит к существенному уменьшению концентрации БПК: концентрация падает с 1.17 до 1.01 ПДК. При этом для стоимости проекта, превышающей 0.4 млн., паретова граница практически горизонтальна, то есть такие вложения мало эффективны. Отметим, что подобный эффект наблюдается при любых концентрациях соединений азота (pi). Этот пример показывает, как опасно ориентироваться на оптимальные значения без многокритериального анализа замещений.
Концентрация соединений фосфора (р2) задана на полосе прокрутки в нижней части рис. 18. Анализ карты решений при изменении значений р2 показал, что концентрация соединений фосфора не влияет на карту решений.
На рис. 19 приведена увеличенная часть карты решений с рис. 18, для которой стоимость проекта не превышает одного миллиона рублей. Сечения по-прежнему соответствуют различным концентрациям соединений азота (pi), меняющимся от 1.05 до 1.30 ПДК с шагом 0.05, а концентрация фосфора (р2) установлена равной 1.01
ПДК. Как видно из рис. 19, только 260 тысяч рублей (вместо 4.87 миллиона!) необходимы для снижения концентрации БПК и фосфора до 1.01 ПДК, а также концентрации соединений азота до 1Л ПДК. Точка, соответствующая таким значениям критериев, отмечена на рис. 19 крестом.
Выбрав в качестве цели точку, отмеченную крестом, пользователь получит несколько вариантов стратегии выполнения очистных мероприятий, реализация которых приведет к результатам, близким к указанной точке. Эти варианты стратегии приведены на рис. 20. В верхней строке указана разумная цель, выбранная пользователем (goal point). В левом столбце - код проекта (alternative), остальные столбцы содержат информацию о критериальных величинах: стоимости проекта (cost) и концентрациях соединений азота (pi), фосфора (р2) и БПК (рЗ). Как видно, полученные варианты проекта мало отличаются от выбранной цели. Таким образом, рассмотренный пример показывает, что с помощью визуализации ВОЭП можно получить информацию о большой совокупности возможных проектов в наглядной форме и выявить наиболее предпочтительные из них.
На рис. 21 представлена зависимость числа гиперграней аппроксимирующих многогранников от точности расчета ВОЭП множества достижимых целей задачи, исследованной в предыдущем пункте. С помощью метода УО построено многогранное множество Р] с т(Р\) =107 за число итераций п = 36. Методом ЭОА построено многогранное множество Р2 с rrf(P2) — 46 за число итераций п = 139.
Похожие диссертации на Анализ методов полиэдральной аппроксимации выпуклых тел и их применение в задачах многокритериальной оптимизации
