Study On Interior-Point Algorithms In Wide Neighborhoods For Linear Programming And Complementarity Problems

The interior-point methods in wide neighborhoods are effective for linear programming and linear complementarity problems,but they always have a relative poor complexity result in theory.Ai-Zhang wide neighborhood can fill the gap.In view of its importance,we study it at first.The two neighborhood parameters are generalized to larger ranges,and three new wide neighborhoods are defined,which are N1(?,?),N2(?,?),and N?(?,?).Then we study some primal-dual interior-point algorithms about their complexity and local convergence in the three wide neighborhoods,respectively,for linear programming and linear complementarity problems.Firstly,we study in N1(?,?).It is proved that the neighborhood-following algorithm,proposed by Ai Wenbao,is quadratic convergent even for degenerate linear programming.Then the algorithm is generalized for linear complementarity problems.The new algorithm has an O((?)L)complexity bound,which is the best result so far.Its quadratic convergence can be shown,assuming that a strictly complementary solution exists.Furthermore,a modified algorithm is proposed.The algorithm adds an affine scaling step before the second algorithm's step,called a fast step and a safe step,respectively.If a fast step fails,a safe step will be taken,which is the cause that its complexity is O((?)L).Specially,a successful fast step is iterated in an enlarged wide neighborhood.When iterations are sufficiently large,fast steps are taken all through.The modified algorithm is local superlinearly convergent.Assuming a strictly complementary solution exists,the sequence generated by the algorithm is convergent.The numerical results show the algorithm effective.Secondly,we study algorithms in N2(?,?).A new Mizuno-Todd-Ye predictor-corrector algorithm for linear complementarity problems is proposed,which is based on the idea that the positive part of the decomposed classical path-following direction is responsible for centrality and the negative one is for optimality.It has a polynomial complexity bound of O((?)L).However,the duality gap is not reduced in corrector steps,and the numerical results show the algorithm is necessary to be improved.Based on the thought,the second algorithm is proposed,which remains predictor direction of the first algorithm and adds the affine scaling direction into the corrector direction.The duality gap is decreased not only in predictor steps but also in corrector steps.Numerical results show that it is superior to the first algorithm,and its complexity is O((?)L).Then the third algorithm is proposed based on the second algorithm,which has an adaptive center parameter.The algorithm has the best complexity,and it is superlinearly convergent.Finally,numerical tests show the different performance of four algorithms with different center parameters.Finally,a first-order Mehrotra-type predictor-corrector algorithm and a second-order one are proposed in N(?,?)for linear programming.The safeguard strategy,substituting a constant for Mehrotra's adaptive center parameter,is used in both algorithms,which makes them effective in practice and polynomial in complexity.In fact,the classical Mehrotra predictor-corrector steps are done normally.But when the step size in a predictor step is small or the actual step size is small,the safeguard strategy and a new second-order corrector term are used.It is proved that the first-order algorithm has a polynomial complexity bound of O((?)L),which is better than the result of an algorithm using only the safeguard strategy.The second-order algorithm is also O(nL),in which the step size in a predictor step is applied as a coefficient in the next iterate point,different from other Mehrotra-type predictor-corrector algorithms.Numerical results show the two algorithms are efficient.