is added to the original constraints as an additional constraint, and each other right hand side values are modified to zero.) With the help of these programs the following QP problems have been solved on a PC.10. Computational results
We have experience with some smaller size nonconvex quadratic programming problems. The computer code has been written in Fortran. In order to deal with usual QP problems, a separate program has been written for the determination of the extreme points and extreme directions by the help of the method given by Manaš and Nedoma [10]. (Only a slight modification has to be taken on this method for the case of the extreme directions. For this purpose is added to the original constraints as an additional constraint, and each other right hand side values are modified to zero.) With the help of these programs the following QP problems have been solved on a PC.
Problem 1 - example of Balas [1]:
minimize
subject to
,
.
Problem 2 - example of Majthay et al. [9]:
maximize 
subject to 
,
,
.
Problems 3 and 4 - examples of Kough [8]:
maximize 
subject to
,
.
(Matrices A, B and C contain 5 rows in the first case, 8 rows in the second case.)
Problem 5 - example of Kough [8]:
(The same conditions set as for Problem 4, but the objective function is changed as follows.)
maximize 
Problem 6: The union (Descartes product) of Problem 1 and Problem 2.
Problem 7: The union (Descartes product) of two identical problems.
Problems 8, 9, and 10: Problems with a single constraint, which is 
in the first and second case, while 
in the third case.
Problems 11 and 12: Two further examples to test the algorithm.
The following table contains the main characteristics together with the running times of the problems listed above.
Table 10.1. (placed separately)
In the next table we serve more details about Problems 1-5 by listing the sequence of feasible solutions found during the program execution. Also it can be seen there, how the objective function becomes better and better from step to step.
Table 10.2. (placed separately)
Remark 10.3. My attention was drawn to Kough’s paper [8] by J. Fülöp. He also told me that the report contained in [8] does not give the right optimal solution for the first example problem of reference [8] (i.e. Problem 3 in our notation). As a matter of fact, my algorithm produces a solution for this problem with the same objective function as the one, computed by J. Fülöp.
Remark 10.4. The general QP problem can be formulated as follows:
(10.1) minimize
subject to 
and 
.
The main difference between this problem and problem (5.1) is that the condition set is given by its external representation, i.e. in the form of linear inequalities in (10.1), while it is given by its internal representation, i.e. by the help of extreme generators in (5.1). Therefore the algorithm developed here for problem (5.1) will be applicable for the solution of general QP problems only if we can find the extreme points and extreme directions of the polyhedral set of conditions. For this reason, the algorithm can be applied by a direct manner to solve problems containing only a few number of constraints and variables. The applicability of the algorithm depends; however, on the actual number of the extreme points and extreme directions rather than the number of constraints and variables.
We see a better opportunity for the indirect application of the algorithm by combining it with other QP methods.
I hope that the material discussed in this paper will broaden the mathematical arsenal of QP in the nonconvex case. The algorithm in itself, as it has been presented in this paper can be applied to QP problems containing only a few number of constaints and variables, so it should be combined with other QP methods, or somehow further developed. On the other hand, it might also be interesting to find applications of the outlined methods with respect to the more general classes of parametral matrices and the corresponding algorithms.
References