Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.04.2024

Просмотров: 205

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

# 2] Градиентный метод 67

 

Д о к а з а т е л ь с т в о .

Если

при

некотором

п ^ О окажется

J'(u n) — 0, то из условий

(1),

(2)

формально получаем ип — ип+ 1—

=

, и утверждение теоремы lim/'(wn) = 0

становится

тривиаль-

 

 

 

 

 

 

 

 

П - > оо

 

 

( п = 0,

 

 

 

 

 

ным.

Поэтому

будем

считать

]'{ип) Ф 0

1,

...).

Так как

J (u n+l) = g n(a n) ^ g n ( a ) = J ( u n—а Г ( и п))

при

всех

 

0,

то

из

неравенства (1.18)

при v = un, и = и п— а Г ( и п)

имеем

 

 

 

 

J (и„) — J («„+i) >

J (ип) — J (a„—

aJ' (ип)) >

a

^ 1 —

 

|/' («„) |2

при всех а > 0

и всех п — 0,

1,

2, . . . . Следовательно:

 

 

 

 

 

J (и„) — J

(un+1) >

шах а ( 1 -----a )\ J'

(un) I2 =

 

 

 

 

 

 

 

 

 

 

 

a^O

 

\

 

2

J

 

 

 

 

 

 

 

 

 

 

= - ^ | / ' K ) l 2 >

0

(n =

0,

1 , . . . ) .

 

 

 

 

(5)

Таким

образом,

последовательность

{J («„)}

 

стррго

убывает.

Но

J (ип) ></*>-— оо,

поэтому

 

существует

lim J { u n),

и

/(«„) —

— J(un+i) - * 0 при я -> оо. Из оценки

(5)

 

л-freo

 

 

 

 

0.

тогда

имеем lim J' (ип) =

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

f W o o

 

 

 

 

Пусть теперь

/(и) -выпукла, и множество М(ио)

ограничено.

Поскольку М(и0),

кроме

того,

замкнуто в

силу

непрерывности

/ (и)

(и даже выпукло), то I(и)

достигает своей нижней грани на

М (п0),

а стало

быть,

и

на

Ет,

хотя

бы

в

одной

точке

 

 

М {и0)

: J ( u * ) = J * .

Тогда

с помощью

неравенства

(1.9)

имеем

0 <

/

Ю - / ( О < (/ '(« „ ),

 

uK- u * ) < D \ J ' ( u a)\

(п = 0 , 1 , . . . ) .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(6 )

Так

как J' (ип)-*-0,

то

отсюда

следует

'lim J

(un) = J

(и*) =

J*,

т.

е.'

последовательность

{ип}

является

 

 

П —> э о

 

 

 

Так как

(ял} 6

минимизирующей.

6 М (и0), то последовательность {пл} имеет хотя бы одну предельную

точку v* = lim

. Но J (и)

непрерывна,

поэтому Г

= lim J (ил.) =

k~> oo

 

 

 

 

 

/г—* оо

 

=«/ (к*). Если J («) достигает своего минимума в единственной точке

«*, то lim ип =

и".

 

 

 

 

 

 

П —* о о

 

 

 

 

 

 

 

Для доказательства оценки

(3) обозначим ал =

/ («,,)— /*.

Из

неравенств (5),

(6) следует

— сл+1>

1/'.(«„) |2, a„< D | / ' (ил)|,

а тогда

 

 

 

 

 

 

 

 

 

 

(п =

0,

1,2, ...)•

 

 

Так как an> 0

(если ап= 0,

то

ип — точка

минимума), то с

по­

мощью леммы 1.2 отсюда получаем оценку (3).

 

 

3*

 

 

 

 

,

 

 

68

М И Н И М И З А Ц И Я Ф У Н К Ц И И М Н О ГИ Х ПЕРЕМЕННЫХ

[Га . 2

Наконец, пусть J(u ) сильно выпукла, и по-прежнему

J (и) 6

£ С1(£ m),

J ' (и) удовлетворяет условию Липшица. Согласно

теоре­

ме 1.7 тогда сохраняют силу все предыдущие рассуждения. Докажем

оценки (4).

Из теоремы

1.6 имеем 0

 

•< —

I /' (и ) I2.

Отсюда и

 

 

 

 

 

 

 

Р

 

 

 

 

 

из оценки

(5)

вытекает

ап— а^-н >

ап, или

 

 

 

 

 

 

 

ап+\ < ( - ~ ) а п = Я ^ п (П = 0,

 

 

 

 

 

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

ап < а 0<7" (п = 0, 1, . . . ) — первая

из оценок

(4) полу­

чена. Вторая оценка (4)

непосредственно следует из

первой

и нера­

венства

(1.15).

Остается

заметить,

что

0 < < 7 = 1

Л .

<

1, ибо

р. < L (см. замечание к теореме 1.5). А

 

 

2L

 

 

 

 

 

 

 

 

Для

функций /(ы) е С 1 (£,„)

описанный

метод

скорейшего

спуска при т = 2 имеет простой геометрический смысл:

оказывает­

ся, точка ип+1, определяемая условиями

(1),

(2),

лежит

на луче

и ( а ) = и п— aJ'(u n) (а ^ О )

в точке

его

касания

линии

 

уровня

Гп+1 = {м : /(и)

= / (« n+i)}.

Это вытекает из следующих двух факто­

ров: 1) градиент функции в фиксированной точке v всегда перпен­

дикулярен линии уровня Г (о) = {и : J (и) = J (v)}

в точке v. В самом

деле, если u — u{t) некоторое параметрическое

уравнение линии

уровня Г(и), то J ( u ( t ) ) = / ( о ) = co n st. Поэтому

 

=

и ( 0 ) = о ,

at

 

 

т. е. градиент в каждой точке Г (и) перпендикулярен касательному направлению к Г (о) в этой точке; 2) направление J' (ип) является касательным к линии уровня Гп+ь что в силу предыдущего равно­ сильно равенству (J'(un), J'(un+1 ))= 0 . Последнее следует из усло­ вия (2) и формулы (1.4)

g'a (« л )

=

— W (“ л ). J' («л-н)) = 0

при а п> 0.

Из рис. 7,

8

видно, что чем ближе линия уровня /(■«)= const

к окружности,

тем

быстрее сходится метод

скорейшего спуска.

Р и с. 7

Р и с. 8

§ 2}

Градиентный метод

69

 

В тех случаях, когда поверхности уровня сильно вытянуты, то

этот метод может сходиться очень медленно. Приемы

ускорения

сходимости в таких случаях будут обсуждены ниже, в п. 4.

2. Известны и другие способы выбора величины а„ в формуле

(1). Простейшим

из них является выбор

an = cc= const. При этом

на каждом шаге

проверяется

условие

монотонности: J (ип+1) <

< J ( u n). Если оно нарушается,

то а дробится до тех пор, пока не

восстановится монотонность; время от времени полезно пробовать увеличить а с сохранением монотонности.

В тех случаях,

когда заранее известна величина,

J* =

inf J (и),

 

 

 

 

 

 

 

 

и£Ет

то в равенстве (1)

можно взять

a n= [ J ( u n) — /*]|/'(ггп) )-2—это

абсцисса точки пересечения прямой / = /*

и касательной к кривой'

J= g n {a )

в точке

(£ п (0),'0)

плоскости (/,

а ). Еще

два

способа

выбора

а„

можно

получить

из

методов, описанных

в §

3, 5

при

U= Em.

 

 

 

 

а п выбран, то итерации

 

 

3. Если

способ определения

(1)

про­

должают до выполнения тех или иных критериев окончания счета.

На практике часто

используются критерии

|ип+1— «п | ^ е, или

|/(«n+i) — /(ыэт)| ^ е ,

или |/'(ып)|<Св и другие;

возможны сочета­

ния различных критериев. Разумеется, к этим критериям надо от­ носиться критически, ибо они могут выполняться и вдали от иско­ мого минимума.

Следует заметить также, что вблизи точки минимума градиент J ' (ип) близок к нулю, и метод (1) становится слишком чувстви­ тельным к выбору а п, отыскание более точных приближений точки

минимума и*

затрудняется, так как расстояние

|ип— и* | пере­

стает уменьшаться.

Поэтому вблизи

точки

и* целесообразно

использование

других,

более

тонких методов, опирающихся на

квадратичную

аппроксимацию

функции

в окрестности каждого

приближения

(см. § 7,

8).

 

 

 

4. Как уже отмечалось, метод скорейшего спуска и другие , варианты градиентного метода медленно сходятся в тех случаях, когда поверхности уровня функции J (и) сильно вытянуты и функ­ ция имеет так называемый «овражный» характер. Это означает, что небольшое изменение некоторых переменных приводит к рез­ кому изменению значений функции — эта группа переменных характеризует «склон оврага», а по остальным переменным, за ­ дающим направление «дна оврага», функция меняется незначи­ тельно (на рис. 9 изображены линии уровня «овражной» функции двух переменных). Если точка лежит на «склоне оврага», то на­ правление спуска из этой точки будет почти перпендикулярным к

направлению

«дна оврага», и в результате приближения {ип},

получаемые

градиентным методом, будут поочередно находиться

то на одном,

то на другом «склоне оврага». Если «склоны оврага»

70

М И Н И М И З А Ц И Я Ф У Н К Ц И И М Н О ГИ Х П ЕРЕМЕННЫ Х

[Гл. 2

достаточно круты, то такие скачки «со склона на склон» точек ип могут сильно замедлить сходимость градиентного метода.

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

В начале поиска задаются две точки й0, й\, из которых произ­ водят спуск с помощью какого-либо варианта градиентного мето­ да и получают две точки и0, щ на «дне оврага». Пусть, например, /(«[) </ («„). Тогда полагают

где h — положительная постоянная, называемая овражным шагом. Из точки «2, которая, вообще говоря, находится на «склоне овра­ га», производят спуск с помощью градиентного метода и опреде­

ляют следующую точку и2 на «дне

оврага». Если уже известны

точки «о. иь ..., ип ( д ^ 2 )

и J {ип)

то из точки

Un+ 1 =

ип

ип- 1 ^

и п - f

ип - 1 I

 

I и п

совершают спуск с помощью градиентного метода и находят следующую точку ип+1 на «дне оврага» (см. рис. 9; спуск из точки й„ в точку и„, состоящий, быть может, из нескольких итерацион­ ных шагов градиентного метода, на рис. 9 условно изображен от­ резком прямой, соединяющей точки йп, ип, п — 0, 1-, ...).

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

§ 2} Градиентный метод 71

висит скорость сходимости метода. Если, шаг h велик, то на кру-^ тых повоторах «оврага» точки йп могут слишком удаляться от «дна оврага» и спуск из точки йп в точку ип может потребовать большого объема вычислений. Кроме того, при больших h на кру­ тых поворотах может произойти выброс точки йп из «оврага» и правильное направление поиска точки минимума будет потеряно. Если шаг слишком мал, то поиск может очень замедлиться и эффект от применения овражного метода может стать незначи­ тельным.

Эффективность овражного метода может существенно возрас­ ти, если величину овражного шага выбирать переменной, реаги­ рующей на повороты «оврага» с тем, чтобы: 1) по возможности

быстрее

проходить

прямолинейные

участки на «дне

оврага» за

счет увеличения овражного шага; 2)

на крутых поворотах «оврага»

избежать

выброса

из «оврага» за

счет уменьшения

овражного

шага; 3) добиться по возможности меньшего отклонения точек йп от «дна оврага» и тем самым сократить объем вычислений, тре­ буемый на градиентный спуск из точки йп в точку ип, п = 0, 1, 2 ,....

Интуитивно ясно, что для правильной реакции на поворот «оврага» надо учитывать «кривизну дна оврага», причем информацию о «кривизне» желательно получить, опираясь на результаты преды­

дущих итераций овражного метода.

 

 

 

 

В работе

[211]

предлагается

следующий

способ

выбора

овражного шага:

 

 

 

 

 

 

 

hn+l =

К ■с ^ п - ^ п - г ,

п =

2, 3, . . . ,

(7)

где а п— угол

между

векторами ип— ип-\,

ип — ип-\, т. е.

 

 

cos а п =

п~

~ LLn~l) ■,

 

 

 

 

 

I иП иП-1 I I

 

4/I-J |

 

 

постоянная с > 1 является

параметром

алгоритма.

Точка u„+i тогда

определяется так:

 

 

 

 

 

 

ип+ 1 =

ип

 

•hn+i (при I (u„) < / (u„_i)) .

 

 

\иП~ И/1-ll

 

 

 

 

* Разность

cos а п— cos an_i в равенстве (7) связана с «кривизной

дна оврага», и, кроме того,

обладает важным свойством указывать

направление изменения «кривизны». А

именно при переходе с участ­

ков «дна оврага» с малой «кривизной» на участки с большей

«кривиз­

ной» будем иметь cos а п— cos an_ i< 0 (см. рис. 10). Тогда в силу соот­ ношения (7) /in+i</i„, т. е. овражный шаг уменьшается, приспосабли­ ваясь к повороту «дна оврага», что, в свою очередь, приводит к уменьшению выбросов точки -йп+\ на «склоны оврага». При пере­ ходе с участков «дна оврага» с большей «кривизной» на участки

Смотрите также файлы