Лагранжева релаксация

---

В области математической оптимизации лагранжева релаксация — это метод релаксации, который аппроксимирует сложную задачу условной оптимизации более простой задачей. Решение ослабленной задачи является приблизительным решением исходной задачи и дает полезную информацию.

Метод наказывает нарушения ограничений неравенства с помощью множителя Лагранжа , который налагает издержки на нарушения. Эти дополнительные затраты используются вместо строгих ограничений неравенства при оптимизации. На практике эту ослабленную задачу часто можно решить легче, чем исходную.

Задача максимизации функции Лагранжа двойственных переменных (множителей Лагранжа) является двойственной задачей Лагранжа .

Предположим, что нам дана задача линейного программирования с и следующего вида:${\ Displaystyle х \ в \ mathbb {R} ^ {п}}$${\ Displaystyle А \ в \ mathbb {R} ^ {м, п}}$

Если мы разделим ограничения таким образом, что и мы можем написать систему:${\ Displaystyle А}$${\ Displaystyle А_ {1} \ в \ mathbb {R} ^ {м_ {1}, п}}$${\ Displaystyle А_ {2} \ в \ mathbb {R} ^ {м_ {2}, п}}$${\ Displaystyle м_ {1} + м_ {2} = м}$

Если мы допустим неотрицательные веса, мы будем оштрафованы, если нарушим ограничение (2), и мы также вознаградимся, если мы строго соблюдаем ограничение. Приведенная выше система называется лагранжевой релаксацией нашей исходной задачи.${\ displaystyle \ lambda = (\ lambda _ {1}, \ ldots, \ lambda _ {m_ {2}})}$

---