The optimal problems of the second order cone programming(SOCP)and their solving algorithms are discused in this paper which consists of two sections.In the first section,a new self-concordant barrier functionφ(t)=(tp+1-1)-(p+1) In t is offered,and the properties of the self-concordant barrier function and its inverse function are discussed.A primal-dual interior-point algorithm for SOCP is presented based on the self-concordant barrier function,and the complexity of the primal-dual interior-point algorithm is given by the properties of the self-concordant barrier function and its inverse function.In the second section,a method of linearization of SOCP is proposed.The problem of SOCP is relaxed to a problem of linear programmings by substituting a series of inequalities corresponding to the half-spaces containing the circumscribed regular pyramid of the second cone for the restriction of the second order cone in the SOCP.The probability that feasible solutions for the linear laxation of SOCP are the ones for the SOCP is estimated by the volumes of the regular pyramid and the taper in the Euclidean space of dimension n.An example is given to show the feasibility of the method of linearization of SOCP.
|