Studies On Efficient Algorithms For Complementarity Problems

The paper deals with the study of efficient algorithms for complementarity problems (CPs). CPs have been developed very quickly since they appeared in the 60s last century, especially the recent two decades. Many formulations of them were proposed and widely used in engineering, economics and operations research. Roughly speaking, the study of CPs can be classified into two classes: theory and algorithms. The former is devoted to the existence, uniqueness, stability and sensitivity analysis of the solutions, while the latter is intended to solve the problems efficiently, together with the theoretical analysis of the algorithms.Different formulations of CPs are introduced in Chapter one, along with various applications in engineering, economics and operations research. Some algorithms for CPs are described. Meanwhile, the thesis work is outlined briefly.Chapter two introduces the concept of entropy in information theory, maximum entropy principle, and minimum cross-entropy principle. It is difficult to analytically solve the inequality constrained NLPs in the dual space, due to the linear Lagrangian. A perturbed (regularized) Lagrangjan approach is proposed, which provides an analytic solution of the dual variables in terms of primal variables. The applications of Shannon entropy and Kullback's cross-entropy as perturbations are discussed. By maximizing the perturbed Lagrangians in dual space, we obtain the exponential penalty function and exponential multiplier penalty function, respectively, for inequality constrained NLPs. Thus, a bridge is built between the Lagrange perbuation methods and the exponential penalty methods. Then the perturbation methods are used to an equivalent NLP problem of minmax problems and the resulted smooth functions are just aggregate functions obtained by maximum entropy principle and minimum cross-entropy principle, respectively.Chapter three introduces the development of interior-point methods for linear programs first since the interior-point methods for LCPs can be looked as a natural extension of primal-dual interior-point methods for LPs. A new merit function (potential function) is constructed in Chapter three, based on the balanced effect of the min-max problem. Because of the non-smoothness, Shannon entropy is used to smooth the merit function. The resulted smooth merit function is convex and its optimal conditions contain a set of extra parameters, compared with the usual perturbed complementarity conditions. The set of parameters is updated by using the information of the last iteration and brings about the centering effect towards the central path, which was called the self-adjusting effect. An infeasible path-following algorithm is constructed, and its polynomial complexity is analyzed. Numerical tests show the self-adjusting effect of the parameters.The one-step non-interior continuation method of Chen and Xiu for LCPs is refined in Chapter four. It is extended to NLPs. The control parameter is replaced by the smoothing parameter in the perturbation term of Newton Step. The convergence of the refined non-interiorcontinuation method for NCPs is analyzed, the same global linear convergence as Chen-Xiu's is obtained. Locally quadratic convergence is also obtained, compared with the locally superlinear convengence of Chen-Xiu's. Smoothing functions, in some sense, are the center in continuation methods. Kullback's cross-entropy function is tried to smooth the minimal NCP-function and a non-interior continuation method is constructed for LCPs. Its numerical performance is very good, even better partly than the infeasible path-following methods in chapter three and chapter six. At last of the Chapter, the mid(.) function is reformulated. Shannon entropy function is used to smoothing it. A non-interior predictor-corrector continuation method is built for a class of mixed complementarity problems. Its global convergence is analyzed.Shannon entropy and Kullback's cross-entropy are used to smooth the max function respectively in a fixed-point formulation of NC...