Градієнтні методи. Огляд градієнтних методів у задачах математичної оптимізації

У основі методу лежить така ітераційна модифікація формули

x k +1 = x k + ak s (x k),

x k + 1 = x k - a k F (x k), де

a – заданий позитивний коефіцієнт;

Ñ ​​f(x k) - градієнт цільової функціїпершого порядку.

Недоліки:

необхідність вибору відповідного значення ;

повільна збіжність до точки мінімуму через малість f(x k) в околиці цієї точки.

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

Вільний від першого недоліку найпростішого градієнтного методу, т.к. a k обчислюється шляхом розв'язання задачі мінімізації Ñ f(x k) вздовж напрямку Ñ f(x k) за допомогою одного з методів одновимірної оптимізації x k+1 = x k - a k f (x k).

Цей метод іноді називають методом Коші.

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

Метод сполучених напрямків

Загальне завдання нелінійного програмування без обмежень зводиться до такого: мінімізувати f(x), x E n , де f(x) є цільовою функцією. При розв'язанні цього завдання ми використовуємо методи мінімізації, які призводять до стаціонарної точки f(x), яка визначається рівнянням f(x *)=0. Метод сполучених напрямів відноситься до методів мінімізації без обмежень, що використовують похідні. Завдання: мінімізувати f(x), x E n де f(x) є цільовою функцією n незалежних змінних. Важливою особливістює швидка збіжність за рахунок того, що при виборі напрямку використовується матриця Гессе, яка описує область топології поверхні відгуку. Зокрема, якщо цільова функція квадратична, можна отримати точку мінімуму лише за кількість кроків, рівне розмірності завдання.

Для застосування методу на практиці його необхідно доповнити процедурами перевірки збіжності та лінійної незалежності системи напрямків. Методи другого порядку

Метод Ньютона

Послідовне застосування схеми квадратичної апроксимації призводить до реалізації оптимізаційного методу Ньютона за формулою

x k +1 = x k - 2 f (x k -1) Ñ f (x k).

Недоліком методу Ньютона є недостатня надійність при оптимізації не квадратичних цільових функцій. Тому його часто модифікують:

x k +1 = x k - a k Ñ 2 f(x k -1) Ñ f(x k), де

a k - параметр, що вибирається таким чином, щоб f(x k+1) min.

2. Знаходження екстремуму функції без обмеження

Дано деяку функцію f(х) на відкритому інтервалі (а, в) зміни аргументу х. Припускаємо, що exst всередині цього інтервалу існує (треба сказати, що в загальному випадку математично заздалегідь це стверджувати не можуть; проте в технічних додатках дуже часто наявність exst всередині деякого інтервалу зміни інтервалу зміни аргументу може бути передбачено фізичними міркуваннями).

Визначення exst. Функція f(x) задана на інтервалі (а, в) має в точці x * max (min), якщо цю точку можна оточити таким інтервалом (x * -ε, x * +ε), що міститься в інтервалі (а, в) , що всім її точок х, що належать інтервалу (x * -ε, x * +ε), виконується нерівність:

f(x) ≤ f(x *) → для max

f(x) ≥ f(x *) → для min

Це визначення не накладає жодних обмежень клас функцій f(x), що, звісно, ​​дуже цінно.

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

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

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

* У разі має місце min, а при →max. Нарешті, якщо при х = х 0 то використання 2-ой похідної не допомагає і потрібно скористатися, наприклад, визначенням exst.

При розв'язанні задачі I необхідні умови exst (тобто теорема Ферма) використовують дуже часто.

Якщо рівняння exst має речові корені, то точки, що відповідають цим корінням, є підозрілими на exst (але не обов'язково самими екстремумами, бо маємо справу з необхідними, а не з необхідними та достатніми умовами). Так, наприклад, у точці перегину Х п має місце, проте, як відомо, це не екстремум.

Зауважимо ще, що:

з необхідних умовне можна сказати, який вид екстремуму знайдено max або min: визначення цього потрібні додаткові дослідження;

із необхідних умов не можна визначити, глобальний це екстремум чи локальний.

Тому, коли знаходять точки підозрілі на exst, їх додатково досліджують, наприклад, на основі визначення exst або 2 похідної.

Лекція 6

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Схема розв'язання.

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

3. Вибір кроку h.

x(k+1) = x(k)

"-" - якщо min.

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

Якщо
, Рішення знайдено;

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

приклад. F(x) = -6x 1 + 2x 1 2 – 2x 1 x 2 + 2x 2 2
min,

x 1 +x 2 2, x 1 0, x 2 0,= 0,1.

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

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

Схема розв'язання.

1. Визначення х 0 = (х 1 x 2 ... x n),

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

та F(x 0), k = 0.

2. Визначення grad F(x0) або –gradF(x0).

3. Вибір кроку h.

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

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

"-" - якщо min.

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) = 3x 1 – 0,2x 1 2 + x 2 - 0,2x 2 2
max,

x 1 + x 2 7, x 1 0,

x 1 + 2x 2 10, x 2 0.

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

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

Схема розв'язання.

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

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

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

(min - "-"; max - "+").

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

5. Визначення кроку обчислень x (k +1) = x (k) + (k) (z(k)-x(k)), де (k) – крок, коефіцієнт, 0 1. (k) вибирається так, щоб значення функції F(x) було max (min) у точці х (k +1). Для цього вирішують рівняння
і вибирають найменший (найбільший) з коріння, але 0 1.

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

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

Якщо ні, перехід до п. 2.

приклад. F(x) = 4x1 + 10x2-x12-x22
max,

x 1 +x 2 4, x 1 0,

x 2 2, x 2 0.

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

Нехай необхідно знайти F(x 1 x 2 ... x n)
max(min),

g i (x 1, x 2, ..., x n) b i , i =
, x j 0, j = .

Функції F і g i – опуклі чи увігнуті.

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

H(x) =
,

де

- Деякі позитивні Const.

Примітка:

Чим менше тим швидше знаходиться рішення, однак, точність знижується;

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

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

Схема розв'язання.

1. Визначення початкової точки х 0 = (х 1 ,x 2 ,…,x n), F(x 0) і k = 0.

2. Вибирають крок обчислень h.

3. Визначають приватні похідні і .

4. Визначають координати наступної точки за формулою:

x j (k +1)
.

5. Якщо x (k+1) Допустимої області, перевіряють:

а якщо
- Рішення знайдено, якщо ні – перехід до п. 2.

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

Якщо x (k+1) Допустимої області, задають нове значення та переходять до п. 4.

приклад. F(x) = – x 1 2 – x 2 2
max,

(x 1 -5) 2 + (x 2 -5) 2 8, x 1 0, x 2 0.

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

Існують різні способи вибору кроку кожен із яких задає певний варіант градієнтного методу.

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

Розглянемо функцію однієї скалярної змінної і виберемо в якості значення, для якого виконується рівність

Цей метод, запропонований 1845 р. О. Коші, прийнято тепер називати методом якнайшвидшого спуску.

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

Зазначимо, що з кожної ітерації вибір кроку передбачає вирішення завдання одномірної мінімізації (10.23). Іноді цю операцію вдається виконати аналітично, наприклад, для квадратичної функції.

Застосуємо метод якнайшвидшого спуску для мінімізації квадратичної функції

із симетричною позитивно визначеною матрицею А.

Відповідно до формули (10.8), у цьому випадку Тому формула (10.22) виглядає тут так:

Зауважимо, що

Ця функція є квадратичною функцією параметра і досягає мінімуму при такому значенні для якого

Таким чином, стосовно мінімізації квадратичної

функції (10.24) метод якнайшвидшого спуску еквівалентний розрахунку за формулою (10.25), де

Зауваження 1. Оскільки точка мінімуму функції (10.24) збігається з рішенням системи метод якнайшвидшого спуску (10.25), (10.26) може застосовуватися і як ітераційний метод розв'язання систем лінійних рівнянь алгебри з симетричними позитивно визначеними матрицями.

Зауваження 2. Зазначимо, що відношення Релея (див. § 8.1).

Приклад 10.1. Застосуємо метод якнайшвидшого спуску для мінімізації квадратичної функції

Тому точне значення точки мінімуму нам заздалегідь відомо. Запишемо цю функцію у вигляді (10.24), де матриця та вектор Як неважко бачити,

Візьмемо початкове наближення і вести обчислення за формулами (10.25), (10.26).

І ітерація.

ІІ ітерація.

Можна показати, що для всіх на ітерації буде отримано значення

Зауважимо, що таким чином,

послідовність отримана методом якнайшвидшого спуску, сходиться зі швидкістю геометричної прогресії, знаменник якої

На рис. 10.5 зображено саме траєкторію спуску, яка була отримана в даному прикладі.

Для мінімізації квадратичної функції справедливий наступний загальний результат .

Теорема 10.1. Нехай А – симетрична позитивно визначена матриця та мінімізується квадратична функція (10.24). Тоді за будь-якого вибору початкової наближення метод найшвидшого спуску (10.25), (10.26) сходиться і вірна наступна оцінка похибки:

Тут і Ладо – мінімальне та максимальне власні значення матриці А.

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

Приклад 10.2. Застосування методу якнайшвидшого спуску для мінімізації квадратичної функції при початковому наближенні дає послідовність наближень, де Траєкторія спуску зображена на рис. 10.6.

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

ніж у попередньому примірю. Тому що тут і отриманий результат цілком узгоджується з оцінкою (10.27).

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

Зауваження 2. Для квадратичної цільової функції (10.24) розв'язання задачі одновимірної мінімізації (10.23) вдається знайти у вигляді простої явної формули (10.26). Однак для більшості інших нелінійних функцій цього зробити не можна і для обчислення методом якнайшвидшого спуску доводиться застосовувати чисельні методи одномірної мінімізації типу тих, що були розглянуті в попередньому розділі.

2. Проблема "ярів".

З проведеного вище обговорення випливає, що градієнтний метод сходиться досить швидко, якщо для мінімізованої функції поверхні рівня близькі до сфер (при лінії рівня близькі до кола). Для таких функцій і 1. Теорема 10.1, зауваження 1, а також результат прикладу 10.2 вказують на те, що швидкість збіжності різко падає при збільшенні величини. . У двовимірному випадку рельєф відповідної поверхні нагадує рельєф місцевості з яром (рис. 10.7). Тому такі функції прийнято називати яружними. Уздовж напрямів, що характеризують "дно яру", ярова функція змінюється незначно, а в інших напрямках, що характеризують "схил яра", відбувається різка зміна функції.

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

Для прискорення збіжності градієнтного методу при мінімізації яружних функцій розроблено низку спеціальних "яружних" методів. Дамо уявлення про один із найпростіших прийомів. З двох близьких початкових точок здійснюють градієнтний спуск на "дно яру". Через знайдені точки проводять пряму, вздовж якої роблять великий "яружний" крок (рис. 10.8). Зі знайденої таким чином точки знову роблять один крок градієнтного спуску в точку Потім роблять другий "яружний" крок уздовж прямої, що проходить через точки . В результаті рух уздовж "дна яру" до точки мінімуму суттєво прискорюється.

Більш детальну інформацію про проблему "ярів" та "яружних" методах можна знайти, наприклад, у , .

3. Інші підходи щодо визначення кроку спуску.

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

Також можна шукати не найкращу точку в напрямку градієнта, а якусь краще за поточну.

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

Опис [ | ]

Удосконалення[ | ]

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

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

Застосування у штучних нейронних мережах[ | ]

Метод градієнтного спуску з деякою модифікацією широко застосовується для навчання перцептрону і теоретично штучних нейронних мереж відомий як метод зворотного поширення помилки. При навчанні нейромережі типу персептрон потрібно змінювати вагові коефіцієнти мережі так, щоб мінімізувати середню помилку на виході нейронної мережі при подачі на вхід послідовності навчальних вхідних даних. Формально, щоб зробити всього один крок за методом градієнтного спуску (зробити лише одну зміну параметрів мережі), необхідно подати на вхід мережі послідовно абсолютно весь набір навчальних даних, для кожного об'єкта навчальних даних обчислити помилку та розрахувати необхідну корекцію коефіцієнтів мережі (але не робити цю корекцію), і після подачі всіх даних розрахувати суму в коригуванні кожного коефіцієнта мережі (сума градієнтів) і зробити корекцію коефіцієнтів «на крок». Очевидно, що при великому наборі навчальних даних алгоритм працюватиме вкрай повільно, тому на практиці часто здійснюють коригування коефіцієнтів мережі після кожного елемента навчання, де значення градієнта апроксимуються градієнтом функції вартості, обчисленому тільки на одному елементі навчання. Такий метод називають стохастичним градієнтним спуском або оперативним градієнтним спуском . Стохастичний градієнтний спуск є одним із форм стохастичного наближення. Теорія стохастичних наближень дає умови збіжності способу стохастичного градієнтного спуску.

Посилання [ | ]

• J. Mathews.Модули для Steepest Descent або Gradient Method. (недоступне посилання)

Література [ | ]

• Акуліч І. Л.Математичне програмування в прикладах та задачах. - М.: Вища школа, 1986. - С. 298-310.
• Гілл Ф., Мюррей У., Райт М.Практична оптимізація = Practical Optimization. - М.: Світ, 1985.
• Коршунов Ю. М., Коршунов Ю. М.Математичні засади кібернетики. - М.: Вища школа, 1972.
• Максимов Ю. А., Філіповська Є. А.Алгоритми розв'язання задач нелінійного програмування. - М.: МІФІ, 1982.
• Максимов Ю. А.Алгоритми лінійного та дискретного програмування. - М.: МІФІ, 1980.
• Корн Р., Корн Т.Довідник з математики для науковців та інженерів. - М.: Наука, 1970. - С. 575-576.
• С. Ю. Городецький, В. А. Гришагін.Нелінійне програмування та багатоекстремальна оптимізація. – Нижній Новгород: Видавництво Нижегородського Університету, 2007. – С. 357-363.

Лекція №8

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

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

Розглянемо завдання максимізації нелінійної диференційованої функції f(x). Суть градієнтного пошуку точки максимуму х* Досить проста: треба взяти довільну точку х 0 і за допомогою градієнта , обчисленого в цій точці, визначити напрямок, в якому f(х) зростає з найбільшою швидкістю (рис. 7.4),

а потім, зробивши невеликий крок у знайденому напрямку, перейти до нової точки x i. Потім знову визначити найкращий напрямок для переходу до чергової точки х 2 і т. д. На рис. 7.4 пошукова траєкторія є ламаною х 0 , x 1 , х 2 ... Отже, треба побудувати послідовність точок х 0 , x 1 , х 2 ,...,x k , ... так, щоб вона сходилася до точки максимуму х*, тобто для точок послідовності виконувались умови

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

Рух із точки х kу нову точку x k+1здійснюється по прямій, що проходить через точку х kі має рівняння

(7.29)

де k - числовий параметр, від якого залежить величина кроку. Як тільки значення параметра в рівнянні (7.29) вибрано: k = k 0 , так стає визначеною чергова точка на пошуковій ламаною.

Градієнтні методи відрізняються один від одного способом вибору величини кроку - значення k 0 параметра k. Можна, наприклад, рухатися з точки в точку з постійним кроком k = λ, тобто при будь-якому k

Якщо при цьому виявиться, що , то слід повернутися в точку і зменшити значення параметра, наприклад, до λ /2.

Іноді величина кроку береться до пропорційної модулю градієнта.

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

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

Поширеним є варіант градієнтного пошуку, який називається методом якнайшвидшого підйому. Суть його наступного. Після визначення градієнта у точці х дорух вздовж прямої виробляється до точки х до+ 1 , в якій досягається максимальне значення функції f(х) у напрямку градієнта . Потім у цій точці знову визначається градієнт, і рух відбувається по прямій у напрямку нового градієнта до точки х до+ 2 , в якій досягається максимальне в цьому напрямку значення f(x). Рух триває доти, доки не буде досягнуто крапки х*, що відповідає найбільшому значенню цільової функції f(x). На рис. 7.5 наведено схему руху до оптимальної точки х* шляхом якнайшвидшого підйому. У цьому випадку напрямок градієнта у точці х kє дотичним до лінії рівня поверхні f(х) у точці х до+ 1 , отже, градієнт у точці х до+ 1 ортогональний градієнту (порівняйте з рис. 7.4).

Переміщення з точки х kу точку супроводжується зростанням функції f(x) на величину

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

(7.31)

Знайдемо вираз для похідної, диференціюючи рівність (7.30) як складну функцію:

Підставляючи цей результат у рівність (7.31), отримуємо

Ця рівність має просте геометричне тлумачення: градієнт у черговій точці х до+ 1 ортогональний градієнту в попередній точці х до.

побудовані лінії рівня цієї поверхні. З цією метою рівняння наведено до виду ( x 1 -1) 2 + (x 2 -2) 2 = 5-0,5 f, з якого ясно, що лініями перетину параболоїда з площинами, паралельними площині x 1 Про x 2 (лініями рівня), є кола радіусом . При f=-150, -100, -50 їх радіуси рівні відповідно , а загальний центр знаходиться у точці (1; 2). Знаходимо градієнт цієї функції:

I крок. Обчислюємо:

На рис. 7.6 з початком у точці х 0 =(5; 10) побудований вектор 1/16, що вказує напрямок якнайшвидшого зростання функції в точці х 0 . На цьому напрямку розташована наступна точка. У цій точці.

Використовуючи умову (7.32), отримуємо

або 1-4 = 0, звідки = 1/4. Оскільки, то знайдене значення є точкою максимуму. Знаходимо x 1 =(5-16/4; 10-32/4)=(1; 2).

II крок. Початкова точка для другого кроку x 1 = (1; 2). Обчислюємо =(-4∙1+4; -4∙2+8)=(0; 0). Отже, х 1 = (1; 2) є стаціонарною точкою. Але оскільки ця функція увігнута, то знайденої точці (1; 2) досягається глобальний максимум.

Завдання з лінійними обмеженнями. Відразу ж відзначимо, що якщо цільова функція f(х) у задачі з обмеженнями має єдиний екстремум і він знаходиться всередині допустимої області, то для пошуку екстремальної точки х* застосовується викладена вище методика без будь-яких змін.

Розглянемо задачу опуклого програмування з лінійними обмеженнями:

(7.34)

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

Почнемо з геометричної ілюстрації процесу розв'язання задачі (рис. 7.7). Нехай початкова точка х 0 розташована всередині припустимої області. З точки х 0 можна рухатися в напрямку градієнта , поки f(x) не досягне максимуму. У нашому випадку f(x) весь час зростає, тому зупинитися треба в точці х, на граничній прямій. Як видно з малюнка, далі рухатися у напрямку градієнта не можна, оскільки вийдемо з допустимої області. Тому треба знайти інший напрямок переміщення, який, з одного боку, не виводить із допустимої області, а з іншого – забезпечує найбільше зростання f(x). Такий напрямок визначить вектор , що становить вектор найменший гострий кут в порівнянні з будь-яким іншим вектором, що виходить з точки x iі лежать у допустимій області. Аналітично такий вектор знайдеться за умови максимізації скалярного твору . В даному випадку вектор, що вказує найвигідніший напрямок, збігається з граничною прямою.

Таким чином, на наступному кроці рухатися треба по граничній прямій доти, доки зростає f(x); у нашому випадку - до точки х 2 . З малюнка видно, що далі слід переміщатися у напрямку вектора , що з умови максимізації скалярного твору , Т. е. по граничній прямий. Рух закінчується у точці х 3 оскільки в цій точці завершується оптимізаційний пошук, бо в ній функція f(х) має локальний максимум. Через увігнутість у цій точці f(х) Досягає також глобального максимуму в допустимій області. Градієнт у точці максимуму х 3 =х* Складає тупий кут з будь-яким вектором з допустимої області, що проходить через х 3тому скалярний твір буде негативним для будь-якого допустимого. r kкрім r 3 , спрямованого по граничній прямій. Для нього скалярний добуток =0, так як і взаємно перпендикулярні (гранична пряма стосується лінії рівня поверхні f(х), що проходить через точку максимуму х*). Ця рівність і є аналітичною ознакою того, що в точці х 3 функція f(x) досягла максимуму.

Розглянемо тепер аналітичне розв'язання задачі (7.33) – (7.35). Якщо оптимізаційний пошук починається з точки, що лежить у допустимій області (всі обмеження задачі виконуються як суворі нерівності), то переміщатися слід у напрямку градієнта так, як встановлено вище. Однак тепер вибір λ kу рівнянні (7.29) ускладнюється вимогою, щоб чергова точка залишалася у допустимій області. Це означає, що її координати повинні відповідати обмеженням (7.34), (7.35), тобто повинні виконуватися нерівності:

(7.36)

Вирішуючи систему лінійних нерівностей (7.36), знаходимо відрізок допустимих значень параметра λ k, При яких точка х k +1 належатиме допустимій області.

Значення λ k *, Яке визначається в результаті рішення рівняння (7.32):

За якого f(x) має локальний максимум по λ kу напрямі, має належати відрізку . Якщо ж знайдене значення λ kвиходить за межі зазначеного відрізка, то як λ k *приймається. У цьому випадку чергова точка пошукової траєкторії виявляється на граничній гіперплощині, що відповідає тій нерівності системи (7.36), за якою при вирішенні системи отримана права кінцева точка . відрізка допустимих значень параметра λ k.

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

при обмеженнях

для тих t, за яких

де .

В результаті розв'язання задачі (7.37) - (7.40) буде знайдено вектор , що становить з градієнтом найменший гострий кут.

Умова (7.39) говорить про те, що точка належить межі допустимої області, а умова (7.38) означає, що переміщення з вектором буде направлено всередину допустимої області або по її кордоні. Умова нормалізації (7.40) необхідна для обмеження величини , тому що в іншому випадку значення цільової функції (7.37) можна зробити як завгодно великим Відомі різні форми умов нормалізації, і в залежності від цього завдання (7.37) - (7.40) може бути лінійною або нелінійною .

Після визначення напрямку знаходиться значення λ k *для наступної точки пошукової траєкторії. При цьому використовується необхідна умова екстремуму у формі, аналогічній до рівняння (7.32), але із заміною на вектор , тобто.

(7.41)

Оптимізаційний пошук припиняється, коли досягнуто точки x k *, в якій .

Приклад 7.5.Максимізувати функцію при обмеженнях

Рішення.Для наочного подання процесу оптимізації супроводжуватимемо його графічною ілюстрацією. На рис 7.8 зображено кілька ліній рівня даної поверхні та допустима область ОАВС, у якій слід знайти точку х*, що доставляє максимум цієї функції (див. приклад 7 4).

Почнемо оптимізаційний пошук, наприклад, з точки х 0 =(4, 2,5), що лежить на граничній прямій АВ x 1 +4x 2 = 14. При цьому f(х 0)=4,55.

Знайдемо значення градієнта

у точці x 0 . Крім того, і по малюнку видно, що через допустиму область проходять лінії рівня з позначками вищими, ніж f(x 0) = 4,55. Словом, треба шукати напрямок r 0 =(r 01 , r 02) переміщення до наступної точки x 1 ближчу до оптимальної. З цією метою розв'язуємо задачу (7.37) – (7.40) максимізації функції при обмеженнях

Оскільки точка х 0 розташовується тільки на одній (першій) граничній прямій ( i=1) x 1 +4x 2 = 14, то умова (7.38) записується у формі рівності.

Система обмежувальних рівнянь цього завдання має лише два рішення (-0,9700; 0,2425) та (0,9700;-0,2425) Безпосередньою підстановкою їх у функцію T 0 встановлюємо, що максимум Т 0 відмінний від нуля і досягається при вирішенні (-0,9700; 0,2425) Таким чином, переміщатися з х 0 потрібно за напрямом вектора r 0 = (0,9700; 0,2425), тобто по граничній прямий ВА.

Для визначення координат наступної точки x 1 =(x 11 ; x 12)

(7.42)

необхідно знайти значення параметра , у якому функція f(x) у точці x

звідки =2,0618. У цьому =-0,3999<0. Значит,=2,0618. По формуле (7.42) находим координаты новой точки х 1 (2; 3).

Якщо продовжити оптимізаційний пошук, то при вирішенні чергової допоміжної задачі (7.37)-(7.40) буде встановлено, що Т 1 = , а це свідчить, що точка x 1 є точкою максимуму х* цільової функції у допустимій області. Це видно і з малюнка в точці x 1 одна з ліній рівня стосується межі допустимої області. Отже, точка х 1 є точкою максимуму х*. При цьому f max = f(x*)=5,4.

Завдання із нелінійними обмеженнями. Якщо в завданнях з лінійними обмеженнями рух по граничним прямим виявляється можливим і навіть доцільним, то при нелінійних обмеженнях, що визначають опуклу область, будь-яке як завгодно мале переміщення з граничної точки може відразу вивести за межі області допустимих рішень, і виникне необхідність повернення в допустиму область (Мал. 7.9). Подібна ситуація характерна для завдань, у яких екстремум функції f(x) досягається на межі області. У зв'язку з цим застосовуються різні

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