f (x) = a + (x, b) + ½ (x, H · x). (10)
з позитивно певної n · n матрицею. Виявляється, що квадратична функція (10) може бути мінімізована шляхом пов'язаних напрямків не більше ніж за n кроків.
Щоб скористатися цим методом мінімізації квадратичної функції (10) потрібно знати n - взаємно пов'язаних напрямків S0. S 1, ..., S n-1. Ефективність таких напрямків - самостійна проблема. Існує багато взаємно пов'язаних напрямків S0. S 1, ..., S n-1 і способів їх побудови. Нижче викладається метод сполучених градієнтів Флетчера - Ривса, в якому вибір Н - пов'язаних напрямків здійснюється спільно з одновимірної мінімізацією f (х) по # 945; ..
1.2.2 Метод Флетчера - Ривса.
Цей метод використовує послідовність напрямків пошуку, кожна з яких є лінійною комбінацією антіградіента в поточній точці і попереднього напрямку спуску. Метод змінюється до квадратичної цільової функції
f (x) = a + (x, b) + ½ (x, H · x).
При мінімізації її методом Флетчера - Ривса вектори Sk обчислюються за формулами
величини # 946; k-1 вибираються так, щоб напрямки S k. S k-1 були Н - сполученими.
Точка х k-1, визначається в результаті мінімізації функції f (х) в напрямку S k. що виходить з точки x k. тобто
де # 945; k доставляє мінімум по # 945; k функції f (x k. # 945; · S k).
Отже, пропонована процедура мінімізації функції f (x) виглядає наступним чином. В заданій точці x0 обчислюється антіградіента
S0 = - f '(x 0). Здійснюється одномірна мінімізація в цьому напрямку і визначається точка x 1. У точці x 1 сново обчислюється антіградіента - f '(x 1). Так як ця точка доставляє мінімум функції f (x) вздовж напрямку S0 = - f '(x 0), вектор f' (x 1) ортогонален f '(x 0). Потім за відомим значенням f '(x 1) за формулою (11) обчислюється вектор S 1. який за рахунок вибору # 946; 0 буде Н - зв'язаним до S 0. Далі відшукується мінімум функції f (х) вздовж напрямку S 1 і т.д.
При k = 0 введення початкового наближення x0. Обчислення антіградіента S0 = - f '(x0).
Рішення завдання одномірної мінімізації за a функції f (xk + a · Sk), в результаті чого визначається величина кроку ak і точка xk + 1 = xk + ak · Sk.
Якщо f '(xk + 1) = 0, то xk + 1 - рішення задачі. Інакше визначаємо новий напрямок пошуку: Sk + 1 зі співвідношення. Sk + 1 = - f '(xk + 1) + · Sk Далі r = r + 1 і перехід до кроку 2.
Це і є остаточний вигляд алгоритму Флетчера-Ривса. Як було відмічено раніше, він знайде мінімум квадратичної функції не більше ніж за n кроків.
1.2.3 Мінімізація неквадратічной цільової функції.
Метод Флетчера-Ривса може застосовуватися для мінімізації і неквадратічних функцій. Він є методом першого порядку і в той же час швидкість його збіжності квадратична. Зрозуміло, якщо цільова функція не квадратичного, метод вже не буде кінцевим. Тому після (n + 1) -й ітерації процедура повторюється з заміною x0 на xn + 1. а рахунок закінчується при || f '(xk + 1) || £ # 949 ;, де # 949; - задане число. При мінімізації неквадратічних функцій зазвичай застосовується така модифікація методу Флетчера-Ривса.
Схема алгоритму для неквадратічних цільових функцій.
При k = 0 введення початкового наближення x0 і умови зупинки # 949; 3. Обчислення антіградіента S0 = - f '(x0).
Рішення завдання одномірної мінімізації за a функції f (xk + a · Sk), в результаті чого визначається величина кроку ak і точка xk + 1 = xk + ak · Sk.