A Semi-Interior-Point Method For Convex Programming

In 1984, Karmarkar presented a new method called interior-point method for solving linear programming, which was proved a polynomial algorithm, and its efficiency is higher than simplex method in practical application. Since the publication of Karmarkar's paper, interior-point method becomes a hot topic for research. But boundedness of solution and uniform convexity are needed for interior-point method, therefor, Feng Guochen, Yu Bo and Lin Zhenghua proposed the combined homotopy interior-point method using Newton homotopy and fixed point homotopy, and proved the existence and convergence of the homotopy path under the certain condition. And this method needs a feasible interior-point as the initial point.Recently, Yu Bo and Shang Yufeng proposed the Constraint Shifting Combined Homotopy Method (CSCHM), which didn't have the constraint that the initial point must in the feasible region and can solve more general nonconvex programming problems also. Sometimes, homotopy path of CSCHM walks up to the optimal solution outside the feasible region, which resulted in approximate solution solved is not feasible for all the constraints. In this thesis, we give a modified CSCHM for convex programming, the second part of homotopy path is in the feasible region for all the initial points. So we can get the feasible approximate solution by tracing homotopy path numerically. The existence and convergence of the homotopy path are proved, and efficiency of our method is illustrated by the numerical experimentations at last.