It is proposed to study extensions of Karmarkar's algorithm to global optimization of quadratic programs. Quadratic Feasibility over Simplex (QFS) refers to the problem of determining if a given quadratic form attains the value of zero over a simplex. This problem is fundamental to quadratic programming. Our feasibility algorithm, which is essentially an algorithm for QFS with a positive semidefinite form, consists of repeating the following steps: calculation of a "good" descent direction for an appropriately defined potential (barrier) function based on optimization over a circumscribing sphere, a line search for the potential function, and centralization using a projective transformation. It is proposed to generalize this approach to the indefinite case. Despite the NP-hardness of the indefinite case, the convergence of this approach in general for some special cases (even in worst-case exponential time) would result in an alternate algorithm for nonconvex programming which is expected to be competitive with those which, in the worst-case, are of exponential time and space complexity. Having studied convergence, it is planned to investigate computational approaches for such a procedure. As an alternate method for the calculation of descent direction, feasible direction methods with projective transformation will be investigated. It is also planned to study the effectiveness of projective algorithms within our earlier methods for nonconvex quadratic programs which require repeated application of a linear or convex quadratic programming algorithm. Finally, the implementation of the resulting algorithms using parallel architectures, such as NCUBE10 or ETA10 supercomputers, is planned.
