The Dual of Quadratic Programing (QP)

The dual of a QP problem is also another QP problem but with simpler box constraints. Therefore, no matter how complex the primal constraints are, the dual of a QP problem will always have box constraints and can always be solved using the PGD algorithm.

Calculating the dual of the QP problem

Consider a QP problem with the primal objective given as follows:

where $A \in \R^{m \times d}$, $b \in \R^m$, $c \in \R^d$, and $Q \in \R^{d\times d}$ is a square symmetric positive definite matrix.

The Lagrangian function is given by the following:

where $\lambda \in \R^m \geq 0$ are Lagrange multipliers.

Note: The Lagrangian here is a convex function because it is a combination of quadratic and linear functions. Therefore, the local optimum is always the global optimal solution.

To find the dual objective $\mathcal{D}(\lambda) = \min_{x \in \R^d} \pounds(x, \lambda)$ ...