Page 178 - 5637

Нехай – довільна точка , ( , ) – деяка (відповідна метриці ( , ) )

околиця радіусу з центром в точці . Якщо ∈ і ( ) < ( ), то елемент

∈ ( , ) будемо вважати відповідним. Векторну функцію назвемо ∆-вектором

функції в околиці ( , ) довільної точки ∈ , якщо вона має компоненти

∆ ( ) = ( ) − ( ),

⋳ ( , ), = 1, … , ( , ) (8.15)

(тут ( , ) – число елементів околиці ( , )). Очевидно, що ∆-вектор функції є

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

межах округа ( , )).

Надалі будемо вважати, що на задана метрика Хеммінга ( , ) =

= ∑ | − |. При інший метриці на алгоритм аналогічний.

Алгоритм методу направляючих околиць складається з наступних основних
етапів:

1. Задаємо початкове наближення ∈ і максимальний радіус перебору

> 0. Вважаємо = 0.

2. Вважаємо = 1.

3. На ( + 1)-м кроці виробляємо перебір всіх -елементів околиці Хеммінга

( , ). На кожному кроці процедури перебору визначаємо, чи є поточний

згенерований на даному кроці елемент підходящим. Якщо підходящих-елементів в

( , ) ні, переходимо до п.4, якщо є, виробляємо наступні дії:

3.1. Визначаємо розмір кроку пошуку з точки у відповідності з наступною
п
п
формулою:

= max{ : + ⋳ , ( + ) ≥ ( + )},
п
п
п
п
п
п
п
де = − , 0 ≤ ≤ .
п
п
3.2. Якщо = ∞, то робиться висновок, що рішення задачі (8.1) – (8.3) не
п
обмежена знизу, і алгоритм закінчує свою роботу.
3.3. Якщо = 0, то проводиться повернення до п.3.1, для продовження
п
'процедури послідовного перебору околиці ( , ).