Study On Several Algorithms For Mathematical Programs With Complementarity Constraints

The mathematical programs with complementarity constraints (MPCC for short) has many significant applications in economic equilibrium, engineering design and multilevel games. This thesis is devoted to study the algorithms for solving MPCC. The main results are summarized as follows:1. Using the Lagrangian function of the complementarity problem, a mathematical program of complementarity constraints is reformulated as a general nonlinear program-ming problem with the parameter. A new smooth multiplier sequential penalty method for solving MPCC is proposed by the simple modified strategy of the parameter. The fea-siblity of the limited point of the sequence generated from the algorithm is discussed. We show the limited point is B-stationary point if the MPCC linear independence constraint qualification(LICQ) and the upper lever strict complementarity(ULSC)hold. Moreover, MPCC satisfies the second-order necessary condition if the penalty problems satisfy the second-order necessary condition.2. A multiplier sequential partial penalty method for solution of MPCC is presented. Without requiring the second-order necessary condition, we show the limited point of the sequence generated from the algorithm is M-stationary point if it is the feasible to MPCC and the MPCC-LICQ holds. Moreover, it is B-stationary point if the upper lever strict complementarity(ULSC) holds. Numerical examples are given to demonstrate the effectiveness of the method.3. Using the Lagrangian function of complementarity problem, we present a new active set identification technique and apply to the multiplier sequential partial penalty method. We propose a hybrid algorithm for solving MPCC which is termination in finite iterations under ULSC assumptions.4. A new relaxed problem of MPCC is given. We show that the linear independence constraint qualification holds for the new relaxed problem under some mild conditions. A multiplier relaxed method for solving MPCC is presented. The limited point of stationary points of the relaxed problems is M-stationary point under the MPCC-LICQ, and if the ULSC holds at the limited point, it is B-stationary point. At last, we propose a new condition for convergence to B-stationary point.5. A new piecewise SQP algorithm for solving MPCC is discussed by the reasonable modified strategy of the multiplier of the Lagrangian function of the complementarity problem. Under mild conditions, the new algorithm is globally convergence to the piece-wise stationary point. Moreover, if the partial MPCC-LICQ holds, then it is globally convergence to B-stationary point.6. A new smooth approximation method is presented for solving MPCC by the entropy function of the minimization function. As the smooth parameter tends to zero, without requiring strong assumptions such as the upper lever strict complementarity condition or the asymptotically weakly nondegenerate condition, the limited point of the KKT point sequence of the smooth problems that satisfies second-order necessary condition is B-stationary point if the MPCC-LICQ holds.