Studies On Some Algorithms For Second-order Cone Programming

Second-order cone programming is a convex optimization problem in which a linear function is minimized over the intersection of an affine linear manifold with the Carte-sian product of second-order cones. Many mathematical problems can be formulated as the second-order cone programming such as linear programming, convex quadratic programming and quadratically constrained convex quadratic programming. In recent years, the second-order cone programming has become one of important research direc-tion in the mathematical programming fields for its wide range of applications in many fields, such as engineering, control and design, machine learning and combinatorial optimization and so onThis thesis aims to study the interior-point algorithms and smoothing algorithms for the second-order cone programming. It consists of eight parts. In the first chapter, we introduce the modeling, research background, significance and the recent situations of second-order cone programming and summarize the main results of the paper.In Chapter2, an inexact infeasible interior-point algorithm for solving the second-order cone programming is investigated. This algorithm does not require the initial points and iteration points to be feasible. All iterative points are in a neighborhood of the infeasible central path. With proper choices of step-size, we prove that the algorithm has global convergence and polynimial-time complexity.In Chapter3, we introduce a new kernel function which has a linear growth term. Based on this function, we design a primal-dual interior-point method for solving the second-order cone programming and obtain a iteration bound O(rlogγ/ε) for large-update methods. Here r denotes the number of second-order cones in the problem formulation. This bound is the same as the classical primal-dual interior-point method, which is based on the logarithmic barrier function. In addition, we also give a numerical example and study the influence of the parameters in the kernel function on the run of the algorithm.In Chapter4, we extend the weighted-path-following interior-point algorithm forlinear programming to solve the second-order cone programming. At each iteration, thealgorithm uses only full Nesterov-Todd step; no line searches are required. The algo-rithm has local quadratical convergence rate and the currently best known polynomialcomplexity bound.In Chapter5, a new smoothing function is given by smoothing the symmetricperturbed Fischer-Burmeister function. Based on this smoothing function, we refor-mulate the second-order cone programming concerned as a family of parameterizedsmooth equations and then propose a non-interior continuation method. The algo-rithm can start from an arbitrary initial point and does not require the initial pointand iteration points to be in the sets of strictly feasible solutions. It needs to solve onlyone system of linear equations and to perform only one line search at each iteration.Without requiring strict complementarity assumption, the algorithm is globally andlocally quadratically convergent. Numerical results show that the proposed algorithmis efective.In Chapter6, we present a one-parametric class of smoothing functions whichincludes some known smoothing functions as special cases. Based on these functions, asmoothing Newton method is proposed for solving the second-order cone programming.Under a mild assumption, the proposed algorithm is globally and locally quadraticallyconvergent. We also conduct some numerical experiments by some randomly generatedsecond-order cone programming problems. Numerical results not only indicate that ouralgorithm is efective but also show that the parameter of the smoothing function playsan important role in the implementation of the algorithm.In Chapter7, based on a non-symmetrically perturbed smoothing Fischer-Burmeisterfunction, we propose a new smoothing method for solving the second-order cone pro-gramming. It is shown that any accumulation point of the iteration sequence generatedby the proposed algorithm is a solution of the second-order cone programming. Fur-thermore, the generated iteration sequence is bounded and hence it has at least oneaccumulation point. Under the assumption of nonsingularity, we establish the local quadratic convergence of the proposed algorithm. Numerical experiments demonstratethe feasibility and efciency of the proposed algorithm.The last chapter, we sum up the main work of the paper and propose some futureresearch work.