Two Classes Of Primal-dual Interior-point Algorithms For Semidefinite Programming

Semidefinite programming is also called a linear programming with a positive semidef-inite cone constraint.It can be degenerated into a linear programming or a convex quadratic programming.Semidefinite programming is widely used in many fields,such as system theory,control theory,financial engineering,quantum chemistry and signal pro-cessing,etc.Some comprehensive and thorough studies have been invested in by a large number of the operational research scholars.The polynomial time interior-point method for solving semidefinite programming can efficiently conquer the small or middle size NP-hard problems in the combinational optimization area,such as the well-known traveling salesman problem and the max-cut problem.A key issue lies in semidefinite program-ming is how to design efficient algorithms for solving large size semidefinite programming problems.This paper considers wide neighborhood infeasible interior-point algorithms and predictor-corrector interior-point algorithms for semidefinite programming.1.In chapter 2,the focus is on wide neighborhood infeasible interior-point algorithms.Inspired by the literatures[25,26],we propose a wider neighborhood of a central path in order to get a lager iterative step and then design an infeasible interior-point algorithm.It is proved that the complexity bound is O（nL）when the NT direction is chosen.A new wide neighborhood infeasible interior-point algorithm is developed by combining the the wide neighborhood considered in[29]with the modified Newton direction proposed in[36,44].This algorithm does not need solving the positive and negative parts of the Newton direction in each iteration.When the NT direction is chosen,the complexity bound is O(n^1/2L).Numerical results are also presented for illustration the efficiency of these newly designed algorithms.2.In chapter 3,it is concentrated on predictor-corrector interior-point algorithm-s.Based on the searching direction provided in references[44,45],algorithm 3 is intro-duced for some given wide neighborhood Ν（τ,β）and a matrix V.By comparison with the related known algorithm,we prove that the duality gap goes to 0 but not at the cost of the large increase in the number of the iterates when we choose the KM search direction.And the iteration complexity bound is proved to be O(n^1/2L).Then,similar to the strategy put forward by[46-49],a correction step is added in algorithm 3 thus produce a new predictor-corrector interior-point algorithm:algorithm 4.At last,a wide neighborhood of Ν∞-（1-γ）introduced in[50,51]is employed to improve the corrective step which give rise to a predictor-corrector algorithm with corrective step safety strategy and predictive step reduction strategy.we prove the iteration complexity bound of this algorithm is o（nL）.Numerical examples are provided to show the effectiveness of these algorithms.