On the complexity of approximating a KKT point of quadratic programming

We present a potential reduction algorithm to approximate a Karush—Kuhn—Tucker (KKT) point of general quadratic programming (QP). We show that the algorithm is a fully polynomial-time approximation scheme, and its running-time dependency on accuracy (0, 1) is O((l/) log(l/) log(log(l/))), compared to the previously best-known result O((l/)²). Furthermore, the limit of the KKT point satisfies the second-order necessary optimality condition of being a local minimizer. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research support in part by NSF grants DDM-9207347 and DMI-9522507, and the Iowa Business School Summer Grant.