The Dual of Linear Programming (LP)

In some cases, the dual problem of an LP problem might be easier to solve than the primal problem. If the primal is a minimization problem, the dual will be a maximization problem, and vice versa. So, depending on the specifics of the problem (simpler constraints or objective function), it might be easier to solve the dual problem than the primal problem.

Calculation of the dual objective

Consider an LP problem whose primal is given as follows:

where $c \in \R^d$ is the cost vector, $A \in \R^{m \times d}$ is the constraint matrix, and $b \in \R^m$ is the constraint vector.

The Lagrangian function $\pounds(x, \lambda)$ is given by the following:

where $\lambda \in \R^m$ is the vector of the nonnegative Lagrange multipliers. Rearranging the terms corresponding to $x$ yields the following:

The dual of Lagrangian is given as follows:

Because $\pounds(x, \lambda)$ is a convex function, we can find its minimum (with respect to $x$) using the gradient-solving ...