4.3 Метод возможных направлений
Представленный ниже алгоритм предназначается для поиска экстремума при наличии ограничений только типа неравенств. Рассмотрим задачу
пип/(ж) (4-6)
¥>.-(ж)<0 ^=1,...,то, (4.7)
ж е Яп, (4.8)
где /(ж), <~р{{х) - гладкие выпуклые функции. Вводя дополнительные переменную и ограничение, можно сделать функционал задачи линейным:
ппп у (4-9)
/(ж) < у (4.10)
<~рг{х) < 0 г = 1,то, (4-11)
ж е Кп, (4.12)
Поэтому без ограничения общности будем считать, что /(ж) = (с, ж). Пусть, как и прежде, = {ж | </зг(ж) < 0, г = 1,...,то} — множество допустимых решений задачи (4.6)-(4.8), /(ж) = {г \ <рч(х) = 0}, и выполняется условие Слейтера.
Ненулевой вектор р назовем возможным направлением для множества <5 из точки ж, если найдется «о > 0 такое, что для всех а 6 (0, «о) точка ж + ар принадлежит <5.
Ненулевой вектор р называется направлением спуска для множества <5 из точки ж, если р возможное направление из этой точки и (с,р) < 0.
Для фиксированной точки ж 6 <3 рассмотрим вспомогательную задачу линейного программирования
Г = тш£ (4.13)
(с,р)<£ (4.14)
((р[(х),р) < £ для всех г 6 </(ж), (4-15)
| р1 |< 1, для всех / = 1,..., п. (4.16)
Условия (4.16) называются условиями нормировки. Из условий (4.16) и (4.14) следует, что целевая функция (4.13) ограничена снизу на множестве допустимых решений. Тогда из критерия разрешимости для задач линейного программирования следует, что найдется хотя бы одно оптимальное решение задачи (4.13)-(4.16). Нулевое решение р = 0,£ = 0 является допустимым решением вспомогательной задачи и, значит, £* < 0.
Предположим, что £* < 0. Тогда (с,р*) < £* < 0 и (ср[(х),р*) < £* < 0, г £ /(ж). Следовательно, р* ф 0 и для любого номера г £ /(ж) имеем
щ(х + ар*) = срг(х + ар*) - срг(х) = (ср'г(х),р*)а+
+о(а) < а(£* + о(а)/а) < 0
для всех достаточно малых а > 0. Если г ^/(ж), то есть (^г-(ж) < 0, то в силу непрерывности функции <рч неравенство <~р{{х + ар*) < 0 будет выполняться для всех достаточно малых а > 0. Поэтому найдется «о > 0 такое, что ж + ар* £ <5 Для всех а £ (0,«о), и, следовательно, вектор р* является возможным направлением для множества <5 из точки ж. Из неравенства (4.14) получим, что р* является также и направлением спуска. Следовательно,
/(ж + ар*) - /(ж) = (с,р*)а < £*а < 0.
Если £* = 0, то нельзя утверждать, что р* будет возможным направлением или направлением спуска в точке ж. Например, может оказаться, что (с,р*) = 0 или у'-(ж) = 0 для некоторого номера г £ /(ж).
В случае общей задачи нелинейнного программирования без дополнительных условий типа выпуклости равенство £* = 0 является лишь необходимым условием минимума. Для задачи выпуклого программирования (4.6)-(4.8) при выполнении условия Слейтера последнее равенство является также и достаточным условием оптимальности.
Теорема 4.4 (Критерий оптимальности) Пусть оптимальное решение вспомогательной задачи для ж* £ Q. Тогда f = 0 е том и только в том случае, когда х* — оптимальное решение задачи (4-6)-(4-8).
Доказательство. Покажем достаточность. Пусть х* — оптимальное решение задачи (4.6)-(4.8) и предположим, что £* < 0. Тогда р* ф 0. Рассмотрим вектор х* + ар* и выберем значение а = а* следующим образом.
Если г £ J(x*), то (ср[(х*), р*) < 0. Следовательно, <~pi{x* + ар*) < 0 при всех а £ (0, аг) для достаточно малого аг- > 0.
Если г ^ J(x*), то есть <~pi{x*) < 0, то в силу непрерывности функции <~pi{x) неравенство <~pi{x* + ар*) < 0 сохранится при всех а £ (0, аг) для достаточно малого аг- > 0. Положим а* = min^i^.^mlaj'}. Тогда для любого а £ (0, а*) вектор х* + ар* является допустимым решением задачи (4.6)-(4.8). Из условия (с,р*) < £* < 0 получим f(x* + ар*) < f(x*), при а £ (0,а*), что противоречит оптимальности ж*.
Докажем необходимость. Пусть ж* не является оптимальным решением задачи (4.6)-(4.8). Тогда существует ж £ Q, для которого
/(ж) - /(ж*) = (с, ж - ж*) < 0.
Пусть р = ж — ж*. Тогда (с,р) < 0. Если <~pi{x*) = 0, то есть г £ J(x*), то из следующего неравенства для гладких выпуклых функций
срг(х) > рг(х*) + (ср'г(х*),х - ж*)
получим
(rt(x*),p)<0. (4.17)
Из условия Слейтера следует существование вектора ж, для которого <pi(x) < 0, г = 1,..., т. Пусть Р=х —х*. Если г £ J(x*), то аналогично (4.17) имеем
№(х*),р)<0.
Выберем р* = р + а Р . Тогда при достаточно малом а справедливо (с,р*) < 0 и (ср[(х*), р*) < 0 для г 6 /(ж*). Отсюда непосредственно вытекает, что £* < 0. Теорема доказана.
Если в решении задачи (4.13)-(4.16) величина £* < 0
мала по абсолютной величине, то это может привести к замедлению скорости сходимости метода возможных направлений. Чтобы избежать этих трудностей, следует изменить множество номеров /(ж) в ограничении (4.15). Опишем один из таких подходов, в котором используется следующее множество номеров {г | — 8 < <~р{{х) < 0}, где 8—положительное число. Другими словами, это множество номеров ограничений задачи (4.6)-(4.8), которые в точке ж выполняются как равенства с точностью до 8 > 0.
Пусть 5о > 0 и жо € С; - некоторое начальное приближение. Допустим, что известно к —е приближение хк 6 С; и 8к > 0. Введем множества номеров
Зк = 3(хк,8к) = {г\ -8к < срг(хк) <0},
4 = {г | &(хк) = 0}. Рассмотрим следующую задачу линейного программирования:
& = гшп£ (4.18)
(с,р)<£ (4.19)
(р'1(хк),р) < £, для всех 2 £ Зк, (4.20)
| р1\\тг(1 < 1, для всех / = 1,..., п. (4-21)
Обозначим эту задачу Р(хк,Зк). Приведем описание одной итерации метода возможных направлений. Пусть (рк1^к) — оптимальное решение задачи Р(хк,Зк). Рассмотрим три случая:
1) Если ^к < —5к, то полагаем 8к+\ = 8к.
2) Если —8к < ^к < 0, то полагаем 8к+\ = 8к/2.
3) Если ^к = 0, то найдем решение (рк,^к) задачи Р(хк, «/д). При £к = 0 вектор хк согласно критерию оптимальности является
оптимальным решением задачи (4.6)-(4.8). Если же £fc < 0, то полагаем
8к+1 = 6к/2, рк =рк.
Как уже упоминалось выше, в случае ^к = 0 нельзя утверждать, что вектор рк является направлением спуска. Поэтому, решив задачу Р(хк, Jq), на основании теоремы 4.4 можно оценить оптимально или нет текущее приближение хк. Если ^к < 0, то в качестве направления спуска выбирается вектор рк.
Длина шага ак определяется по следующей схеме. Пусть oik{ -наименьший положительный корень уравнения <pi{xk + а рк) = 0. Тогда полагаем ак = min8- oik{ и
хк+г = хк + ак рк, Jk+1 = J{xk+\8k+l).
Теорема 4.5 Пусть <~pi{x) - гладкие выпуклые функции, выполнено условие Слейтера и множество Q ограничено. Тогда
1) последовательность {f(xk)} сходится к величине
f* = min^gg f(x), то есть f(xk) = (с, xk) —> f* при k —> со;
2) любая предельная точка х* последовательности {хк} есть точка минимума функции f(x) на множестве допустимых решений Q.
Доказательство. По построению последовательность {f(xk)} невозрастающая и, в виду ограниченности множества Q, существует предел / = limk f(xk) и
f(xk) - f(xk+1) ^ОприА;^ оо. (4.22)
Величина Sk на каждом шаге либо делится пополам, либо остается без изменений. Покажем, что 6 = Hindoo Sk = 0. Предположим противное, то есть 8 > 0. Тогда найдется Ко такое, что Sk = 8 и £fc < — 8 для всех к > Ко. Другими словами, начиная с номера Ко в алгоритме всегда реализуется первый случай 8к = 8. Выберем некоторую сходящуюся подпоследовательность {хк,1ркг} —т- (ж*,р*). Такая подпоследовательность существует в
виду ограниченности множества С; и условия нормировки (4.21). Пусть
,Р = /(ж*, 8) = {з | -8 < щ(х*) < 0}.
Тогда при некотором К\ > Ко для всех к{ > К\ справедливо —5 = — 5^ < ^р3{хкг) < 0 для 2 6 ■]*■ Это означает, что 3* С .]кг для достаточно больших к{. Следовательно,
(с,Рк)<Ь, < -б,
($(хк<),рк<)<£к{<-5, для 2 е Г.
Тогда из непрерывности функций ¥^(ж) следует (^(ж*),р*) < —6 для ] € 7*. С другой стороны, <р^{х*) < — 8 для 2 ^ </*• Отсюда вытекает, что существует а* > 0 такое, что <^?(ж* + а* Р*) < 0 для всех 2- С учетом непрерывности функций это означает, что ^р3\хкг -\- а* ркг) < 0 для достаточно больших &г- и всех Таким образом, отсюда следует, что акг > а*. Тогда /(хкг) — /(хк,+1) = — ак1(с,рк') > а*5 > 0, что противоречит (4.22). Следовательно, 6 = 0.
Покажем, что / = /*. Пусть ^ < Ь2 < ... < < ••• ~~ номера тех итераций, когда происходит дробление величины 8к. Из неравенств —8^ < < 0 следует, что Нт4г_>00 ^г = 0. Можно считать, что ж*г —> ж*. Пусть / = /(ж*) > /*. Тогда из критерия оптимальности следует, что существуют р*,£* < 0 такие, что
(с,Р*)<С,
(фх*),р*) < Г, для 2 е Го = {г | ¥>.■(**) = 0}-
С другой стороны, найдется а > 0 : ^(ж*) < —а для всех ^ «/р. Из непрерывной дифференцируемости функций lt,j(x) следует, что найдется номер К такой, что для всех Ь{ > К
(с,Я<Г/2, (4.23)
(фх^),р*) < Г/2, для всех 2 е Го, (4.24)
Lpj(xtl) < — <т, для всех j $ Jq. (4.25)
Кроме того, из сходимости к 0 последовательности {5к} следует неравенство —а < —8tt для достаточно больших t{. Из последнего неравенства и неравенства (4.25) имеем Jt% с Jq для всех t{ больших некоторого К\ > К. Отсюда, с учетом неравенств (4.23), (4.24) и выбора р*, получаем
(с,Я<Г/2, (^(хи),р*) < Г/2, для всех j G А ||р*|| — 1) для всех ^ = 1, • • •, и.
Таким образом,
Г < Г/2 < о,
для любого ti > К\, что противоречит сходимости последовательности {ГЛ к нулю. Следовательно,
/ = f(xl = /* = шт/(ж).
Поскольку f(xk) > /(a;fc+1), то для любой предельной точки х последовательности {хк} имеет место равенство
f(x) = f(x*).
Теорема доказана.