g(x)=( g1(x) g2(x)-... gm(x)) задовільняють умові , множина , - опукла.
Нехай маємо задачу
(*)
Позначимо та введемо функцію Лагранжа
Тоді справедлива Теорема Куна Таккера
Якщо задачa опуклого програмування задовольняє умові регулярності (це умова Слейтера: існування хоча б однієї допустимої точки в обмеженнях (*)), то оптимальне рішення по х: = х * існує, тоді і тільки тоді, якщо існує вектор , , що точка (х*,λ*) є сідловою для функції Лагранжа
Наслідок:
вирішувати задачу (*) еквівалентно знаходженню сідлової точки функції !!!!!!!!!!!!!!!
Лагранжа
Метод множників Лагранжа
По суті це метод зведення задачі умовної оптимізації до задачі безумовної оптимізації.
Для вирішення задачі побудуємо функцію Лагранжа
де ,i=1,..,m - називають множниками Лагранжа
Визначимо часткові похідні , та прирівняємо їх нулю. Одержимо систему нелінійних рівнянь відносно n+m змінних
(**)
Необхідно вирішити систему нелінійних рівнянь (**), - ми звертаємося до попередньої теми, де описаний чисельний метод вирішення задач безумовної оптимізації та як варіант, вирішуємо систему нелінійних рівнянь методом найшвидшого спуску (метод Ньютона) – это один из возможных вариантов(чи іншими чисельними підходами: метод Зейделя, генетичний алгоритм, метод рою частинок, інше) - завдання вирішено
(нахожд седл точки – это реш системы мин
Достарыңызбен бөлісу: |
