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

Используя уравнения (243) и (241), получим

определенная и поэтому неособенная. Таким образом, показано, что точка хп+1 совпадает с точкой минимума квадратичной формы

(242).

Как следует из алгоритма метода Вольфа, перед началом его применения требуется провести п + 1 вычисление градиента функции. Если предварительно использовался градиентный метод, то за систему базисных точек можно взять последние итерационные точки этого метода. При совершении каждого нового шага тре­ буется вычислить градиент и значение функции всего в одной точке, т. е. существенно меньше, чем в конечно-разностном ва­ рианте метода Ньютона.

Для расширения области сходимости метода Вольфа рекомен­ дуется применять следующие меры:

1. Предотвращать слишком большие шаги. Если параметры Ягвелики (I Кі 1 20), то делается неполный шаг по направлению

хп+1. Результирующая точка * п+1 определяется соотношением

Параметр Я выбирается как наименьшее значение, при котором удовлетворяется система неравенств:

2. Во вновь полученной точке хп+х всегда проверять усло­

вие F (хп+1) s=^ max F (xl). Если это условие не выполнено, то из

І

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

Теоретически при использовании метода Вольфа может воз­ никнуть затруднение, связанное с отсутствием решения системы уравнений (240). Такое положение, например, может возникнуть при минимизации квадратичной функции (242), когда базовые точки х°, X1, . . ., хп находятся в подпространстве размерности, меньшей п. Практический опыт применения метода Вольфа не оправдывает этого опасения, однако при появлении трудностей

104

метод барицентрических координат, который не требует вычисления производных функции F (X) и ограничивается только вычисле­ нием функции F (х) в некоторых точках. Разумеется, метод Вольфа легко свести к методу нулевого порядка, используя замену частных производных функции F (X) отношением конечных разностей, од­ нако метод Лаврова требует примерно в 2 раза меньшее количе­ ство вычислений значения функции для осуществления первой итерации, чем метод Вольфа.

Аналогично предыдущему при использовании метода Лаврова

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

Все рекомендации по практическому осуществлению метода Вольфа непосредственно переносятся на метод барицентрических координат.

5. Метод сопряженных градиентов

Метод сопряженных градиентов, предложенный Хестеном и Штифелем в 1952 г. [132], является одним из эффективнейших со­ временных методов безусловной минимизации функций. Как бу­

105

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

Выведем основные расчетные соотношения метода сопряженных градиентов. Пусть требуется найти точку минимума х+ для квад­ ратичной формы q (х), определяемой выражением

где А — положительно определенная симметричная матрица. Зададимся точкой начального приближения х° и построим первое приближение вида

где а 0 — выбирается из равенства

q (х° — ocqS1) = min q (х° — ts-1). t

Обозначим через sl вектор, определяющий направление дви­

ляются из условия минимума:

деленностью матрицы А точка х1 есть точка минимума функции х‘ = х+ и итерационная процедура считается законченной.

106

Из равенств (244) и (245) легко вывести рекуррентное соотно­

=/ = 1, 2, . . і + 1; I - 0, 1, 2 , . . . (248)

Сопоставляя равенство (248) и тождество

которое следует из формулы (245), получим

( - ^ ) * Д М = о , , +

Иначе говоря, при реализации итерационной процедуры (245) векторы градиентов в различных итерациях взаимно ортогональны. Это указывает на конечность данной процедуры, так как в я-мер- ном пространстве не может существовать более чем я взаимно ортогональных векторов, т. е. итерационная процедура должна закончиться не более, чем за я шагов. Условие (248) при / = 1, 2, . . ., і можно также представить в виде

Это означает, что направления движения в различных итера­ циях процедуры (245) взаимно Л-ортогональны [98].

107