Investigation Into Non-Interior-Point Smoothing Algorithms For Complementarity Problems

Complementarity problems are of an important branch in the mathematical programming field, which are widely found in many fields such as engineering, economics and traffic control. Therefore, it is significant to investigate algorithms for solving these problems. Non-interior-point smoothing algorithms for some complementarity problems are proposed and their global convergence is analysed under some weaker conditions. Main contributions of this dissertation are as follows.1. An algorithm is developed to solve linear programming problems (LPs) by introducing a smoothing function with a normalized symmetrical perturbation. The optimality condition for LPs are reformulated as a mixted linear complementarity problem, witch is solved by using the developed smoothing algorithm. The proposed algorithm is shown to be globally convergent without any normality assumption. In addition, the proposed smoothing algorithm is able to find a strictly complementary solution if LPs are feasible, or to indicate infeasibility of LPs instead.2. A smoothing-type algorithm is proposed to solve a standard monotone linear complementarity problem (LCP), and establish the relations between the augmented system and LCP. The algorithm is then used to solve the augmented system with global convergence and without any assumption of a prior knowledge of feasibility/infeasibility of LCP. In particular, if LCP is solvable, then the algorithm is able to generate either a maximal complementary solution to the LCP or detect correctly solvability of LCP, and in the latter case, an existing smoothing-type algorithm can be directly applied to solving LCP without any additional assumption, delivering a maximal complementary solution to LCP. If, however, LCP is infeasible, the algorithm detects correctly infeasibility of LCP. To the best of my knowledge, such properties have not been discovered and contributed in the existing literatures on smoothing-type algorithms.3. A non-interior-point smoothing algorithm is further proposed in this dissertation to solve monotone nonlinear complementarity problem (NCP) and a P * nonlinear complementarity problem . The algorithm is simpler than many existing similar algorithms in the sense that it needs only to solve one system of linear equations and to perform one linear search at an iteration step. The proposed algorithm is proved to be globally convergent under an assumption that the NCP has a nonempty solution set. Such assumption is weaker than those required by most other non-interior-point smoothing algorithms. In particular, the solution obtained by the proposed algorithm is shown to be a maximally complementary solution to the NCP concerned.To sum up, a non-interior-point smoothing algorithm for solving the complementarity problem is proposed in this dissertation, which outperforms many existing non-interior-point smoothing algorithms in the sense that only one system of linear equations is solved and one linear search needs to be made for the solution at an iteration step.