Також можна шукати не найкращу точку в напрямку градієнта, а якусь краще за поточну.
Найбільш простий у реалізації із усіх методів локальної оптимізації. Має досить слабкі умовизбіжності, але при цьому швидкість збіжності досить мала (лінійна). Крок градієнтного методу часто використовується як частина інших методів оптимізації, наприклад, метод Флетчера – Рівса.
Опис [ | ]
Удосконалення[ | ]
Метод градієнтного спуску виявляється дуже повільним при русі по яру, причому зі збільшенням кількості змінних цільової функціїтака поведінка методу стає типовою. Для боротьби із цим явищем використовується, суть якого дуже проста. Зробивши два кроки градієнтного спуску і отримавши три крапки, третій крок слід зробити у напрямку вектора, що з'єднує першу і третю точку, вздовж дна яру.
Для функцій, близьких до квадратичних, ефективним є метод сполучених градієнтів.
Застосування у штучних нейронних мережах[ | ]
Метод градієнтного спуску з деякою модифікацією широко застосовується для навчання перцептрону і теоретично штучних нейронних мереж відомий як метод зворотного поширення помилки. При навчанні нейромережі типу персептрон потрібно змінювати вагові коефіцієнти мережі так, щоб мінімізувати середню помилкуна виході нейронної мережі при подачі на вхід послідовності навчальних вхідних даних. Формально, щоб зробити всього один крок за методом градієнтного спуску (зробити лише одну зміну параметрів мережі), необхідно подати на вхід мережі послідовно абсолютно весь набір навчальних даних, для кожного об'єкта навчальних даних обчислити помилку та розрахувати необхідну корекцію коефіцієнтів мережі (але не робити цю корекцію), і після подачі всіх даних розрахувати суму в коригуванні кожного коефіцієнта мережі (сума градієнтів) і зробити корекцію коефіцієнтів «на крок». Очевидно, що при великому наборі навчальних даних алгоритм працюватиме вкрай повільно, тому на практиці часто здійснюють коригування коефіцієнтів мережі після кожного елемента навчання, де значення градієнта апроксимуються градієнтом функції вартості, обчисленому тільки на одному елементі навчання. Такий метод називають стохастичним градієнтним спуском або оперативним градієнтним спуском . Стохастичний градієнтний спуск є одним із форм стохастичного наближення. Теорія стохастичних наближень дає умови збіжності способу стохастичного градієнтного спуску.
Посилання [ | ]
- J. Mathews.Модули для Steepest Descent або Gradient Method. (недоступне посилання)
Література [ | ]
- Акуліч І. Л.Математичне програмування в прикладах та задачах. - М.: Вища школа, 1986. - С. 298-310.
- Гілл Ф., Мюррей У., Райт М.Практична оптимізація = Practical Optimization. - М.: Світ, 1985.
- Коршунов Ю. М., Коршунов Ю. М.Математичні засади кібернетики. - М.: Вища школа, 1972.
- Максимов Ю. А., Філіповська Є. А.Алгоритми розв'язання задач нелінійного програмування. - М.: МІФІ, 1982.
- Максимов Ю. А.Алгоритми лінійного та дискретного програмування. - М.: МІФІ, 1980.
- Корн Р., Корн Т.Довідник з математики для науковців та інженерів. - М.: Наука, 1970. - С. 575-576.
- С. Ю. Городецький, В. А. Гришагін.Нелінійне програмування та багатоекстремальна оптимізація. - Нижній Новгород: Видавництво Нижегородського Університету, 2007. – С. 357-363.
Метод якнайшвидшого спуску є градієнтним методом зі змінним кроком. На кожній ітерації величина кроку k вибирається з умови мінімуму функції f(x) у бік спуску, тобто.
Ця умова означає, що рух уздовж антиградієнта відбувається доти, доки значення функції f(x) зменшується. З математичної точки зору на кожній ітерації необхідно вирішувати завдання одномірної мінімізації за функцією
() = f (x (k) -f (x (k)))
Скористайтеся при цьому методом золотого перерізу.
Алгоритм методу якнайшвидшого спуску полягає в наступному.
Визначаються координати початкової точки x (0) .
У точці x (k), k = 0, 1, 2, …, обчислюється значення градієнта f (x (k)).
Визначається величина кроку k шляхом одномірної мінімізації за функцією
()=f(x(k)-f(x(k))).
Визначаються координати точки x (k):
x i (k+1) = x i (k) - k f i (x (k)), i = 1, …, n.
Перевіряється умова зупинки ітераційного процесу:
||f(x(k+1))|| .
Якщо воно виконується, то обчислення припиняються. В іншому випадку здійснюється перехід до п. 1. Геометрична інтерпретація методу якнайшвидшого спуску представлена на рис. 1.
Мал. 2.1. Блок схема методу якнайшвидшого спуску.
Реалізація методу у програмі:
Метод якнайшвидшого спуску.
Мал. 2.2. Реалізація способу якнайшвидшого спуску.
Висновок: У разі метод зійшовся за 7 ітерацій. Крапка А7 (0,6641; -1,3313) є точкою екстремуму. Метод сполучених напрямів. Для квадратичних функцій можна створити градієнтний метод, при якому час збіжності буде кінцевим і дорівнює кількості змінних n.
Назвемо деякий напрямок і сполученими стосовно деякої позитивно визначеної матриці ГессаH, якщо виконується:
Тоді тобто. Значить при одиничній H, сполучений напрямок означає їх перпендикуляр. У загальному випадку H непоодинока. У загальному випадкуСполученість - це застосування матриці Гесса до вектора - означає поворот цього вектора на деякий кут його розтяг або стиснення.
А тепер вектору векторортогонален т. е. сполученість це не ортогональність вектора, а ортогональність повернутого векторат.е.і.
Мал. 2.3. Блок-схема методу сполучених напрямів.
Реалізація методу у програмі: Метод сполучених напрямків.
Мал. 2.4. Реалізація методу пов'язаних напрямів.
Мал. 2.5. Графік методу сполучених напрямів.
Висновок: Точка А3 (0,6666; -1,3333) була знайдена за 3 ітерації і є точкою екстремуму.
3. Аналіз методів визначення мінімального, максимального значення функції за наявності обмежень
Нагадаємо, що загальне завданняумовної оптимізації виглядає так
f(x) ® min, x Î W,
де W - власне підмножина R m. Підклас завдань з обмеженнями типу рівностей виділяється тим, що безліч задається обмеженнями виду
f i (x) = 0, де fi: R m ®R (i = 1, …, k).
Таким чином, W = (x R m: f i (x) = 0, i = 1, …, k).
Нам буде зручно писати у функції f індекс "0". Таким чином, завдання оптимізації з обмеженнями типу рівностей записується у вигляді
f 0 (x) ® min, (3.1)
f i (x) = 0, i = 1, …, k. (3.2)
Якщо позначити тепер через f функцію на R m зі значеннями R k , координатний запис якої має вигляд f(x) = (f 1 (x), …, f k (x)), то (3.1)–(3.2)можна також записати у вигляді
f 0 (x) min, f(x) = Q.
Геометрично завдання з обмеженнями типу рівностей - це завдання пошуку найнижчої точки графіка функції f 0 над різноманіттям (див. рис. 3.1).
Точки, що задовольняють усім обмеженням (тобто точки множини ), зазвичай називають допустимими. Допустима точка x* називається умовним мінімумом функції f 0 при обмеженнях f i (x) = 0, i = 1, ..., k (або розв'язанням задачі (3.1)–(3.2)), якщо при всіх допустимих точках x f 0 (x *) f 0 (x). (3.3)
Якщо (3.3) виконується тільки для допустимих x, що лежать в околиці V x * точки x *, то говорять про локальний умовний мінімум. Природно визначаються поняття умовних суворих локального та глобального мінімумів.
У цьому варіанті градієнтного методу мінімізуюча послідовність (X k ) також будується за правилом (2.22). Однак величина кроку ak перебуває в результаті вирішення допоміжного завдання одномірної мінімізації
min(j k (a) | a>0), (2.27)
де j k (a) = f (X k - a · (X k)). Таким чином, на кожній ітерації у напрямку антиградієнта 
виконується вичерпний спуск. Для вирішення задачі (2.27) можна скористатися одним із методів одновимірного пошуку, викладених у розділі 1, наприклад, методом розрядного пошуку або методом золотого перерізу.
Опишемо алгоритм методу якнайшвидшого спуску.
Крок 0Задати параметр точності e>0, вибрати X 0 ÎE n, покласти k = 0.
Крок 1Знайти (X k) та перевірити умову досягнення заданої точності || (x k) ||£ e. Якщо воно виконується, то перейти до кроку 3, інакше до кроку 2.
Крок 2Розв'язати завдання (2.27), тобто. знайти a k . Знайти ще одну точку , покласти k=k+1 і перейти до кроку 1.
Крок 3Завершити обчислення, поклавши X * = X k, f * = f (X k).
Мінімізувати функцію
f(x)=x 1 2 +4x 2 2 -6x 1 -8x 2 +13; (2.28)
Спочатку вирішимо задачу класичнимметодом. Запишемо систему рівнянь, що являють собою необхідні умовибезумовного екстремуму
Вирішивши її, отримаємо стаціонарну точку X * = (3; 1). Далі перевіримо виконання достатньої умовидля чого знайдемо матрицю других похідних
Так як, згідно з критерієм Сильвестра, ця матриця позитивно визначена при ", то знайдена точка X * є точкою мінімуму функції f (X). Мінімальне значення f * = f (X *) = 0. Таке точне рішення задачі (11).
Виконаємо одну ітерацію методу градієнт спускудля (2.28). Виберемо початкову точку X 0 =(1;0), задаємо початковий крок a=1 та параметр l=0,5. Обчислимо f(X0)=8.
Знайдемо градієнт функції f(X) у точці X 0
(X 0) = = (2.29)
Визначимо нову точку X = X 0 -a · (X 0), обчисливши її координати
x 1 = 
x 2 = 
(2.30)
Обчислимо f (X) = f (X 0 -a · (X 0)) = 200. Оскільки f(X)>f(X 0), то виконуємо дроблення кроку, вважаючи a=a·l=1·0,5=0,5. Знову обчислюємо за формулами (2.30) x 1 = 1 + 4a = 3; x 2 =8a=4 і бачимо значення f(X)=39. Оскільки знову f(X)>f(X 0), ще зменшуємо величину кроку, вважаючи a=a·l=0,5·0,5=0,25. Обчислюємо нову точку з координатами x 1 = 1 + 4 · 0,25 = 2; x 2 =8·0,25=2 і значення функції у цій точці f(X)=5. Оскільки умова зменшення f(X) Виконаємо одну ітерацію за методом якнайшвидшого спускудля (2.28) з тією самою початковою точкою X 0 = (1; 0). Використовуючи вже знайдений градієнт (2.29), знаходимо X = X 0 -a · (X 0) і будуємо функцію j 0 (a) = f (X 0 -a · (X 0)) = (4a-2) 2 +4 (8a-1) 2 . Мінімізуючи її за допомогою необхідної умови j 0 ¢(a)=8·(4a - 2)+64·(8a - 1)=0 знаходимо оптимальне значення величини кроку a 0 = 5/34. Визначаємо точку мінімізуючої послідовності X 1 = X 0 -a 0 · (X 0) Градієнтом диференційованої функції f(x) у точці хназивається n-мірний вектор f(x)
, компоненти якого є приватними похідними функції f(х),обчисленими у точці х, тобто. f"(x ) = (дf(х)/дх 1 , …, дf(х)/дх n) T. Цей вектор перпендикулярний до площини, проведеної через точку. х, та дотичної до поверхні рівня функції f(x),проходить через точку х.У кожній точці такої поверхні функція f(x)набуває однакового значення. Прирівнюючи функцію різним постійним величинам 0 , 1 , ... , отримаємо серію поверхонь, що характеризують її топологію (Рис. 2.8). Вектор-градієнт спрямований у бік якнайшвидшого зростання функції у цій точці. Вектор протилежний градієнту (-f'(х))
, називається антиградієнтомі спрямований у бік якнайшвидшого зменшення функції. У точці мінімуму градієнт функції дорівнює нулю. На властивостях градієнта засновані методи першого порядку, звані також градієнтним та методами мінімізації. Використання цих методів у випадку дозволяє визначити точку локального мінімуму функції. Очевидно, якщо немає додаткової інформації, то з початкової точки хрозумно перейти до точки х, що лежить у напрямку антиградієнта - найшвидшого зменшення функції. Вибираючи як напрямок спуску р[k] антиградієнт - f'(х[k] )
у точці х[k], отримуємо ітераційний процес виду х[ k+ 1] = x[k]-a k f"(x[k] )
,
а k > 0; k=0, 1, 2, ... У координатній формі цей процес записується так: x i [ k+1]=х i[k] - a kf(x[k] )
/x i i = 1, ..., n; k= 0, 1, 2,... Як критерій зупинки ітераційного процесу застосовують або виконання умови трошки збільшення аргументу || x[k+l] - x[k] || <= e
,
либо выполнение условия малости градиента || f'(x[k+l] )
|| <= g
, Тут e та g - задані малі величини. Можливий і комбінований критерій, що полягає у одночасному виконанні зазначених умов. Градієнтні методи відрізняються один від одного способами вибору величини кроку а k. При методі з постійним кроком всім ітерацій вибирається деяка постійна величина кроку. Досить малий крок а kзабезпечить зменшення функції, тобто виконання нерівності f(х[ k+1])
= f(x[k] – a k f'(x[k] ))
< f(x[k] )
. Однак це може призвести до необхідності проводити неприйнятно велику кількість ітерацій для досягнення точки мінімуму. З іншого боку, занадто великий крок може викликати несподіване зростання функції або призвести до коливань близько мінімальної точки (зациклювання). Через складність отримання необхідної інформації для вибору величини кроку методи з постійним кроком застосовуються практично рідко. Більш економічні у сенсі кількості ітерацій та надійності градієнтні методи зі змінним кроком,коли залежно від результатів обчислень величина кроку певним чином змінюється. Розглянемо варіанти таких методів, що застосовуються на практиці. При використанні методу якнайшвидшого спуску на кожній ітерації величина кроку а kвибирається з умови мінімуму функції f(x)у напрямі спуску, тобто. Ця умова означає, що рух уздовж антиградієнта відбувається доти, доки значення функції f(x)зменшується. З математичної точки зору на кожній ітерації необхідно вирішувати задачу одномірної мінімізації по афункції Алгоритм методу якнайшвидшого спуску полягає в наступному. 1. Визначаються координати початкової точки х.
2. У точці х[k],
k = 0, 1, 2, ... обчислюється значення градієнта f'(x[k])
. 3. Визначається величина кроку a k шляхом одномірної мінімізації по афункції j (a) = f(x[k]- af"(x[k])).
4. Визначаються координати точки х[k+ 1]: х i [ k+ 1]= x i[k]– а k f' i (х[k]), i = 1, ..., п. 5. Перевіряються умови зупинки стераційного процесу. Якщо вони виконуються, то обчислення припиняються. В іншому випадку здійснюється перехід до п. 1. У аналізованому методі напрямок руху з точки х[k] стосується лінії рівня в точці x[k+ 1] (Рис. 2.9). Траєкторія спуску зигзагоподібна, причому сусідні ланки зигзагу ортогональні один одному. Дійсно, крок a k вибирається шляхом мінімізації по афункції? (a) = f(x[k] - af"(x[k]))
. Необхідна умова мінімуму функції d j (a)/da = 0.Обчисливши похідну складної функції, отримаємо умову ортогональності векторів спускових напрямків у сусідніх точках: dj (a)/da = -f'(x[k+ 1]f'(x[k])
= 0.
Градієнтні методи сходяться до мінімуму з високою швидкістю (зі швидкістю геометричної прогресії) для гладких опуклих функцій. У таких функцій найбільше Мі найменше mвласні значення матриці других похідних (матриці Гессе) мало відрізняються один від одного, тобто матриця Н(х)добре обумовлена. Нагадаємо, що власними значеннями l i , i
=1, …, nматриці є коріння характеристичного рівняння Однак на практиці, як правило, мінімізовані функції мають погано зумовлені матриці других похідних (Т/М<<
1). Значення таких функцій вздовж деяких напрямків змінюються набагато швидше (іноді кілька порядків), ніж у інших напрямах. Їх поверхні рівня в найпростішому випадку сильно витягуються (Рис. 2.10), а в складніших випадках згинаються і являють собою яри. Функції, які мають такі властивості, називають яружними.Напрямок антиградієнта цих функцій (див. мал. 2.10) істотно відхиляється від напрямку в точку мінімуму, що призводить до уповільнення швидкості збіжності. Швидкість збіжності градієнтних методів залежить також від точності обчислень градієнта. Втрата точності, а це зазвичай відбувається в околиці точок мінімуму або в яру, може взагалі порушити збіжність процесу градієнтного спуску. Внаслідок перерахованих причин градієнтні методи найчастіше використовуються у комбінації з іншими, більш ефективними методами на стадії вирішення завдання. У цьому випадку точка хзнаходиться далеко від точки мінімуму, і кроки в напрямку антиградієнта дозволяють досягти суттєвого зменшення функції. Розглянуті вище градієнтні способи шукають точку мінімуму функції у випадку лише за нескінченне число ітерацій. Метод сполучених градієнтів формує напрями пошуку, більшою мірою відповідні геометрії функції, що мінімізується. Це суттєво збільшує швидкість їх збіжності та дозволяє, наприклад, мінімізувати квадратичну функцію. f(x) = (х, Нх) + (b, х) + а із симетричною позитивно визначеною матрицею Нза кінцеву кількість кроків п,дорівнює кількості змінних функції. Будь-яка гладка функція на околиці точки мінімуму добре апроксимується квадратичною, тому методи сполучених градієнтів успішно застосовують для мінімізації та неквадратичних функцій. У разі вони перестають бути кінцевими і стають ітеративними. За визначенням, два n-мірні вектор хі уназивають пов'язанимипо відношенню до матриці H(або H-сполученими), якщо скалярний твір (x, ну) = 0.Тут Н -симетрична позитивно визначена матриця розміром пх п. Однією з найістотніших проблем у методах сполучених градієнтів є проблема ефективної побудови напрямків. Метод Флетчера-Рівса вирішує цю проблему шляхом перетворення кожного кроку антиградієнта -f(x[k])
у напрям p[k],
H-пов'язане з раніше знайденими напрямками р, р, ..., р[k-1]. Розглянемо спочатку цей метод стосовно задачі мінімізації квадратичні функції. Напрями р[k] обчислюють за формулами: p[ k] = -f'(x[k])
+b k-1 p[k-l], k>= 1; p = - f’(x)
. Величини b k-1 вибираються так, щоб напрямки p[k], р[k-1] були H-сполученими :
(p[k], Hp[k- 1])= 0.
В результаті для квадратичної функції ітераційний процес мінімізації має вигляд x[ k+l] =x[k]+a k p[k], де р[k] -
напрямок спуску на k-м кроку; а k -величина кроку. Остання вибирається з умови мінімуму функції f(х)по ау напрямку руху, тобто в результаті вирішення задачі одновимірної мінімізації: f(х[ k] + а k р[k])
= f(x[k] + ар [k])
. Для квадратичної функції Алгоритм методу сполучених градієнтів Флетчера-Рівса полягає у наступному. 1. У точці хобчислюється p = -f'(x)
. 2. На k-м кроку за наведеними вище формулами визначаються крок а k .
і крапка х[k+ 1]. 3. Обчислюються величини f(x[k+1])
і f'(x[k+1])
. 4. Якщо f'(x)
= 0, то точка х[k+1] є точкою мінімуму функції f(х).В іншому випадку визначається новий напрямок p[k+l] із співвідношення та здійснюється перехід до наступної ітерації. Ця процедура знайде мінімум квадратичної функції не більше ніж за пкроків. При мінімізації неквадратичних функцій метод Флетчера-Рівса з кінцевого стає ітеративним. У такому разі після (П+ 1)-ї ітерації процедури 1-4 циклічно повторюються із заміною хна х[п+1] , а обчислення закінчуються при , де - Задане число. При цьому застосовують таку модифікацію методу: x[ k+l] = x[k]+a k p[k],
p[ k] = -f'(x[k])+
b k- 1 p[k-l], k>= 1; p = -f'( x); f(х[ k] + a k p[k])
= f(x[k] + ap[k];
Тут I- безліч індексів: I= (0, n, 2 п, Зп, ...), тобто оновлення методу відбувається через кожні пкроків. Геометричний змістметоду сполучених градієнтів полягає у наступному (Рис. 2.11). Із заданої початкової точки хздійснюється спуск у напрямку р = -f"(x). У точці хвизначається вектор-градієнт f"(x). Оскільки хє точкою мінімуму функції у напрямку р,
то f'(х)
ортогональний вектор р. Потім знаходиться вектор р , H-сполучений до р. Далі знаходиться мінімум функції вздовж напрямку рі т.д. Методи сполучених напрямів є одними з найефективніших для вирішення задач мінімізації. Проте слід зазначити, що вони чутливі до помилок, що виникають у процесі рахунку. При великій кількості змінних похибка може настільки зрости, що процес доведеться повторювати навіть для квадратичної функції, тобто процес для неї не завжди вкладається в пкроків. Метод найшвидшого спуску (в англ. літературі «method of steepest descent») - це ітераційний чисельний метод (першого порядку) розв'язання оптимізаційних завдань, що дозволяє визначити екстремум (мінімум або максимум) цільової функції: Відповідно до аналізованого методом екстремум (максимум чи мінімум) цільової функції визначають у бік найбільш швидкого зростання (зменшення) функції, тобто. у напрямі градієнта (антиградієнта) функції. Градієнтом функції у точці де i, j, ..., n - Поодинокі вектори, паралельні координатним осям. Градієнт у базовій точці Метод якнайшвидшого спуску є подальшим розвиткомметоду градієнтного спуску. У загальному випадку процес знаходження екстремуму функції є ітераційною процедурою, яка записується так: де знак "+" використовується для пошуку максимуму функції, а знак "-" використовується для пошуку мінімуму функції; Одиничний вектор напряму, що визначається за формулою: Константа, що визначає розміри кроку і однакова всім i-х напрямів. Величина кроку вибирається з умови мінімуму цільової функції f(х) у напрямку руху, тобто в результаті вирішення задачі одновимірної оптимізації в напрямку градієнта або антиградієнта: Іншими словами, величину кроку визначають при вирішенні даного рівняння: Таким чином, крок розрахунку вибирається такої величини, що рух виконується доти, поки відбувається поліпшення функції, досягаючи таким чином екстремуму в деякій точці. У цій точці знову визначають напрямок пошуку (за допомогою градієнта) і шукають нову точку оптимуму цільової функції тощо. Таким чином, у даному методі пошук відбувається більшими кроками, і градієнт функції обчислюється в меншій кількості точок. У разі функції двох змінних даний методмає наступну геометричну інтерпретацію: напрямок руху з точки стосується лінії рівня в точці . Траєкторія спуску зигзагоподібна, причому сусідні ланки зигзагу ортогональні один одному. Умова ортогональності векторів напрямків спуску в сусідніх точках записується таким виразом: Траєкторія руху до точки екстремуму при використанні методу якнайшвидшого спуску, зображена на графіку лінії рівного рівня функції f(x) Пошук оптимального рішення завершується у разі, коли на ітераційному етапі розрахунку (кілька критеріїв): Траєкторія пошуку залишається в малій околиці поточної точки пошуку: Збільшення цільової функції не змінюється: Градієнт цільової функції в точці локального мінімуму перетворюється на нуль: Слід зазначити, що метод градієнтного спуску виявляється дуже повільним при русі по яру, причому зі збільшенням кількості змінних цільової функції така поведінка методу стає типовою. Яр є западиною, лінії рівня якої приблизно мають форму еліпсів з півосями, що розрізняються в багато разів. За наявності яру траєкторія спуску має вигляд зигзагоподібної лінії з малим кроком, внаслідок чого результуюча швидкість спуску до мінімуму сильно сповільнюється. Це пояснюється тим, що напрямок антиградієнта цих функцій суттєво відхиляється від напрямку в точку мінімуму, що призводить до додаткової затримки у розрахунку. В результаті алгоритм втрачає обчислювальну ефективність. Чудова функція Метод градієнта разом з його численними модифікаціями є поширеним і ефективним методомпошуку оптимуму досліджуваних об'єктів. Недоліком градієнтного пошуку (і розглянутих вище методів) і те, що з його використанні можна знайти лише локальний екстремум функції. Для пошуку інших локальних екстремумівнеобхідно шукати з інших початкових точок. Так само швидкість збіжності градієнтних методівістотно залежить також від точності обчислень градієнта. Втрата точності, а це зазвичай відбувається в околиці точок мінімуму або в яру, може взагалі порушити збіжність процесу градієнтного спуску. Методика розрахунку 1 крок:Визначення аналітичних виразів (у символьному вигляді) для обчислення градієнта функції 2 крок: Задаємо початкове наближення 3 крок:Визначається необхідність рестарту алгоритмічної процедури для обнулення останнього напряму пошуку. В результаті рестарту пошук здійснюється заново у напрямку якнайшвидшого спуску.
.
f(x[k]-a k f'(x[k]))
= f(x[k] - af"(x[k]))
.
j (a) = f(x[k]- af"(x[k]))
.
,
.
- Це значення аргументу функції (керовані параметри) на речовій області.називається вектор, проекціями якого на координатні осі є приватні похідні функції за координатами:
суворо ортогональний до поверхні, яке напрям показує напрям якнайшвидшого зростання функції, а протилежне напрям (антиградіент), відповідно, показує напрям якнайшвидшого зменшення функції.
- модуль градієнта визначає швидкість зростання або зменшення функції в напрямку градієнта або антиградієнта:
