科研之友
微信
新浪微博
Facebook
分享链接
摘要
In this paper, we present a Mehrotra-type predictor-corrector infeasible-interior-point method, based on the one-norm wide neighborhood, for semi-definite programming. The proposed algorithm uses Mehrotra's adaptive updating scheme for the centering parameter, which incorporates a safeguard strategy that keeps the iterates in a prescribed neighborhood and allows to get a reasonably large step size. Moreover, by using an important inequality that is the relationship between the one-norm and the Frobenius-norm, the convergence is shown for a commutative class of search directions. In particular, the complexity bound is O(nlog epsilon-1) for Nesterov-Todd direction, and O(n3/2log epsilon-1) for Helmberg-Kojima-Monteiro directions, where epsilon is the required precision. The derived complexity bounds coincide with the currently best known theoretical complexity bounds obtained so far for the infeasible semi-definite programming. Some preliminary numerical results are provided as well.
