Лекція 6 (градієнтні методи)

Градієнтні методи розв'язання задач нелінійного програмування.

Питання: 1. Загальна характеристика методів.

2. Метод градієнта.

3. Метод найшвидшого спуску.

4. Метод Франка-Фулфа.

5. Метод штрафних функцій.

1. Загальна характеристика методів.

Градієнтні методи являють собою наближені (ітераційні) методи розв'язання задачі нелінійного програмування і дозволяють вирішити практично будь-яке завдання. Однак при цьому визначається локальний екстремум. Тому доцільно застосовувати ці методи для вирішення задач опуклого програмування, в яких кожен локальний екстремум є і глобальним. Процес рішення задачі полягає в тому, що, починаючи з певної точки х (початкової), здійснюється послідовний перехід в напрямку gradF (x), якщо визначається точка максимуму, і -gradF (x) (антіградіента), якщо визначається точка мінімуму, до точки , що є вирішенням завдання. При цьому ця точка може виявитися як всередині області допустимих значень, так і на її кордоні.

Градієнтні методи можна розділити на два класи (групи). До першої групи належать методи, в яких всі досліджувані точки належать допустимої області. До таких методів належать: метод градієнта, найшвидшого спуску, Франка-Вулфа та ін. До другої групи належать методи, в яких досліджувані точки можуть і не належати допустимої області. Загальним з таких методів є метод штрафних функцій. Всі методи штрафних функцій відрізняються один від одного способом визначення «штрафу».

Основним поняттям, використовуваним у всіх градієнтних методах, є поняття градієнта функції, як напрямки найшвидшого зростання функції.

При визначенні рішення градієнтними методами ітераційний процес триває до тих пір, поки:

- або grad F (x *) = 0, (точне рішення);

де

- дві послідовні точки,

- мале число, що характеризує точність рішення.

2. Метод градієнта.

Уявімо людину, що стоїть на схилі яру, якому необхідно спуститися вниз (на дно). Найбільш природним, здається, напрямок в сторону найбільшої крутизни спуску, тобто напрямок (-grad F (x)). Отримана при цьому стратегія, яка називається градієнтним методом. являє собою послідовність кроків, кожен з яких містить дві операції:

а) визначення напрямку найбільшої крутизни спуску (підйому);

б) переміщення в обраному напрямку на деякий крок.

Правильний вибір кроку має істотне значення. Чим крок менше, тим точніше результат, але більше обчислень. Різні модифікації градієнтного методу і складаються у використанні різних способів визначення кроку. Якщо на якомусь етапі значення F (x) не зменшилася, це означає, що точку мінімуму «проскочили», в цьому випадку необхідно повернутися до попередньої точки і зменшити крок, наприклад, удвічі.

що належить допустимої області

2. Визначення grad F (x 0) або -gradF (x 0).

4. Визначення наступної точки по формулі

x (k + 1) = x (k)

h grad F (x (k)), «+» - якщо max,

5. Визначення F (x (k +1)) і:

- якщо, рішення знайдено;

- якщо немає, то перехід до п. 2.

Зауваження. Якщо grad F (x (k)) = 0, то рішення буде точним.

Приклад. F (x) = -6x1 + 2x1 2 - 2x1 x2 + 2x2 2

min,

x1 + x2

2, x1

0, x2

= 0,1.

3. Метод найшвидшого спуску.

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

що належить допустимої області,

2. Визначення grad F (x 0) або -gradF (x 0).

4. Визначення наступної точки по формулі

x (k + 1) = x (k)

h grad F (x (k)), «+» - якщо max,

5. Визначення F (x (k +1)) і:

- якщо, рішення знайдено;

а) при пошуку min: - якщо F (x (k +1))

- якщо F (x (k +1))> F (x (k)) - перехід до п. 2;

б) при пошуку max: - есліF (x (k +1))> F (x (k)) - перехід до п. 4;

- якщо F (x (k +1))

Зауваження: 1. Якщо grad F (x (k)) = 0, то рішення буде точним.

2. Перевагою методу найшвидшого спуску є його простота і

скорочення розрахунків, так як grad F (x) обчислюється не в усіх точках, що

важливо для задач великої розмірності.

3. Недоліком є те, що кроки повинні бути малими, щоб не

пропустити точку оптимуму.

Приклад. F (x) = 3x1 - 0,2x1 2 + x2 - 0,2x2 2

max,

x1 + 2x2

10, x2

4. Метод Франка-Вулфа.

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

1. Визначення х 0 = (х1, x2, ..., xn), що належить допустимої області, і F (x 0), k = 0.

2. Визначення grad F (x (k)).

3. Будують функцію

4. Визначення max (min) f (x) при вихідних обмеженнях. Нехай це буде точка z (k).

5. Визначення кроку обчислень x (k +1) = x (k) +

(K) (z (k) -x (k)), де

(K) - крок, коефіцієнт, 0

(K) вибирається так, щоб значення функції F (x) було max (min) в точці х (k +1). Для цього вирішують рівняння

і вибирають найменший (найбільший) з коренів, але 0

6. Визначення F (x (k +1)) і перевіряють необхідність подальших обчислень:

- якщо або grad F (x (k +1)) = 0, то рішення знайдено;

- якщо немає, то перехід до п. 2.

Приклад. F (x) = 4x1 + 10x2 -x1 2 -x2 2

max,

5. Метод штрафних функцій.

Нехай необхідно знайти F (x1, x2, ..., xn)

max (min),

gi (x1. x2, ..., xn)

bi. i =

, xj

0, j =

Функції F і gi - опуклі або увігнуті.

Ідея методу штрафних функцій полягає в пошуку оптимального значення нової цільової функції Q (x) = F (x) + H (x), яка є сумою вихідної цільової функції і деякої функції H (x), яка визначається системою обмежень і званої штрафний функцією. Штрафні функції будують таким чином, щоб забезпечити або швидке повернення в допустиму область, або неможливість виходи з неї. Метод штрафних функцій зводить задачу на умовний екстремум до вирішення послідовності завдань на безумовний екстремум, що простіше. Існує безліч способів побудови штрафний функції. Найбільш часто вона має вигляд:

де