(514e) Solving Mpccs with IPOPT

Mathematical Programs with Complementarity Constraints (MPCCs) are used to model certain types of disjunctions without introducing binary variables. Mathematically, bi-level optimization, piecewise functions, and equilibria all can be reformulated as MPCCs. In process optimization, complementarities allow for models containing disappearance of phases, flow reversal, safety valve options, and some other discrete events within an NLP framework. However, MPCCs pose well-known difficulties, particularly because they violate constraint qualifications (CQs), such as the Linear Independence Constraint Qualification and the Mangasarian Fromovitz Constraint Qualification, at all feasible points. Without a CQ, the classical necessary optimality conditions do not apply so the optimum may or may not be a KKT point. Therefore MPCCs are challenging for most NLP solvers, which are based on the KKT conditions.

Nevertheless, nonlinear programming reformulation strategies may be used to find strongly stationary MPCC solutions, which are characterized by solutions to relaxed nonlinear programming (RNLP) problems that satisfy LICQ. Such reformulations include i) inequality relaxations of the complementarity constraints, ii) replacing complementarity constraints by smoothed NCP functions and iii) embedding complementarity terms as exact penalties. Inequality relaxations solve a sequence of more and more ill-posed NLPs. Similarly, the NCP function reformulation is extremely nonlinear near the solution leading to numerical difficulty. The exact penalty reformulation requires a priori knowledge of a suitable penalty parameter to be effective.

This talk discusses our experiences in extending the well-known primal-dual barrier solver, IPOPT, which is designed for large scale NLP problems, to deal with the solution of MPCCs. First, we propose two automatic penalty adjustment approaches in IPOPT. The first approach is similar to that from Leyffer, Lopez-Calva and Nocedal (2007), in which the complementary error is checked and the penalty parameter is potentially adjusted after each barrier problem is converged. The second approach only adjusts the penalty term after the penalty NLP converges. Next, we propose an improvement to the equality reformulation of MPCCs. When a complementary constraint is biactive, the equality constraint leads to a singular row in the Jacobian. For this case, our previous work on structured regularization can detect dependent equalities automatically and numerically eliminate them at each iteration. Therefore, we propose an altered equality reformulation of MPCCs using structured regularization. If only one part of a complementary constraint is active, we relax the corresponding inequality constraint to effectively remove this constraint. As a result, the problem is well posed at all points and the modified Newton step leads to fast convergence.

We evaluate the proposed approaches on 120 problems from the MacMPEC library, other examples that do not have strongly stationary solutions, and several larger MPCCs derived on engineering systems. The latter examples are also scalable to variable problem sizes. For all of these case, we compare the efficiency of the new approaches are compared to previous NLP reformulation strategies.