Interior-point Algorithms Based On Wide Neighborhood For Conic Programming

This paper focuses on interior-point methods based on wide neighborhood forsemidefinite programming and symmetric conic programming. In terms of itstheoretical, We obtain the complexity as good as the currently best complexity, andanalysis their superior complexity.First, the basic content and theoretical knowledge,associated emblems andterminology are proposed. In order to expand the back of work, we understand thewhole development and present situation over conic programming firstly.Then,we propose a Mehrotra-type predictor and corrector algorithm based on wideneighborhood for semidefinite programming. The wide neighborhood is based on minusinfinity neighborhood. This neighborhood ensures the iterative points are central.Dr. Liuchange gives a Mehrotra-type predictor and corrector algorithm with safeguard. Such asthe method, with improving the corrector step and combining withV matrix, we give anew second order predictor and corrector algorithm. By introducing some technicallemmas, and the complexity bound is nL,where n is the number of variablesand L is the input data length. It is the best complexity of the interior point at present.Finally,we research into the Mehrotra-type predictor and corrector algorithm forsymmetric conic programming. A new Mehrotra-type predictor and corrector algorithmis proposed. The algorithm is based on a new wide neighborhood, the proposition of theneighborhood is based on the minus infinity neighborhood proposed by Dr. Liu changhe.The algorithm is basis of the algorithm proposed by Liu change, with improving thecorrector step and using the machinery of Euclidean Jordan algebras, we obtain the newMehrotra-type predictor and corrector algorithm for symmetric conic programming.The rL iteration complexity of the algorithm is shown, where r is the rank ofthe Jordan algebras. It is the best complexity of the interior point method at present.