Розділ 2
МЕТОДИ ОДНОВИМІРНОЇ ОПТИМІЗАЦІЇ
2.1. Методи Фібоначі
Задача 0. Знайти 
для заданої функції 
і заданого відрізка 
.
Припущення 0. Функція
така, що на відрізку точка її локального мінімуму 
є точкою абсолютного мінімуму на відрізку .
Методи Фібоначі є оптимальними для класу функцій , які задовольняють припущенню 0 за кількістю обчислень мінімізуючої функції при заданій точності обчислень .
1. Основний алгоритм
Алгоритм 1
Початок. І. Вибрати число 
– точність обчислення точки мінімуму функції на відрізку ; покласти 
.
ІІ. Покласти 
.
ІІІ. Обчислити число 
.
IV. Якщо 
, то покласти 
і перейти на крок V; інакше покласти 
і перейти на крок ІІІ.
V. Обчислити точки
VI. Якщо 
, то покласти 
, 
і перейти на крок VII; інакше покласти 
, 
і перейти на крок VII.
VII. Покласти 
.
Основний цикл. VIII. Якщо 
, то обчислити точку 
, обчислити значення 
і перейти на крок IX; інакше покласти 
, 
і перейти на крок X.
IX. Покласти 
; 
і перейти на крок XI.
X. Обчислити точку 
, обчислити значення 
і перейти на крок XІ.
XI. Якщо 
, то покласти 
, 
і перейти на крок XІІ; інакше покласти 
, 
і перейти на крок XІІ.
XII. Якщо 
, то покласти 
і перейти на крок VIIІ; інакше покласти 
і зупинити обчислення.
Теорема 1. Якщо виконується припущення 0, то для будь-якого точка яка породжена алгоритмом 1, задовольняє нерівність 
.
Зауваження 1. Недоліком алгоритму 1 є те, що похибки в обчисленнях точок 
, 
можуть настільки швидко накопичуватися, що очікувана точність розв’язку буде суттєво відрізнятися від реальної. Наступна модифікація методу Фібоначі менш чутлива до похибок обчислень.
2. Модифікація методу Фібоначі
Алгоритм 2
Початок. Кроки І – IV такі ж, як у алгоритмі 1.
V. Обчислити точки
VI. Якщо , то покласти , і перейти на крок VII; інакше покласти , і перейти на крок VII.
VII. Покласти .
Основний цикл. VIII. Якщо , то обчислити точку
,
обчислити значення і перейти на крок IX; інакше покласти , і перейти на крок X.
IX. Покласти 
; 
і перейти на крок XI.
X. Обчислити точку 
, обчислити значення і перейти на крок XІ.
XI. Якщо , то покласти , і перейти на крок XІІ; інакше покласти , і перейти на крок XІІ.
XII. Якщо , то покласти і перейти на крок VIIІ; інакше покласти і зупинити обчислення.
Точка 
задовольняє нерівність , якщо виконується припущення 0.
2.2. Метод золотого перерізу
Задача 1. Знайти 
для заданої функції 
і заданого відрізка 
.
Припущення 1. Функція така, що на відрізку 
точка її локального мінімуму є точкою абсолютного мінімуму на відрізку .
Алгоритм 1
Початок. I. Обчислити константу 
(
).
II. Обчислити точки
і значення 
.
III. Якщо 
, то покласти 
і перейти на крок IV, інакше покласти 
і перейти на крок IV.
IV. Покласти 
Основний цикл. V. Якщо 
, то обчислити 
, 
і перейти на крок VI; інакше покласти 
, 
і перейти на крок VII.
VI. Покласти
, 
і перейти на крок VIII.
VII. Обчислити 
, 
і перейти на крок VIII.
VIII. Якщо 
, то покласти 
і перейти на крок IX; інакше покласти 
і перейти на крок IX.
IX. Обчислити 
.
X. Покласти і перейти на крок V.
Теорема 1. Якщо виконується припущення 1, то послідовність 
яка породжена алгоритмом 1, така, що
.
Зауваження 1. Довжина відрізку 
, побудованого по методу золотого перерізу, на 17% більша довжини відрізку 
, побудованого по методу Фібоначі. Проте метод золотого перерізу має наступну перевагу, що на кожній його ітерації доводиться робити менше обчислень.
Зауваження 1'. Іноді на практиці комбінують обидва методи: перші кроки роблять по методу золотого перерізу, а коли оптимум достатньо близький, обраховують число m і переходять до методу Фібоначі.
2.3. Методи типу Ньютона
Задача 0. Знайти 
для заданої функції і заданого відрізка 
.
Припущення 0. Функція двічі неперервно диференційована на і задовольняє умову
, 
.
1. Метод Ньютона
Ідея методу Ньютона полягає в тому, що функція 
лінеаризується в околі точки 
і знаходять точку 
, в якій лінеаризована функція перетворюється в нуль.
Алгоритм 1
Початок. І. Вибрати початкове наближення 
; покласти 
.
Основний цикл. ІІ. Обчислити 
– першу похідну функції в точці .
ІІІ. Якщо 
, то зупинити обчислення (в цьому випадку точка є стаціонарною точкою функції ), інакше перейти на крок IV.
IV. Обчислити 
– другу похідну функції в точці .
V. Обчислити наступне наближення
VI. Покласти 
і перейти на крок ІІ.
Теорема 1. Якщо виконується припущення 0 і, крім того, 
для всіх 
для всіх 
виконується нерівність
то послідовність , яка породжена алгоритмом 1, збігається до стаціонарної точки 
функції з квадратичною швидкістю, тобто
Тут
де
2. Метод січних
Метод січних є модифікацією методу Ньютона (алгоритму 1), в якому замість другої похідної 
використовується її різницева апроксимація.
Алгоритм 2
Початок. І. Вибрати довільне початкове наближення 
покласти .
Основний цикл. ІІ. Обчислити 
– першу похідну функції в точці 
.
ІІІ. Якщо , то зупинити обчислення (в цьому випадку точка є стаціонарною точкою функції ), інакше перейти на крок IV.
IV. Обчислити наступне наближення
V. Покласти 
і перейти на крок II.
Теорема 2. Якщо виконуються всі умови теореми 1, то послідовність, яка породжена алгоритмом 2, збігається до стаціонарної точки функції із зверхлінійною швидкістю
,
де 
– розв’язок рівняння 
.
2.4. Методи глобального пошуку
Задача 0. Знайти 
для заданої функції 
та заданого відрізку дійсної осі 
.
Приведені нижче алгоритми застосовуються для обчислення абсолютного мінімуму багатоекстремальної функції на відрізку .
1. Алгоритм глобального пошуку
Алгоритм 1
Початок. I. Вибрати довільну константу 
.
II. Покласти 
.
III. Покласти 
.
Основний цикл. IV. Розташувати точки послідовності 
в порядку зростання їх значень і нову послідовність позначити через 
, тобто
.
V. Знайти максимальне абсолютне значення відносної першої різниці
.
VI. Якщо 
, то покласти 
і перейти на крок VII; інакше покласти 
і перейти на крок VII.
VII. Покласти 
.
VIII. Обчислити 
– характеристику інтервалу 
.
IX. Якщо 
, то покласти 
і перейти на крок VIII; інакше перейти на крок X.
X. Знайти найменше значення 
, при якому виконується рівність
.
XI. Обчислити наступне наближення
.
XII. Покласти і перейти на крок IV.
Теорема 1. Нехай функція 
задовольняє на 
умові Ліпшиця із константою
.
Тоді: 
якщо функція має на відрізку скінчене число локальних екстремумів, то будь-яка гранична точка 
послідовності, яка породжена алгоритмом 1, локально-оптимальна; 
якщо поряд із граничною точкою існує інша гранична точка 
послідовності , тоді 
; якщо – гранична точка послідовності, тоді 
– якщо на деякій ітерації алгоритму 1 справедлива нерівність, тоді множина граничних точок послідовності 
співпадає з множиною точок абсолютного мінімуму функції на відрізку .
Теорема 1'. Нехай для наперед вибраної константи (
– точність обчислення абсолютного мінімуму) за допомогою алгоритму 1 побудована послідовність точок, де 
– найменший індекс 
, при якому виконується нерівність
.
Тоді: 
– якщо на 
-й ітерації виконується нерівність
,
де, то
,
тобто точка абсолютного мінімуму не може належати інтервалу, довжина якого перевищує дану точність ; 
– якщо 
, то
,
тобто оцінка 
мінімального значення функції досягається на одному із кінців інтервалу, довжина якого не перевищує точності ; 
– для будь-якого додатнього 
існує настільки велике значення коефіцієнту 
, що точки 
утворюють 
-сітку в інтервалі .
Зауваження 1. Значення константи повинно бути достатньо великим, щоб виконувалася нерівність 
, яка являється достатньою умовою збіжності алгоритму 1. Але, з іншого боку, зі збільшенням зростає (наближаючись при 
до кількості вузлів сітки методу перебору) число обчислень функції . У випадку, коли відома константа Ліпшиця 
, вибір значення параметру не викликає ніяких труднощів. У випадку, якщо відомі лише грубі апріорні верхні оцінки константи Ліпшиця, можна скористатися описаним нижче алгоритмом.
2. Рандомізований алгоритм глобального пошуку
Алгоритм 2
Початок. I. Вибрати нижню 
і верхню 
оцінки параметру .
II – X. Кроки II – X такі ж, як в алгоритмі 1, лише при обчисленні 
на кроці VI замість константи потрібно взяти константу .
XI. Обчислити
.
XII. Покласти 
.
XIII. Якщо , то покласти 
і перейти на крок XIV; інакше покласти 
і перейти на крок XIV.
XIV. Покласти .
XV. Обчислити
.
XVI. Якщо , то покласти і перейти на крок XV; інакше перейти на крок XVII.
XVII. Знайти найменше значення індексу 
, при якому виконується рівність 
.
XVIII. Обчислити
.
XIX. Покласти 
.
XX. Якщо 
, то обчислити 
і перейти на крок XXI; інакше обчислити 
і перейти на крок XXI.
XXI. Однократно реалізувати випадковий механізм з двома виходами 1 та 2, відповідно, які мають ймовірності 
і 
.
XXII. Якщо випадковий механізм дав результат 1, то покласти 
і перейти на крок XXIII; інакше покласти 
і перейти на крок XXIII.
XXIII. Обчислити наступне наближення
.
XXIV. Покласти і перейти на крок IV.
2.5. Адаптивні методи
1. Алгоритми Кіфера-Вольфовиця
Задача 1. Знайти 
для заданої функції 
Припущення 1. Функція унімодальна.
Метод Кіфера-Вольфовиця застосовується для мінімізації унімодальних функцій, обчислення яких проводиться з випадковими перешкодами.
Алгоритм 1
Початок. I. Вибрати довільне початкове наближення 
II. Покласти 
Основний цикл. III. Обчислити значення крокового множника 
і зміщення 
які задовольняють умовам теореми 1.
IV. Знайти величину 
результат обчислення з випадковими перешкодами значення функції в точці 
V. Знайти величину 
результат обчислення з випадковими перешкодами значення функції в точці 
VI. Обчислити наступні наближення
VII. Покласти і перейти на крок III.
Теорема 1. Нехай функція 
являється унімодальною і задовольняє умові
де 
розв’язок задачі 1; 
деякі константи.
Тоді, якщо в алгоритмі 1 похибка обчислень функції рівномірно обмежена і має нульове математичне сподівання, тобто
і якщо крокові множники і зміщення 
такі, що
то послідовність 
яка породжена алгоритмом 1, збігається до точки максимуму функції в середньоквадратичному і з ймовірністю 1, тобто
Зауваження 1. Якщо наближення 
на кроці VI алгоритму 1 обчислювати за формулою
то отримаємо нормалізований варіант методу Кіфера–Вольфовиця.
2. Простий перебір
Задача 2. Знайти для заданої функції 
і заданого відрізку .
Припущення 2. Функція така, що на відрізку точка її локального мінімуму являється точкою абсолютного мінімуму на відрізку .
Алгоритм 2
Початок. I. Задати: число – точність обчислення точки мінімуму функції на відрізку ; натуральне число 
(рекомендується вибрати число із відрізку 
); покласти
Основний цикл. II. Покласти 
III. Покласти 
обчислити 
і покласти 
IV. Обчислити зміщення
V. Обчислити точку
та обчислити 
VI. Якщо 
то перейти на крок VII; інакше перейти на крок VIII.
VII. Якщо 
то покласти 
і перейти на крок IX; інакше покласти 
і перейти на крок IX.
VIII. Якщо 
то покласти 
і перейти на крок V; інакше покласти 
і перейти на крок IX.
IX. Якщо 
то перейти на крок X; інакше покласти 
і зупинити обчислення.
X. Покласти і перейти на крок II.
Теорема 2. Якщо виконано пропущення 2, то для довільного алгоритм 2 за скінчене число ітерацій приводить в точку таку, що
Зауваження 2. Недоліком методу простого перебору являється те, що в багатьох «зайвих» точках доводиться обчислювати значення функції 
що небажано у випадку, коли визначається в результаті експерименту або коли для обчислення значення функції в точці потрібно значно багато машинного часу.
Література до розділу 2
1. , , Сборник задач по оптимизации. Теория. Примеры. Задачи. –М.: Наука. –1984. –288 с.
2. , , Методы и алгоритмы решения задач оптимизации. – К.: Вища школа, 1983. –512 с.
3. Численные методы решения экстремальных задач. –М.: Наука, 1988. –552 с.
4. , Исследование операций. –М.:Машиностроение, 1986.
5. Практическая оптимизация. –М.: Мир, 1985. –509 с.
6. , , Математические методы исследования операций. –Киев: Вища школа, 1979. –312 с.
7. Методы поиска глобального экстремума. –М.: Наука, 1991. –248 с.
8. Жилинскас А. Г. Глобальная оптимизация. Аксиоматика статических моделей, алгоритмы, применения. –Вильнюс: Мокслас, 1986. –166 с.
9. Поиск оптимума: компьютер расширяет возможности. –М.: Наука, 1989. –128 с.
10. Дослідження операцій. – Київ: ЗАТ «Віпол», 2000. –688 с.
11. , Исследование операций. – Киев: Вища школа, 1984. –224 с.
12. Математическое программирование. – М. Наука, 1975.–272 с.
13. , , Методы невыпуклой оптимизации. –М.: Наука, 1987. –280 с.
14. , І., І. Методи оптимізації. –Навчальний посібник. – Київ.: 1999. –217 с.
15. Оптимизация. Теория и алгоритмы. –М.: Мир, 1973. –244 с.
16. Численные методы в многоэкстремальных задачах (Информационно-статистические алгоритмы). –М.: Наука, 1978. –240 с.
17. Методы поиска экстремума. –М.: Наука, 1967. – 267 с.
18. Прикладное нелинейное программирование. –М.: Мир, 1975. –536 с.
