Quadratic programming

From DDWiki

Jump to: navigation, search
This article has been marked as incomplete and requiring attention. You can help DDWiki by expanding it.


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

Minimize

f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T Q\mathbf{x} + \mathbf{c}^T \mathbf{x}

with respect to x subject to

\mathbf{g(x) = Ax -b } \le \mathbf{0}
\mathbf{x>0}

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:

L(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T Q\mathbf{x} + \mathbf{c}^T \mathbf{x} + \mathbf{\mu (Ax-b)}

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

\mathbf{\nabla_x} L=0 \Rightarrow \mathbf{Q}^T+\mathbf{c}+\mathbf{\mu A} = 0
\mathbf{\nabla_\mu} L=0 \Rightarrow \mathbf{Ax - b} \le \mathbf{0}
\mathbf{\mu g(x)=0} \Rightarrow \mathbf{\mu(Ax - b)=0}
\mathbf{\mu>0}
\mathbf{x>0}

Reference

  • Singiresu S. Rao, 1996, Engineering Optimization: Theory and Practice, 3rd Ed., Wiley-Interscience.
Retrieved from "http://ddl.me.cmu.edu/ddwiki/index.php/Quadratic_programming"