Метод сопряженных направлений

Метод сопряженных направлений

Рассмотрим следующую задачу локальной безусловной оптимизации: найти минимум критерия оптимальности

(

), определенного в

-мерном евклидовом пространстве

,

(1)

Введем прежде следующие понятия: векторы

, принадлежащие пространству

, называются векторами сопряженными относительно матрицы A

(A – ортогональными векторами), если

для всех

.

В методе сопряженных направлений применяется итерационная формула метода Гаусса-Зейделя в виде, близком к использованному в параграфе 6.3.

Положим

и пусть

,

,...,

- орты используемой системы координат. Тогда итерационную формулу метода Гаусса-Зейделя можно записать в виде

(2)

где коэффициенты

находятся из условий

(3)

Схема метода сопряженных направлений:

Задаем начальную точку и полагаем =0, =1.
Последовательно для =1,2,..., по формулам (2), (3) находим точки , , .
Исходя из точки , еще раз находим минимум функции () вдоль первого координатного направления - вычисляем координаты точки
(4)

где коэффициент находится из условия
(5)
Исходя из точки , находим минимум функции вдоль вектора - вычисляем
(6)

где коэффициент находится из условия
(7)

Если одно из стандартных условий окончания итераций
(8)

выполнено, то полагаем , и заканчиваем вычисления. Иначе - полагаем =+1 и переходим к п.2)

Метод сопряженных направлений иллюстрирует рис. 1, на котором показаны линии уровня функции Химмельблау (

=2).

Рис. 1. Траектория поиска минимума функции Химмельблау методом сопряженных направлений.

Рассмотрим еще один пример – см. рис. 2, на котором показаны линии уровня двумерной квадратичной функции

(9)

Линии уровня получены с помощью MATLAB-программы, приведенной в параграфе 6.1.

Рис. 2. Траектория поиска минимума квадратичной функции (9) методом сопряженных направлений.

Произвольную

-мерную квадратичную функцию можно записать в виде

(10)

где

– квадратная

*

матрица,

–

*1 столбец,

– скалярная константа. Например, если положить

то имеем функцию (9):

Утверждение 1. В случае минимизации двумерной квадратичной функции (10) методом сопряженных направлений, направления

,

являются

-ортогональными.

Доказательство (см. рис. 2). По определению

-ортогональности для доказательства утверждения достаточно показать, что скалярное произведение

(11)

Легко видеть, что производная функции (10) равна

. Поэтому

Подставляя этот результат в выражение (11), получим

.

Последнее равенство следует из ортогональности пар векторов

Утверждение 1 объясняет название рассмотренного метода.

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