Study On Wide Neighborhood Interior-Point Method For Symmetric Cone Programming

Symmetric cone programming is an active branch of mathematical programming and has extensive applications in economic, management, traffic, control, information, and other disciplines. Moreover, linear programming, semi-definite programming and second-order cone programming are special subproblems of symmetric conic program-ming, which is a kind of new content, wide-ranging of the content, abundant theory, high level academic value of optimization problem and attracts many experts and scholars to study it deeply and achieves fruitful results. There are many methods for solving symmetric cone programming, in which one of the most important is the interior-point methods. It is well known that the wide neighborhood algorithm and the narrow neigh-borhood algorithm have advantages and disadvantages, which are the wide neighborhood algorithm is effective in practice and the complexity is high in theory, on the contrary the narrow neighborhood algorithm is inefficient in practice and the complexity is low in theory. The purpose of this thesis is to design some algorithms with the advantages of both. Therefore, we design several wide neighborhood interior-point methods with low complexity. The main research work of this thesis can be summarized, as follows:1. Based on the negative infinity neighborhood, we propose a new arc-search interior-point method for linear programming. The proposed algorithm searches for optimizers along the ellipses that approximate the central path. By analyzing, we ob-tain the complexity bound is O(n3/4 L), where n means the dimension of problem, the entering data size is L. It shows that the proposed algorithm improves the complexity of the wide neighborhood interior-point. Moreover, some limited encouraging computa-tional results are reported.2. First, we define a new wide neighborhood by using Schatten 1-norm. Based on the defined neighborhood, we present a new second-order Mehrotra-type predictor-corrector algorithm for semi-definite programming. Moreover, in order to prove the convergence of the proposed algorithm, we first need to prove an important inequality ‖UV+VU‖1≤2‖U‖F‖V‖.By using the inequality, the convergence is shown for a specific class of search directions. Specially, the polynomial complexity is O(nlogε-1) for the H..K..M search direction, and O(1/2nlogε-1) for the Nesterov-Todd search direc-tion. Finally, we provide some preliminary numerical results as well.3. First, we extend the introduced neighborhood by Ai and Zhang1 to symmetric cone programming and obtain our neighborhood N(β,τ). We present a new infeasible-interior-point method, based on a wide neighborhood, for symmetric cone programming. The Euclidean Jordan algebra is a basic tool in our analysis. We also prove the conver-gence of algorithm for a commutative class of search directions(CCSD), which includes the Nesterov-Todd direction and the xs and sx directions. Compared with the results in Rangarajan, the complexity bound is reduced by a factor of r0.5. Especially, the complexity bound for the NT direction coincides with the bound obtained for LP by Zhang et al.3. As far as we know, we derive the complexity bound of the wide neigh-borhood infeasible interior-point methods that coincides with the currently best known theoretical complexity bounds for the short step path-following algorithm. Eventual-ly, if strictly feasible starting points are used, we briefly analyze the complexity of the algorithm.4. Since high-order correction algorithm has the characteristics of high accuracy, good numerical results, low complexity, it attracts much attention. The second-order correction algorithm is a special case of high-order correction algorithm and attracts researchers’interest. In order to improve the complexity of the previous wide neighbor-hood first-order correction algorithm, we propose a new second-order infeasible primal-dual path-following algorithm for symmetric cone programming, which is based on the wide neighborhood N(β,τ). Moreover, we prove that the proposed algorithm is con-vergence for a CCSD. In particular, the complexity bound is O(r5/4logε-1) for the Nesterov-Todd direction, and O(r7/4 logε-1) for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ε is the required precision.5. Based on the negative infinity neighborhood, we present an Mehrotra-type pre-diction corrector infeasible-interior-point method with safeguard strategy for symmetric cone programming. In order to show that the convergence of our algorithm for the CCSD, we prove the important inequality‖x o y‖1≤1/23‖x‖F‖y‖F, where a mapping ‖·‖1 is defined by ‖x‖1=∑ir1=|λi| with the spectral decomposition x=∑ir=1λiCi.To our knowledge this is the first time that the inequality is proved. Using the relationship, we showed the convergence of our algorithm for a CCSD. Especially, the complexity is O(r2logε-1) for the Nesterov-Todd search direction, and O(r5/2logε-1) for the xs and sx search directions. By testing some problems from Netlib and Sdplib, we provide some preliminary numerical results as well.