Файл: Методы оптимизации в статистических задачах управления..pdf

диентном методе даже несколько выше, так как имеет место не­ равенство

Однако в тех случаях, когда отсутствует априорная информация относительно минимизируемой функции F (х), метод наискорей­ шего спуска может оказаться предпочтительным, так как он га­ рантирует всегда ту же скорость сходимости, что и простой гра­ диентный метод с оптимальным выбором шага а°, зависящего от параметров т и М.

2. Практическая реализация градиентных методов

Как было отмечено в предыдущем параграфе, скорость сходи­ мости градиентных методов при минимизации квадратичной функ­ ции определяется значением коэффициента обусловленности ма­ трицы вторых производных Q. Если рассмотреть случай функции двух переменных (п = 2), то геометрическое изображение линий уровня минимизируемой функции имеет вид эллипсов. Причем эллипсы оказываются тем более вытянутыми, чем больше коэффи­ циент обусловленности матрицы Q. Поверхность, изображающая функцию такого типа, имеет вид оврага. При практическом при­

менении градиентного метода к подобным функциям точка х‘ до­ статочно быстро спускается на дно оврага. Причем в процессе этого спуска траектория движения имеет прямолинейный харак­ тер, а значение функции достаточно резко убывает. При дости­ жении дна оврага траектория движения приобретает вид «зигзага» (рис. 33). Значение функции при этом убывает очень мед­ ленно.

Если коэффициент обусловленности матрицы Q близок к еди­ нице, то линии уровня имеют вид окружности, и градиентный метод быстро сходится к точке минимума О (рис. 34).

95

Как показывает теоретическое и экспериментальное исследо­ вание, это свойство квадратичных функций остается справедливым и для общего класса функций. В случае многомерного простран­ ства, если поверхности уровня функции близки к гиперсфере, то градиентный метод имеет быструю сходимость. Если поверхности уровня имеют вид вытянутых эллипсоидов (функции овражного типа), скорость сходимости градиентного метода резко умень­ шается. Учитывая это, естественно постараться изменить систему координат таким образом, чтобы уменьшить степень вытянутости гиперповерхностей уровня функции. Эта идея используется в гра­ диентном методе с подбором масштабов [78, 79]. Рассмотрим конк­ ретные случаи реализации градиентного метода.

Градиентный метод с подбором масштабов. Предлагается осу­ ществлять минимизацию исходной функции F (х) в пространстве переменных z — (zlt z2, . . ., zn), связанных с х соотношением

zi = Уіхі> і = К 2, . . ., n,

где параметр у( определяется выражением

В качестве s рационально выбирать точку, «подозреваемую» на экстремум. Заметим, что для квадратичной функции значение 7 , не зависит от s. При таком преобразовании поверхности уровня функции

F (х) = £ г, (хі — Ь;)\ rt > О

I- 1

преобразуются в гиперсферы. Для минимизируемой функции об­ щего вида степень вытянутости (значение коэффициента обуслов­ ленности матрицы вторых производных) уменьшится, а поэтому скорость сходимости градиентного метода возрастет.

В старых координатах х градиентный метод будет иметь вид

Практически оказывается рациональным перед осуществле­ нием градиентного метода производить покоординатную оптими­ зацию, при которой последующее приближение получается из предыдущего варьированием одной из компонент векторной пере­ менной X при фиксированном значении всех остальных компонент. Затем по очереди варьируются все остальные координаты. В про­ цессе осуществления покоординатной оптимизации по трем заме­ рам функции в окрестности точки минимума удобно получать

оценки второй производной — &= 1, 2, . . ., п. Покоординат­ ной

96

ная оптимизация осуществляется до стабилизации значений мно­ жителей yk.

Метод JI. А. Люстерника. Вначале оптимизация производится простым градиентным методом. В процессе его осуществления вы­ числяется значение коэффициента

3F (хк)

дх

dF (хк~ 1)

дх

После замедления скорости убывания функции и при стабили­ зации значения параметра 8k вблизи некоторого значения б < 1 предлагается совершить большой шаг по градиенту

не обращая внимания на возможное возрастание функции. Затем

из точки хк+1 снова производится спуск простым градиентным ме­ тодом до стабилизации параметра б. Далее этот процесс повто­ ряется.

Метод «тяжелого шарика» [80, 25]. В этом методе каждый следующий шаг делается по направлению, являющемуся линей­ ной комбинацией антиградиента в очередной точке и предыдущего направления движения:

x*+' = xl - a + (233)

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

dF (х)

если на него действует поле с силой------§7 ^ -

Действительно, непрерывное уравнение движения имеет вид

тх + гх -I---- — 0.

Соответствующее дискретное уравнение можно записать сле­ дующим образом

Заметим, что если в выражении (234) положить т = О, то будет получено -уравнение простого градиентного метода. Таким образом, разница между методом «тяжелого шарика» и простым градиентным методом состоит в наличии инерционности движения итерационной точки х1 в первом методе.

Предлагается [80] в методе «тяжелого шарика» выбирать кон­ станты а и р следующим образом. Сначала принимается ß = 0 и выбирается а, как это делается в градиентном методе, когда ско­ рость сходимости метода уменьшится, ß следует увеличить до зна­ чения 0,8—0,99. Одновременно целесообразно увеличить а.

Метод «тяжелого шарика» является двухшаговым и немоно­ тонным. Он дает возможность не останавливаться итерационной точке X1 в локальных неглубоких минимумах.

В процессе реализации метода нужно переходить к уменьшению значений а и ß только при устойчивом росте функции. Отдельные случаи роста функции закономерны, и их можно игнорировать.

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

вторых производных, сокращает приблизительно в ]/р раз число итераций по сравнению простым градиентным методом при оптимальном выборе размера шага.

Ускорение сходимости метода наискорейшего спуска. Из основ­ ных соотношений, определяющих метод наискорейшего спуска, следует, что при точной реализации метода всегда будет выпол­ няться условие

(xt+l — хіУ (х1— X(_1) = 0, і = 1 , 2 , 3, . . .

Это означает ортогональность смещения итерационной точки х■' на двух соседних шагах. Данное обстоятельство приводит к тому,

98