Чувствительность решения некоторых возмущенных задач оптимизации

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

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

Вопросы чувствительности решений динамических систем к изменениям параметров, включая решения динамических и статических

Статья выполнена при частичной поддержке гранта РФФИ №15-29-06053.

○ c А. О. Блинов, М. Г. Дмитриев, 2016

○ c Институт программных систем им. А.К. Айламазяна РАН, 2016

○ c Программные системы: теория и приложения, 2016

задач оптимизации, отдельно изучались в литературе [1] . Асимптотические разложения решений регулярно и сингулярно возмущенных динамических систем, в том числе и задач оптимизации в динамических системах строились в многочисленных работах (см. обзоры [2 –4] ).

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

Как отмечал Т. Л. Саати в [5] , исследование чувствительности в задачах многокритериальной оптимизации является актуальной проблемой.

Один из распространенных методов решения многокритериальных задач –– сведение многокритериальной задачи оптимизации к соответствующей скалярной. В литературе имеется много подходов к решению задачи «скаляризации» критериев [6 –9] , в их числе линейная свертка критериев.

• 1.    Чувствительность линейной свертки для метода главного критерия

Не останавливаясь на аксиоматике и корректности использования линейной свертки [9] , определим формулы чувствительности для некоторых возмущенных скалярных задач оптимизации.

Пусть для конечного набора критериев

Ik (ж) ^ max, к = 1,.. ., m, xEX где X С Д” — некоторое выпуклое множество. Используя линейную свертку, приходим к однокритериальной задаче оптимизации т                     т

• (1)        I (ж) = У' C k I k (ж) ^ max,      C k >  0,       C k = 1,

t E X k=1                               k=1

где предполагаем, что веса критериев известны. Будем также считать, что в (1) первый критерий является главным или базовым (доминирующим), т. е. с 1 > C k , к = 1, а остальные веса достаточно малые с _к = c _k е, a _k >  0, к = 2,. .., m, и их можно упорядочить, используя упорядоченность между a _k . Числовые конкретные значения малого положительного параметра 0 < е <  е о < 1 и множителей ctk вводятся

т с помощью соотношений С1 + 52 „ке = 1, Ск = „ке, к = 1, „к > 0.

к=2

Получаем регулярно возмущенную задачу однокритериальной оптимизации

т

• (2)              ! _е (ж) = С 1 1 1 ( х) +     еа к ! к (ж) ^ max,

^—^            хЕХ к=2

решение которой зависит от малого положительного параметра е. Предположим, что выполнены следующие условия:

• (1)    множество X — выпуклое ограниченное множество в пространстве Я ” и все функции-критерии ! _к (ж) достаточно гладкие функции своих переменных на X;

• (2)    функция-критерий I 1 (ж) сильно вогнутая на X.

Учитывая, что все критерии — гладкие функции, построим серию задач максимизации для членов разложения 1 _е (ж), представляя решение в виде ряда по целым степеням малого параметра и используя соответствующее разложение критерия I _e (ж) в ряд по целым степеням е , как в [10, 11] .

Пусть

• (3)                     ж(е) = ж ⁰ + еж ¹ + ... е X.

Подставляя (3) в ( 2) и раскладывая ! _е (ж) в ряд по степеням е, имеем

• (4)    I (ж(е)) = 1_е(ж) = I ⁰ (ж ⁰ ) + е! ¹ (ж ⁰ ) + е ² ! ² (ж ¹ ) + ... ^ max

х0,х1,...ЕХ или

! _е (ж) = c i f ! 1 (ж 0 ) + е ( " V ж ¹ ₊ 1 е ² (ж 1Г ^ 2 !^ ж ¹ + ... ) +

I           у дж у 2           дж ²           j

+_е( £ а к ! к (ж - )+ е ] Г „ к (°^ Vж 1 +...) = \ к =2              к =2          ^ж /           у

= сЫ.^Н = [= , ( \)

т m        1

ж1 + ^ «к Ыж" + к=2

+_E 2 = 1 (« 1 ) ^т ■        « 1

A  / дI k (ж " \

⁺ L"« k=2 ^{x        7}

т ж1 + O(£3) =

m т д I ж ж1+

= = 1 I 1 (« 0 ) + £ ^ « к I k (ж " ) + £ ² ^Ц (ж ¹ )

+ '^ « _к f ^1^(ж ) ^   ж ¹] + е ³ ^(ж " ,ж 1 ) + О(е 4 ) ^ max

■

\ дж   / I                                   х ⁰ ,х 1 ,... е х

Здесь К(ж°,ж¹) — известная функция своих аргументов. На основе леммы о перестановке операции максимизации с разложением в регулярный ряд [11] , при четных степенях параметра е последовательно получаются оптимизационные задачи для ж " , ж ¹ и т. д., а при нечетных степенях параметра е — известные функции предыдущих приближений.

Из представления (5) получаем, что главный вклад в искомую оптимальную альтернативу ж(е) вносит ж" — решение задачи

I"(ж") = =111 (ж) ^ max, хех где последнее выражение –– главная часть критерия (2), а коэффициент эь(х0)\т      mm

^С1 ( — дх ) ж ¹ + 52 « к I k (ж " ) при первой степени е в разложении (5) ' ^Х             к=2

в силу необходимого условия оптимальности для ж " принимает вид

m

£ «кIk(ж")■ к=2

Последнее выражение есть чувствительность по значению функции линейной свертки (2) к изменению параметра е (или чувствительность оптимального значения функции (2) ).

Учитывая гладкость критериальных функций и ограниченность множества X , легко показать, что имеет место

Утверждение 1. При выполнении условий 1, 2 в задаче (2) найдется такое достаточно малое £", что при всех 0 < е < £" для чувствительности по значению линейной свертки

т

• (8)                       1 1 (х 0 ) = £ « к 1 _к (х ⁰ )

к=2

имеет место соотношение I * = I * + el 1 (х 0 ) + О(е ² ), где I * = max 1 _е (х) , I * = 1 0 (х 0 ) = c 1 I 1 (х) ^ max .

х Е Х     '                           х Е Х

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

Далее, из (5) следует, что для нахождения х ¹ -чувствительности решения задачи (2) к изменениям параметра е, имеем задачу (9)      ¹ c i (x 1 ) ^{T д}4 ¹ (х 0 )х 1 + ^ « к Г^ (х ⁰ ) ^ х ¹ ^ max .

• ²          .             к =2       ^{дх                 х} 1

Из условия 2 следует, что гессиан функции есть отрицательно определенная матрица и поэтому точка максимума в (9) –– искомая чувствительность решения –– имеет следующее представление /_1пх              1      ( 9^{2 l} 1( оЛ Х^ « к ^д1 к , Ох

• ^{(10)           х} = ^-(ах?^(х)) Еса?^(х).

^{4           7} к=2  ¹

Из (10) и свойств гессиана следует, что чувствительность х ¹ зависит явно от всех весов и градиентов небазовых критериев.

Используя (10) , субоптимальная альтернатива первого порядка для задачи (2) , или асимптотическое приближение первого порядка, получается из (3) и имеет вид

Г 9 ^{2 i} 1 / оЛ \^ ^с к ^д1 к / ох

• (11)     х(е)=х ⁰ + ех =х ’ -         (х ⁰ )                 (х ⁰ ).

дх2     ! ^-^ с дх х          7    к=2 1

Теперь, применяя традиционные рассуждения при построении асимптотического приближения решения вариационных задач методом малого параметра (см. [11] ), нетрудно получить, что имеет место доказанное в [10]

Утверждение 2. Если при выполнении условий 1, 2 в задаче (2) найдется достаточно малое e q такое, что Х ( е ) = х° + ex ¹ Е X при всех 0 <  е <  Е о , тогда

• (1)    решение х * задачи (2) существует и единственно в некоторой окрестности решения х ⁰ , и при этом имеет место оценка II^х * - ^{х ( е ) |} <  ^СЕ 2 ;

• (2)    1 _е (х ⁰ ) <  1 _е ( Х ( е )) , причем неравенство строгое, если х ¹ = 0 ;

• (3)    I * — I_£ ( X ( e )) <  Се ⁴ , где С >  0 — некоторая постоянная.

Если вычисляемая по формуле (10) чувствительность х ¹ решения х * ненулевая, то она формирует коррекцию к х ⁰ и приближение (11) к решению обеспечивает точность приближения порядка О ( е ²) , а по значению функции линейной свертки—порядка О ( е ⁴ ).

Следствие 1. Значение критерия линейной свертки имеет вид

т

I* = IE(x*) = Ii(x0) + е £ «кIk(х0)+ к=2

• + 2Е 2 [ (х ¹ ) -    . Л +2 g « к () ^Т х - ] + ... ..

Последнее представление следует из (5) , поскольку в силу необходимых условий оптимальности для базовой альтернативы выполня- 811 ( ж ⁰ ) ются соотношения — д_ж ’ = 0.

Таким образом, несмотря на сравнительно малый вклад ех ¹ в общую эффективность (порядка О ( е ² )), эта коррекционная альтернатива может существенно влиять на изменение базовой альтернативы, приближая ее к оптимальной.

Следующий член ё²! ² (х 1 ) в представлении (4) вносит существенно меньший (на порядок по е ) вклад в общий критерий эффективности I _e (х). Он формируется на основе определения х ¹ решением задачи максимизации квадратичного критерия, порождаемого гессианом базового и градиентами остальных критериев.

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

Например, если вдоль базовой альтернативы значение || ^ ^у- (ж ⁰ ) больше значений взвешенных норм градиентов других небазовых критериев, тогда больший вклад в чувствительность ж ¹ вносит слагаемое, порождаемое соответствующим небазовым критерием c номером s.

Отметим также, что сравнение норм векторов ^ дХ (ж ⁰ ), к = 2,..., т, намечает другой подход к сравнению критериев между собой с точки зрения альтернативы ж ⁰ , и при этом это ранжирование может не совпадать с первоначальным.

Пример. Пусть рассматриваются три задачи максимизации:

71 (ж) = —0.5((ж1 — 1)2 + (ж2 — 0.5)2) ^ max, 72(ж) = —0.5((ж1 — 2)2 + (ж2 — 3)2) ^ max, 73(ж) = —0.5((ж1 — 4)2 + (ж2 — 6)2) ^ max, и для линейной свертки предложены веса с1 = 0.75, с2 = 0.15, с3 = 0.1. Имеем

7 (ж) = ^ с к 1 _к (ж) = — 0.375((ж 1 — 1) 2 + (ж 2 — 0.5) ² ) — к =1

• — 0.075((ж 1 — 2) 2 + (ж ₂ — 3) 2 ) — 0.05((ж 1 — 4) 2 + (ж ₂ — 6) 2 ) ^ max. х Е Х

• 2.    Чувствительность решения для метода идеальной точки

Пусть при этом е = 0.1, ( 2 = 1.5, ( 3 = 1, тогда

7(ж) = 7 * (ж) = 1 1 (ж) + е 5 ( к 7 к (ж) ^ max . х Е Х к=2

Нетрудно видеть, что точное решение ж *( е ) в задаче на максимум линейной свертки (2) имеет вид ж * = (- /Х^ ) , и оптимальное значение критерия линейной свертки 7(ж * ) = — 1.977. Вдоль очевидного базового решения ж ⁰ = (₀ 1 ₅) линейная свертка принимает значение 7 * (ж ⁰ ) = — 2.506. Находя градиенты всех частных критериев и гессиан базового критерия вдоль ж ⁰ , из (9) получаем поправку к базовой альтернативе ж ¹ = (₁₂ 333) . Теперь из (11) следует, что ж ( е ) = ж ⁰ + еж ¹ = (, 1 . 6 ,) . 7 3 3 /

Вычисляя 7 * ( ж ( е )) = — 2.036, замечаем, что 7 * ( ж ( е )) = — 2.036 >  7 * (ж ⁰ ) = — 2.506, т. е. с ростом номера асимптотического приближения растет точность аппроксимации по оптимизируемому критерию и значение критерия свертки вдоль асимптотического приближения значительно возрастает.

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

Перейдем к анализу чувствительности для метода идеальной точки при наличии главного критерия.

Для простоты изложения рассмотрение проведем на классе трехкритериальных задач. Пусть известен вектор

Ildeal = (I*, I* I , I*k = maxIk(ж), к = 1, 2, 3, сЕХ определяющий так называемую идеальную точку в пространстве критериев.

Предположим, что положительно определенная матрица весов R, ранжирующая среднеквадратичные отклонения компонент текущего критериального вектора I _r (ж) = (1 1 (ж) 1 2 (ж) 1 з (ж)) ^т от их идеальных значений I * к = 1, 2, 3, имеет вид

R = (

R i   eR 2

ER 2 eR ₃

) > °'

где e — малый параметр, ° <  e <  Е о < 1, и

R 1 = Т 11 ,   R 2 = (Г 12 г_и), R 3 = ( ^Г 2 ^{2   Г} 2 ³ ) .

\^23   Т зз)

Будем искать альтернативу ж Е X С R ” путем решения задачи 4М = ⁽1 _Т ^(ж) — ^I * _deal ^{) Т r ( i} _t ^(ж) — ^I * _deal ⁾ ^ min . сс Е Х

С учетом представлений I _r (ж) = (^ ^{г (ж )} ), I^ i = ( ^ *^eal ) , где \и _г ^(ж)/              XJLduaeaU

L _T (ж) = 1 1 (ж), D _T (ж) = ( 1 2 (ж) ) , L* deal = I * , D *deal ( l * ) , из (11)

имеем

• (13)            min { I _E (x) = (I r (x) - I * deai )^TR(I _r (x) - I * deai )} =

же A

= min{[(Lr(x) - L’deal)TRl(Lr(x)   Lideal) + xGX

+2e(L r (x)    ^L ideal ^{) T R} 2 ^{( D} r ^{( x ) - D} *deal ^{) +}

^{+ e ( D} r ^{( x ) - D}* deal)^{T R} 3 ^{( D} r ^{( x ) - D} *deal ⁾ ] ^} =

= { [^ 11 (I 1 (x) - I 1 ) 2 + -T 22 (^R(x) - I * ) ² + -T 33 (I 3 (x) - I * ) ² +

+2-Tu(I 1 (x) - I * )(I 2 (x) - I * ) + 2eT i3 (I i (x) - I * )(I 3 (x) - I * ) +

^{+2 eT} 23 ^{( I} 2 ^{( x ) - I} 2 ^{)( I} 3 ^{( x ) - I} 3 ) ⁺ . . .] ^} x ^min .

^ex

Подставим (3) в (13) и разложим 1 _Е (х(е)') в ряд по степеням е:

Г(г(е)) = /th U/1 (x 0 ) - I * )+ +- ('.  ) T x 1 +2-w      x 1 +..: ,               0\    r*\ I     (dI 2( x 0 ) A      1  .   1 2/ 1\T d' 2 I 2 ( x + eT 22 ( I 2 ( x )  ^И -^ 9x  J  x + 2- ( x )     gx 2 ,       Lr / 0x r*\ . ( dI3(x0) A 1 . 1 2/ 1\T 9' 2 I 3 ( a + -T 33 [( I 3 ( x )  ^       dx  )   x  1 2 -■ ( x ) 8x 2 Lr ( 0\     г *A 1     ( dI1(x0) \     1 , 1 2/ b,T 9 2 I 1 ( +2 -T 12 ^(I 1 ( x ) I 1 )+ -(^ dx ) x 1 2-• ( x )     dx		2 +
		X1 +.. X1 +.. ^+. ^x 1 + . . .	. .] .. +	2 + 2 + ] X
X	/Г / 0\    r*\ . ( dI 2 (x0) A 1 1 2/ bT 92I 2 (x 0 ( I 2 ( x ) I 2 )+ 4 dx ) x + 2- ( x )     dx 2
,9               0x     T *x .     (dI 1 ( x0 ) \      1     1 2, 1xT Э 2I 1 ( x 0 ) 1 . +2 -T 13 ( I 1 ( x )   I 1 ) + e^ dx J x + 2 - ( x )     dx 2    x + .			..	X
X	/Г / 0\    r*\ . ( dI 3 (x 0 ) A 1 . 1 2/ 1\T d2I 3 (x 0 ( I 3 ( x ) I 3 )+ 4 dx ) x + 2e ( x )     dx 2	^x 1 + . . .	+
.9             0\     T *\ .    (dI 2 ( x 0 ) \     1     1 2/ bT Э 2 I 2 ( x 0 ) 1 +2eT 23 (I 2 (x ) I 2 ) + el ^x ) x +2e (x )     ^^ 2   x +.			..	X
X	(r ( 0\    r*A_L (dI3(x0) V 1 , 1 2/ 1aT d2I3(x0 [ (I 3 ( x ) I 3 ) + 4 dx ) x + 2e ( x )     dx 2	x + . . .	}

• (14)                      I _e ( x ( s )) = eVr 22 (I 2 (x⁰) - I * ) 2 +

+г зз (/ з (х ⁰ ) - I 3 ) ² + 2 t 23 ( I 2 ( x ⁰ ) - I * )( I 3 ( x ⁰ ) - I * ) } + +е ² |2г 22 (1 2^0 ) - I * ) ( ^Э1 дХ ^Х1 ) х ¹ +2г зз ( 1 з ( x ⁰ ) - I * ) ( ^Э1 дхХ ⁰1 ) х 1 + +2Г 23 [ ( I 2 ( x ⁰ ) - I * ) (^dIdX ^X^ У х ¹ + (1 з ( х ⁰ ) - I * ) (^dI 2 dX ⁰ ) у X 1 ]j +

+Н (х ⁰ ,х 1 )е ³ + О ( е ⁴ ) ^    min .

ж ,ж .... £

Учитывая гладкость критериев, ограниченность X , а также равенства 1 1 (ж ⁰ ) = ! * , ^^т-) = 0, получаем

Утверждение 3. При выполнении условий 1, 2 найдется доста точно малое в о , что при всех 0 < Е <  Е о для чувствительности по значению 1 ¹ (ж ⁰ ) функции 1 _е (х) в задаче (13) имеет место соотношение

• (15)          1 1 (ж ⁰ ) = Т 22 (1 2 (х ⁰ ) - I * ) ² + т зз (1 з (х ⁰ ) - 7 * ) ² +

+Г23(12(Х°) - 12)(1з(х°) - I*), и при этом I* = е1 1 (ж0) + О(е2).

Здесь, как и в случае задачи (2) , чувствительность по критерию является функцией весов и значений неглавных критериев вдоль базовой альтернативы. Указанная чувствительность является также положительной функцией отклонений значений неглавных критериев от максимальных значений этих критериев и поэтому из (15) следует, что при слабом уменьшении весов неглавных критериев близость к идеальной точке в пространстве всех критериев возрастает, а при слабом увеличении тех же весов – уменьшается.

Заключение

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