Page 134 - 5637

При наявності апріорної інформації про унімодальність

оптимізуючого критерію з'являється можливість побудови ефективних методів

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

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

B основі метода золотого перетину лежить схема Кіфера [2, 58, 59]. Уявімо, що в

процесі роботи алгоритму функція ( ) обчислюється раз ( > 1). Звичайно

прагнення використовувати інформацію, отриману в процесі цих обчислень таким

чином, щоб максимально звузити інтервал невизначеності положення точки

екстремуму.

Введемо наступні позначення: – координата на відрізку [ , ] обчислена на -му

∗
кроці роботи алгоритму; – положення мінімального значення ( ) до -му кроці

пошуку; – відповідне значення з інтервалу невизначеності.

Розіб'ємо простір можливих результатів ( + 1)-гo кроку на події Ω і Ω :

∗
∗
Ω : ( ) > ( ), Ω : ( ) > ( ), Ω = Ω ⋃ Ω .

Тепер завдання побудови траєкторії пошуку , … , такою, щоб максимально звузити

інтервал невизначеності , можна сформулювати у вигляді наступного
мінімаксного завдання:
= ( , Ω) → min max

Ω {Ω ,Ω }

Введемо = ℎ − , де – координата лівого кінця інтервалу

невизначеності . Побудуємо функцію ( , Ω).

∗
1. Якщо < = − , то

− при Ω = Ω

= при Ω = Ω

2. Якщо > , то

при Ω = Ω

=
− при Ω = Ω

Тепер неважко визначити як саму залежність функції max ( , Ω),

Ω
так і гарантоване значення інтервалу невизначеності = − . Чергову точку

пошуку слід розташовувати в межах < < − . Зазвичай вибирають точку

∗
, максимально віддалену від найкращої вже відібраної точки , вважаючи

= − . Останнє співвідношення і визначає мінімаксне правило Кіфера: нову

точку пошуку слід розташовувати симетрично екстремального щодо середини