|
|
Узагальнення методу множників Лагранжа. Теорема Куна-Таккера.⇐ ПредыдущаяСтр 11 из 11
Теорема Куна—Таккера Розглянутий метод множників Лагранжа уможливлює знаходження лише локальних сідлових точок функції Лагранжа. Теорема Куна—Таккера дає змогу встановити типи задач, для яких на множині допустимих розв’язків існує лише один глобальний екстремум зумовленого типу. Вона тісно пов’язана з необхідними та достатніми умовами існування сідлової точки. Розглянемо задачу нелінійного програмування, яку, не зменшуючи загальності, подамо у вигляді:
(Очевидно, що знак нерівності можна змінити на протилежний множенням лівої і правої частин обмеження на (– 1)). Теорема 8.1. (Теорема Куна—Таккера). Вектор Х* є оптимальним розв’язком задачі (8.22)—(8.24) тоді і тільки тоді, коли існує такий вектор
і функція мети Доведення. Необхідність. Нехай Х* — оптимальний план задачі (8.22)—(8.24), тобто є точкою глобального максимуму задачі. Отже, для всіх інших планів задачі Х з множини допустимих розв’язків виконуватиметься співвідношення:
Розглянемо тепер вектор З умови (8.21) маємо:
Для точки з координатами
Функція Для встановлення нерівності, що відповідає лівій частині умови (8.13), а саме:
Отже, у точці Х * функція Лагранжа має глобальний максимум по Х, що повністю доводить необхідність теореми. Достатність. Для доведення достатності умов теореми потрібно виходити з того, що Підставимо у нерівність (8.13) вираз функції Лагранжа (8.12) для задачі (8.22)—(8.23):
при всіх значеннях Розглянемо праву частину подвійної нерівності (8.26).
Остання нерівність має виконуватися для всіх
Тоді з лівої частини нерівності (8.26) маємо:
Через те що Отже, точка Х * задовольняє обмеження і надає максимального значення цільовій функції задачі, тому що для всіх інших Умови теореми Куна — Таккера виконуються лише для задач, що містять опуклі функції.
Градієнтні методи безумовної оптимізації 1.2.1 Загальна схема градієнтного спуску Як відомо, градієнт функції в деякій точці xk спрямований в бік найшвидшого локального зростання функції й перпендикулярний лінії рівня (поверхня постійного значення функції f (x), що проходить через точку xk). Вектор, протилежний градієнту, називається антиградієнтом, що спрямований убік найшвидшого убування функції f (x). Вибираючи як напрямок спуска pk антиградієнт - у точці xk, ми приходимо до ітераційного процесу виду: xk+1 = xk - k f' (xk), k>0, k=0, 1, 2, … У координатній формі цей процес записується в такий спосіб: Всі ітераційні процеси, у яких напрямок руху на кожному кроці збігається з антиградієнтом функції, називаються градієнтними методами. Вони відрізняються друг від друга тільки способом вибору кроку k. Існує багато різних способів вибору k, але найпоширеніші: метод з постійним кроком, метод із дробленням кроку й метод найшвидшого спуска. Метод найшвидшого спуска У градієнтному методі з постійним кроком величина кроку, що забезпечує убування функції f (x) від ітерації до ітерації, виявляється дуже малої, що приводить до необхідності проводити велику кількість ітерації для досягнення точки мінімуму. Тому методи спуска зі змінним кроком є більше ощадливими. Алгоритм, на кожній ітерації якого крок до вибирається з умови мінімуму функції f (x) у напрямку руху, тобто: називається методом найшвидшого спуска. Зрозуміло, цей спосіб вибору до складніше раніше розглянутих варіантів. Реалізація методу найшвидшого спуска припускає рішення на кожній ітерації досить трудомісткої допоміжної задачі одномірної мінімізації. Як правило, метод найшвидшого спуска, проте, дає виграш у числі машинних операцій, оскільки забезпечує рух із самим вигідним кроком, тому що рішення задачі одномірної мінімізації пов'язане з додатковими обчисленнями тільки самої функції f (x), тоді як основний машинний час витрачається на обчислення її градієнта.   ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...  Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...  ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...  Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
, (8.22)
, (8.23)
. (8.24)
, що при 
для всіх 
точка 
є сідловою точкою функції Лагранжа
,
для всіх 
угнута, а функції 
— опуклі.
.
, що відповідає точці глобального максимуму 
, і значення функції Лагранжа в точках 
, 
, 
, де 
— вектор множників Лагранжа, що відповідає Х.
, тоді
. (8.25)
можуть бути відмінними від нуля. Оскільки за умовою задачі 
, то лише за умови, що 
.
— лінійна відносно 
, тобто остання нерівність виконується для будь-якого 
— точка глобального мінімуму по 
, скористаємося також рівнянням (8.21), підсумувавши його по і: 
. За умовою теореми 
— угнуті функції і 
, 
— сідлова точка функції 
(тобто для 
(8.26)
.
.
, тобто нерівність справджується лише у разі, коли
.
.
, приходимо до нерівності 
, яка справджується для всіх значень