Основы теории оптимизации (стр. 58 )

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

Методу сопряженных градиентов можно придать и иную форму. Рассмотрим итерационный процесс

(22)

Лемма 2. Для случая квадратичной функции (15) методы (13), (16), (17) и (22) при одинаковом х0 определяют одну и ту же последовательность точек xk.

Поскольку pk в (22) и (16) отличаются лишь скалярными (ненулевыми) множителями, а rk в (22) и (16) совпадают, то процесс (22) обладает теми же свойствами, что и (13), (16) векторы рi являются сопряженными, а градиенты ri — взаимно ортогональны. Из леммы 2 и теоремы 1 следует, что метод (22) дает точку минимума квадратичной функции (15) в Rn за число итераций, не превосходящее п. Для неквадратичных задач ме­тод (22) проще, чем (13), (14), так как требует решения лишь одномерной (а не двумерной) вспомогательной задачи миними­зации. Разумеется, в неквадратичном случае теряется свойство конечности метода и (22) превращается в, вообще говоря, бес­конечный итерационный двухшаговый метод.

Обычно для неквадратичных задач метод сопряженных гра­диентов применяется в несколько иной форме В него вводится процедура обновления — время от времени шаг делается не по формуле (22), а как в начальной точке, т. е. по градиенту. Наиболее естественно производить обновление через число итераций, равное размерности пространства:

(23)

Нетрудно доказать, что метод сопряженных градиентов с обновлением обладает свойством глобальной сходимости. Оказывается, что в то же время в окрестности мини­мума он сходится с квадратичной скоростью.

Теорема 3. Пусть х* — невырожденная точка минимума, и в ее окрестности удовлетворяет условию Липшица. Тогда для метода (23) в окрестности х* справедлива оценка

Иначе говоря, по скорости сходимости п шагов метода со­пряженных градиентов эквивалентны одному шагу метода Нью­тона. Мы не приводим доказательства теоремы, так как оно до­вольно громоздко. В его основе лежит идея квадратичной ап­проксимации f(x) и факт конечности метода для квадратичных функций (см. теорему 2).

Возможны иные вычислительные схемы метода сопряжен­ных градиентов для неквадратичных функций. С одной из них, требующей решения двумерной задачи минимизации на каждом шаге, мы начали анализ этого метода — см. (13), (14). Другие, подобно (22), обычно включают лишь одномерные вспомога­тельные задачи, но отличаются от (22) правилом выбора βk. Примером может служить схема

(24)

Как и для (22), здесь возможны варианты либо с обновле­нием, либо без него. Для квадратичной функции последователь­ности xk, порождаемые методами (22) и (24), совпадают.

Как показывает опыт вычислений, для неквадратичного слу­чая несколько более быструю сходимость обычно дает схе­ма (24).

Представляет интерес поведение метода для задач большой размерности (когда число итераций меньше размерности). Ока­зывается, здесь можно гарантировать лишь сходимость со скоростью геометрической прогрессии даже для квадратичного слу­чая. Пусть A — матрица п×n,

(25)

и f(x) — соответствующая ей квадратичная функция на Rn:

(26)

Точка xk может быть представлена в виде

(27)

где Рk(А) — матричный полином k-й степени вида

(28)

поэтому

где— обычный полином. В силу свойств метода оценка для f(xk)=f* справедлива для всех Pk(λ), Pk(0)= 1, в частности, для

где

(29)

Поэтому

Можно показать на примерах, что оценка (30) неулучшаема.

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

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

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

Естественно, большая скорость схо­димости не может достигаться и в более широком классе сильно выпуклых с константой l функций, градиент которых удовле­творяет условию Липшица с константой L. Факт квадратичной сходимости (теорема 3) имеет место только при числе итера­ций, существенно большем размерности пространства.

5.11. Краткий анализ методов одномерной минимизации

Методы точечного оценивания

Эти методы учитывают информацию об относительном изменении значений функции в пробных точках. Методы накладывают дополнительные ограничения на функцию: функция должна быть непрерывной и достаточно гладкой.

Основная идея метода: возможность аппроксимации гладкой функции полиномом достаточно высокого порядка и использование этого полинома для оценивания точки оптимума.

Качество этой оценки может быть повышено двумя способами:

1.  Увеличением степени полинома;

2.  Уменьшением интервала аппроксимации.

Второй способ предпочтительнее, так как построение полинома порядка более 3 – достаточно сложная задача, а сужение интервала  для унимодальной функции – достаточно простая.

  Использование квадратичной аппроксимации для нахождения оптимума.

  Чтобы функция имела минимум внутри отрезка она должна быть по крайней мере квадратичной.

Заданы  и соответствующие им . Можно задать аппроксимацию полинома  вида:

и  выбрать  так, чтобы

, , .

Найдём стационарную точку  полинома q(x)

Так как функция y=f(x) унимодальна на рассматриваемом интервале и полином q(x) тоже унимодальная функция, то  является приемлемой оценкой истинного оптимума x*. На этом основан метод Пауэлла.

Метод Пауэлла

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

  Алгоритм.

1.  Задать x1 и шаг ∆x

2.  Найти . Вычислить f(x1) и f(x2).