Study On The Algorithms For Some Optimization Problesm And Applications

Optimization theory plays more and more important roles in many areas, such as en-gineering design, product management, transportation, government decision-making and so on, and thus much attention has been paid to optimization algorithms. Second order cone programming (SOCP) is one of the important nonsmooth convex programming prob-lems. Due to its wide application, special cone structure and simple computation, SOCP has independent research value, and many optimization problems can be formulated as SOCP problems. As an extension of SOCP, second order cone complementarity problem (SOCCP) includes linear and nonlinear forms. At the same time, variation inequality and complementary problem are also two important research topics for optimization problems.In this dissertation, the author focuses on the algorithms of the above optimization problems and the applications of complementarity problem to support vector machine, and obtains the following main results:(1) The algorithms for solving second order cone programming problem are studied. First, Two algorithms for solving linear second order cone programming are pre-sented. One is a predictor-corrector smoothing Newton method. The proposed algorithm does not need additional computation while keep the iteration sequence staying in the given neighborhood. Furthermore, the global and the local quadratic convergence of the algorithm are obtained. The other is a semismooth inexact New-ton method. The proposed algorithm solves the problem only approximately in each iteration and reduce significantly the oversolving problem of the Newton-type method. Under proper assumptions, the global convergence and the local conver-gence of the algorithm are established. Second, the nonlinear SOCP is considered. By combining a trust-region method and a filter technique, we present a SQP trust region filter method for solving this problem. The proposed algorithm avoids using the classical merit function with penalty term. Under standard assumptions, the presented algorithm converges globally.(2) The smoothing Newton methods for solving second-order cone complementarity problem are considered. First, we translate the second order cone complementar-ity problem into a system of nonlinear equation based on the Fischer-Burmeister function and a perturbed symmetrically smoothing function, respectively. Then we present two smoothing Newton methods for the monotone SOCCP. Both of the two algorithms have global convergence. Second, by using a new regularization method, we present a regularization smoothing Newton method for solving the SOCCP with Cartesian P0 property. Under proper conditions, we obtain the global convergence and local super linear convergence of the proposed algorithm.(3) The algorithm for variational inequality problem is studied. We first reformulate the variational inequality problem as a system of parameterized smooth equations, then propose a non-interior-point smoothing method for solving the problem. The proposed algorithm has no restriction on the initial point. Moreover, under suitable assumptions, it has global convergence and local quadratic convergence. Preliminary numerical results show that the algorithm is promising.(4) The applications of complementarity problem to support vector machine are consid-ered. First, by simplifying the optimization problem of the support vector machines, a complementarity problem is obtained, which is equivalent to the dual problem of the amended quadratic programming problem. Then a one-step smoothing Newton method is presented. The proposed algorithm does not have restriction on the start point. At each iteration, it solves only a linear system of equations and performs only one line search. It has the property of quadratic convergence. Second, to over-come the shortcoming of Lagrangian method, a complementarity support vector machines is obtained from the amended quadratic programming problem of sup-port vector machines, and then a new descent algorithm for support vector machine optimization problem is presented. The proposed algorithm has simple and small computational work, overcomes the shortcoming of Lagrangian method, and does not need to compute any Hesse or the inverse matrix. Numerical experiments show that the algorithm is feasible and effective.