Quadratic Programming Problem

A quadratic programming problem is a mathematical programming problem, which consists of an objective function composed of linear and quadratic terms and a set of linear constraints. A quadratic programming problem can be solved by a modification of the simplex procedure.

The general quadratic programming problem is given by

Maximize f = c_jx_j + c_jkx_jx_k

subject to
a_ijx_j - b_i ≤ 0 , i = 1, 2, ...., m

x_j ≥ 0, j = 1, 2, ...., n

If the quadratic form is negative semidefinite and symmetric, then it is a concave function of the decision variables. Since the constraints are linear, the feasible region is convex. Thus, Kuhn-Tucker conditions in this case are both necessary and sufficient.

To derive these conditions, we use multipliers λ_i ( i = 1, 2, ...., m) corresponding to the constraints

a_ijx_j - b_i ≤ 0;
and μ_j ( j = 1, 2, ...., n) corresponding to the non-negativity constraints.

df/dx_j = c_j + 2 c_jkx_k , j = 1, 2, ...., n

On small screens, use horizontal scrollbar to view full table

d ---- dxj

aijxj - bi

=

aij ; i = 1, 2, ...., m; j = 1, 2, ...., n

Let S_i = b_i - a_ijx_j; i = 1, 2, ...., m .....(i)
Where S_i is a slack variable.

Hence, Kuhn-Tucker conditions are given by

c_j + 2 c_jkx_k - λ_ia_ij + μ_j = 0; j = 1, 2, ...., n

or - 2 c_jkx_k + λ_ia_ij - μ_j = c_j; j = 1, 2, ...., n .....(ii)

S_iλ_i = 0, x_jμ_j = 0
S_i, λ_i, μ_j, x_j ≥ 0, i = 1, 2, ...., m; j = 1, 2, ...., n

If we ensure that the pairs ( λ_i, S_i) and (μ_j, x_j) are not into the basis simultaneously, then the conditions S_iλ_i = 0 and x_jμ_j = 0 will be automatically satisfied. Therefore, we use simplex procedure with a restricted entry rule.