Lagrange Duality

Lagrange multipliers and the primal-dual theorem can be used to convert any convex-constrained optimization problem into a simpler optimization problem. Lagrange multipliers are very useful in transforming constrained optimizations, such as LP and QP problems, into simpler optimization problems.

Lagrange multipliers

Suppose we want to solve the following constrained optimization problem:

Here, we assume both $g(.)$ and $h_i(.)$ are convex functions.

One of the obvious ways to convert the constrained problem above into an unconstrained one is to use an indicator function, as follows:

where $\textbf{1}(z)$ ($z$ is any arbitrary input in $\R$) is known as the indicator function and represented as follows:

This gives an infinite penalty if the constraint is not satisfied and, therefore, would provide the same solution as the original constrained problem. However, this infinite-step function is equally difficult to optimize because of its steepness. We can overcome this challenge by using Lagrange multipliers. The idea of Lagrange multipliers is to replace the indicator function with a linear function as follows:

where $\lambda_i \geq 0$ are known as Lagrange multipliers. Here, we have concatenated all the constraints $h_i(x)$ into a vector $h(x)$ and all Lagrange multipliers into a vector $\lambda \in {\mathbb{R}}^m$ ...