Study On The Interior-point Algorithms For Second-order Cone Programming

Second-order cone programming(SOCP)is a convex optimization prob-lem to minimize or maximize a linear function over the intersection of an affine set with the Cartesian product of finite second-order cones.SOCP is a general-ization of linear programming and a special case of semi-definite programming.Therefore many mathematical problems can be formulated as the second-order cone programming.This paper focuses on the numerical solution of the second-order cone programming i.e.primal-dual interior-point methods.Our paper includes the following parts:In chapter 1,we introduce Second-order cone programming and the de-velopment of second-order cone programming.In chapter 2,we present a new quadratic kernel function,and analyze the properties of the function.Then we design a primal-dual interior-point method for solving the second-order cone programming based on the new kernel func-tion.We obtain the iteration bound O(r3/4 logr/?)for large-update method.The iteration bound is slightly better than the classical primal-dual interior-point method,which is based on the logarithmic barrier function.Furthermore,we give numerical experiments,the results show that our algorithm i,s feasible.In chapter 3,we provide another new kernel function,which is a convex combination function with logarithmic kernel function?(t)=(t~2-1)/2-log(t)and kernel function ?(t)=1/2(t-1/t)~2.We also analyze the properties of the function.A primal-dual interior-point for solving the second-order cone programming based on the new function is discussed.Furthermore,we obtain the iterationbound O(r2/3 logr/?)for large-update methods by analyzing the complexity of the algorithm.The iteration bound is similar to the iteration bound of kernel func-tion ?(t)= 1/2(t-1/t)~2.The last chapter,we give a brief summary about this paper.