## Quadratic Programming (QP)

A quadratic programming (QP) problem is to minimize a quadratic function subject to some equality and/or inequality constraints: (233)

where is an positive definite matrix, an matrix, and is an M-D vector. Also, . Here the scalar constant can be dropped as it does not play any role in the optimization. Note that is a hyper elliptic paraboloid with the minimum at point in the N-D space.

We first consider the special case where the QP problem is only subject to equality constraints and we assume , i.e., the number of constraints is smaller than the number of unknowns in . Then the solution has to satisfy , i.e., it has to be on hyper planes in the N-D space.

The Lagrangian function of the QP problem is: (234)

To find the optimal solution, we first equate the derivatives of the Lagrangian with respect to both and to zero:      (235)

These two equations can be combined and expressed in matrix form as: (236)

We then solve this system of equations to get the optimal solution and the corresponding .

Example where  Solving this equation we get the solution and , at which the function is minimized subject to .

If , i.e., the number of equality constraints is the same as the number of variables, then the variable is uniquely determined by the linear system , as the intersect of hyper planes, independent of the objective function . Further if , i.e., the system is over constrained, and its solution does not exist in general. It is therefore more interesting to consider QP problems subject to both equality and inequality constraints: 