A New Polynomial Time Algorithm for Convex Quadratic Programming Problem

Shiquan Wu and N. Xiu
Institute of Applied Mathemetics, Academia Sinica
wsq@amath8.amt.ac.cn

Abstract

In this paper, we will consider the following convex quadratic programming (CQP) problem:

where is symmetric and positive semi-definite, , are constant vectors and is a matrix.

The main result of this paper is to propose a new polynomial algorithm for (CQP), unlike the interior point methods, in each iteration of the new algorithm, only a projection to the positive orthant is needed which is very simple to implement. It is shown for the first time that this kind of projection method is polynomial.

It is well known that a point is an optimal solution of (CQP) if and only if there exists and such that is a solution of (KKT):

Let

Then (KKT) is equivalent to the following variational inequality problem

Denote

We have

 

where . Now we may outline the new algorithm as follows:

0:

Given , and .

1:

If (the solution set of (KKT)), then stop.

2:

Find such that

 

where .

3:

Compute the new iterative point

 

.

4:

, go to Step 1.

From (4-6) we know that the computation at each iteration is very simple and the sparseness of the original problem is preserved. So it is hoped to be efficient for large scale problems.