Lagrangian Duality

Lagrangian dual

In optimization theory, the Lagrangian dual is a technique for transforming an optimization problem, also known as a primal problem, into a different problem, called the dual problem, which provides a lower bound on the optimal value of the original problem. The Lagrangian dual is named after Joseph-Louis Lagrange, a famous mathematician who significantly contributed to calculus and mechanics.

Lagrangian function

The Lagrangian dual is obtained by introducing a set of auxiliary variables, called Lagrange multipliers or dual variables, to enforce the constraints of the original optimization problem. The resulting Lagrangian function is a function of the original variables, also known as decision variables and the dual variables. It provides a way to express the original optimization problem as a maximization problem over the space of the Lagrange multipliers.

Note: In mathematical optimization, Lagrange multipliers are a set of coefficients that are introduced to find the maxima or minima of a function subject to constraints. They allow the transformation of a constrained optimization problem into an unconstrained one by incorporating the constraints into the objective function.

Primal to dual transformation

Consider an optimization problem (not necessarily convex) in the standard form as follows:

$$\begin{aligned} \min_{\bold x} \quad & f_0(\bold x)\\ \textrm{s.t.} \quad & f_i(\bold x)\le0 \quad & i=1,2,\dots,m\\ \quad & h_j(\bold x)=0 \quad & j=1,2,\dots,k \\ \end{aligned}$$ ...