Path-Following Algorithms With Extended Self-Dual Embedding For The Second-Order Cone Program

Second-order cone programming(SOCP)problems are convex optimization problems in which a linear function is minimized or maximized over the intersection of an affine linear manifold with the Cartesian product of second-order(Lorentz)cones.Most commonly solved convex optimization problems can be transformed into this problem class.Second-order cone planning involves many applications,such as finance,communication,machine learning,control,etc.So solving the second-order cone programming problem is of great significance.The path-following algorithm for the second order cone programming forms a system of linear equations to compute the newton direction at each iteration,because it consumes a lot of memory and time to compute the Newton search direction,therefore,the scale of problem solving is limited,and the ill-conditioned degree of the equations will become more and more serious as the iteration goes on.To solve the above problem,this paper studies the path-following algorithms with extended self-dual embedding for the second-order cone program,the specific work includes the following aspects:An efficient interior point method,Mehrotra prediction-correction algorithm based on self-dual embedding and scale transformation,is studied.Firstly,the basic contents and theoretical knowledge of interior point method and second-order cone programming are given,and then an extended self-dual embedding model is established,which has the advantages of strict feasible interior points and can detect infeasibility,and give a concrete proof.In order to improve the computing efficiency,the computing method of scale transformation matrix correlation is given.Using Mehrotra predictioncorrection algorithm,three specific search directions are generated,including affine scale direction,centering direction and corrector direction,and focus on the corresponding search direction.In the total calculation time,the solution time of the search direction should account for more than 90%.In order to improve the calculation efficiency,the three search directions are converted into formulas with the same coefficient matrix by calculation,and this matrix is disturbed to make it becomes a quasi-definite matrix with better properties,thereby obtaining higher calculation efficiency.