A Path-Following Interior Point Algorithm for Smooth Convex Programming

Author: Liang-Ju Chu(Department of Mathematics, National Taiwan Normal University)

Abstract：

We extend the Monteiro-Adler path-following interior point algorithm for solving smooth convex programming. Under a kind of strict feasibility assumption, we show that the algorithm under modification requires a total of number of iterations, and the total arithmetic operations are not more than , where t is the initial input size. As an application to usual linear or convex quadratic programming, this algorithm solves the pair of primal and dual problems in at most iterations, and the total arithmetic operations are shown to be of the order of , where L is the input size. Moreover, we show that any sequence generated by the algorithm is bounded, and that every cluster point is a maximal complementary solution in the sense of McLinden [16,17].

Keywords：Smooth convex programming, path-following interior point algorithm, complementarity problem, maximal complementary solution

《Full Text》