Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 82
Текст из файла (страница 82)
Положим ! Чг'сгг У=(е, сг), е = е/8е)(! сг = с/Зе8. Ясно, что г Е Иг. Следовательно, (а, г) = (д, г)/()е)! = о- = с/8 ей > О, так что (с(, г) = о > О. Зем самым показано, что неравенство (10) верно для всех г Е К. о теореме Фаркаша 3.5.8 тогда существуют неотрицательные, числа ..., Л* такие, что О = -Л;/ (х„) - ~„ Л,*.д/(х,), 1 = Л," + У; Л;. (11) сог, сог, Кроме того, из определения множества 1, следует, что дс(х.) = О, поэтому Л,*.дс(х) =О, 4 Е 1,. Доопределим Л;.
=0 при всех о ф Е„. В результате с учетом первого равенства (11) получим Ло/'(х,)+ 2; Л,*д,.'(х.) =О, Л,*дс(х,) =О, 4 = 1,..., гп, (12) с=! а из второго равенства (11) следует, что Л = (Л*, Л,*,..., Л* ) ф О. Покажем, что Л*) О. Если Е„=И, то из (11) сразу имеем Ло = 1. Допустим, что 1, ~ !сг, но тем не менее Л; = О. Тогда среди неотрицательных чисел Л,*., 274 Гл.
5, МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ » е 1„, найдется хотя бы одно положительное число. Пусть Л„" > О, р е 1,. По условию существует точка х е Х такая, что дг(х) < 0 для всех з = 1,... ..., ги, Поскольку 1„ф О, то х ф х,. В силу выпуклости множества Х тогда сх х + (1 — ст)х„= х„+ сг(х, — х,) й Х при всех ст, 0 < сх < 1. Это значит, что направление е = х — х, ф 0 является возможным для множества Х в точке х„. Из выпуклости функций д,. (х) для всех «е 1„имеем 0 > д«(х) = = дг(х) — д,(х„) > (д,'(х,), х — х,) = (д,.'(х,), е). Поэтому 2' Л,*.(д,'(х,), е) < '=! < Л*„(д,'(х,), е) < О. Но с другой стороны, из первого равенства (12) при е Л* = 0 получим )" Л;.(д,'(х.), е) =О.
Полученное противоречие показывает, =! что Л" > О. Разделив первое равенство (12) на Л' > 0 и сделав очевидные о ы переобозначения, придем к равенству /'(х,)+ 2 Л,*.д,(х„) = О. Отсюда и из з=! второго равенства (12) с помощью леммы 4.9,2 и теоремы 4.9.1 получим, что х, е Х,, Теорема 1 доказана.(3 В невыпуклых задачах условие а, =0 не является достаточным для оптимальности точки х„.
Это показывает следующий Пример 1. Пусть 1(и) = х+ соз д, и е Х = (и = (х, д) е.Ез! д(и) = = — х < О). Возьмем точку и„=(0, 0). Тогда /'(и,) =(1, 0), д'(и,) =( — 1, 0), И"„= ((е, гг) = (е ', ее, сг): е ' ( гг, — е ' ( а, (е ' ! < 1, )ее! ( 1). Отсюда )е' ! ( сг при всех (е, гт) я Иг,. Это значит, что 1п( а = а„=О, причем нижняя грань достигается при е„= (О, 1) или е, = (О, — 1), гг„= О.
Но здесь и„=(0, 0) не является точкой минимума /(и) на Х. Любопытно заметить, что векторы е„= (О, 1) или (О, — 1) в данном случае являются возможными направлениями убывания. 2. Описанный выше вариант метода возможных направлений (2)ш(4) на практике применяют редко. Дело и том, что когда в решении (е„, г?„) задачи (2) координата аь (0 мала по абсолютной величине, направление е„ теоретически являясь возможным направлением убывания в точке х„, практически может обладать указанными свойствами в весьма слабой форме. Это означает, что либо (д,'(х,), е„) яе а =0 при некотором «' е 1„и направление е почти «касается» мйожества Х, не ведет «вглубь» Х, а величина )3» из (4) может оказаться очень малой, либо (/'(хь), е„) гм а, -О, т.
е. вдоль еь функция /(х) в точке х, убывает слишком медленно. В результате длина шага схь в (3) может получиться очень малой даже'вдали от стационарной точки, й сходимость метода может оказаться очень медленной. Чтобы избежать таких неприятных явлений, можно попытаться варьировать множество номеров 1, в (2) и осуществлять спуск из точки х„только в том случае, когда получаемое из (2) направление е обладает достаточно ярко выраженными свойствами возможного направления убывания.
Опишем один из таких подходов. Пусть х е Х, в, > 0 — некоторое начальное приближение. Допустим, что к-е приближенйе (х„е„), хь ~ Х, е > О, при каком-то гс > 0 уже известно. Определим множество йомеров 1„= Т«! 1 < «< т, — еь (~ дз(хь) ( О) (13) и решим вспомогательную задачу (2) при таком 1„. Задача (2) по-прежнему будет задачей линейного программирования и будет обладать хотя бы одним решением (е„, ггь) с аь = (п( и < О. Имеются две возможности: и'ь ,ргп ' *! 13 1(х), д!(х), ..
ч д (х) с С! '(Х), Ао — — гпах зир )д,".(х)! < оо, «Х а последовательности (х»), (еь), (оз), (Дь), (гь), (оь) определены условиями (2), (3), (6), (! 3)-(15), Тогда Рь ) А! ю1п(гь,)оь!), А =0,1,..., (17) где А! — — ю1п(1/(Лоеги)11/(пЬ)) > О, 1 — константа Липшица для градиентое 1 (х), д!'(*), , д '( ) 4 5. МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ 275 ! ,л-г, 1) ое < -е„. В этом случае считаем, что ея является достаточно хорошим возможным направлением убывания в точке х„и полагаем хь ! — — хь+сгьеь, 0<сг <)Уь, еьь,=е, (14) где )3» определяется из (4), а выбор сг может быть осуществлен одним из описанных выше способов.
2) — ед < аь < О. В этом случае считаем, что направление еь не обладает ясно выраженным свойством возможного направления убыванйя в точке хь, полагаем х„, = х„, еь„! = е /2 (15) и снова переходим к рассмотрению задачи (2) с заменой множества 1, на множество 1», — — («: 1 < з < т,/, — е, = — е„/2 < дз(х„) < О), надеясь на то, что на более широком множестве (при сужении 1, множество Игь, вообще говоря, расширяется) удастся найти лучшее возможное направление убывания и т. д. Описание одной итерации метода возможных направлений для задачи (1) закончено.
В методе (2), (13)-(15) имеются параметры ео, е„..., удачным выбором которых, вообще говоря, можно улучшить выбор направлений еь на каждой итерации, ускорить сходимость метода. Кстати, в (15) вместо деления пополам можно принять иной способ дробления ею например, е„, =0,9е,. 3. Следуя [3?41, изучим сходимость метода (2), (3), (6), (13) — (15). Предварительно докажем несколько лемм. Лемма !. Пусть Пх), у,.(х) с С ' (Х), ! =1,, т, и 1 — некоторое фиксированное мноасестео номеров, взятых из (1, 2,, .
ч т) (еозмохсности 1 = ю или 1 = (1,..., т) не исключаю!пел) Для каждого х С Х полоз«им о(х) = тю а, где С(х) = ((е, о) = (е!,... о! 1 ..., е, а) с Ь~э'! (1(х), е)< а, (д,.'(х), е) < о, ! е 1; !ег! < 1, 1 = 1, .. ч п). Тогда )гг(и) — о(е)! < Ь |и!и — е), и, е С Х, (!6) где Ь вЂ” константа Липшица для градиенгпое 1'(х), д,'(е), ! = 1, ..
ч т, Доказательство. Возьмем произвольные тачки и, е е Х. Пусть (е, а) с С(е), т, е. (1(е),е)<о, (д (е),е)<о, «61, е! <1, 1=1,... п. ! Тогда (1г(и), е) = (уг(е), е) -1- (1 (и) — 1 (е), е) < о+ о)и — е)!е! < о+ 5)и — е)еги "1!!','." и, аналогично, (д, (и), е) < о«-1)и — е)еги, ! с 1. Это значит, что при каждом (е, о) с С(е) точка (е, о+ Ь его!и — е!) принадлежит множеству С(и). Тогда и(и) = т!п а < о + Ь еги!и — е! для любых (е, о) с С(е). Следовательно, о(и) < о! 1 <о(е)+Ьехй)и — е!. ПаменЯЯ в этих РассУждениех точки и е РолЯми, полУчим о(е) < о(и)+ + ь ьги)и — е!.
из последних двух неравенств следует неравенство (16). Г> Лемма 2. Пусть 6 5. МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ 277 276 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ (18) /(х„) — /(х. „() > Аэ в(п(дй (ай (; ай) — бй, Согласно лемме ! при С(хй ) = Игй имеем (21) Ив (/(хй) — /(хй „()) =0 (22) Доказательство. Если /Уй —— со, то неравенство (17) верна. Поэтому пусть /)й <оо. Из определения (4) величины /Уй и замкнутости Х следует, что хй Ч Дй ей Е Х и д (хй ч /Уй ей) = 0 хотя бы для одного номера с. Зафиксируем один из таких номеров с.
Может оказаться, что ду(хй) <-г„. Тогда г <-д(х ) =д(хй+/(йей)-дс(хй)= (д,.'(хй+д/Уйей),/Уйей) < Ао/Уй(ей! < ( Ась(п)уй, т. е. Дй ) гй/(Аочгп) Если же оказалось, что -гй < д (хй) < О, то с е 1» и (ду(хй), е») ( ай < О, Допустим, что ай < < О. Тогда направление ей является возможным в точке хй и заведомо Дй > О. По определению /Уй имеем д (ай + ией) < 0 при всех и, 0 < и (/)й. Кроме того, д (ха+ /У»ей) = 0 по выбору номера с. Тогда 0 > дэ(хй + ией) — д,.(хй Ч-/)йей) = (д/(хй + Дйей), ей)(и — /Уй)+ а((и — (Уй!) или (ду(хй + /Уйей), ей) > а((и — )Уй!)(/Уй — и) ' при всех и, 0 < и < дй. О~сюда при и -» -» д — 0 получим (дг (х, + /)й ей ), гй ) > О. Тогда (ай ! = — ай < ( — д, (хй ), ей ) < (д, (хй + /Уй ай)— — ду(хй), е,) < Ьдй(е ! < Ьп)уй, т, е.
/У ) (ай(/(п5). Если ай — — О, то последнее неравенство также остается верным, так как согласно (4) всегда Дй ) О. Объединяя абе полученные оценки для (Уй, приходим к оценке (17). Лемма 2 доказана. П Лемма 3. Пусть /(х), д;(х) е СЦ'(Х), с =1,...,т. Пусть, кроме того, з процессе (2), (3), (6), (13)-(15) на некоторой й-й итерации оказалось ай < — ей. Тогда где Аэ — — ппп( 1 /2; 1 /(2пб )) > О. Доказательство, Из неравенства ай ( -гй и определения ей, ай следует, что (/'(хй), ей) < ай < — гй < О. Кроме того, ей является возможным направлением в точке хй и, следовательно, )Уй > О.
Из (6) и леммы 2.6.! имеем /(*й) — /(х.,) >/(х„) — (и( д„(и) — бй > Х(хй) — /(хй+ ией) — бй > а ( о < д» > — и(/'(х„), ей) — иэЬ»!ей(~/2 — бй В )— иай — сс с»/2 — бй (!9) при всех и, 0 < сс < /Уй. Положим здесь и = в(п((3й,((ай(/(и| )). Может случиться, что и = /Уй < (ай(/(пЬ). Тогда иэ (!9) получаем /(хй ) — /(хйй»))и (ай ! — и и ' п1/2 — бй ) Дй (ай ! /Уй((ай(/(пЬ ))(пЬ/2) ба =)Уй (ай (/2 — бй Если же и = (и»(/(пб ) < у„то из (19) следует /(хй) — /(ха+ () Р )ай/(п5) — (ай/(п5 ) )(г»1/2) — бй — — ай/(2пб ) — бй Объединяя оба рассмотренных случая, приходим к оценке (18).О Теорема 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
