Quadratic Programming - Lagrangian Duality

Lagrangian Duality

See also: Dual problem

The Lagrangian dual of a QP is also a QP. To see that let us focus on the case where and Q is positive definite. We write the Lagrangian function as

Defining the (Lagrangian) dual function, defined as, we find an infimum of, using

hence the dual function is

hence the Lagrangian dual of the QP is

maximize:

subject to: .

Besides the Lagrangian duality theory, there are other duality pairings (e.g. Wolfe, etc.).

Read more about this topic:  Quadratic Programming