Study On The Algorithms For Second-Order Cone Programming

Second-order cone programming (SOCP) is one of the important non-smooth convex programming problems. The SOCP problem is to minimize or maximize a linear function over the intersection of an affine space with the Cartesian product of a finite number of second-order cones. Many mathematical problems can be formulated as SOCP problems, e.g., linear programming, convex quadratic programming. Recently great attention has been paid to SOCP, since it has a variety of applications such as engineering, control, finance and so on.This thesis is devoted to the study of some infeasible interior-point algorithms and smoothing methods for SOCP, and the investigation of some smoothing functions of second-order cone complementarity functions and their properties. The main contributions are listed as follows:1. To overcome the deficiency that initial points should be strictly feasible in interior point methods, we present three infeasible interior point algorithms for SOCP—a primal dual infeasible interior point algorithm, an infeasible interior point algorithm based on a merit function, and an infeasible interior point predictor corrector algorithm. Without the strict feasibility, the initial points and iteration points generated by the three algorithms should be confined within a certain infeasible neighborhood of the central path. With proper choices of steplength, the three algorithms are shown to possess both global convergence and polynomial-time complexity.2. By applying inexact computation techniques of search directions in linear programming to SOCP, three inexact infeasible interior point algorithms for solving SOCP are proposed. The algorithoms allow the use of inexact search directions, and do not require initial points and iteration points to be in the sets of strictly feasible solutions. The inexact search directions are calculated with only moderate accuracy, so much computer time and memory can be saved especially for large-scale SOCP problems. The three algorithms are shown to be globally convergent.3. Some properties of the Chen-Harker-Kanzow-Smale (CHKS) smoothing function and the Fischer-Burmeister smoothing function are studied. We introduce two new vector-valued functions, study their Lipschitzian, strong semismooth and differential properties, and derive formulas for their Jacobians. Then we show that the two new functions are smoothing functions of the minimum function and the Fischer-Burmeister function, respectively. These results can play an important role in developing and analyzing smoothing methods for solving SOCP.4. Five smoothing Newton methods with smoothing parameters for SOCP are given. Based on either the CHKS smoothing function or the Fischer-Burmeister smoothing function, SOCP is reformulated as a nonlinear system of equations. Newton's method is applied to the perturbation of the system, and at each iteration the smoothing parameter is chosen suitably. Thus optimal solutions of SOCP can be obtained. Without restrictions regarding starting points, the algorithms are shown to be globally convergent.5. Five smoothing Newton methods with smoothing variables for SOCP are presented and shown to be globally convergent. Based on smoothing functions of second-order cone complementarity functions, the optimality condtions are reformulated as a nonlinear system of equations. This reformulated system does not contain any explicit inequality constraints like x∈K, s∈K or x∈K~0, s∈K~0. Then Newton's methods are applied to the system to obtain the optimal solutions of SOCP. Since the parameter in smoothing functions is viewed as a variable, the five smoothing methods with smoothing variables solve only one linear system of equations and perform only one line search at each iteration. The algorithms do not have restrictions regarding their starting points and their convergence analysis does not depend on the assumption of uniform nonsingularity.