Analysis Of Numerical Algorithms For Several Classes Of Optimization Problems

The design of an efficient algorithm is one of the most important research ar-eas in numerical optimization community. This thesis considers several important and hot optimization problems in recent years,such as unconstrained optimiza-tion,complementarity problems,polynomial programming,tensor conic program-ming,and mainly concentrates on the design,convergence analysis,numerical implementation and practical applications of algorithms.These algorithms are tested by using standard testing libraries CUTEr and MCPLIB,as well as real data from MRI center in Tianjin First Center Hospital,respectively. The corre-sponding numerical results are compared with some well known algorithms and sophisticated software,such as SOSTOOLS and OptimizationTools(MatLab),re-spectively. The results are encouraging.Concretely, there are three main chapters in this thesis:The main issue of Chapter 2 is to consider unconstrained optimization.We first propose a new nonmonotone line search algorithm,and prove its global con-vergence and local R-linear convergence.The numerical results based on testing library CUTEr for this newly proposed algorithm are compared with two famous nonmonotone schemes, which indicate that the newly proposed algorithm is ef-fective.Then,a nonmonotone line search algorithm is extended to a class of constrained optimization problems. Under the assumption that the considered manifold defined by the constrained set has nonnegative sectional curvature and the involved function is quasi-convex,the iteration sequence of the algorithm globally converges to a global optimum.Chapter 3 deals with complementarity problems(CPs).NCP-functions play a key role in reformulation methods for CPs.Firstly, a new family of NCP-functions is proposed,and its various favorable properties are investigated,in-cluding continuous differentiability, Lipschitz continuity,(strong)semismoothness, LC1,SC1 and so on.A derivative free algorithm based on the newly proposed NCP-functions is analyzed.Some numerical results for testing library MCPLIB show the value of this family of NCP-functions.Secondly, we consider the re-lationships between linear complementarity problems(LCPs)and absolute value equations(AVEs):without any assumption, we prove that LCP and AVE are equivalent to each other, and give some properties of the solution set for AVE; we also extend the AVE to the framework of second order cone(SOCAVE),and ana-lyze a generalized Newton algorithm for solving SOCAVE.The properties related to convergence of this algorithm are developed,some preliminarily numerical re-sults show its efficiency. As an application,we hence develop a new method towards LCP on second order cone.Thirdly, since the existing smoothing New-ton algorithms for complementarity problems are based on monotone line search, while their numerical implementations are based on nonmonotone line search, there lack theoretical analysis.After introducing Kanzow-Kleinmichel smooth-ing function and proving its Jacobian consistency, a smoothing Newton algorithm with a newly designed nonmonotone line search is proposed.The global linear and local quadratic convergence are proved.The numerical results based on MCPLIB indicate that this algorithm is efficient. Lastly, we consider CPs in the framework of symmetric cone which gives a unify framework for most CPs.We propose a smoothing Newton algorithm with a nonmonotone line search,and prove its global convergence under the weakest assumption.We consider polynomial programming in Chapter 4.Firstly, we propose a favorable approximation ratio for bi-quadratic programming(Bi-QP) in an aspect which is different from that in the literature.An alternating direction method (ADM)is designed for a relaxation problem of Bi-QP, the global convergence is proved and the numerical results indicate:the ADM here could provide a favorable approximation solution for Bi-QP;and the ADM here is superior to the methods in the literature.Some results for Bi-QP are archived through an eigenvalue method of tensors as well.Secondly, we extend the approximation ratio for quadratic programming with rank constraints from positive semidefinite objective to the arbitrary case.Thirdly, based on two new decomposition results of matrices, serval alternative theorems are given.Especially, we generalize S-Lemma to the higher degree polynomial case under some suitable conditions.As an application, we give the (sufficient and necessary)optimality conditions for the extreme Z-eigenvalue problems of tensor.Lastly, a sequential SDP method for space tensor conic linear programming (STLP) is proposed.Some numerical results based on randomly generated examples are compared with those by SOSTOOLS,which show that the newly proposed method is promising. STLP is extended to tensor conic linear program(TCLP),and some duality results are proved.The former sequential SDP method is extended as well,which is called TCOSS in this thesis. Using the ideas above,we analyze the positive definiteness of diffusion kurtosis tensor imaging,and a newly conic linear programming(CLP)model is proposed. Numerical results for CLP and methods in OptimizationTools(MatLab)based on both synthetic and real data are compared,and the result is encouraging.