5.3. Методи нелінійного програмування

Методи нелінійного програмування розподіляють на такі класи: градієнтні, безградієнтні, випадкового пошуку.

Градієнтні методи використовують, як правило, коли пошук ведеться на моделі, а інші – під час пошуку на об’єкті.

В основі градієнтних методів лежить аналіз і обчислення похідної цільової функції I(u). Найбільше поширення серед градієнтних методів отримали три методи: релаксації, градієнта і найшвидшого спуску. У методі релаксації пошук ведуть за осьовими напрямками, на яких змінюється тільки одна складова вектора управлінь, тому цей метод вимагає найменших обчислювальних витрат порівняно з іншими градієнтними методами і найбільшого часу пошуку. У методі градієнта напрям пошуку визначає градієнт, тому час пошуку тут найменший, а обчислювальні витрати найбільші. У методі найшвидшого спуску на початку напрям руху визначає градієнт, але далі напрям руху не змінюється до знаходження екстремуму за цим напрямком. Тому за обчислювальними витратами і часом пошуку цей метод займає середню позицію.

Спільні недоліки градієнтних методів:

1. вони виявляють тільки локальний екстремум;

2. можливе «застрявання» процедури пошуку у будь-якій точці обмеження типу нерівностей цільової функції чи в будь-якій точці «яру» цільової функції, особливо коли напрямок «ярів» не співпадає з осьовими лініями;

3. процедура пошуку не ефективна у випадку, коли пошук ведеться безпосередньо на об’єкті.

У безградієнтних методах пошуку використовують інформацію, отриману не під час аналізу похідних, а від порівняння значення критерію оптимізації (КО), визначеного на двох послідовних кроках. Найчастіше використовують такі методи багатовимірного (з кількома вхідними змінними) безградієнтного пошуку: покоординатного спуску (Гаусса-Зейделя), сканування (перебору) чи симплексний.

Метод Гаусса-Зейделя є безградієнтним аналогом методу релаксації, відмінність якого полягає в тому, що на кожному кроці аналізують не знак похідної, а значення КО. Метод Гаусса-Зейделя має також недоліки, як і метод релаксації, однак потребує менше обчислень за рахунок відсутності розрахунків похідної цільової функції.

Метод сканування (англ. scan – поле зору) полягає в послідовному перегляді значень КО в наперед обраних точках поверхні відгуку цільової функції, причому точність методу визначається тим, як щільно розташовані вибрані точки. Основна перевага методу – це можливість визначення глобального критерію незалежно від виду поверхні відгуку цільової функції. Недолік – велика кількість обчислень.

Симплексний метод полягає у визначенні КО біля вершин випуклого багатогранника – симплекса, під яким у n-мірному просторі розуміють багатогранник, що має n+1 вершин. У 2-мірному просторі – це трикутник, у 3-мірному – піраміда. У процесі руху виключають вершини симплексів із найбільшими значеннями цільової функції (під час пошуку мінімуму) і на протилежній грані будують новий симплекс, що відрізняється від попереднього розташуванням тільки однієї вершини. Цей метод є безградієнтним аналогом методу градієнта. Його недоліки співпадають з недоліками методу градієнта за винятком того, що в цьому випадку, по-перше, не треба розраховувати часткові похідні і градієнт, а, по-друге, його реалізація не потребує істотного збільшення обчислювальних витрат із збільшенням розмірності задачі [1, С. 28-30].