Theory And Algorithms For Mathematical Programs With Equilibrium Constraints

This dissertation studies the theory and the algorithms for mathematical programs with equilibrium constraints (MPKC fur short), which form a relatively now and interesting class of optimization problems. The roots of MPEC lie in game theory and especially bilevel optimization. MPEC include a number of significant applications in economics and engineering. However, this cla.ss of optimization problems are very complicate. The major difficulty lies in the unusual nature of the constraints. For example, a standard constraint qualifications in the ordinary nonlinear programming such a.s MFCQ. LICQ or CRCQ never holds for MPEC. Therefore, serious attention has recently been paid to them. Theoretically, some new stationarity conditions are proposed under novel constraint qualifications. On the other hand, the development of numerical methods for the solution of MPEC is at a less advanced stage than optimality theory. This dissertation is organized as follows:First, we study the feasibility issues on MPEC, in which additional joint constraints are present that must be satisfied by the state and design variables of the problems. We introduce sufficient conditions that guarantee the feasibility of two classes of MPECs. the first is mathe?matical programs with linear complementarity constraints, the second is mathematical programs with nonlinear complementarity constraints. It turns out that these conditions also garantee the feasibility of the quadratic programming (QP) subproblems arising from the penalty interior point algorithm (PIPA) and the smooth sequential quadratic programming (SSQP) algorithm for solving MPECs. Thus the same conditions ensure that these algorithms are applicable for solving these class of jointly constrainted MPECs.Then, we study the inexact methods for solving MPECs. One, we present an inexact, smooth?ing continuation method for mathematical programs with complementarity constraints, which is a very general class of MPECs. Two, we propose an inexact SSQP algorithm for mathematical programs with linear complementarity constraints.Then, we proposed a new penalty interoir point algorithm for solving mathematical programs with mixed linear complementarity constraints, which does not require that the upper-level con?straints must be satisfied throughout all iterations of the algorithm. Under appropriate conditions. we establish the global convergence theory.Then again, a smooth trust-region algorithm (STRA) is proposed to solve mathematical programs with linear complementarity constraints, in which the upper-level constraints involves with the state and the design varibles. Besides concerning with the global convergence, numerical experiments are also done to verify the effectiveness of the algorithm.Finally, we develop a SSQP algorithm for mathematical programs with implicit complc- mentarity constraints, in which the upper-level constraints include nonlinear equality constraints. I'nder deriving new constraint qualification conditions corresponding to this class of MPECs, we establish the global convergence theory.