Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




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

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

(14.4)

де - точка розкладення із простору RN; х=х- — величина зміни х; f(x) — N-мірний вектор - стовпчик перших похідних f(x), обчислених в точці ; 2f()=Hf() — симетрична матриця порядку NґN других частинних похідних f(x), вирахуваних у точці . (Цю матрицю часто називають матрицею Гессе. Її елемент, розташований на перетині i-й строчки і j-го стовпчика, дорівнює J2f/dxiJxj.) O3( x)- сума всіх членів розкладу, які мають порядок по х вище другого. Нехтуючи членами найвищих порядків (тобто виключаючи О3( х)), визначимо величину зміни цільової функції f(x), відповідно довільній зміні х:

. (14.5)

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

)і0. (14.6)

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

)Ј0, (14.7)

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

Повернемось до рівняння (14.5) і згадаємо про висунуте раніше припущення про те, що f(x), і f(x) існують і неперервні для всіх хОRN. Як випливає з формули (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.




Поделиться с друзьями:


Дата добавления: 2014-11-08; Просмотров: 676; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.01 сек.