Study Of The Predictor-Corrector Algorithms For Linear Programming And Semi-definite Programming

This paper mainly studies two different kinds of interior point predictor-correctoralgorithms for linear programming and semi-definite programming. The so calledpredictor-corrector algorithm means taking a corrector step after the predictor step.Most path-following algorithms only use predictor steps, and do not take correctorsteps. In order to ensure the worst-case complexity, we must fix the centringparameter, then this will limit the possible convergence speed. When we allow largeimprovement and let centring parameter equal to 0, to find reasonable step, we mustenlarge the neighborhood of the central path in the predictor step, then the correctorstep is necessary. These two algorithms only fix the iterates in their narrowneighborhoods and can only be used for either linear programming or semi-definiteprogramming. So to some extent, they are limited and restrict the application inchoosing initial points. This paper is to improve the methods, eliminate theselimitations, and extend the algorithms, so that they can be used for both linearprogramming and semi-definite programming.The main jobs of this paper are as follows:1. Analyzing the theoretic basis of the interior point for linear programming andsemi-definite programming, and providing the corresponding theoretic foundationfor predictor-corrector algorithms.2. Extending the range of the parameters and giving proofs for the formerpredictor-corrector algorithm used for semi-definite programming, and thenspecializing the improved algorithm to linear programming.3. Making the parameters genetic first for the former Predictor-Corrector algorithmused for linear programming, then introducing operators to change the form of thesystem, giving proofs to ensure the correctness, and extending the improved algorithm to semi-definite programming.4. Programming the extending algorithms and showing the feasibility of the improvedand extended algorithms.