14.2 Критерії оптимальності

Розглянемо умови, які дозволяють характеризувати (тобто класифікувати) точки простору керованих змінних. Критерії оптимальності необхідні для розпізнавання рішень і, крім того, складають основу більшості методів пошуку рішень, що використовуються.

Для цього розглянемо розклад Тейлора для функції декількох змінних :

          (14.4)

де - точка розкладення із простору R^N; х=х- — величина зміни х; f(x) — N-мірний вектор - стовпчик перших похідних f(x), обчислених в точці ; ²f( )=H_f( ) — симетрична матриця порядку NґN других частинних похідних f(x), вирахуваних у точці . (Цю матрицю часто називають матрицею Гессе. Її елемент, розташований на перетині i-й строчки і j-го стовпчика, дорівнює J²f/dx_iJx_j.) O₃( x)- сума всіх членів розкладу, які мають порядок по х вище другого. Нехтуючи членами найвищих порядків (тобто виключаючи О₃( х)), визначимо величину зміни цільової функції f(x), відповідно довільній зміні х:

     .     (14.5)

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

     )і0.          (14.6)

Точка є точкою глобального мінімуму, якщо нерівність (14.6) виконується для всіх хОR^N; такі точки будемо позначати через х**. Коли формула (14.6) справедлива лише в деякому d-околі точки , т.б. для всіх х, таких, що (х- (d при заданому d>0, то є точкою локального мінімуму, чи х*. Якщо

     )Ј0 ,     (14.7)

то є точкою максимуму ( локального чи глобального у відповідності з даним вище визначенням). Виключення знака рівності із формул (14.6) і (14.7) дозволяє визначити точку строгого мінімуму чи максимуму. В тому випадку, коли приймає як додатне, так і від’ємне, так і нульове значення в залежності від вибору точок із d-околу, точка являє собою сідлову точку.

Повернемось до рівняння (14.5) і згадаємо про висунуте раніше припущення про те, що f(x), і f(x) існують і неперервні для всіх хОR^N. Як випливає з формули (14.5), для того щоб знак не змінювався при довільній зміні , градієнт f( ) повинен дорівнювати нулю, тобто повинна бути стаціонарною точкою. В протилежному випадку різниця f може приймати додатні чи від’ємні значення в залежності від знаків ( ) і . Таким чином, точка повинна задовольняти умові стаціонарності

     ( )=0 ,     (14.8)

і формула (14.5) приймає такий вигляд :

     ) .     (14.9)

Звідси видно, що знак визначається квадратичною формою

     ) ,     (14.10)

чи Q(x)=zTAz.                         (14.11)

Із лінійної алгебри ми знаємо, що:

А- додатньо визначена матриця, якщо Q(z)>0 для любих z;

А- додатньо напіввизначена матриця, якщо Q(z)і0 для любих z;

А- від’ємно визначена матриця, якщо Q(z)<0 для любих z ;

А- від’ємно напіввизначена матриця, якщо Q(z)Ј0 для любих z ;

A-невизначена матриця, якщо Q(z)>0 для деяких z і Q(z)<0 для останніх z.

Із (14.11) видно, що стаціонарна точка є

- точкою мінімуму, якщо ) — додатньо напіввизначена матриця;

- точкою максимуму, якщо ) — від’ємно напіввизначена матриця;

- сідлова точка, якщо ) > (або <) 0 — невизначена матриця.

Крім того, іноді корисно провести аналіз стаціонарної точки в деякому іншому аспекті. Розглянемо стаціонарну точку разом з оточуючим її d- колом і векторами, що виходять із точки (рис. 14.2). При цьому

     s( ).      (14.12)

Шляхом відповідного вибору a і s можливо побудувати всі точки із кола точки . Підстановка (14.12) в (14.9) дає формулу

     .     (14.13)

Тепер за допомогою (14.11) і (14.12) можливо класифікувати s(x) як напрямок спуску, напрямок підйому чи напрямок загального вигляду. Якщо напрямок спуску знайти не вдається, то є точкою локального мінімуму х*, що відповідає випадку, коли - додатньо напіввизначена матриця.

    

     Рисунок 14.2 - Окіл стаціонарної точки

Теорема 1. Необхідні умови

Для наявності в точці х* локального мінімуму необхідно, щоб виконувалась рівність

          (14.14а)

і матриця була додатньо напіввизначеною:

     0.     (14.14б)

Теорема 2. Достатні умови

Якщо

          (14.15а)

і матриця додатньо визначена, то

     > 0.     (14.15б)

Доведення цих теорем витікає із наведеного вище судження. Звичайно доводиться обмежуватись находженням локального мінімуму; разом з тим, якщо можна показати, що для всіх х, то f(x) називають випуклою функцією, а локальний мінімум називають глобальним.

Приклад 14.1. Критерії оптимальності

Розглянемо функцію

,

лінії рівня якої зображені на рис. 14.3.

    

     Рисунок 14.3 - Лінії рівня нелінійної функції двох змінних з прикладу 14.1

Треба класифікувати точку =[0,0]^T .

Розв’язок.

,

,

.

Звідси, точка — стаціонарна.

,

Звідси,

Матриця є невизначеною, так як квадратична форма приймає додатнє значення при z=(0,1) і від’ємне значення при z=(1,1). Тому представляє собою сідлову точку, що і відображено на рис. 14.3.