ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2008, том 48, < 6, с. 990-998
УДК 519.658
МОДИФИЦИРОВАННЫЙ МЕТОД УТОЧНЕНИЯ ОЦЕНОК ДЛЯ ПОЛИЭДРАЛЬНОЙ АППРОКСИМАЦИИ ВЫПУКЛЫХ
МНОГОГРАННИКОВ1)
© 2008 г. А. В. Лотов*, А. И. Поспелов**
(*119333 Москва, ул. Вавилова, 40, ВЦ РАН; **109004 Москва, ул. Большая Коммунистическая, 25, ИСП РАН) e-mail: lotov08@ccas.ru; ap@ispras.ru Поступила в редакцию 12.10.2007 г.
Предлагается и экспериментально исследуется модифицированный метод уточнения оценок, предназначенный для итеративной аппроксимации выпуклых многомерных многогранников с большим числом вершин. Аппроксимация осуществляется последовательностью выпуклых многогранников с постепенно увеличивающимся относительно малым числом вершин. Приводятся результаты экспериментального сравнения модифицированного метода уточнения оценок с исходным методом уточнения оценок, предназначенным для полиэдральной аппроксимации многомерных выпуклых компактных тел общего типа. Библ. 14. Фиг. 5.
Ключевые слова: полиэдральная аппроксимация выпуклых тел, выпуклые многогранники, итеративные методы, скорость сходимости.
ВВЕДЕНИЕ
Предлагается и изучается метод аппроксимации выпуклых многомерных многогранников, заданных явно или неявно и имеющих большое число вершин, многогранниками с малым числом вершин. Эта задача возникает во многих приложениях, в частности при упрощенном описании выпуклых многомерных многогранников (см. [1]), в некоторых методах многокритериальной оптимизации и т.д. В качестве примера такого метода многокритериальной оптимизации можно назвать метод достижимых целей, который в линейном случае основан на аппроксимации многогранного множества достижимых критериальных векторов (см. [2], [3]).
Задача полиэдральной аппроксимации выпуклых многомерных многогранников является частным случаем общей задачи полиэдральной аппроксимации многомерных выпуклых компактных тел в евклидовом пространстве, решение которой требует разработки методов, позволяющих строить выпуклый многогранник, аппроксимирующий заданное выпуклое компактное тело с заданной степенью точности (в некоторой метрике, скажем, в метрике Хаусдорфа). Методами полиэдральной аппроксимации выпуклых компактных тел, наиболее пригодными для практического использования, являются итеративные методы, в которых на каждой итерации последующий многогранник строится на основе предыдущего. До недавнего времени единственным широко используемым на практике итеративным методом аппроксимации выпуклых компактных многомерных тел был метод уточнения оценок (УО), описанный, например, в [2], [3]. Метод УО предназначен для аппроксимации выпуклых компактных тел, заданных своей опорной функцией, быть может, алгоритмически. В методе УО на каждой итерации осуществляется расчет опорной функции аппроксимируемого тела для конечного набора направлений, причем выбор этих направлений осуществляется адаптивным образом. Поскольку опорная функция обычно задана алгоритмически, в виде максимума линейной целевой функции на аппроксимируемом множестве, метод УО предполагает решение значительного числа задач оптимизации на каждой итерации. В частности, как показывает опыт, для пространства размерности порядка пяти на каждой итерации может потребоваться решение до нескольких сотен таких задач. Если решение такой задачи оптимизации требует существенных вычислительных затрат, то для постро-
1) Работа выполнена при финансовой поддержке гранта Президента РФ по государственной поддержке ведущих научных школ (проект < НШ-2982.2008.1), РФФИ (код проекта 07-01-00472), программы фундаментальных исследований РАН < 14 "Фундаментальные проблемы информатики и информационные технологии" (проект 2.31) и программы фундаментальных исследований ОМН РАН № 3.
ения достаточно точной аппроксимации выпуклого тела может потребоваться значительное время.
Такое свойство метода УО может затруднить его применение в многокритериальных системах поддержки принятия решений в тех случаях, когда пользователи этих систем хотели бы вести исследование в эволюционном режиме, т.е. модифицировать задачу многокритериальной оптимизации в ходе ее изучения и многократно аппроксимировать различные множества достижимых критериальных векторов, не отрываясь от компьютера (см. [4]). Таким образом, для того чтобы реализовать эволюционный режим исследования на основе метода достижимых целей, требуется обеспечить достаточно быструю аппроксимацию множества достижимых критериальных векторов. К сожалению, для широкого класса адаптивных методов (см. [5]), для которых доказана асимптотическая оптимальность по порядку числа вершин и скорости сходимости, оптимальность по порядку числа вычислений опорной функции в общем случае, скорее всего, не имеет места. Даже для метода УО, принадлежащего этому классу, первые оценки числа вычислений опорной функции получены лишь недавно (см. [6]); при этом асимптотическая оптимальность по порядку числа вычислений опорной функции доказана только для гладких тел.
Было предложено несколько подходов, направленных на снижение трудоемкости методов полиэдральной аппроксимации выпуклых компактных тел. Один из них заключается в предварительном расчете опорной функции для некоторого вспомогательного внешнего многогранника. Реализациями этой идеи являются метод сближающихся многогранников (см. [7]) и его модификация (см. [8]), для которой имеет место асимптотическая оптимальность по порядку числа вычислений опорной функции для выпуклых тел, в том числе с негладкой границей. В то же время эти методы имеют определенные недостатки, которые приводят к отсутствию существенных преимуществ перед методом УО в скорости счета; к тому же эти методы уступают методу УО в надежности программного обеспечения, которая в случае УО обеспечивается в последние 25 лет его интенсивным использованием в прикладных задачах многокритериальной оптимизации (см. [2], [3]). Для преодоления недостатков имеющихся методов были предложены также так называемые самодвойственные методы полиэдральной аппроксимации выпуклых тел (см. [9]), которые являются асимптотически оптимальными по всем упомянутым характеристикам (включая порядок числа вычислений опорной функции), но пока не применяются из-за отсутствия надежной вычислительной реализации. В связи с этим метод УО остается основным средством аппроксимации многомерных выпуклых множеств.
Второй подход к снижению трудоемкости методов полиэдральной аппроксимации основан на совершенствовании метода УО. При этом можно по-прежнему использовать программное обеспечение метода УО, несколько модифицировав его. Вычислительные затраты могут быть уменьшены, в частности, за счет снижения трудоемкости решения совокупности задач расчета опорной функции для определенного класса аппроксимируемых тел. В данной статье предлагается использовать именно такой подход. Описывается и экспериментально исследуется модификация метода УО, позволяющая уменьшить трудоемкость метода для практически важного случая, когда аппроксимируемое тело - многогранник с большим числом вершин. При этом изучается трудоемкость метода на относительно малом числе итераций, которые следует выполнить для построения аппроксимирующего многогранника с относительно малым числом вершин (порядка нескольких сотен).
В разд. 1 дается описание предлагаемой модификации метода УО, а в разд. 2 и 3 приводятся результаты экспериментального сравнения модифицированного метода с исходным методом УО.
Начнем изложение с описания математической формулировки задачи аппроксимации, для решения которой может использоваться модифицированный метод УО. Во-первых, это задача построения многогранника с малым числом вершин, аппроксимирующего множество решений системы неравенств
где у - вектор евклидова пространства Ял, Н, Н - заданные матрица и столбец, причем предполагается, что множество решений (1) является компактным. Во-вторых, это задача аппроксимации множества достижимых критериальных векторов в критериальном евклидовом пространстве Ял, задаваемого как
1. МОДИФИЦИРОВАННЫЙ МЕТОД УТОЧНЕНИЯ ОЦЕНОК
Ну < Н,
(1)
у = ¥х, Ох < g,
где x е Rn, Gx < g - компактное множество допустимых решений, G и g - заданные матрица и столбец, F : Rn —► Rd - заданное линейное отображение, связывающее значения критериев с решениями.
Метод УО является методом полиэдральной аппроксимации выпуклого телесного компактного тела C евклидова пространства Rd с использованием расчета опорной функции аппроксимируемого тела, которая для ненулевых векторов u из пространства Rd определяется в виде
g(u|C) = max<у, u). (3)
у е C
Метод УО итеративным образом строит последовательность аппроксимирующих телесных многогранников {Pk}¡°=0, сходящуюся к телу C в метрике Хаусдорфа, определяемую для компактных множеств C1 и C2:
5( C1, C2) = max{ sup inf ||x - y||, sup inf ||x - у||}.
у е C2 x е C1 x е C1 У е C2
Сначала строится некоторый аппроксимирующий многогранник P0, вершины которого лежат на границе аппроксимируемого тела C. Многогранник P0 должен иметь двойное описание: в виде списка вершин и как множество решений конечной системы линейных неравенств (см. [10]).
Рассмотрим k + 1-ю итерацию метода УО. Пусть на k-й итерации построен многогранник Pk, вписанный в тело C в виде списка вершин и как множество решений конечной системы линейных неравенств. Обозначим через U(Pk) множество единичных внешних нормалей к гиперграням (т.е. граням максимальной размерности) многогранника Pk. Множество U(Pk) задается системой линейных неравенств, описывающей многогранник Pk.
Шаг 1. На основе вычисления опорной функции тела C среди элементов множества U(Pk) находится такое направление u*, что
k
u* е Argmax{g(u|C)-g(u|P )}.
u е U (Pk)
Если
max {g(u|C) -g(u|Pk)} = 0,
u е U (Pk)
то работа алгоритма завершается. В противном случае берется точка у* такая, что
<у*, u*) = g(u*|C), после чего переходим ко второму шагу.
Шаг 2. В качестве очередного многогранника берем Pk + 1 = conv{Pk, у*}. Этот многогранник также строится в виде множества решений системы линейных неравенств с помощью методов теории линейных неравенств (см. [2]). На этом
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.