а умови непустоту множин допустимих планів) і опукле програмування (також за деяких умов регулярності, серед яких найбільш відомим є умова Слейтера, що вимагає існування внутрішньої точки для безлічі, що задається обмеженнями (2 )).
Теорема Куна-Таккера. Якщо задача (4) є завданням опуклого програмування, що задовольняє умові Слейтера, то необхідною і достатньою умовою оптимальності плану x0 k X є існування такого y0 k Y, що пара (x0, у0) є сідловою функції Лагранжа, тобто задовольняє (8) .
Відповідно до теоремами подвійності рішення задач математичного програмування можна зводити до знаходження сідлових точок, причому на множинах більш простої структури (без обмежень виду нерівностей (2)).
Градієнтні методи.
Розглянемо спочатку задачу максимізації функції f (x) без обмежень, тобто у разі, коли Х збігається з усім простором R n. Градієнт функції f (x) позначимо f 1 (х). Умова оптимальності в цьому випадку має вигляд, проте безпосереднє рішення системи рівнянь (9) може виявитися надто складним.
1 (х)=0
Тому на практиці поступають таким чином. Вибираючи довільну початкову точку х1, будують ітеративний процес
+ 1=xk + ak f 1 (xk), k=1, 2, _
Число ak називають довжиною кроку або просто кроком. Якщо все ak рівні між собою, то маємо процес з постійним кроком.
Процес (10), що лежить в основі градієнтних методів, являє собою рух у бік зростання функції f (x), тому що якщо f 1 (хk)? 0, то завжди можна вибрати ak так, що f (xk + 1)> f (xk). Існують різні способи вибору ak. Взагалі кажучи, найкращим є вибір такого ak, при якому забезпечується максимальне зростання функції f (x). Таке ak знаходиться з умови
Градієнтний метод пошуку екстремуму (10) з вибором кроку за способом (11) називається методом якнайшвидшого підйому (або спуску для задачі на мінімум). Такий метод вимагає найменшого числа ітерацій, але зате на кожному кроці доводиться вирішувати додаткову завдання пошуку екстремуму (11) (правда, в одновимірному випадку). На практиці часто задовольняються знаходженням будь-якого ak, забезпечує зростання функції. Для цього беруть довільне ak і перевіряють умова зростання. Якщо воно не виконується, то дроблять ak до тих пір, поки ця умова не буде виконана (таке досить мале ak при f 1 (хk)? 0 існує завжди).
Процес (10), очевидно, зупиняється, коли виконана умова (9). При цьому якщо функція f (x) увігнута, то знайдена стаціонарна точка буде вирішенням завдання максимізації. В іншому випадку необхідно провести додатково дослідження функції f (x) в околиці знайденої точки. Однак, навіть якщо вона буде точкою максимуму, в неопуклого випадку важко визначити, локальний це максимум або глобальний. Тому градієнтні методи забезпечують знаходження глобального екстремуму тільки для увігнутих (опуклих) функцій, а в загальному випадку дають лише локальні екстремуми (при цьому можна спробувати знайти глобальний екстремум, застосовуючи ітеративний процес багато разів з різними початковими точками).
Якщо розглядається задача максимізації f (x) при обмеженнях, тобто коли Х не збігається з R n, то безпосереднє застосування процесу (10) може призвести до порушення обмежень, навіть якщо початкова точка x1 k X. Однак ці труднощі можна...
