On the complexity of approximating a KKT point of quadratic programming

作     者：Ye, YY 

作者机构：Univ Iowa Coll Business Adm Dept Management Sci Iowa City IA 52242 USA 

出 版 物：《MATHEMATICAL PROGRAMMING》 (数学规划)

年 卷 期：1998年第80卷第2期

页      面：195-211页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0835[工学-软件工程] 0701[理学-数学] 

基　　金：National Science Foundation  NSF  (9522507) 

主　　题：quadratic programming KKT point local minimizer fully polynomial-time approximation scheme 

摘      要：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 epsilon is an element of (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. (C) 1998 The Mathematical Programming Society,Inc. Published by Elsevier Science B.V.