Nonlinear Programming

Introduction To Quadratic Programming

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.

Quadratic programming model is the simplest nonlinear extension of the linear programming model.

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 l_i ( i = 1, 2, ...., m) corresponding to the constraints

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

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

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 - l_ia_ij + m_j = 0; j = 1, 2, ...., n

or - 2 c_jkx_k + l_ia_ij - m_j = c_j; j = 1, 2, ...., n .....(ii)

S_il_i = 0, x_jm_j = 0
S_i, l_i, m_j, x_j ³ 0, i = 1, 2, ...., m; j = 1, 2, ...., n

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

Don't be too concerned about this horrendous notation. The next section provides an example that will make the concepts clear. So you can easily skip this section and move to the next example.