Використовуючи градієнтні методи, можна знайти, рішення будь-якої задачі нелінійного програмування. Застосування цих методів в загальному випадку дозволяє знайти точку локального екстремуму. Тому більш доцільно використовувати їх для знаходження рішення задач опуклого программірова-ня. Процес знаходження рішення задачі за допомогою градієнтних методів
полягає в тому, що починаючи з деякої точки здійснюється послідовно-вательного перехід до деяких інших точок до тих пір, поки не буде знайдено прийнятне рішення вихідної задачі. Градієнтні методи можуть бути поділені на дві групи.
До першої групи належать методи, при використанні яких дослі-дуємо точки не виходять за межі області допустимих рішень задачі. В даному випадку найбільш поширеним є метод Франка - Вульфа. До другої - методи, при використанні яких досліджувані точки можуть як належати, так і не належати області припустимих рішень. Од-нако в результаті реалізації ітераційного процесу знаходиться точка об-ласті допустимих рішень, що визначає прийнятне рішення. Найбільш часто використовуються метод штрафних функцій і метод Ерроу - Гурвіца. При знаходженні рішення задачі градієнтними методами ите-ротаційний процес триває до тих пір, поки градієнт функції в черговій крапці не стане рівним нулю або ж поки не виконається нерівність
. де (точність отриманого рішення).
Метод Франка - Вульфа. Нехай потрібно знайти максимальне зна-ня увігнутою функції
Обмеження містять тільки лінійні нерівності. Ця особливість є основою для заміни в околиці досліджуваної точки нелінійної цільової функції лінійною, в результаті чого рішення вихідної завдання сво-диться до послідовного розв'язування задач лінійного програмування.
Процес знаходження рішення починають з визначення точки, принад-лежить області допустимих рішень. Нехай це точка. Обчислюють в цій точці градієнт функції (9):
будують лінійну функцію
Знаходять максимум функції (12) при обмеженнях (10) і (11). Нехай рішення даної задачі визначається точкою. За нове допустиме рішення вихідної задачі приймають координати точки. які знаходять за формулами
де - деяке число, зване кроком обчислень. За приймають найменший корінь рівняння або вибирають довільно, якщо він не належить інтервалу (0; 1).
Метод штрафних функцій. Розглянемо задачу нелінійного програмування (6) - (8), де - опуклі функції.
Замість того. щоб вирішувати цю задачу, знаходять максимум функції
де визначається системою обмежень і називається штрафний функцією. Останню можна побудувати різними способами. Найбільш часто вона має вигляд
а - деякі постійні числа, що представляють собою вагові ко-коефіцієнти.
Використовуючи штрафну функцію, послідовно переходять від однієї точки в іншу до тих пір, поки не отримають прийнятне рішення. Координати подальшої точки знаходять за формулою
де - крок обчислень.
Ітераційний процес зазвичай починають при порівняно малих зна-ченіях і, продовжуючи його, ці значення поступово збільшують.
Метод Ерроу - Гурвіца. При знаходженні рішення задачі нелінійно-го програмування методом штрафних функцій значення. вибирають довільно, що призводить до значних коливань віддаленості визна-ється точок від області допустимих рішень. Цей недолік усувається при вирішенні задачі методом Ерроу - Гурвіца, згідно з яким на оче-редную кроці числа знаходять за формулою
В якості вихідних значень беруть довільні невід'ємні числа.