|
Abstract
|
In this paper, we propose a Mizuno-Todd-Ye type predictor-corrector infeasible interiorpoint
method for linear optimization based on a wide neighborhood of the central path. According
to Ai-Zhang’s original idea, we use two directions of distinct and orthogonal corresponding to the
negative and positive parts of the right side vector of the centering equation of the central path.
In the predictor stage, the step size along the corresponded infeasible directions to the negative
part is chosen. In the corrector stage by modifying the positive directions system a full-Newton
step is removed. We show that, in addition to the predictor step, our method reduces the duality
gap in the corrector step and this can be a prominent feature of our method. We prove that the
iteration complexity of the new algorithm is O(n log "1), which coincides with the best known
complexity result for infeasible interior-point methods, where " > 0 is the required precision.
Due to the positive direction new system, we improve the theoretical complexity bound for this
kind of infeasible interior-point method [1] by a factor of
p
n. Numerical results are also provided
to demonstrate the performance of the proposed algorithm.
|