ABSTRACT
Strikes to solve all the dilemmas of interior-point methods that use line search techniques. Two algorithms are proposed for this purpose. These algorithms remove several unnecessary restrictions in interior-point methods with line search techniques. These restrictions were used in the proofs for polynomial bounds. The two proposed algorithms also adopt three known strategies that are useful to speed up the computation: a) use high-order derivatives (to construct the arc), b) search optimizer in widest neighborhood, and c) start from infeasible interior-point. In addition, instead of using heuristics to select the centering parameter, a systematic scheme is used to optimally select the step size and centering parameter at the same time. It first shows that the first algorithm is polynomial and then shows that the most restrictive constraint is actually removable, which leads to the second algorithm and the second algorithm is proved to have the best polynomial bound in all interior-point algorithm. Moreover, numerical test demonstrates that the two proposed algorithms are more efficient and robust than Mehrotra's predictor-corrector algorithm. This solves all the dilemmas we discussed in previous chapter.
