ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 6, с. 34-43
МЕТОДЫ ^^^^^^^^^^^^^^ ОПТИМИЗАЦИИ
УДК 519.2
ОПТИМИЗАЦИЯ НА ОСНОВЕ ТЕОРИИ МЯГКИХ МНОЖЕСТВ. I*
© 2007 г. Д. В. Ковков, В. М. Колбанов, Д. А. Молодцов
Москва, ВЦ РАН Поступила в редакцию 21.06.07 г.
Рассматривается устойчивость множеств, заданных ограничениями, в контексте теории мягких множеств. Отдельно представлены линейные ограничения. Приводится сравнение результатов с классическим случаем.
Введение. Задачи оптимизации весьма важны как в математике, так и особенно в ее приложениях. Если их понимать достаточно широко, включая туда и задачи математического программирования, и задачи максиминного типа, и многокритериальные задачи, то практически вся теория принятия решений в той или иной мере опирается на теорию оптимизации. Особенно широкое распространение получила задача оптимизации с линейными функциями и ограничениями - линейное программирование. Во многих физических теориях принципы оптимизации используются для формулировки физических законов.
Несмотря на столь широкое применение оптимизации, многие ее задачи являются неустойчивыми, что служит определенным препятствием для их практического применения. В классической математике для решения проблемы неустойчивости используют построение регуляризующих операторов. Теория мягких множеств предлагает новые средства в борьбе с неустойчивостью. Во-первых, существенно расширяются возможности формализации задач оптимизации. За счет подходящего выбора понятия приближенного решения можно сделать задачу устойчивой. Во-вторых, оптимизационная задача может стать устойчивой за счет применения новых, более адекватных практике понятий непрерывности мягких отображений. В-третьих, привлечение регуляризации мягких отображений позволяет свести построение мягкого регуляризующего отображения для произвольного отображения Е к вычислению двух отображений (в зависимости от типа регуляризации) тЕ и ехЕ, конструкция которых определяется достаточно просто.
С другой стороны, в теории оптимизации формулируются постановки, которые учитывают неопределенность в исходных параметрах задач. Это, во-первых, так называемое стохастическое программирование [1, 2], где задаются вероятностные характеристики параметров и целью являет-
*
Работа выполнена при финансовой поддержке РФФИ
(проект < 06-07-89300).
ся, в частности, получение детерминированных эквивалентов. Сами решения могут трактоваться как детерминированные или случайные векторы и ограничения могут выполняться с той или иной вероятностью. В так называемых жестких постановках условия задач выполняются при любых реализациях случайной величины. Наконец, в двух-этапных задачах стохастического программирования вводятся невязки, позволяющие нарушаться ограничениям, которые, однако, минимизируются при помощи соответствующих функций штрафа.
Также следует упомянуть цикл работ [3-5] по аппроксимации несобственных задач оптимизации, которые тоже направлены на учет неопределенности. Используемые там корректирующие элементы и различные нормы (см., например, [6]) приводят к различным решениям, зачастую далеким друг от друга, хотя анализ проводится в конечномерных пространствах. Наконец, интересным направлением по проблемам неопределенности в оптимизации является так называемое возмож-ностное программирование с нечеткими бинарными отношениями, когда в критериях и ограничениях присутствуют нечеткие отношения Заде [7]. Здесь также удается построить детерминированные элементы и исследовать устойчивость.
В данной работе оптимизационные задачи рассматриваются в свете теории мягких множеств [8], которая направлена на формализацию понятия приближенного описания объекта. Заметим, что понятие мягкого множества близко к определению нечеткого множества Заде [9], где вводятся степени принадлежности, но первое является более широким понятием и лишено ряда противоречий, в частности субъективизма в понимании самой степени принадлежности.
На основе теории мягких множеств развивается анализ [10], при этом формулируются понятия мягкого числа, мягкой производной, мягкого интеграла и т.д. В работе это относится к мягким оптимизационным задачам. Поскольку в теории мягких множеств отсутствует понятие инфините-зимальности и топология зависит от самого объ-
екта исследования, то удается преодолеть трудности, связанные с неустойчивостью классических оптимизационных задач, решить проблему различия решений при различных нормах корректирующих элементов, упомянутую ранее, а также разработать единый аппарат исследования. Предполагается знакомство читателя с основными конструкциями теории мягких множеств [8].
1. Множество, заданное ограничениями. Начнем исследования с этой простейшей задачи, которая является основой для изучения других более сложных задач математического программирования, многокритериальных задач оптимизации и максиминных задач.
Пусть X - универсальное множество с метрикой р. Ограничения, задающее множество, будем описывать с помощью функции /, определенной на множестве Вот/ с X и принимающей значения в пространстве Е", т.е. /: Вот/ —► Е". Каждая такая функция / может отождествляться с ее графиком дг(/), где
д/) = {(X, и) е X X Е"| х е Вот/), и = /х)}.
Множество всех возможных графиков обозначим М, оно и будет играть роль множества возможных моделей в этой задаче. Введем окрестности в пространстве X, 5-окрестностью точки х е X будем называть множество 05(х) = {у е X|р(х,у) < 5}, а под 5-окрестностью множества У с X будем понимать множество 05(У) = ^ 05( х). Множество,
х е У
заданное ограничениями, опишем с помощью мягкого отображения (Т, Еф X Е), где а е Еф, в е Е,
а, Ь е Е",
Т/ а, в) = 0а{х е Вот/\а - в </х) < Ь + р}.
Параметры a и b, где a < b, полагаются фиксированными и поэтому не включаются в число аргументов. Напомним, что сумма и разность вектора и числа понимается в следующем смысле: (a1, ..., an) -- в = (a1 - в, ..., an - в). Если положить в = 0, то получим классический вариант описания приближенного решения для множества, заданного ограничениями, а именно
T0(f, a) = Tf, a, 0) = Oa{x e Bomf)\a <fx) < b}.
Классическому представлению соответствует мягкое отображение (T0, Еф). Определим теперь псевдометрику для описания возмущения моделей, т.е. графиков функций. Будем использовать для этих целей псевдометрику Хаусдорфа. Для этого сначала зададим метрику r на множестве X х En следующим образом: r((x, u), (y, v)) = max{p(x, y), \\u - v||}, где \\u\\ = max \u\ . Псевдометрика Хау-
1 < i < n
сдорфа rH записывается как rH(U, V) = max{ sup inf r(u, v), sup inf r(u, v)},
u e Uv e V v e Vu e U
где U, V с X х En. В качестве псевдометрики для моделей | рассмотрим псевдометрику Хаусдорфа для графиков этих функций, т.е.
If, g) = rH(gr(f), gr(g)).
Открытая окрестность модели f тогда имеет вид
Mf, 5) = {g e M\ |f g) < 5}, 5 > 0.
Подставляя определение псевдометрики Хау-сдорфа, получаем
M( f, 5) = \ g e M\ sup inf max{p(x, y), \\f(x) - g(y)||}<5,
I x e Dom(f) y e Dom(g)
sup inf max{p(x,y), |f(x)-g(y)||}<5}.
y e Dom(g) x e Dom(f)
Для более удобной записи множества T(f, а, ß) введем обозначения
d(и) = min и,,
1 < i < n
ф(и) = min{d(и - a), d(b - и)}.
Тогда множество T(f, а, ß) можно представить следующим образом
Tf, а, ß) = Oa{x e Dom(f)\ f)) > -ß}.
Для классического варианта соответственно имеем представление
Ш а) = Oa{x e Domf)\ 9(fx>) > 0}.
Нам потребуется элементарная оценка для функции ф.
Утверждение 1. Для любых и, v e En выполнено \ф(и) - ф(v)\ < \\и - v|\.
Доказательство. Из очевидного неравенства \\u\\ > и следует, что \\и - v\\ + v > и. Отсюда получаем, что \\и - v\\ + d(v) > d(u). Применяя это неравенство для векторов и - a и b - и, имеем d(и - a) < < d(v- a) + \\и - vH и d(b - и) < d(b - v) + \\и - v\\, откуда и следует требуемое. Утверждение доказано.
Обозначим
ф* (f) = sup ф( f( x)).
x e Dom(f)
Если Dom(f) = 0, то будем считать, что ф*(/) =
Утверждение 2. Для любых моделей f и g, таких, что Dom(f) Ф 0, Dom(g) Ф 0, справедлива оценка
|ф*(/ - ф*(?)| < Ц/, g).
Доказательство. Для любого положительного числа £ существует хе е Dom(f), такой, что Ф(/(х£)) > Ф*(/) - £. Поскольку справедливо неравенство
sup inf max{p(x, y), ||/(x) - g(y)|| } <
x е Dom(/) y е Dom(g)
f, g),
то также выполняется и неравенство
inf max{ р(x£, y), ||/(x£) - g(y)||} < f, g).
y е Dom(g)
Следовательно, по определению точной нижней грани для любого положительного числа t существует точка y^ е Dom(g), такая, что имеет место неравенство max{ pfe, y^), \/x£) - g(y^)||} < |i/ g) + t Отсюда
ф*(/ - £ < ф/x)) < ф^)) + |/x^ - g(^)|| < < ф*^) + ц/, g) + t Осталось заметить, что положительные числа £ и t произвольны и f и g можно поменять местами. Утверждение доказано.
Утверждение 3. Если Dom(f) = 0, то
inf ф* (g) = ф*(/) - 5.
g е M(/ ,5)
Доказательство. Из предыдущего утверждения следует оценка inf ф * (g) > ф*(/) - 5.
g е M(/,5)
Рассмотрим функцию g е Mf, 5), определенную следующим образом (0 < 5' < 5):
g,(x) = f(x) - 5', если 2/(x) < a, + b,;
gi(x) = /(x) + 5', если 2/(x) > a, + b,.
Вычислим ф(g(x)). Примем
I (x) = {,|1 < i < n, 2/(x) < a, + b,},
I+(x) = {,|1 < , < n, 2/(x) > a, + b,}.
Справедлива цепочка равенств
ф(g(x)) = min min{g,(x) - a,, b, - g,(x)} =
1 < , < n
= min min (g,(x) - a,), min (b, - g,(x))l =
I , е I_(x) , е I+(x) I
= min min (/(x) - a,), min (b, - /,(x))l - 5' =
[,е I (x) ,е I+(x) J
=ф(/(x)) - 5'. Утверждение доказано.
С помощью функции ф* нетрудно дать оценку для внутреннего эффективного множества мягких отображений (T, Еф X E) и (T0, Еф). Выполняются следующие оценки:
Def „(T, Еф X Е) с {/, а, ß) е MX Еф X Е|ф*(/) > -ß}, Def „(T, Еф X Е) з {/, а, ß) е MX Еф X Е|ф*(/) > -ß}, Def„(To,Еф X Е) с {/, а, ß) е MX Еф X Е|ф*(/) > 0}, Def„(To,Еф X Е) з {(/ а, ß) е MX Еф X Е|ф*(/) > 0}.
Для исследования непрерывности мягких отображений (T, Еф X Е) и (T0, Еф) нам потребуются оценки на мягкие отображения exT и inT.
Утверждение 4. Справедливы следующие оценки:
1). Если у > 5 > 0, то exTf а, ß, 5) с Tf а + у, ß + у);
2). Если b + 2ß > а, то T(/, а,
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.