Якщо умова лінійної незалежності в точці оптимуму не виконується, то завдання Куна-Таккера може не мати рішення.
Приклад 4
Мінімізувати
при обмеженнях
Рішення.
На рис.1 зображена область допустимих рішень сформульованої вище нелінійної задачі. Ясно, що оптимальне рішення цього завдання є . Покажемо, що умова лінійної незалежності не виконується в точці оптимуму.


Рис.1 Допустима область в задачі 4
Так як
Легко бачити, що вектори лінійно залежні, тобто умова лінійної незалежності в точці не виконується.
Запишемо умови Куна-Таккера і перевіримо, чи виконуються вони в точці (1, 0). Умови (3), (6) і (7) приймають такий вигляд;
(11)
(12)
(13)
(14)
(15)
(16)
При з рівняння (11) випливає, що , Тоді як рівняння (14) дає , Отже, точка оптимуму не є точкою Куна - Таккера.
Зауважимо, що порушення умови лінійної незалежності не обов'язково означає, що точка Куна-Таккера не існує. Для того щоб підтвердити це, замінимо цільову функцію з цього прикладу функцією . При цьому оптимум, як і раніше досягається в точці (1,0), в якій умова лінійної незалежності не виконується. Умови Куна-Таккера (12) - (16) залишаються незмінними, а рівняння (11) набуває вигляду

Неважко перевірити, що точка є точкою Куна-Таккера, тобто задовольняє умовам Куна-Таккера.
Теорема про необхідність умов Куна-Таккера дозволяє ідентифікувати неоптимальні точки. Іншими словами, теорему 1 можна використовувати для доказу того, що задана допустима точка, яка задовольняє умові лінійної незалежності, не є оптимальною, якщо вона не задовольняє умовам Куна-Таккера. З іншого боку, якщо в цій точці умови Куна-Таккера виконуються, то немає гарантії, що знайдено оптимальне рішення нелінійної задачі. Як приклад розглянемо таку задачу нелінійного програмування.
Наступна теорема встановлює умови, при виконанні яких точка Куна-Таккера автоматично відповідає оптимальному вирішенню задачі нелінійного програмування.
Теорема.2 Достатність умов Куна-Таккера
Розглянемо завдання нелінійного програмування (0) - (2). Нехай цільова функція опукла, всі обмеження у вигляді нерівностей містять увігнуті функції , А обмеження у вигляді рівностей містять лінійні функції . Тоді якщо існує рішення , Що задовольняє умовам Куна-Таккера (3) - (7), то x * - оптимальне рішення задачі нелінійного програмування.
Якщо умови теореми 2 виконуються, то знаходження точки Куна-Таккера забезпечує отримання оптимального розв'язку задачі нелінійного програмування.
Теорему 2 можна також використовувати для доказу оптимальності даного рішення задачі нелінійного програмування. В якості ілюстрації знову розглянемо приклад:
Мінімізувати
при обмеженнях
За допомогою теореми 2 доведемо, що рішення є оптимальним. Маємо

Так як матриця позитивно полуопределена при всіх х, функція виявляється опуклою. Перше обмеження у вигляді нерівності містить лінійну функцію , Яка одночасно є як опуклої, так і увігнутої. Для того
щоб показати, що функція є увігнутою, обчислимо

Оскільки матриця негативно визначена, функція є увігнутою. Функція входить в лінійне обмеження в вяде рівності. Отже, всі умови теореми 2 виконані; якщо ми покажемо, що - Точка Куна-Таккера, то дійсно встановимо оптимальність рішення . Умови Куна-Таккера для прикладу 2 мають вигляд
(22)
(23)
(24)
(25)
, (26)
, (27)
(28)
(29)
Точка задовольняє обмеженням (24) - (26) і, отже, є допустимими. Рівняння (22) і (23) приймають такий вигляд:

Поклавши , Отримаємо і . Таким чином, рішення x *= (1, 5), задовольняє умовам Куна-Таккера. Оскільки умови теореми 2 виконані, то оптимальне вирішення завдання з прикладу 3. Зауважимо, що існують також і інші значення і , Які задовольняють систему (22) - (29).
Зауваження
1.Для зустрічаються на практиці завдань умова лінійної незалежності, як правило, виконується. Якщо в задачі всі функції диференційовні, то точку Куна-Таккера слід розглядати як можливу точку оптимуму. Таким чином, багато хто з методів нелінійного програмування сходяться до точки Куна-Таккера. (Тут доречно провести аналогію з випадком безумовної оптимізації, коли відповідні алгоритми дозволяють визначити стаціонарну крапку.)
2. Якщо умови теореми 2 виконані, точка Куна-Таккера в той же час виявляється точкою глобального мінімуму. На жаль, перевірка достатніх умов дуже складною, і, крім того, прикладні задачі часто не володіють необхідними властивостями. Слід зазначити, що наявність хоча б одного нелінійного обмеження у вигляді рівності призводить до порушення припущень теореми 2.
3.Достаточние умови, встановлені теоремою 2, можна узагальнити на випадок завдань з неопуклих функціями, що входять в обмеження у вигляді нерівностей, неопуклих цільовими функціями і нелінійними обмеженнями-рівностями. При цьому використовуються такі узагальнення опуклих функцій, як квазівипуклие і псевдовипуклие функції.

4. Функції декількох змінних

Обмежені можливості симплексного методу, укладені в задачах з складними видами обмежень і довільним видом цільової функції, привели до широкого використання ітеративних методів пошуку оптимального рішення.
Спочатку розглянемо питання аналізу «в статиці» з використанням положень лінійної алгебри та диференціального числення, а також умови, які (в досить загальних можливих ситуаціях) дозволяють ідентифікувати точки оптимуму. Такі умови використовуються для перевірки вибраних точок і дають можливість з'ясувати, чи є ці точки точками мінімуму або максимуму. При цьому завдання вибору зазначених точок залишається поза рамками проведеного аналізу; основна увага приділяється вирішенню питання про те, чи відповідають досліджувані точки рішенням багатовимірної задачі безумовної оптимізації, в якій потрібно мінімізувати f (x) x при відсутності обмежень на x, де x - вектор керованих змінних розмірності n, f - скалярна цільова функція. Звичайно передбачається, що x _i (для всіх значень i = 1, 2, ..., n) можуть приймати будь-які значення, хоча в ряді практичних додатків область значень x вибирається у вигляді дискретного безлічі. Крім того, часто виявляється зручним припускати, що функція f і її похідні існують і безперервні всюди, хоча відомо, що оптимуми можуть досягатися в точках розриву f або її градієнта

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

4.1. Методи прямого пошуку

Нижче розглядається питання аналізу «в динаміці» для функцій декількох змінних, тобто досліджуються методи і алгоритми, що дозволяють на ітераційної основі отримувати оцінки х *- вектора керованих змінних, якому відповідає мінімальне значення функції f (x). Зазначені методи застосовуються також до завдань максимізації, у яких цільову функцію слід замінити на-f (х). Методи, орієнтовані на вирішення задач безумовної оптимізації, можна розділити на три широких класу відповідно до типу використовуваної при реалізації того чи іншого методу інформації.
1. Методи прямого пошуку, засновані на обчисленні тільки значень цільової функції.
2. Градієнтні методи, в яких використовуються точні значення перших похідних f (x).
3. Методи другого порядку, в яких поряд з першими похідними використовуються також другі похідні функції f (x).
Нижче розглядаються методи, що відносяться до кожного з перерахованих класів, оскільки ні один метод або клас методів не відрізняється високою ефективністю при вирішенні оптимізаційних задач різних типів. Зокрема, можливі випадки, коли відбувається переповнювання пам'яті ЕОМ; в інших ситуаціях обчислення значень цільової функції вимагає надмірних витрат часу; в деяких завданнях потрібно отримати рішення з дуже високим ступенем точності. У ряді програм або неможливо, або дуже важко знайти аналітичні вирази для похідних цільової функції. Тому якщо передбачається використовувати градієнтні методи, слід застосувати процедуру різницевої апроксимації похідних. У свою чергу це призводить до необхідності експериментального визначення довжини кроків, що дозволяє встановити належне відповідність між помилкою округлення і помилкою апроксимації. Таким чином, інженер змушений пристосовувати застосовуваний метод до конкретним характеристикам розв'язуваної задачі.
Методи рішення задач безумовної оптимізації відрізняються відносно високим рівнем розвитку в порівнянні з іншими методами нелінійного програмування. Нижче мова йде про методи прямого пошуку, для реалізації яких потрібні лише значення цільової функції; в наступному розділі розглядаються градієнтні методи і методи другого порядку. Тут передбачається, що f (x) неперервна, а може як існувати, так і не існувати, оскільки відповідні числові значення не використовуються. Однак слід зазначити, що методи прямого пошуку можна застосовувати для вирішення задач, в яких існує, і вони часто використовуються в тих випадках, коли являє собою складну векторну функцію керованих змінних. Нарешті, в цьому і наступних розділах передбачається, що функція f (х) унімодальному в даній області. Якщо ж вивчаються методи застосовуються для аналізу мультимодальних функцій, то доводиться обмежуватися ідентифікацією локальних мінімумів.
Багатовимірні методи, що реалізують процедуру пошуку оптимуму на основі обчислення значень функції, із загальних позицій можна розділити на евристичні та теоретичні. Евристичні методи, як це випливає з назви, реалізують процедури пошуку за допомогою інтуїтивних геометричних уявлень і забезпечують отримання приватних емпіричних результатів. З іншого боку, теоретичні методи засновані на фундаментальних математичних теоремах і володіють такими операційними властивостями, як збіжність (принаймні при виконанні деяких певних умов). Нижче детально розглядаються три методи прямого пошуку:
1) пошук по симплекс, або S ^{2-метод;}
2) метод пошуку Хука-Дживса;
3) метод пов'язаних напрямків Пауелла.
Перші два з перерахованих методів відносяться до категорії евристичних і реалізують принципово різняться стратегії пошуку. У процесі пошуку по S ^{2-методом} послідовно оперують регулярними симплексом в просторі керованих змінних, тоді як при реалізації методу Хука-Дживса використовується фіксоване безліч (координатних) напрямків, обираних рекурсивним способом. Метод Пауелла заснований на теоретичних результатах і орієнтований на вирішення завдань з квадратичними цільовими функціями; для таких завдань метод сходиться за кінцеве число ітерацій. До числа загальних особливостей всіх трьох методів слід віднести відносну простоту відповідних обчислювальних процедур, які легко реалізуються і швидко коригуються. З іншого боку, реалізація зазначених методів може вимагати (і часто вимагає) більш значних витрат часу в порівнянні з методами з використанням похідних.

4.1.1. Метод пошуку по симплекс (S ^{2-метод)}

Перші спроби розв'язання оптимізаційних задач без обмежень на основі прямого пошуку пов'язані з використанням одновимірних методів оптимізації. Як правило, при реалізації таких методів допустима область визначення показника якості функціонування системи (цільової функції) замінюється дискретною безліччю (гратами) точок простору керованих змінних, а потім використовуються різні стратегії зменшення області, яка містить рішення задачі. Часто ця процедура виявляється еквівалентній рівномірному пошуку у вузлах грат і, отже, непридатною для вирішення завдань з числом змінних, що перевищує 2. Більш корисна ідея полягає у виборі базової точки і оцінюванні значень цільової функції в точках, що оточують базову точку. Наприклад, при вирішенні завдання з двома змінними можна скористатися квадратним зразком, зображеним на рис.2


Рис 2. Квадратний зразок (приватний випадок кубічного зразка)
Потім «найкраща» з п'яти досліджуваних точок вибирається в якості наступної базової точки, навколо якої будується аналогічний зразок. Якщо жодна з кутових точок не має переваги перед базової, розміри зразка слід зменшити, після чого продовжити пошук.
Цей тип еволюційної оптимізації був використаний Боксом і іншими дослідниками для аналізу функціонування промислових підприємств, коли ефект варіювання значень змінних, що описують виробничі процеси, вимірюється з помилкою. У задачах великої розмірності обчислення значень цільової функції проводиться у всіх вершинах, а також у центрі ваги гіперкуба (гіперкуб - куб в n-мірному евклідовому просторі, тобто множина S = {x = ( ) | }, Де а і b - задані числа), тобто в точках так званого кубічного зразка. Якщо кількість змінних (розмірність простору, в якому ведеться пошук) дорівнює n, то пошук по кубічному зразком вимагає +1 Обчислень значення функцій для одного зразка. При збільшенні розмірності задачі необхідну кількість обчислень значення цільової функції зростає надзвичайно швидко. Таким чином, незважаючи на логічну простоту пошуку по кубічному зразком, виникає необхідність використання більш ефективних методів прямого пошуку для вирішення виникаючих на практиці завдань оптимізації.
Одна з викликають особливий інтерес стратегій пошуку покладена в основу методу пошуку по симплекс, запропонованого Спендлі, Хекста і Хімсвортом. Слід зазначити, що вказаний метод і інші подібні методи не мають відношення до симплекс-методу лінійного програмування, а схожість назв носить випадковий характер. Процедура симплексного пошуку Спендлі, Хекста і Хімсворта базується на тому, що експериментальним зразком, що містить найменшу кількість точок, є регулярний симплекс. Регулярний симплекс в n-мірному просторі представляє собою багатогранник, утворений n +1 равностоящими один від одного крапками-вершинами. Наприклад, у випадку двох змінних симплексом є рівносторонній трикутник; в тривимірному просторі симплекс є тетраедр. В алгоритмі симплексного пошуку використовується важлива властивість симплексу, згідно з яким новий симплекс можна побудувати на будь-якої грані початкового симплекса шляхом переносу обраної вершини на належне відстань уздовж прямої, проведеної через центр тяжіння інших вершин початкового симплекса. Отримана таким чином точка є вершиною нового симплекса, а обрана при побудові вершина початкового симплекса виключається. Неважко бачити, що при переході до нового симплекс потрібно одне обчислення значення цільової функції. Рис 3 ілюструє процес побудови нового симплекса на площині.



Ріс.3.Построеніе нового симплекса.
а - початковий симплекс
б - новий симплекс

Робота алгоритму симплексного пошуку починається з побудови регулярного симплекса у просторі незалежних змінних і оцінювання значень цільової функції в кожній з вершин симплекса. При цьому визначається вершина, якої відповідає найбільше значення цільової функції. Потім знайдена вершина проектується через центр ваги інших вершин симплекса в нову точку, яка використовується як вершини нового симплекса. Якщо функція спадає досить плавно, ітерації тривають до тих пір, поки або не буде накрита точка мінімуму, або не почнеться циклічний рух по двох або більше симплексом. У таких ситуаціях можна скористатися наступними трьома правилами.