Метод золотого січення

При побудові процесу оптимізації намагаються скоротити обсяг обчислень та час пошуку. Цього досягають шляхом скорочення кількості обчислень значення цільової функції . Одним з найбільш ефективних методів, в яких при обмеженому числі обчислень досягається найкраща точність, є метод золотого січення. Він полягає в побудові відрізків (а0, b0) , (а1, b1) , ... , що зтягує до точки мінімума функції . На кожному кроці, за виключенням першого, обчислення значення функції проводиться лише один раз. Ця точка обирається певним чином.

На першому кроці процеса оптимізації в середині відрізку (а0, b0) (мал.1)обираємо дві внутрішні точки х1, х2 і обчислюємо значення цільової функції та . Оскільки в даному випадку < , очевидно, що мінімум розташований на одному з прилеглих до х1 відрізків (а0, х1) чи (х1, х2). Тому відрізок (х1, в0) можна відкинути, звузивши тим самим початковий інтервал невизначеності.

мал. 1

Другий крок поводимо на відрізку (а1, в2) (мал. 2)де а1=а0 , в1= х2 . Потрібно знову обрати дві внутрішні точки , але одна з них (х1) залишилась від попереднього крока, тому достатньо обрати лише одну точку х3 , обчислити значення та провести порівняння. Оскільки тут >, ясно, що мінімум знаходиться на відрізку (х3, в0). Позначимо відрізок (а2, в2), знову оберемо одну внутрішню точку і повторимо процес звуження інтервалу невизначеності. Процес оптимізації повторюється доти доки довжина чергового відрізку (an, bn) не стане меншою від заданої величини .

мал. 2

Тепер розглянемо спосіб розташування внутрішніх точок на кожному відрізку (an, bn). Нехай довжина інтервалу невизначеності дорівнює L , а точка ділення ділить його на частини L1,L2 : L1>L2 , L= L1+L2 . Золоте січення інтервалу невизначеності обирається так, щоб співвідношення довжини більшого відрізка до довжини меншого дорівнювало співвідношенню довжини до довжини меншого більшого відрізка.

=

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

L12=L1*L2

L12=L2*(L1+L2)

L22+L1*L2-L12=0

=

Оскільки нас цікавлять лише додатні розвязки то:

=0.618

Звідци L1=0.618L, a L2=0.382L

Блок - схема методу золотого січення.