In this paper, we propose an arc-search interior-point algorithm for convex quadratic programming with a wide neighborhood of the central path, which searches the optimizers along the ellipses that approximate the entire central path. The favorable polynomial complexity bound of the algorithm is obtained, namely O ( n log(( x 0)T s 0/ε)) which is as good as the linear programming analogue. Finally, the numerical experiments show that the proposed algorithm is efficient.
|