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

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

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

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

Математическое описание

Предположим, нам дан задача линейного программирования, с ${displaystyle xin mathbb {R} ^ {n}}$ и ${displaystyle Ain mathbb {R} ^ {m, n}}$ , следующего вида:

Максимум		${displaystyle c ^ {T} x}$
s.t.
		${displaystyle Axleq b}$

Если мы разделим ограничения на ${displaystyle A}$ такой, что ${displaystyle A_ {1} в mathbb {R} ^ {m_ {1}, n}}$ , ${displaystyle A_ {2} в mathbb {R} ^ {m_ {2}, n}}$ и ${displaystyle m_ {1} + m_ {2} = m}$ мы можем написать систему:

Максимум		${displaystyle c ^ {T} x}$
s.t.
(1)		${displaystyle A_ {1} xleq b_ {1}}$
(2)		${displaystyle A_ {2} xleq b_ {2}}$

Мы можем ввести ограничение (2) в цель:

Максимум		${displaystyle c ^ {T} x + лямбда ^ {T} (b_ {2} -A_ {2} x)}$
s.t.
(1)		${displaystyle A_ {1} xleq b_ {1}}$

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

Решение LR как оценка

Особенно полезно свойство, которое для любого фиксированного набора ${displaystyle {ilde {lambda}}}$ значений, оптимальный результат для задачи лагранжевой релаксации будет не меньше, чем оптимальный результат для исходной задачи. Чтобы увидеть это, позвольте ${displaystyle {hat {x}}}$ оптимальное решение исходной задачи, и пусть ${displaystyle {ar {x}}}$ - оптимальное решение лагранжевой релаксации. Тогда мы можем увидеть, что

{displaystyle c ^ {T} {hat {x}} leq c ^ {T} {hat {x}} + {ilde {lambda}} ^ {T} (b_ {2} -A_ {2} {hat {x }}) leq c ^ {T} {ar {x}} + {ilde {lambda}} ^ {T} (b_ {2} -A_ {2} {ar {x}})}

Первое неравенство верно, потому что ${displaystyle {hat {x}}}$ выполнимо в исходной задаче, а второе неравенство верно, поскольку ${displaystyle {ar {x}}}$ - оптимальное решение лагранжевой релаксации.

Итерация в направлении решения исходной проблемы

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

мин

{displaystyle P (лямбда)}

s.t.

{displaystyle lambda geq 0}

где мы определяем ${displaystyle P (лямбда)}$ в качестве

Максимум		${displaystyle c ^ {T} x + лямбда ^ {T} (b_ {2} -A_ {2} x)}$
s.t.
(1)		${displaystyle A_ {1} xleq b_ {1}}$

Таким образом, алгоритм лагранжевой релаксации переходит к исследованию диапазона возможных ${displaystyle lambda}$ значения, стремясь минимизировать результат, возвращаемый внутренним ${displaystyle P}$ проблема. Каждое значение, возвращаемое ${displaystyle P}$ является потенциальной верхней границей задачи, наименьшая из которых сохраняется как лучшая верхняя граница. Если мы дополнительно воспользуемся эвристикой, вероятно, посеянной ${displaystyle {ar {x}}}$ значения, возвращаемые ${displaystyle P}$ , чтобы найти возможные решения исходной проблемы, затем мы можем выполнять итерацию до тех пор, пока наилучшая верхняя граница и стоимость наилучшего допустимого решения не сойдутся до желаемого допуска.

Связанные методы

В расширенный лагранжев метод очень похож по духу на метод лагранжевой релаксации, но добавляет дополнительный член и обновляет двойные параметры ${displaystyle lambda}$ в более принципиальной манере. Он был представлен в 1970-х годах и широко использовался.

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

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

Содержание

Математическое описание

Решение LR как оценка

Итерация в направлении решения исходной проблемы

Связанные методы

Рекомендации

Книги

Статьи