2.2. Множники Лагранжа

За допомогою методу множників Лагранжа по суті встановлюються необхідні умови, що дозволяють ідентифікувати точки оптимуму в задачах оптимізації з обмеженнями у вигляді рівностей. При цьому завдання з обмеженнями перетворюється на еквівалентну завдання безумовної оптимізації, в якій фігурують деякі невідомі параметри, звані множниками Лагранжа. Розглянемо задачу мінімізації функції n змінних з урахуванням одного обмеження у вигляді рівності: Мінімізувати (3) при обмеженнях (4) Відповідно до методу множників Лагранжа це завдання перетвориться в таку задачу безумовної оптимізації: мінімізувати L (x, u) = f (x)-u * h (x) (5) Функція L (х; u) називається функцією Лагранжа, u - невідома стала, яка носить назву множника Лагранжа. На знак u ніяких вимог не накладається. Нехай при заданому значенні u = u ⁰ безумовний мінімум функції L (x, u) по х досягається в точці і задовольняє рівнянню . Тоді, як неважко бачити, x ⁰ мінімізує (1) з урахуванням (4), оскільки для всіх значень х, що задовольняють (4), і L (x, u) = min f (x). Зрозуміло, необхідно підібрати значення u = u ° таким чином, щоб координата точки безумовного мінімуму х ° задовольняла рівності (4). Це можна зробити, якщо, розглядаючи u як змінну, знайти безумовний мінімум функції (5) у вигляді функції u, а потім вибрати значення u, при якому виконується рівність (4). Проілюструємо це на конкретному прикладі. Приклад 2 Мінімізувати при обмеженні = 0 Відповідна завдання безумовної оптимізації записується в наступному вигляді: мінімізувати L (x, u) = -U Рішення. Прирівнявши дві компоненти градієнта L до нуля, одержимо Для того щоб перевірити, чи відповідає стаціонарна точка х ° мінімуму, обчислимо елементи матриці Гессе функції L (х; u), що розглядається як функція х, , яка виявляється позитивно визначеною. Це означає, що L (х,, u) - опукла функція х. Отже, координати , визначають точку глобального мінімуму. Оптимальне значення u знаходиться шляхом підстановки значень і в рівняння = 2, звідки 2u + u / 2 = 2 або . Таким чином, умовний мінімум досягається при і і дорівнює min f (x) = 4 / 5. При вирішенні завдання з прикладу 2 ми розглядали L (х; u) як функцію двох змінних і і, крім того, припускали, що значення параметра u вибрано так, щоб виконувалося обмеження. Якщо ж рішення системи , J = 1,2,3, ..., n у вигляді явних функцій u отримати не можна, то значення х і u знаходяться шляхом рішення наступної системи, що складається з n +1 рівнянь з n +1 невідомими: , J = 1,2,3, ..., n Для знаходження всіх можливих рішень даної системи можна використовувати чисельні методи пошуку (наприклад, метод Ньютона). Для кожного з рішень ( ) Слід обчислити елементи матриці Гессе функції L, що розглядається як функція х, і з'ясувати, чи є ця матриця позитивно визначеною (локальний мінімум) або негативно певної (локальний максимум). Метод множників Лагранжа можна поширити на випадок, коли завдання має кілька обмежень у вигляді рівностей. Розглянемо загальну задачу, в якій потрібно Мінімізувати f (x) при обмеженнях = 0, k = 1, 2, ..., К. Функція Лагранжа приймає наступний вигляд: L (x, u) = f (x) - Тут -Множники Лагранжа, тобто невідомі параметри, значення яких необхідно визначити. Прирівнюючи приватні похідні L по х до нуля, отримуємо таку систему n рівнянні з n невідомими: ... ... ... .. Якщо знайти рішення наведеної вище системи у вигляді функцій вектора u виявляється скрутним, то можна розширити систему шляхом включення до неї обмежень у вигляді рівностей Рішення розширеної системи, що складається з n + К рівнянь з n + К невідомими, визначає стаціонарну точку функції L. Потім реалізується процедура перевірки на мінімум чи максимум, яка проводиться на основі обчислення елементів матриці Гессе функції L, що розглядається як функція х, подібно до того, як це було зроблено в разі завдання з одним обмеженням. Для деяких завдань розширена система n + К рівнянь з n + K невідомими може не мати рішень, і метод множників Лагранжа виявляється непридатним. Слід, однак, відзначити, що такі завдання на практиці зустрічаються досить рідко.