Augmented Lagrangian Method For Mathematical Programs With Complementarity Constraints

Mathematical programs with complementarity constraints(MPCC)are an important class of optimization problems,which have many practical applications in such fields as engineering design,economic equilibrium,transportation,etc.Due to the existence of complementarity constraints,some commonly used optimization theories and algorithms can not be directly implemented to solve this kind of problems.Currently,there are many methods to solve MPCC,such as penalty function method,smoothing method.All of these methods approximate the problem to a nonlinear programming problem by dealing with the complementarity constraint structure.Different from the above referred methods,in the article,MPCC is studied from a viewpoint of the complementarity constraint set being equipped with the property of semi-algebraic.In this paper,we study the Augmented Lagrangian method for mathematical programs with complementarity constraints,and obtain the following threefold results.First,we reformulate the considered problem into an optimization problem with equality constraints and a simple complementarity constraint set,then give formulas of the tangent cone and normal cone for the feasible set.Moreover,under a constraint qualification,we construct first-order optimality conditions for the reformulated problem.Second,we establish the Augmented Lagrangian of the reformulated problem,then utilize the Augmented Lagrangian method to solve the dual problem.In each iteration step of the Augmented Lagrangian method,we need to handle a subproblem.Since the simple complementarity constraint set of the subproblem possesses the property of semi-algebraic,we adopt the projected gradient method and analyze the convergence for the subproblem.Third,we lift up the subproblem to a non-differentiable unconstrained optimization problem satisfying the Kurdyka-(?)ojasiewicz property,and investigate the convergence of the projected gradient algorithm for the extended subproblem.We also show that the sequence of KKT stationary points for the Augmented Lagrangian dual problem converges to the weak stationary point of MPCC.Finally,we illustrate the proposed algorithm by three examples.