НОУ ІНТУЇТ | лекція | Однопараметрична (одномірна) оптимізація. Методи одновимірної оптимізації: метод дихотомії, метод Фібоначчі, метод "золотого перетину", метод Ньютона.

2. Метод Фібоначчі. Метод "золотого перетину"

Одним з методів однопараметричній оптимізації є метод Фібоначчі.

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

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

Покладемо х2-х1 = L і х3-х 2 = R, причому L> R, як показано на Мал. 9.3 , І ці значення будуть фіксовані, якщо відомі x1, x2 і х3. Якщо х4 знаходиться в інтервалі (х1; х2), то:

1. якщо f (x4) <f (x2), то новим інтервалом невизначеності буде (x1, x2) довжиною х2-х1 = L;
2. якщо f (х4)> f (x2), то новим інтервалом невизначеності буде (х4, х3) довжиною х3-х4.

Оскільки не відомо, яка з цих ситуацій буде мати місце, виберемо х4 таким чином, щоб мінімізувати найбільшу з довжин х3-х4 і х2-х1. Досягти цього можна, зробивши довжини х3 - х4 і х2 - х1 рівними тобто помістивши х4 всередині інтервалу симетрично відносно точки х2, вже лежить всередині інтервалу. Будь-яке інше положення точки х4 може привести до того, що отриманий інтервал буде більше L. Помістивши х4 симетрично щодо х2, ми нічим не ризикуємо в будь-якому випадку. Якщо виявиться, що можна виконати ще одне обчислення функції, то слід застосувати описану процедуру до інтервалу (х1, х2), в якому вже є значення функції, обчислене в точці х4, або до інтервалу (х4, х3), в якому вже є значення функції, обчислене в точці х2.

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

На n-му обчисленні n -ю точку слід помістити симетрично по відношенню до (n - 1) -й точці. Положення цієї останньої точки в принципі залежить від нас. Для того щоб отримати максимальне зменшення інтервалу на даному етапі, слід розділити навпіл попередній інтервал. Тоді точка х буде збігатися з точкою хn-1. Однак при цьому ми не отримуємо ніякої нової інформації. Зазвичай точки хn-1 і хn відстоять один від одного на достатній відстані, щоб визначити, в якій половині, лівої чи правої, знаходиться інтервал невизначеності. Вони поміщаються на відстані е / 2 по обидві сторони від середини відрізка Ln-1; можна самим задати величину е або вибрати цю величину рівної мінімально можливого відстані між двома точками.

Інтервал невизначеності матиме довжину Ln, отже, Ln-1 = 2Ln - е ( рис.9.4 , Нижня частина). На попередньому етапі точки хn-1 і хn-2 повинні бути поміщені симетрично всередині інтервалу Ln-2 на відстані Ln-2 від кінців цього інтервалу. Отже, Ln-2 = Ln-1 + Ln ( pіс.9.4 , Середня частина).

Зауваження. З малюнка ясно, що на передостанньому етапі хn-2 залишається в якості внутрішньої точки.

Аналогічно Ln-3 = Ln-2 + Ln-1 ( мал. 9.4 , верхня частина)

У загальному випадку Lj-1 = Lj + Lj + 1 при 1 <j <n.

Таким чином,

Якщо визначити послідовність чисел Фібоначчі наступним чином: F0 = 1, F1 = l, і Fk = Fk-1 + Fk-2 для k = 2, 3, ..., То

Якщо початковий інтервал (a; b) має довжину L = (b-а), то

Отже, провівши n обчислень функції, ми зменшимо початковий інтервал невизначеності в l / Fn разів у порівнянні з його початкової довжиною (нехтуючи е), і це - найкращий результат.

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

Після того як знайдено положення першої точки, числа Фібоначчі більше не потрібні. Використовується значення е може визначатися з практичних міркувань. Воно повинно бути менше L1 \ Fn + x, в іншому випадку ми будемо даремно витрачати час на обчислення функції.

Таким чином, пошук методом Фібоначчі, названий так з огляду на появу при пошуку чисел Фібоначчі, є ітераційної процедури. В процесі пошуку інтервалу (x1; x2) з точкою х2, вже лежить в цьому інтервалі, наступна точка х2 завжди вибирається такий, що х3-х4 = х2-х1 або х4-х1 = х3-x2, тобто x4 = х1-х2 + х3.

Якщо f (x2) = f2 і f (x4) = f4, то можна розглянути чотири випадки ( Мал. 9.5 ).

Наступний з методів одновимірної оптимізацією називається методом "золотого перетину".

Не завжди можна заздалегідь визначити, скільки разів доведеться обчислювати функцію. У методі Фібоначчі це потрібно знати для визначення L2, тобто положення початкової точки (див. рівняння 2.4).

Метод "золотого перетину" майже настільки ж ефективний, як і метод Фібоначчі, проте при цьому не потрібно знати n - кількість обчислень функції, визначається спочатку. Після того як виконано j обчислень, виходячи з тих же міркувань, що і раніше (див. Рівняння 2.1), записуємо

Однак якщо n невідомо, то ми не можемо використовувати умова Ln-1 = Ln - е. Якщо відношення наступних інтервалів буде постійним, тобто

то тобто

Таким чином, , звідки . тоді

отже, , Тобто

В результаті аналізу двох розглянутих значень функції буде визначений той інтервал, який повинен досліджуватися в подальшому. Цей інтервал буде містити одну з попередніх точок і наступну точку, що поміщається симетрично їй. Перша точка знаходиться на відстані L1 / t від одного кінця інтервалу, друга - на такій же відстані від іншого. оскільки

то з рівняння (2.4) видно, що пошук методом "золотого перетину" є граничною формою пошуку методом Фібоначчі. Назва "золотий перетин" походить від назви відносини в рівнянні (2.7). Видно, що Lj-1 ділиться на дві частини так, що відношення цілого до більшої частини дорівнює відношенню більшої частини до меншої, тобто одно так званому "золотому відношенню".

Таким чином, якщо шукається інтервал (х0, х3) і є два значення функції f1 і f2 в точках x1 і x2, то слід розглянути два випадки ( Мал. 9.6 ).

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

Схема алгоритму методу "золотого перетину" представлена ​​на рис 9.7

Тут c - константа,

При виведенні x - координата точки, в якій функція F (x) має мінімум (або максимум), FM - значення функції F (x) в цій точці.