Research On Theory And Algorithms For Second-Order Cone Programming

Second-order cone programming (SOCP) problem minimizes a linear function overthe intersection of an a?ne linear manifold with the Cartesian product of second-ordercones. It is a branch of conic programming. SOCP , which has pretty framework, isthe generalized linear programming (LP), and also a special case of semi-definite pro-gramming (SDP). SOCP problems have broad application in real world, such as facilitylocation, grasping force optimization, antenna array design, portfolio investment, andin the areas of finance, engineering design, digital signal disposal, acoustics, mechan-ics, civil aviation, electrical engineering, and so on. Therefore, research on theory andalgorithms for SOCP has an important academic significance and applying value.The study of SOCP began from 17 century and has been active in ten years recently.There was a survey in 2003. The interior-point algorithms and the non-interior-pointalgorithms are the main methods for solving SOCP. The primal-dual interior-point al-gorithms are familiar interior-point algorithms, which include"feasible interior-pointmethod"and"infeasible interior-point method". The initial point and the iterativepoints are required feasible in feasible interior-point methods. However, The initialpoint and the iterative points are only required feasible in second-order cones in in-feasible interior-point methods. The feasible interior-point methods own primal-dualpath-following algorithms, primal-dual interior-point algorithms based on a class of ker-nel functions, etc. There are some main infeasible interior-point methods, such as in-feasible interior-point predictor-corrector algorithms, inexact infeasible interior-pointalgorithms, and so forth. The non-interior-point algorithms have smoothing Newtonmethods, non-interior-point continuous algorithms, sequential quadratic programming(SQP) algorithms, etc.In this thesis, we study theory and algorithms for SOCP. The main results of thethesis are stated as follows.We improve the proof of one important theorem proposed by Alizadeh F. andGoldfarb D. in detail (see Theorem 1.2.3). Further, we present three new results ofJordan algebra (see Theorems 1.2.6-1.2.8).We study two-dimensional SOCP. Every second-order cone in this kind of SOCP is two-dimensional. We present a dual simplex method and a primal-dual simplex methodfor two-dimensional SOCP. First, two-dimensional SOCP can be reformulated as LP.And then, we prove some important conclusions in detail. Finally, we show the e?ec-tiveness of the proposed methods by several examples, and sensitivity analysis are madetoo.Based on the ideas of infeasible interior-point methods and predictor-correctoralgorithms, two predictor-corrector algorithms for SOCP are presented. We use theNewton direction and the Euler direction as the predictor directions, respectively. Thecorrector directions belong to the category of the Alizadeh-Haeberly-Overton (AHO)directions. These algorithms are suitable to the cases of feasible and infeasible interioriterative points. A simpler neighborhood of the central path for the SOCP is proposed,which is the pivotal di?erence from other interior-point predictor-corrector algorithms.Under some assumptions, the algorithms possess the global, linear, and quadratic con-vergence. The complexity bound O(rln(ε0/ε)) is obtained, where r denotes the numberof the second-order cones in the SOCP problem. The numerical results show that theproposed algorithms are e?ective.We give two di?erent new smoothing functions of the well-known nonsmoothFischer-Burmeister (FB) function and the vector-valued min-function, respectively. Bas-ing on the new smoothing functions, we present two non-interior-point continuous al-gorithms for SOCP problems. The features of the two algorithms are as follows: first,the starting point can be chosen arbitrarily; second, at each iteration, only one sys-tem of linear equations and one line search are performed; finally, global and strongconvergence are obtained without assumption of strict complementarity. Furthermore,we show the smoothing Newton-type method has quadratic convergent rate and pos-sesses e?ective numerical results. And the non-interior-point continuous algorithm getssuperlinear convergence.The thesis is organized as follows. In Chapter 1, we introduce the background,the preliminaries for SOCP problems and present three new results of Jordan algebra.Then, we propose a dual simplex method and a primal-dual simplex method for two-dimensional SOCP and make sensitivity analysis in Chapter 2. In Chapter 3, two newpredictor-corrector algorithms for SOCP are presented, which are suitable to the casesof feasible and infeasible initial point and iterative points. In Chapter 4, we propose a new smoothing algorithm for SOCP basing on a new smoothing function of non-smoothFB function. Some large-scale test problems have been done too. In Chapter 5, basedon a new smoothing function of the vector-valued min-function, a new non-interior-pointcontinuous algorithm with superlinear convergence is presented for SOCP. Finally, thesummary and prospect are listed in Chapter 6.