A LARGE-STEP ANALYTIC CENTER METHOD FOR A CLASS OF SMOOTH CONVEX PROGRAMMING PROBLEMS

作     者：Den Hertog, D. Roos, C. Terlaky, T. 

作者机构：Delft Univ Technol Fac Tech Math & Comp Sci NL-2600 GA Delft Netherlands Lorand Eotvos Univ Dept Operat Res H-1088 Budapest Hungary 

出 版 物：《SIAM JOURNAL ON OPTIMIZATION》 (工业与应用数学会最优化杂志)

年 卷 期：1992年第2卷第1期

页      面：55-70页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：convex programming analytic center method Newton method 

摘      要：In this paper, a large-step analytic center method for smooth convex programming is proposed. The method is a natural implementation of the classical method of centers. It is assumed that the objective and constraint functions fulfil the so-called Relative Lipschitz Condition, with Lipschitz constant M 0. A great advantage of the method, over the existing path-following methods, is that the steps can be made long by performing linesearches. In this method linesearches are performed along the Newton direction with respect to a strictly convex potential function when located far away from the central path. When sufficiently close to this path a lower bound for the optimal value is updated. It is proven that the number of iterations required by the algorithm to converge to an epsilon-optimal solution is O((1 + M-2) root n vertical bar ln epsilon vertical bar) or O((1 + M-2) n vertical bar ln epsilon vertical bar) depending on the updating scheme for the lower bound.