книги / Математические методы в системах поддержки принятия решений

значения убывают при увеличении номера итерации и ограничены снизу, то имеет место сходимость метода. Применительно к рассмат­ риваемому методу обобщенного градиента функция Ляпунова конст­ руируется непосредственно на минимизирующей последовательности х*, к = 0,1, 2,..., или на значениях минимизируемой критериальной

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

Покажем это для простейшего варианта задачи минимизации вы­ пуклой квадратичной функции, т.е. сильно выпуклой функции, задан­ ной в двумерном пространстве. Для этого воспользуемся выражением перехода от х*кх*+;:

x l+l = х к - р к grad/(x*),

где составляющие градиента есть частные производные У (х*) , / = 1,2, в Эх,

точке х* е R2 , которые оцениваются в процессе работы алгоритма по­ иска искомого решения х* е R2 .

Обозначим через Э/(х*) оценку частной производной; она вычисля­ ется из равенства вида

где Д — величина пробного шага, g, — координатный орт, /—1, 2.

При этом можно считать, что оценки частных производных выполня­ ются за время A t , т.е. при условии, что состояниям х*+| и х* соответст­ вуют моменты времени /*+|, /* и At = t k+l - t k; тогда при Д-» 0 и At -» О

получаем уравнение

— = -p(/)grad/(x). ot

Теперь, (см., например, [19;22]) введем (на минимизирующей по­ следовательности) функцию

К(0 = (х(/)-х*)2, t>0.

Эта функция удовлетворяет требованию знакоопределенности: она положительно-определенная, содержит все переменные, на множестве значений которых определена критериальная функция, и непрерывна вместе со своими производными. Таким образом, введенная функция V(t) есть функция Ляпунова. Согласно ей и уравнению траектории дви­

жения к искомому решению получаем:

291

V(t) = 2(x(t)-x*)x(t) = 2(x(1)—x*)(-p(Ograd/(x)+p(Ograd/(x*)) =

=-2p(0[(grad/(x)-grad/(x*))(x(0~x*)] <

<-2p(t)a(x(/)-x*)2 = -2p(f)aV(t), a > 0, p(0 > 0,

где неравенство следует из условия выпуклостиfix) [19], а grad/(x*) = 0.

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

В результате имеем уравнение

K(/) = -2p(0aF(0, V{t0) = К0,

интегрирование которого непосредственно приводит к выводу о сходи­ мости градиентного метода в задаче минимизации гладкой сильно вы­ пуклой критериальной функции.

Для локально сильно выпуклых негладких критериальных функций также справедливо неравенство

@Дх) - ЭДу), х —у) £ 0, Vx, у е R 1,

т.е. обобщенный градиент (субградиент) является монотонным операто­ ром, а значит, справедливо и неравенство

(ЭДх) - ЭДу), х - у) > а(х - у)2 Vx, у е R".

В результате получаем сходимость алгоритма метода обобщенного гра­ диента; сходимость — медленная, поэтому на практике применяются релаксационные методы локальной минимизации обобщенно диффе­ ренцируемых критериальных функций [109].

Структура соответствующего алгоритма представляется следующей последовательностью операций [109; 111] :

Ал г о р и т м

1.Задать начальное приближение х° е Rn.

2. Вычислить в точке х° для критериальной функцииДх) субградиентное множест­ во Gf (х°).

3.Выбрать произвольный вектор-субградиент v0 е (y(jc°).

4.Проверить условие Цу0|| й EQ; если оно выполняется, то точка JC° есть искомое реше­

та (-v 0) из тонких® в точкух1; этот шаг определяется из решения задачи

/(•*') = min/( х 0 - a v 0). a>0

Если окажется х1= х° , то направление (-v0) следует изменить, для этого надо перейти к оп. 3 и выбрать другой вектор-субградиент v0 .В случае х1*х° — перейти к оп. 6.

292

6. Проверить условие \\х1- *°|| й 5 или Дх°) - Д х 1) > 5. Если любое из них выполняет­ ся, то алгоритм завершает свою работу и = х*. В противном случае — вычислить в точ­ ке X1 субградиентное множество С/х1) и перейти к оп. 7.

7. Выбрать вектор-субградиент v00 е Gf(x{) из условия: скалярное произведение

(уо» VQO) ^0.

8.Проверить условие Цу^Ц < £д ; если оно выполняется, то х] =х* и алгоритм заверша­ ет свою работу, в противном случае — перейти к оп. 9.

9.Найти новый вектор-субградиент vj из условий

*1 “ Ро *оо + О - РоЧ>

IIV||= min||ро^оо + 0-Po)vo, 0 <р0 <1

10. Перейти к оп. 5 для отыскания точки х2 на луче хх- av I? a > 0, и выполнения при этом соответствующих вычислений.

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

(||х*+1- х*I|S8 v /(дг*)- /(Д(*+1)>8)л|IV*I|Sе0,

где v, л — логические операции «ИЛИ», «И».

Очевидно, что найденное решение х* является локально-опти­

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

9.2. Конечно-разностный метод минимизации липшицевых критериальных функций

Метод построен [19, 109, 133, 136] на идее сглаживания исходной невыпуклой или невыпуклой негладкой критериальной функции fix ) с

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

Формально операция сглаживания записывается так:

где а > 0 — параметр сглаживания (усреднения), (оа(и) = 1/ 2а — плотность равномерно распределенной случайной

величины и , - а й и й а ,

/(х ,a) -> f( x ) и сходимость — равномерная.

293

Операции сглаживания, например, вида

т.е. операции сглаживания функции одной переменной, соответствует операция дифференцирования в форме симметрической конечной раз­ ности

/'(* , а) = - —[Д х + а ) - /(х - а )];

этим замечанием воспользуемся ниже (справедливость формы уста­ навливается непосредственно дифференцированием по х выражения для Дх, а » .

Идея сглаживания широко используется в практике обработки слу­ чайных процессов. В результате исходный процесс преобразуется в дру­ гой согласно преобразованию вида

Дх, а ) = Аа(и)Дх, и),

где Аа(и) — обозначение оператора преобразования (фильтра с памятью

2а по каждой компоненте вектора х), а — неотрицательный скалярный параметр, Дх, и) — преобразуемый процесс,

Дх, а) —преобразованный (сглаженный) процесс.

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

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

Значение параметра а устанавливается в результате анализа негладкостей исходной функции Дх). Оператор Аа(и) при различных а будет

задан соответствующей последовательностью, что, в свою очередь, при­ водит и к соотношению /(х ,а ) -> /(х ), т. е. эффект сглаживания прояв­ ляется лучше при большем а.

Градиент функции Дх, а) в точке х определяется по формуле

Частная производная функции, например, пох^

294

- /( * , - а , у 2,у г ,...,y„)]dy2dyi ...dy„

или

УU U

V/(x,а) = —— J ... J g (x +y)dy, dy2 ...dy„ g(x + у) e ЭДх + у),

-а -а

где последнее выражение (включение) относится к случаю рассмотре­ ния негладкой функцииДх). Отсюда видно, что вычисление УДх, а) — задача сложная, это обусловлено сложностью вычисления многомерно­ го интеграла. Поэтому переходят к математическому ожиданию

МН(х, а) = УДх, а ),

гдеЯ(х, а) — параметрический стохастический градиент [136] (случай­ ный вектор),

здесь х ,, /= 1, и — независимые одинаково распределенные случайные величины на отрезке [х, - а, х, + а], а * 0.

Конечно-разностная аппроксимация градиента функции Дх, а)в точке х, выбранной случайно из «-мерного куба со стороной 2а и цен­ тром в точке х непосредственно приводит к выражению

^ / ( х + А е () - Д х ) _

где смещение ||b|| < -JnLA. / a, L — константа Липшица.

В результате структура алгоритма конечно-разностного метода ми­ нимизации липшицевых критериальных функций записывается в виде

х к*‘ = х* - р к Н (хк, а), (*)

где рь к = 0,1, 2... должны удовлетворять условиям вида [109; 133; 136]

295

|а*+/ - а*| /р к -» 0 при а* -> О и более быстром уменьшении величины Д*

по сравнению с а*. При выполнении этих условий искомое решение бу­ дет принадлежать с вероятностью единица множеству

Г = {х’ / 0 € ЭДх)},

X ’ — ограниченное множество, х* е X ’ Ук.

Алгоритм (*) есть ничто иное, как стохастический вариант градиент­ ного метода, реализующий процедуру Кифера-Вольфовица и операцию усреднения результатов измерений при р* = р0/к + 1, к = 0, 1,2, 3,....

Очевидно, что последовательность рь к = 0, 1, 2,... удовлетворяет требо­

Отметим, что более эффективным конечно-разностным методом выбора оптимального решения в рассматриваемых задачах, в том числе и в задачах минимизации функций максимума

f ( x ) = шах/, (х) -» min,

1й !йг х е Х

где/(х) — выпуклые функции на компактном множестве X с Ея явля­ ется м е т о д п р о е к ц и и о б о б щ е н н о г о г р а д и е н т а . Структура алгоритма этого метода записывается в виде

х*+1 = п х ( х к - p kH J( x k,a))>

где

/,(* , ,...,х,. +а*,...,х„ ) -

-/)(x * ,...,x f - а к,...,хк) •«/»

р* должны удовлетворять тем же требованиям, что и в предыдущем алгоритме,

пх — оператор проектирования точки х на множество X ,

x tky — независимые равномерно распределенные на [хк - а к, х к + а к] случайные величины,

/ )(xk) = f ( x k) = maxf j ( x k)9 т. е. конечные разности вычисляются на

каждой итерации алгоритма по тем функциям, на которых достигаются максимумы.

296

9.3.Структура метода условного градиента

взадаче выбора решения при ограничениях

Установлено (см., например [20; 22]), что схема классического мето­ да условного градиента, изложенного в гл. 6, распространяется и на за­ дачи выбора решений при негладких критериальных функциях, задан­ ных на ограниченных замкнутых выпуклых множествах. Отличие, возникающее при его использовании, состоит в построении последова­ тельности векторов направлений z k+1, к = 0, 1,..., движения кх’ как ли­

нейных комбинаций вида

Zk+' = (1 - a)zk + акН (хк, а*), ? = Я(х°, cto), 1 > ак>0,

а векторы Н (хк, а*) определены в предыдущем пункте, и в построении структуры алгоритма выбора искомого решения х' задачи m in/(x), D бу­ дем считать выпуклым компактом. xeD

Решение задачи будем отыскивать согласно конечно-разностному методу минимизации липшицевой функции Д х) пусть при линейных ог­ раничениях D.

Соответствующую структуру алгоритма обобщенно запишем в виде

х*+| = х к +pt (x* - х к),

гдех* — решение задачи линейного программирования min(z‘ , x - x ‘ ).

x e D

Ал г о р и т м

1.Сгенерировать случайную реализацию-точку jc° равномерно распределенной слу­

чайной величины в л-мерном кубе с центром в *° — начальной точке и ребром 2<х0 .

2. Вычислить Н(:с°, а 0) — конечно-разностную аппроксимацию градиента функ­ цииДх, а) в точкех °

где AQ — заданное значение приращения-смещения, определяющего величину конечной разности, е( — координатный орт / = 1, 2,..., л.

3.Проверить условие ||Я(дс°, а<))|| <е0 ; если оно выполняется, то *0 = JC* и алгоритм за­ вершает работу, иначе — перейти к операции 4.

4.Определить направление

Z k = z k~ x + а к( Щ х к ~ \ а * _ ,) , 0 £ а к й \ .

5. Вычислить точку *° на направлении z° = Я(х°, OQ) и з решения задачи линейного программирования

/( * 0) = U 0,* -x ° ) -> m in-» JC°.

x e D

где шагро и все последующие р*, к - 1, 2,..., должны удовлетворять условиям, приведен­ ным в конце п. 9.2.

7. Проверить условие ||х1 - х°|| й 5 или ||Дх°) -У(х1)| ^ 8 ; если одно из них выполняет­ ся, то завершить работу алгоритма и принять х* = хт , иначе — перейти к on. 1 для выпол­ нения очередной итерации поиска оптимального решения х* .

9.4.Метод наискорейшего спуска

Сущность метода и его применение рассмотрим на конкретных ми­ нимаксных задачах (это негладкие задачи). Алгоритм поиска оптималь­ ного решения, согласно изложенным в п. 5.1.1 необходимым условиям для этого метода, включает следующие операции.

А л г о р и т м 1. Проверить функцииД х ) н а непрерывность, дифференцируемость, выпуклость.

2.Задать начальное приближение х°.

3.Установить множество

Л(х°) = {/е [1,я] / /,(х ° )= max /,(*)}.

1</£Л

4.Вычислить градиенты функций, индексы которых составляют множество Л(х°).

5.Построить выпуклую оболочку

6. Проверить выполнение условия 0 е L(x°). Для этого необходимо решить задачу

вида

которая эквивалентна задаче линейного программирования: найти min А. при ограни­ чениях

Видно, что 0 6 L(x°), когда X = 0. Решение этой задачи можно найти при использова­ нии симплекс-метода. Если в условиях конкретной рассматриваемой задачи для заданно­ го начального приближения х° выполняется условие 0 е L(x°), то х° = х* есть оптимальное решение, в противном случае необходимо построить наилучшее очередное приближение

X1= Х° + Р#(х°)

298

к оптимальному решению (альтернативе** е Е1); здесьg(*°) — направление наискорейше­ го спуска, на котором следует осуществить перемещение из точки*0 на расстояние (шаг) р . Для этого надо перейти к оп. 8.

7. Дополнительно к п. 6 проверить необходимое условие — выполняется ли

ве ** е ЕК Для этого найти точку z — точку из Цх°) , ближайшую к началу координат, или, что то же, найти проекцию точки начала координат на замкнутое выпуклое множест­ во 1(*°). Затем построить прямую, проходящую через точку z е Д*°) и точку начала коор­ динат, и на ней построить единичный вектор, исходящий из точки начала координат в направлении от точки z. Отыскание точки z составляет решение задачи вида

Z ( x ° ) = a rg m in | | 0 - T I||.

Ч€(*°)

Для ее решения можно воспользоваться каким-нибудь итеративным методом, задав пред­ варительно точку — начальное приближение из Д*°). Единичный вектор искомого на­ правления наискорейшего спуска определяется по выражению

гС*°)

Нг(*°)П

9.Найти длину шага р. Для этого надо взять выражение для верхней огибающей

max /. (*), тогда

1£/<л

Ф(х° + fe(x#)) = шах{/)(х° + Р«(*0))}.

10. Вычислить очередное приближение х1 =х° + pg(x°). Перейти к оп. 3 и установить

Л(*‘).

- 11. Далее продолжить решение задачи по оп. 4—6.

Применим этот алгоритм к решению следующих задач.

Задача 1. Пусть на Е2 заданы частные критерии

/ I (* I ,*2) = *,2 + *2> / 2 ( х \ , х 2 ) = 2 - * 1 - 2 * 2 , /з (* ,,* 2) = 2 - * , + * 2.

Найти такую альтернативу х* е Е2, чтобы выполнялось условие

ср(**)= min m a x (*,,*2) , * = ( * , ,*2).

х е Е 21 ^/53

Р е ш е н и е . Данная задача является дискретной минимаксной; функции/i(x ),/г(^), / 3(*) дифференцируемы и выпуклы. При этом выпуклой будет и функция <р(х) но, очевид­ но, негладкой. Зададим начальное приближение *<0) = (-1, -1 ) и вычислим значения функций

/,(*>) = 2, / 2(*<°>) = 5, / 3(*°>) = 2,

по которым определим множество Л(х<°>) = {/ = 2}, так как max /Д х (0)) достигается при

/ = 2. При этом выпуклая оболочка !(*«») состоит из одной точки ( - 1 _ 2) _ ОНа опреде­ ляется только V/2(M°)) = (-1 , -2 ) и не накрывает начало координат те П* /М0)\

Итак, необходимое условие оптимальности альтернативы *°> не выполнено поэтому переходим к поиску следующего приближения (*«>). Для этого через точли Т -1 - ?Ли (О, 0) проводим прямую и строим на ней единичный вектор 1(х<0>), исходящий из точки (-1 , - 2 ) в направлении начала координат, £(х<0>) с координатами(1/ Д 2/<JS). Тогда име­ ем,

В,)=3?°> + р0дао>))

где длина шага р(|) определяется из условия

<р(х<0> + Р(1>| (*<0>)) = mm<p(x(1))= mm niax /)(х<0) + р£(*<0) )) =

= шах. р 2 - А ,р + 2,5 - Р л / 5 ,^ + 2 J.

Воспользуемся геометрической интерпретацией этой функции. Минимум функции

Вычислим значения функций f t{I) при x —Зс*1);

/2(В')) =1, /з(3?'))=2.

Следовательно,

* № ) = V = 2, / - 3}, V/20?») = (-1, -2), V/3(*D) - (-1, 1),

и выпуклая оболочка Дх*]*) представляет собой отрезок, соединяющий точки ( - 1, - 2) и

(-1, 0; видно, что 0 ё Дх*1*) (см. рис. 7, б), т. е. необходимое условие оптимальности ре­ шения не выполнено.

Переходим к поиску следующего приближения. Для этого через ближайшую к нулю точку из Дх*1)), т.е. из точки (-1, 0) проводим единичный вектор в направлении начала координат. Очевидно (см. рис. 7, б), £(3с*0 ) {1, 0}. Тогда хР> =3?!) + р*2) ^ 1)), где длину шага р<2>найдем из условия

ф(Р(2)) = ф (* °} + P(2)|(3c(1})) = min ф (х °} + Р |(х ° })) =

=min max /}(3с(,) + Р(2)КЗс(1)»,

р1£/£3

подставляя численные значения, получаем функцию

фСх*1) + Pit**1))) = max.

300