Градієнтні методи оптимізації

Головна | Про нас | Зворотній зв'язок

Алгоритм методу полягає в знаходженні осьового напрямку, уздовж якого цільова функція зменшується найбільш сильно (при пошуку мінімуму). Розглянемо задачу безумовної оптимізації

Для визначення осьового напрямку в початковій точці пошуку з області визначаються похідні. . по всіх незалежних змінних. Вісьовому напрямку відповідає найбільша за модулем похідна.

Нехай - осьовий напрямок, тобто .

Якщо знак похідної негативний, функція спадає в напрямку осі, якщо позитивний - в зворотному напрямку:

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

Цю процедуру повторюють до тих пір, поки не досягається оптимальна точка, при русі з якої з будь-якого осьового напрямку подальшого зменшення не відбувається. На практиці критерієм закінчення пошуку служить умова

яке при крок до ідеального умова рівності нулю похідних в точці екстремуму. Природно умова (3.7) може бути використано тільки в тому випадку, якщо оптимум лежить всередині допустимої області зміни незалежних змінних. Якщо ж оптимум потрапляє на кордон області. критерій типу (3.7) непридатний і замість нього слід застосовувати позитивності всіх похідних по допустимим осьовим напрямками.

Алгоритм спуску для обраного осьового напрямку може бути записаний так

де-значення варьируемой змінної на кожному кроці спуску;

- величина k + 1 кроку, яка може змінюватися в залежності від номера кроку:

- функція знака z;

- вектор точки, в якій останній раз проводилося обчислення похідних;

Знак "+" в алгоритмі (3.8) приймається при пошуку max I, а знак "-" - при пошуку min I.Чем менше крок h. тим більше кількість обчислень на шляху руху до оптимуму. Але при занадто великій величині h поблизу оптимуму може виникнути зациклення процесу пошуку. Поблизу оптимуму необхідно, щоб виконувалася умова h

Найпростіший алгоритм зміни кроку h полягає в наступному. На початку спуску задається крок. рівний наприклад, 10% від діапазону d; зміни з цим кроком проводиться спуск за обраним напрямом до тез пір, поки виконується умова для двох наступних обчислень

При порушенні умови на будь-якому етапі напрямок спуску на осі змінюється на протилежне і спуск триває з останньої точки зі зменшеною вдвічі величиною кроку.

Формальна запис цього алгоритму наступна:

В результаті використання такої стратегії ша спуску буде зменшаться в районі оптимуму за даним напрямком та пошук у напрямку можна припинити, коли стане менше E.

Після цього знаходиться нове осьовий напрямок початковий крок для подальшого спуску, зазвичай менший пройденого вздовж попереднього осьового напрямку. Характер руху в оптимумі в даному методі показаний на малюнку 3.4.

Малюнок 3.5 - Траєкторія руху до оптимуму в методі релаксації

Поліпшення алгоритму пошуку за цим методом може бути досягнуто шляхом застосування методів однопараметричній оптимізації. При цьому може бути запропонована схема рішення задачі:

Крок 1. - осьовий напрямок,