Complexity and numerical implementation of a new full-Newton step interior point method for weighted convex quadratic optimization.

Abstract

As an extension of convex quadratic optimization (CQO) problems, the weighted convex quadratic optimization (WCQO) plays an important role in the domain of mathematical programming and engineering. In this paper, we propose a short-step primal-dual interior-point algorithm for solving WCQO based on the strategy of weighted-path. The latter generates only full-Newton steps and requires no line search. Under appropriate conditions, the algorithm converges locally quadratically to an optimal solution of WCQO. Moreover, it has the best well-known polynomial complexity, namely, O(√n log(n/ϵ)). Finally, some numerical results are reported to confirm the efficiency  of our proposed algorithm.