Study On The Algorithms For Second-order Cone Programming And Second-order Cone Complementarity Problems

Second-order cone programming is a kind of problem which minimizes or max-imizes a linear function over the intersection of an affine space with the Cartesian product of a finite number of second-order cones. The constraints of second-order cone programming are nonlinear, but they are convex, so it belongs to convex programming. Second-order cone programming is a special case of semidefinite programming, but it covers linear programming, convex quadratic programming, quadratically constraint convex quadratic optimization as well as other problems. The study of second-order cone programming has its independent value due to its wide range of applications, special cone constructer and computational convenience. Second-order cone program-ming has already become one of the important research direction in the mathematical programming fields.Second-order cone complementarity problems are a class of equilibrium problems. In recent years, based on the technique of Euclidean Jordan Algebra, many researchers have achieved a breakthrough in the study of symmetric cone complementarity prob-lems, and made them attract a lot of attention. Second-order cone complementarity problems are generalizations of the second-order cone programming. They contains both linear and nonlinear second-order cone complementarity problems. In the recent years, the study of second-order cone complementarity problems is increasing. The study contains:the existence and properties of the solution, potential function and error bound, many smoothing method and optimization method, and many real appli-cations. However, the study of nonlinear second-order cone programming and nonlinear second-order cone complementarity problems is just in its initial state, and it is one of the current hot fields that researchers pay attention to.The thesis mainly on the study of algorithms for second-order cone programming and second-order cone complementarity problems. It consists of the following eight parts:(1) In the first chapter, we introduce the modeling, research background, signif-icance and the recent situations of second-order cone programming and second-order cone complementarity problems. The existing methods is discussed and summarized, which drops the problems need to be further solved and the main results of the paper.(2) In the second part, we briefly introduce the preliminary knowledge. We mainly focus on Euclidean Jordan algebra, and optimality conditions, central path conditions, complementarity condition and interior-point method for second-order cone program-ming.(3) We define a wide neighborhood of the central path, and present a large-update primal-dual path-following interior-point algorithm for second-order cone programming in the third chapter. Each iterate is always following the wide neighborhood. We show that the method has the best iteration complexity bound of the wide neighborhood algorithms for solving second-order cone programming.(4) In the fourth chapter, a smoothing function corresponding to second-order cone is given, and its properties are studied. Based on the smoothing function, a smooth-ing Newton-type method is proposed for solving second-order cone programming. The method reformulates the perturbed optimality conditions into a system of linear equa-tions to solve. Its results are stronger than corresponding interior-point methods, and its initial point is arbitrary. At each iteration, the proposed algorithm need only to solve one system of linear equations and perform one line search. The sequence gen-erated by the method converges globally and Q-quadratically to the solution of the SOCP under a mild assumption, without strict complementarity condition.(5) A globally convergent non-interior point algorithm with full Newton step for second-order cone programming is proposed in the fifth part. The main idea of the algorithm is that we cast the complementary equation of the primal-dual optimality conditions as a projection equation. This algorithm can start from an arbitrary point. Without performing any line search, we only need to solve a system of linear equa-tions with the same coefficient matrix and compute two simple projections at each iteration. It does not require the row vectors of coefficient matrix of constraints to be linearly independent. The proposed algorithm is globally convergent without strict complementarity conditions.(6) In the sixth part, we study the special second-order cone programming-nonlinear complementarity problem with P0-function. Based on a new smoothing func-tion with penalty, the problem is approximated by a family of parameterized smooth equations and a new non-interior-point continuation method is presented. At each it-eration, the proposed algorithm only need to solve one system of linear equations and perform one Armijo-type line search. The algorithm is proved to be globally and locally superlinearly convergent without strict complementarity. Moreover, the quadratic con-vergence rate is achieved under mild conditions. Numerical experiments demonstrate the feasibility and efficiency of the proposed algorithm.(7) In chapter seven, we introduce a class of one-parametric smoothing second-order cone complementarity functions. Under suitable assumptions, we prove that these functions are coercive. Based on this class of one-parametric smoothing functions, a smoothing Newton method is proposed to solve the monotone second-order cone complementarity problems. It is proved that the proposed algorithm is globally and locally superlinearly convergent under suitable assumptions. Preliminary numerical results for randomly generated second-order cone programs are reported, which confirm the favorable theoretical properties of the method.Finally, based on the problems of the existing methods, including the methods proposed in the thesis, the last chapter is concerned with some future research work.