1612726855-66ce2678ed92310585f0bb1a36623206 (828576), страница 13
Текст из файла (страница 13)
Выберемвозможное направление движения, то есть такой ненулевой вектор, что1. малое перемещение в этом направлении не выводит за пределы множества допустимых решений;2. целевая функция строго убывает в этом направлении.Затем осуществляется перемещение в выбранном направлении до получениянового допустимого решения с лучшим значением целевой функции.
Представленный ниже алгоритм был разработан голландским математиком Зойтендейком [2, 3, 6], который предложил выбирать направление спуска из пересечения конусов возможных направлений и направлений убывания целевойфункции. Особенность метода заключается в учете нелинейности ограничений и в сравнении направлений не только по локальной скорости убыванияцелевой функции, но и по длинам шагов, которые удастся сделать вдоль них.Представленный ниже алгоритм предназначается для поиска экстремумапри наличии ограничений только типа неравенств. Рассмотрим задачуmin f ( x )(1)ji ( x) £ 0 , i = 1,..., m ,(2)x Î Rn ,69(3)где f (x ) , ji (x) , i = 1,..., m , – гладкие выпуклые функции. Вводя дополнительные переменную и ограничение, функционал задачи можно сделать линейным:min yf ( x) £ y ,ji ( x) £ 0 , i = 1,..., m ,x Î Rn .Поэтому без ограничения общности будем считать, что f ( x ) = c, x .
Пусть,как и прежде, Q = {x ji ( x ) £ 0, i = 1,..., m} – множество допустимых решенийзадачи (1)-(3). Обозначим через I ( x ) = {i j i ( x ) = 0, i = 1,..., m} множество ограничений активных в точке x.Предположим, что выполняется условие Слейтера [2, 3, 6], то есть существует точка ~x ) < 0 , i = 1,..., m .x такая, что ji ( ~Ненулевой вектор p назовем возможным направлением для множества Qиз точки x , если найдется a 0 > 0 такое, что для всех a Î (0, a 0 ) точка( x + ap ) принадлежит Q .Ненулевой вектор p является направлением спуска для множества Q източки x , если p – возможное направление из этой точки и c, p < 0 .Для фиксированной точки x Î Q рассмотрим вспомогательную задачу линейного программированияx * = min x(4)c, p £ x ,(5)ji¢ ( x), p £ x , i Î I (x ) ,(6)pl £ 1 , l = 1,..., n .(7)Условия (7) называются условиями нормировки.
Нулевое решениеp = 0, x = 0 является допустимым решением вспомогательной задачи и, зна-чит, x * £ 0 . Из условий (5) и (7) следует, что целевая функция (4) ограниченаснизу на множестве допустимых решений. Тогда из критерия разрешимостидля задач линейного программирования (теорема 3.2) следует, что найдетсяхотя бы одно оптимальное решение ( p*, x * ) задачи (4)-(7).Предположим, что x * < 0 . Тогдаc, p * £ x * < 0 иji¢ ( x ), p* £ x * < 0 ,i Î I (x ) . Следовательно, p* ¹ 0 и для любого i Î I (x ) имеемji ( x + ap* ) = ji ( x + ap* ) - ji ( x ) = ji¢ ( x ), p* a + o(a ) £ a (x * + o(a ) a ) < 0для всех достаточно малых a > 0 .
Если i Ï I (x ) , то есть j i ( x ) < 0 , то в силунепрерывности функции j i неравенство ji ( x + ap* ) < 0 будет выполняться70для всех достаточно малых a > 0 . Поэтому найдется a 0 > 0 такое, что( x + ap* ) Î Q для всех a Î (0, a 0 ) , и, следовательно, вектор p* является возможным направлением для множества Q из точки x . Из неравенства (5) получим, что p* является также и направлением спуска. Следовательно,f ( x + ap* ) - f ( x ) = c, p* a £ x *a < 0 .Если x * = 0 , то нельзя утверждать, что p* будет возможным направлением или направлением спуска в точке x .
Например, может оказаться, чтоc, p* = 0 или ji¢ ( x ) = 0 для некоторого i Î I (x ) .В случае общей задачи нелинейного программирования без дополнительных условий типа выпуклости равенство x * = 0 является лишь необходимымусловием минимума. Для задачи выпуклого программирования (1)-(3) привыполнении условия Слейтера последнее равенство является также и достаточным условием оптимальности.Теорема 1 (критерий оптимальности). Пусть ( p* , x * ) – оптимальноерешение вспомогательной задачи для x* Î Q . Тогда x * = 0 , если и толькоесли, x* является оптимальным решением задачи (1)-(3).Доказательство. Покажем достаточность.
Пусть x* – оптимальное решение вспомогательной задачи (4)-(6). Предположим, что x * < 0 , тогда p* ¹ 0 .Рассмотрим вектор ( x* + ap* ) и выберем значение a = a * следующим образом. Если i Î I ( x* ) , то ji¢ ( x* ), p* < 0 . Следовательно, ji ( x* + ap* ) < 0 привсех a Î (0, a i ) для достаточно малого a i > 0 .Если i Ï I ( x* ) , то есть ji ( x* ) < 0 , то в силу непрерывности функцииji (x ) неравенство ji ( x* + ap* ) < 0 будет справедливо при всех a Î (0, ai )для достаточно малого a i > 0 . Положим a * = min {ai } . Тогда для любогоi = 1,..., ma Î ( 0, a * )вектор( x*+ ap* )Из условияc, p *£ x*является допустимым решением задачи (1)-(3).< 0 получим f ( x* + ap* ) < f ( x* ) при a Î ( 0, a * ) , чтопротиворечит оптимальности x* .Докажем необходимость.
Пусть x* не является оптимальным решениемзадачи (1)-(3). Тогда существует x Î Q , для которогоf ( x ) - f ( x* ) = c, x - x* < 0 .71Пусть p = x - x* . Тогда c, p < 0 . Если ограничение ji активно в точке x* ,то ji ( x* ) = 0 . Тогда из неравенства для гладких выпуклых функций теоремы1.4 имеемj i ( x ) ³ j i ( x* ) + j i ' ( x* ), x - x *и допустимости вектора x получимji¢ ( x* ), p £ 0 .(8)Из условия Слейтера следует существование вектора ~x , для которого~~~**ji ( x ) < 0 , i = 1,..., m . Пусть p = x - x . Если i Î I ( x ) , то аналогично (8)имеемji¢ ( x* ), ~p < 0.Выберем p* = p + a~p . Тогда при достаточно малом a справедливоc, p* < 0 и ji¢ ( x* ), p* < 0 для i Î I ( x* ) .
Отсюда непосредственно вытекает, что x * < 0 . ▄Если в решении ( p* , x * ) задачи (4)-(7) величина x * < 0 мала по абсолютной величине, то это может привести к замедлению скорости сходимости метода возможных направлений. Чтобы избежать этого, следует изменить множество номеров I (x ) в ограничении (6). Опишем один из таких подходов, вкотором используется множество номеров {i - d < ji ( x ) £ 0, i = 1,K, m} , гдеd – положительное число. Другими словами, это множество номеров ограничений задачи (1)-(3), которые в точке x выполняются как равенства с точностью до d > 0 .Приведем описание этой модификации метода возможных направлений.Пусть d 0 > 0 и x 0 Î Q – некоторое начальное приближение.
Допустим,что известно k -ое приближение x k Î Q и d k > 0 . Введем множества номеровI k = I ( x k , d k ) = {i - d k < j i ( x k ) £ 0, i = 1,K, m} , k = 0,1,K,I 0k = {i j i ( x k ) = 0, i = 1,K, m} , k = 0,1,K .Рассмотрим следующую задачу линейного программирования:x k = min xc, p £ x ,j ¢j ( x k ), p £ x , j Î I k ,pl £ 1 , l = 1,..., n .72Обозначим эту задачу P( x k , I k ) .
Приведем описание одной итерации метода возможных направлений. Пусть ( pk , x k ) – оптимальное решение задачиP( x k , I k ) . Рассмотрим три случая:1. Если x k £ -d k , то полагаем d k +1 = d k .2. Если - d k < x k < 0 , то полагаем d k +1 = d k 2 .3. Если x k = 0 , то найдем решение ( p k , x k ) задачи P( x k , I 0k ) . При x k = 0вектор x k согласно критерию оптимальности является оптимальным решением задачи (1)-(3). Если же x k < 0 , то полагаемd k +1 = d k 2 , pk = pk .Как уже упоминалось выше, в случае x k = 0 нельзя утверждать, что вектор pk является направлением спуска. Поэтому, решив задачу P( x k , I 0k ) , наосновании критерия оптимальности можно оценить является ли оптимальным текущее приближение x k . Если x k < 0 , то в качестве направления спуска выбирается вектор pk .Длина шага a k определяется по следующей схеме.
Пусть a k i – наименьший положительный корень уравнения j i ( x k + apk ) = 0 . Тогда полагаемa k = min a ki иix k +1 = x k + a k pk , I k +1 = I ( x k +1, d k +1 ) .Теорема 2. Пусть ji (x) , i = 1, K , m , – гладкие выпуклые функции, выполнено условие Слейтера и множество Q ограничено. Тогда1. последовательность { f ( x k )}k ÎN сходится к величине f * = min f ( x ) , тоxÎQестьf ( xk ) =c, x k®f*при k ® ¥ ;2. любая предельная точка x* последовательности {x k }k ÎN есть точкаминимума функции f (x ) на множестве допустимых решений Q .Доказательство.
По построению последовательность { f ( x k )}k ÎN невозрастающая, множество Q ограниченное, тогда существует пределfˆ= lim f ( x k ) иk ®¥f ( x k ) - f ( x k +1 ) ® 0 при k ® ¥ .73(9)Величина d k на каждом шаге либо делится пополам, либо остается безизменения. Покажем, что d = lim d k = 0 . Предположим противное, то естьk ®¥d > 0 . Тогда найдется K 0 такое, что d k = d и x k £ -d для всех k > K0 .
Другими словами, начиная с номера K 0 в алгоритме всегда реализуется первыйслучай d k = d . Выберем некоторую сходящуюся подпоследовательность{x k j , pk j } jÎN ® ( x * , p* ) . Такая подпоследовательность существует в видуограниченности множества Q и условия нормировки (7). ПустьI * = I ( x* , d ) = {i - d < j i ( x* ) £ 0, i = 1,K, m} .ТогдаприK1 > K 0некотором- d = -d k j < j i ( xkjдлявсехk j > K1справедливо) £ 0 для i Î I * .
Это означает, что I * Í I k j для достаточнобольших k j . Следовательно,c, pk j £ x k j £ -d ,kji¢ ( x j ), pk j £ x k j £ -d , i Î I * .Тогда из непрерывности функций ji¢ ( x ) следует, что ji¢ ( x * ), p* £ -d дляi Î I * . С другой стороны, ji ( x* ) £ -d для i Ï I * . Отсюда вытекает, что существует a * > 0 такое, что j i ( x* + a * p* ) < 0 для i Ï I * . С учетом непрерывно-сти функций ji , i Î I , это означает, что j i ( xбольшихf (xkjиkj) - f (xiÎI .Такимkj+ a * pk j ) < 0 для достаточнообразом,ak j > a * .Тогдаk j +1) -a k j c, pk j > a *d > 0 , что противоречит (9).
Следова=тельно, d = 0 .Покажем, что fˆ = f * . Пусть t1 < t2 < K < t j < K – номера итераций, на которых происходит дробление величины d k . Из неравенств - d t j < xt j £ 0 следует, чтоlim xt j = 0 . Можно считать, что x t j ® x * при t j ® ¥ .
Пустьt j ®¥fˆ = f ( x* ) > f * . Тогда из критерия оптимальности следует, что существуютp* , x * , где x * < 0 такие, чтоc, p * £ x * ,ji¢ ( x* ), p* £ x * , i Î I 0* = {i | ji ( x* ) = 0, i = 1,K, m} .74С другой стороны, найдется s > 0 такое, что ji ( x* ) < -s для i Ï I 0* . Изнепрерывной дифференцируемости функций ji ( x ) , i = 1,K , m , следует, чтонайдется номер K такой, что для всех t j > K справедливы следующие неравенства:c, p * < x * / 2 ,(10)ji¢ ( x t j ), p* < x * / 2 , i Î I 0* ,(11)tji ( x j ) < -s , i Ï I 0* .(12)Поскольку d k ® 0 при k ® ¥ , то - s £ -d t j для достаточно больших t j .Из последнего неравенства и (12) имеем I t j Í I 0* для всех t j больших некоторого K1 > K . Отсюда, с учетом (10), (11) и выбора p* , получаемc, p * < x * / 2 ,tji¢ ( x t j ), p* < x * / 2 , i Î I j ,pl* £ 1, l = 1, K , n.Таким образом,xt j < x * / 2 < 0для любого t j > K1 , что противоречит сходимости последовательности{xt j } jÎN к нулю.Следовательно,fˆ = f ( x* ) = f * = min f ( x ) .xÎQkПоскольку f ( x ) > f ( xk +1) , то для любой предельной точки x последова-тельности {x k }k ÎN имеет место равенство f ( x ) = f ( x* ) .▄§ 2.
Метод Келли или метод секущих плоскостейДанный метод используется для решения задач выпуклого программирования вида (1)-(3). По-прежнему предполагается, что f , j i Î C 1 , i = 1,K , m .Как и в §1 без ограничения общности считаем, что f ( x ) = ( c, x ) , и далее ограничимся изучением выпуклых задач вида:(c, x) =nåcjxjj =175® minj i ( x ) £ 0, i = 1,K, m .Пусть в задаче существует оптимальное решение x* , и множество допустимых решений задачи Q содержится в многогранном множествеQ 0 = {x Î R n | Ax = b, x ³ 0} . Приведем описание k-ой итерации метода Келли, где k = 0, 1, 2, ...Итерация k .1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
