6. A finite algorithm to the general quadratic programming problem (with a condition set given by its internal representation)
Denote by the principal submatrices of A(h) in a nondecreasing order of their size; i.e. the first r such submatrices
are of order 1, while the last such submatrix
is identical to A(h). The sequential order of submatrices of same algebraic order is optional.
The algorithm works in the following way: After setting the initial values for variables and k, a complex test is performed cyclically for every k, increasing its value in each step. In the meantime the value of
may be either increased or left unchanged depending on the result of the test. Whenever it is increased, then also the vector
is redefined. After completing the algorithm it turns out that either the problem is unbounded (the value of
is plus infinity), or the last pair of
and
yields a solution of the derived problem (
and
).
The cyclic test begins with deciding whether the matrix is almost copositive or not. For this procedure, according to the Cottle-Habetler-Lemke's theorem [3, Theorem 3.1], signs of the determinant and the adjoint's entries should be determined and checked. However, Keller's theorem [3, Theorem 4.2] reduces testing of the adjoint to a single column of it.
Algorithm 6.1. (placed separately)
Some remarks about the selection of u and . About this matter we give the following explanation: It will be shown during the proof of the algorithm that if
then the matrix adj
has at least one nonzero column vector. If
denote all such row indices of A that belong to the rows of submatrix
, then the r-dimensional extension of an s-dimensional vector u is meant to be the vector v, for which
(6.1)
and
(6.2)
hold.
The extended vector v is normed according to the flow description of the algorithm (Step B7). Notation applies to the normed vector. The aim of norming is to ensure that the second line of (5.8) will hold for
. (It will be seen that the sum
, which stands in the denominator, cannot be zero valued.)
After determining the vector it is worth to compute also the vector
(6.3)
not only at the end, but also during the procedure, each time when the algorithm updates the value of vector . (Step B9 of the algorithm.) All such vectors are obviously feasible solutions of problem (5.1). Besides, it will turn out during the proof of the algorithm, that obtaining a new value for x always results in an improvement of the objective function's value
. These facts make it possible that even partial results can be usable in case when the procedure is interrupted for any reason.
If A is of order r, then the main cycle of the algorithm is repeated times. Therefore the algorithm consists of an exponential number of operations.
It is possible; however, to specify other terminating conditions instead of k > N, which lead to the reduction of the number of operations. Then only the principal submatrices of relatively smaller sizes should be tested. For characterization of real symmetric matrices we shall use the following notions.
Definition 6.2. For an arbitrary real symmetric matrix A let us denote by
It can be seen that any of the following conditions can be chosen as a terminating condition for the main cycle of our algorithm.
We expect that the third of these conditions is more effective than the other ones, but the latters are easier to check. Otherwise, the following relations are valid for the right hand sides of the terminating conditions listed above:
negrank
rank
ordoD + 1
rank
rankD + 2
negrank
negordo
Proofs will be outlined in Section 8.