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*).

Теорема доказана.