Введення
Завдання у вигляді, придатному для вирішення методом оптимізації, полягає в мінімізації (максимізації) вещественнозначной функції f (x) N-мірного аргументу x. Така задача називається задачею умовної оптимізації. Якщо завдання не містить обмеження і розглядається на всьому просторі, то це завдання безумовної оптимізації. Завдання без обмежень з N=1 називаються завданнями одновимірної оптимізації, з N 2 - багатовимірної оптимізації.
Завданням одновимірної оптимізації є пошук локального мінімуму цільової функції f (х) уздовж заданого напрямку.
Задача знаходження мінімуму функції однієї змінної min f (x) нерідко виникає в практичних додатках. Крім того, багато методи розв'язання задачі мінімізації функції багатьох змінних зводяться до багаторазового пошуку одновимірного мінімуму. Тому розробка все нових, більш ефективних одновимірних методів оптимізації продовжується і зараз, незважаючи на гадану простоту завдання.
Деякі методи не вимагають точного визначення мінімуму. В інших методах при визначенні мінімуму використовується поліноміальна апроксимація. Наприклад, квадратична функція визначається трьома точками, між якими знаходиться точка мінімуму, і мінімум цієї квадратичної функції вважається знайденим, якщо задовольняється критерій збіжності.
Введемо деякі визначення:
Монотонність функції. Функція f (x) є монотонною на інтервалі, якщо для будь-яких x 1 і x 2 з цього інтервалу, таких, що x 1 lt; x 2, виконується нерівність:
f (x 1) lt; f (x 2), якщо функція монотонно зростаюча, або f (x 1) gt; f (x 2), якщо функція монотонно спадна.
унімодального. Функція f (x) є унімодальної на відрізку, якщо вона монотонна по обидві сторони від єдиної на відрізку точки х 0, тобто функція f (x) в полуінтервале [а, х 0) убуває, а в полуінтервале (х 0, b] зростає. Приклади графіків унімодальних функцій наведено на рис. 1.
Точка х 0 може бути внутрішньою точкою відрізка [а, b] або збігатися з одним з його кінців. Унімодального функція не обов'язково неперервна на відрізку [а, b].
Рис. 1. Графіки унімодальних функцій
Визначення глобального мінімуму. Функція f (x), певна на безлічі D, досягає глобального мінімуму в точці x * D, якщо f (x *) lt; f (x) для всіх x D.
Визначення локального мінімуму. Функція f (x), певна на безлічі D, має локальний мінімум в точці x * D, якщо існує така е-околиця точки x *, що для всіх x із цієї е-околиці виконується нерівність f (x *) lt; f ( x).
Якщо функція f (x) НЕ унімодального, то найменший з локальних мінімумів буде глобальним мінімумом. Для знаходження аналітичного оптимуму необхідно знайти стаціонарні або критичні точки функції, використовувати яке-небудь з достатніх умов екстремуму (зміна знака першої похідної або певного знака парній похідної) і порівняти значення функції в точках локальних екстремумів і граничних значеннях. Однак у прикладних задачах нерідкі ситуації, коли важко вирахувати похідні функції (наприклад, якщо функція не задана в аналітичному вигляді). Більше того, не виключено, що значення функції відомі або можуть бути обчислені тільки в окремих точках. У таких ситуаціях використання необхідного і достатнього умов локального мінімуму неможливо і слід застосовувати інші методи розв'язання задачі оптимізації. Методи мінімізації функції однієї змінної, в яких використовують значення функції в точках аналізованого проміжку і не використовують значення її похідних, називають методами прямого пошуку.
Можна виділити дві групи методів прямого пошуку, що відповідають двом принципово різним ситуацій:
. всі N точок х k, k=1, ..., N, в яких будуть обчислені значення функції, вибирають заздалегідь (до обчислення функції в цих точках);
. точки xk вибирають послідовно (для вибору наступної точки використовують значення функції, обчислені в попередніх точках).
У першому випадку пошук найменшого значення називають пасивним, а в другому - послідовним.
Так як в прикладних задачах обчислення кожного значення функції може бути досить трудомістким, то доцільно вибрати таку стратегію пошуку, щоб значення цільової функції f (x *) із заданою точністю було знайдено найбільш економним шляхом.
Будемо вважати, що стратегія пошуку визначена, якщо:
. визначено алгоритм вибору точок xk, k=1, ..., N;
. визначено умову припинення пошуку, тобто умова, при виконанні якого значення f (x *) вважають знайденим із заданою точністю.
Оптимальний пасивний по...
