On the complexity of approximating a KKT point of quadratic programming
Yinyu Ye
We present a potential reduction algorithm to approximate a
Karush-Kuhn-Tucker (KKT) point of general quadratic
programming. We show that the algorithm is a fully polynomial-time
approximation scheme, and its running-time dependency on
accuracy $\epsilon\in (0,1)$ is
$O((1/\epsilon)\log(1/\epsilon)\log(\log(1/\epsilon)))$,
compared to the previously best-known result $O((1/\epsilon)^2)$.
Furthermore, the limit of the KKT point satisfies the second-order necessary
optimality condition of being a local minimizer.
![[POSTSCRIPT]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)