Quadratic programming

From DDWiki

Quadratic programming (QP) is a specific mathematical programming problem. The general QP form can be expressed as:

Minimize

with respect to x subject to

where Q is matrix is a symmetric matrix and c is a vector comprising of coefficients to describe the linear terms in the f(x). Matrix A represents the coefficients of inequality constraint and b is the constant vector on the right hand side.

When f(x) is strictly convex for all feasible points, the local optimal solution is also the global optimum. When the optimum is the minimum point, positive definite of Q matrix provides the sufficient condition of the optimal solution. Further, when Q=0, the problem simply becomes a linear programming problem.

QP in Lagrangian form

To solve the QP problem, the function needs to be formulated into Lagrangian form:

where µ is Lagrangian multiplier. The Karush-Kuhn-Tucker (KKT) conditions for a local minimum are given by:

Reference

• Singiresu S. Rao, 1996, Engineering Optimization: Theory and Practice, 3rd Ed., Wiley-Interscience.