P=А (АА) А (4)
Для цієї функції в силу правила диференціювання складної функції і симетричною матриці Р справедливо рівність
grad (y)=P * grad? (x) (5)
Насамперед переконаємося, що х * ?. Використовуючи уявлення
х *=х + Р * у * (6)
і умова х ?, укладаємо, що (а, х *)=(а, х) + (а, Р * у *)=(а, х)=b, i =. Оскільки вектор Р * у * ортогонален кожному вектору лінійного підпростору?, В тому числі і векторах а. Отже, х *?.
Так як у * є стаціонарною крапкою функції (у), то grad (y *)=0, і тому, враховуючи grad (y)=P * grad? (x) і P=А (АА) А при х =х * й у=у *, знаходимо
Р * grad? (x *)=grad? (x *) - А (АА) grad? (x *)=grad? (x *) + А=grad? (x *) + а=0, (7)
де=- (АА) А grad? (x *), а - координати вектора R ?. Представивши обмеження (3) у вигляді? (Х)=(а, х) -b=0, i =, і враховуючи рівності grad? (X *)=а, укладаємо, що точка х * є стаціонарною крапкою функції Лагранжа
L (x,) =? (x) + ((a, x) -b) (8)
тобто задовольняє необхідній умові мінімуму цільової функції? (х) на множині?.
Стаціонарні точки цільової функції? (х) на допустимому безлічі можна визначати, вирішуючи завдання безумовної мінімізації функції (у). У загальному випадку функція (у) може мати кілька стаціонарних точок, причому кожній її стаціонарній точці у * відповідатиме стаціонарна точка (6) функції Лагранжа (8). Через мінімізацію функції (у) можна знайти всі стаціонарні точки цільової функції. Однак, якщо цільова функція є опуклою функцією на опуклому безлічі?, То для розв'язання задачі мінімізації такої функції достатньо знайти хоча б одну стаціонарну точку цільової функції в?, Оскільки в будь стаціонарній точці опукла функція досягає найменшого значення. Строго опукла функція може мати лише одну стаціонарну точку, так як вона може досягати найменшого значення на опуклому безлічі тільки в одній точці.
Нелінійні обмеження. Якщо серед обмежень в задачі оптимізації є нелінійні, то пошук мінімуму цільової функції? (Х) на допустимому безлічі ускладнюється. Нехай для визначеності?={ХR ?: g (x)? 0, i =}, де g (x) - диференціюються на k-ой ітерації відома точка х ?, для якої активними є обмеження з індексами i={iN: g (x)=0}. Складемо матрицю, рядками якої є матриці-рядка (grad g (x)), i, припускаючи, що вони лінійно незалежні. Тоді проекційна матриця=I- () спроектує антіградіентом w=-grad? (X) цільової функції в точці x на напрямок, ортогональное градієнтам всіх функцій g (x), i, які задають в цій точці активні обмеження. Але в загальному випадку може виявитися, що цей напрямок буде напрямком спуску, оскільки воно може лише торкатися в точці x? кордону? безлічі?.
. 1 Завдання
У цьому випадку цільова функція є квадратичною і її можна записати у вигляді де
Єдине обмеження задачі має вигляд, де. В якості початкової візьмемо точку, а в умови припинення пошуку покладемо.
Обчислимо антіградіентом
І градієнт лівій частині обмеження
.
Розглянемо докладніше перший (k=1) ітерацію при рішенні цієї задачі методом проекції антіградіента.
) оскільки, то антіградіентом і градієнт в початковій точці ортогональні. Отже, немає необхідності обчислювати проекційну матрицю, яка в даному випадку є одиничною.
) за допомогою вичерпного спуску з точки в напрямку вектора р знаходимо значення
І крапку. Ясно, що просування точки в напрямку вектора виводить за межі допустимого безлічі, тобто, так як. Точка лежить на дотичній кривої, заданої рівнянням, в точці.
) проектуємо точку на допустима безліч Х, тобто знайдемо точку кривої В, найменш віддалену від точки. Так як функція дифференцируемая, то точка буде підставою найкоротшого перпендикуляра, опущеного з на криву В. Цю точку можна знайти методом послідовних наближень. де. В якості нульового наближення при s=1 можна прийняти, а умовою припинення послідовних наближень можна вважати виконання нерівності де - заданий параметр точності. При виконанні цієї нерівності вважаємо і. Вибираючи отримуємо, при цьому.
) перевіряємо умову припинення ітерацій:. Так як необхідна точність ще не досягнута, пошук точки мінімуму цільової функції на множині Х слід продовжити. Для цього переходимо до пункту 1, замінивши точку на знайдену на першій ітерації точку.
Таблиця 1. Результати розрахунків на чотирьох ітераціях.
k1 (+0,9211, 0,7191) - 2,90861,1682 (0,9976, 0,9512) - 2,99760,24431,0000, 0,9995) - 3,00000 , +0484 (1,0000, 1,0000) - 3,00000,0005
Таким чином, результат четвертої ітерації із заданою точністю збігся з точним рішенням завдання.
Висновок
Практика породжує все нові й нові завдання оптим...
