2.6.2.5 АЛГОРИТМИ СКАЛЯРНИМ ОПТИМІЗАЦІЇ
Завдання скалярної оптимізації вирішувалася в програмному середовищі Excel 7.0 засобами модуля Solver.xla.
Необхідно докладніше описати принципи його роботи, так як в процесі оптимізації часто виникають різноманітні проблеми, що можуть призвести до невірного рішення. Це досить потужний засіб містить ефективні алгоритми лінійної (симплекс-метод) і нелінійної (метод сполучених градієнтів і квазіньютоновскій) оптимізацій. Користувач може вручну вибирати час, відпускається на пошук рішення задачі, максимальна кількість ітерацій, точність, з якою визначається відповідність осередку цільовим значенням чи наближення до вказаних кордонів, допустиме відхилення від оптимального рішення, якщо безліч значень впливає осередку обмежено безліччю цілих чисел, збіжність (коли відносна зміна значення в цільовій комірці за останні п'ять ітерацій стає менше числа, зазначеного у полі збіжність, пошук припиняється), метод екстраполяції для отримання вихідних оцінок значень змінних в кожному одновимірному пошуку (лінійна, квадратична), метод чисельного диференціювання, який використовується для обчислення приватних похідних цільових та обмежують функцій (прямі, центральні), алгоритм оптимізації (метод Ньютона або сполучених градієнтів для вказівки напрямок пошуку). Для правильного вибору даних параметрів з метою свідомого контролю за вирішенням завдання оптимізації необхідно уявляти собі схему вирішення завдань скалярної оптимізації.
Щоб знайти оптимум (для визначеності - максимум) критерію F (X), потрібно вибрати послідовність точок Хi (i = 1, ..., n), для яких будуть виконані умови:
де aj - скаляр, що визначає довжину кроку вздовж цього напряму (при пошуку мінімуму у формулі - мінус); Р-- вектор, що задає напрям пошуку.
Для визначення вектора Р, використовується поняття градієнта. Градієнт F '(Х) скалярної функції векторного аргументу F (X) в точці Хi - вектор, спрямований у бік найшвидшого зростання функції і ортогональної поверхні рівня [поверхні постійного значення функції F (X)], що проходить через точку Х ^. Вираз (52) можна записати в координатної формі:
Xji + 1 = Xji + aiGj (Xi); j = 1, 2, до, (51)
де Gj - j-я компонента вектора градієнта. Графічна інтерпретація градиентного методу представлена на рис. 1.
Оскільки явний вид функції F (^ невідомий, обчислювальний процес градиентного пошуку будують так. Довільно вибирають початкову точку Х-i і в цій точці обчислюють значення функції F ^ j). Всіма компонентами вектораХ1 дають малі збільшення Dхj (j = 1, 2, ..., к) і формують вектор Х2 = Х1 + DX. Потім виконують пробний крок, тобто? F (Xi)
AxJ
Якщо Е (Х1)>-Р (Х2), то пробний крок невдалий. Тому знаки всіх збільшень Бх ^ змінюються на протилежні, змінюється і напрям вектора градієнта. Знайшовши потрібний напрямок, вибирають величину кроку а, і продовжують процес, вибудовуючи послідовність векторів {X}, що задовольняє умові (49).
Обчислюють значення функції F (X2). Якщо компоненти вектора градієнта:
Проблема вибору кроку - найважливіша у всій процедурі. Саме способом вибору кроку відрізняються один від одного різні градієнтні методи. Справа в тому, що при малому кроці пошук буде майже напевно успішним, тобто сходящимся до шуканого оптимуму, але потребує багато часу на обчислення. Великий крок, заощаджуючи час, не гарантує збіжності, оскільки оптимум можна «проскочити». Нарешті, бувають ситуації, коли процес пошуку зациклюється. Нехай потрібно знайти мінімум функції ^ (х) = Ьх2, де Ь - позитивне число. Для цієї функції формула (50) має вигляд:
Рис. 3 Проблема підміни глобального оптимуму локальним Однак з графіка видно, що оптимальна точка є права межа інтервалу, яку в такій ситуації називають глобальним (або істинним) оптимумом, в той час як знайдена вершина - локальний оптимум. При пошуку оптимуму на багатовимірних поверхнях зі складною топологією завжди існує небезпека «застрягти» на локальному оптимумі і ніколи не дістатися до глобального. Спосіб уникнути цього полягає в повторенні пошуку з різних стартових точок. Якщо при повторах знайдена точка оптимуму і значення функції в ній збережуться, можна з великою ймовірністю вважати, що знайдено глобальний оптимум.
Слід зауважити, що, незважаючи на відносну простоту використовуваних у фінансовій моделі функцій, в ході обчислень виникли проблеми з критерієм зупину, які були вирішені зменшенням параметра в діалоговому вікні «збіжність» до 0,000000005.