Терминът "метод конюгат градиент" The - един от примерите за това как безсмислени фрази стават често срещано, възприема очевидно и не предизвикват никакви недоразумения. Факт е, че, с изключение на частни и не представлява частен случай на интерес, градиентите не са спрегнати и свързаните с тях насоки нямат нищо общо с градиенти. Метод име отразява факта, че методът за намиране на безусловна екстремум комбинира понятията градиент на целевата функция и спрегнати направления.

Няколко думи за отбелязването на използваните.

продукт точка на два вектора е писано $ х ^ Ty $ и сумата от скаларна: $ \ sum_ ^ п \, x_i \, y_i $. Имайте предвид, че $ х ^ Тай = ш ^ Tx $. Ако х и у са ортогонални, след $ х ^ Тай = 0 $. Като цяло, експресията на който се превръща в матрица 1x1, като $ х ^ Тай $ и $ х ^ TA_x $, се третират като скаларни количества.

Първоначално методът на конюгат градиент е разработен за решаване на системи линейни алгебрични уравнения на формата:

където х - неизвестен вектор, б - известен вектор, и A - известно, квадрат, симетричен, с принудително определена матрица. Разтворът на тази система е еквивалентно на намиране на минимума на съответната форма.
Квадратичен форма - това е просто скаларна, квадратна функция на даден вектор х до следното:

Наличието на такава връзка между линейна трансформация матрица А и скаларна функция F (х) прави възможно да се илюстрират някои от формула от линейната алгебра интуитивен чертежи. Например, матрицата е положително определена, ако за всяка ненулева вектор х следното притежава:

Фигура 1 илюстрира как да изглежда за квадратичен форми съответно положително определена матрица (а) отрицателен определена матрица (б), с принудително неопределен матрица (и), неопределен матрица (г).

Това означава, че ако А - положителна категорично, вместо решаване на системата уравнения 1, е възможно да се намери най-малко една квадратна функция. Освен това, методът на конюгат градиент да го направи за п или по-малко стъпки, където п - измерение на неизвестно вектор х. Тъй като всяка гладка функция в квартал на минималната си е добре приблизително чрез квадратно, по същия метод може да се приложи, за да сведе до минимум и не-квадратна функция. По този начин тя престава да бъде цел, но се превръща в повтарящ се.

Разглеждане на метода на конюгат градиент е целесъобразно да се започне с разглеждането на прост метод за търсене функция екстремум - метода на най-стръмната произход. Фигура 2 показва крива на минимална точка на стръмните метод произход. Същността на този метод:

• при начална точка х (0) се изчислява градиент и движението е в посока към antigradient до обективната функция се намалява;
• на мястото, където функцията престане да намалява, отново изчислява спускане градиент и продължава в нова посока;
• процесът се повтаря до достигане на минималната точка.

В този случай, всеки нов посоката на движение, перпендикулярна на предишната. Не дали има по-интелигентен начин да изберете нова посока на движението? Има, и то се нарича методът на спрегнати посоки. метод А конюгат градиент просто се отнася до група от методи на конюгатни посоки. Фигура 3 показва крива на точка на минимум при използване на метода на конюгатни градиенти.

Определяне конюгат се формулира, както следва: два вектора х и у са наречени А-конюгат (или конюгирани към матрица а) или А-ортогонална ако скаларен продукт на х и Ай равно на нула, което е:

Conjugacy може да се разглежда по общите ортогоналните концепции. В действителност, когато матрицата А - идентичност матрица, съгласно уравнение 4, векторите х и у - ортогонална. А иначе може да докаже връзката на концепции и ортогонална конюгат: психически участък Фигура 3, така че линиите на еднаква степен на елипси превърнаха в кръг, със свързаните с перпендикулярни направления ще бъдат просто.

Остава да разберете как да се изчисли посоката на чифтосване. Един възможен начин - да се използват техниките на линейната алгебра, особено ортогонализиране Грам-Шмид процес. Но за това е необходимо да се знае, матрицата, така че за повечето цели (например обучение на многослойни невронни мрежи), този метод не е подходящ. За щастие, има и други итерационни методи за изчисляване посоката на конюгат, най-известният - Флетчър-Рийвс формула:

Уравнение 5 означава, че новата посока, получен чрез добавяне на antigradient конюгат в точката на завъртане и предишната посока на движение, умножен по коефициент изчислява по формулата 6. Начин изчислени от Формула 5, са конюгирани ако функцията да бъде сведена до минимум е дефиниран във формата на 2. Това означава, че за квадратичен функции метод конюгат градиент е най-малко п стъпки (N - измерение на пространството за търсене). алгоритъм престава да бъде цел и става един повтарящ се за общи видове функции. В същото време, Флетчър и Рийвс предложи да поднови алгоритмична процедура на всеки N + 1 стъпки.

Човек може да се цитират формула за определяне на посоката на конюгата, Polak-Reiber формула (Polak-Ribiere):

метод Флетчър-Рийвс клони, ако началната точка е достатъчно близо до необходимия минимум, докато методът на Полак-Reiber може да бъде безкраен цикъл в редки случаи. Въпреки това, той често се съсредоточава по-бързо от първия метод. За щастие, на сближаването на метода на Полак-Reiber може да бъде гарантирана избор = \ макс \ $ $ \ бета. Това е еквивалентно на рестарта на криптографски алгоритъм, състоянието $ \ бета \ LEQ 0 $. Започват алгоритмични процедури, необходими да се забрави неотдавнашния посока на алгоритъма за търсене на и да започне отново в посока на най-стръмната спускане.

Следното е алгоритъм конюгат градиент за свеждане до минимум на общите функции на формата (nonquadratic).

1. Antigradient изчислява на произволна точка х (0).