Semismooth Newton method for the lifted reformulation of mathematical programs with complementarity constraints. (English) Zbl 1245.90124

Summary: We consider a reformulation of mathematical programs with complementarity constraints, where by introducing an artificial variable the constraints are converted into equalities which are once but not twice differentiable. We show that the Lagrange optimality system of such a reformulation is semismooth and \(BD\)-regular at the solution under reasonable assumptions. Thus, fast local convergence can be obtained by applying the semismooth Newton method. Moreover, it turns out that the squared residual of the Lagrange system is continuously differentiable (even though the system itself is not), which opens the way for a natural globalization of the local algorithm. Preliminary numerical results are also reported.


90C30 Nonlinear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)


Full Text: DOI


[1] Billups, S.C.: Algorithms for complementarity problems and generalized equations. Tech. report 95–14 and Ph.D. thesis, Computer Sciences Department, University of Wisconsin, Madison (1995)
[2] De Luca, T., Facchinei, F., Kanzow, C.: A theoretical and numerical comparison of some semismooth algorithms for complementarity problems. Comput. Optim. Appl. 16, 173–205 (2000) · Zbl 0964.90046 · doi:10.1023/A:1008705425484
[3] Dolan, E., Moré, J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[4] Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003) · Zbl 1062.90002
[5] Facchinei, F., Soares, J.: A new merit function for nonlinear complementarity problems and a related algorithm. SIAM J. Optim. 7, 225–247 (1997) · Zbl 0873.90096 · doi:10.1137/S1052623494279110
[6] Fletcher, R., Leyffer, S.: Solving mathematical programs with equilibrium constraints as nonlinear programs. Optim. Methods Softw. 19, 15–40 (2004) · Zbl 1074.90044 · doi:10.1080/10556780410001654241
[7] Fletcher, R., Leyffer, S., Ralph, D., Scholtes, S.: Local convergence of SQP methods for mathematical programs with equilibrium constraints. SIAM J. Optim. 17, 259–286 (2006) · Zbl 1112.90098 · doi:10.1137/S1052623402407382
[8] Izmailov, A.F., Solodov, M.V.: Superlinearly convergent algorithms for solving singular equations and smooth reformulations of complementarity problems. SIAM J. Optim. 13, 386–405 (2002) · Zbl 1026.90085 · doi:10.1137/S1052623401372946
[9] Izmailov, A.F., Solodov, M.V.: An active-set Newton method for mathematical programs with complementarity constraints. SIAM J. Optim. 19, 1003–1027 (2008) · Zbl 1201.90193 · doi:10.1137/070690882
[10] Izmailov, A.F., Solodov, M.V.: On attraction of Newton-type iterates to multipliers violating second-order sufficiency conditions. Math. Program. 117, 271–304 (2009) · Zbl 1163.90025 · doi:10.1007/s10107-007-0158-9
[11] Jiang, H.: Global convergence analysis of the generalized Newton and Gauss–Newton methods of the Fischer–Burmeister equation of the complementarity problem. Math. Oper. Res. 24, 529–543 (1999) · Zbl 0944.90094 · doi:10.1287/moor.24.3.529
[12] Kanzow, C., Kleinmichel, H.: A new class of semismooth Newton-type methods for nonlinear complementarity problems. Comput. Optim. Appl. 11, 227–251 (1998) · Zbl 0913.90250 · doi:10.1023/A:1026424918464
[13] Kojima, M., Shindo, S.: Extensions of Newton and quasi-Newton methods to systems of PC 1 equations. J. Oper. Res. Soc. Jpn. 29, 352–374 (1986) · Zbl 0611.65032
[14] Kummer, B.: Newton’s method for nondifferentiable functions. In: Guddat, J., Bank, B., Hollatz, H., Kall, P., Klatte, D., Kummer, B., Lommalzsch, K., Tammer, L., Vlach, M., Zimmerman, K. (eds.) Advances in Mathematical Optimization, vol. 45, pp. 114–125. Akademie-Verlag, Berlin (1988)
[15] Kummer, B.: Newton’s method based on generalized derivatives for nonsmooth functions. In: Oettli, W., Pallaschke, D. (eds.) Advances in Optimization, pp. 171–194. Springer, Berlin (1992) · Zbl 0768.49012
[16] Leyffer, S.: MacMPEC: AMPL collection of mathematical programs with equilibrium constraints. http://wiki.mcs.anl.gov/leyffer/index.php/MacMPEC
[17] Luo, Z.-Q., Pang, J.-S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge Univ. Press, Cambridge (1996)
[18] Mifflin, R.: Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15, 959–972 (1977) · Zbl 0376.90081 · doi:10.1137/0315061
[19] Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (2006) · Zbl 1104.65059
[20] Outrata, J.V., Kocvara, M., Zowe, J.: Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results. Kluwer Acad. Publ., Boston (1998) · Zbl 0947.90093
[21] Pang, J.S., Qi, L.: Nonsmooth equations: Motivation and algorithms. SIAM J. Optim. 3, 443–465 (1993) · Zbl 0784.90082 · doi:10.1137/0803021
[22] Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227–244 (1993) · Zbl 0776.65037 · doi:10.1287/moor.18.1.227
[23] Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993) · Zbl 0780.90090 · doi:10.1007/BF01581275
[24] Ralph, D.: Sequential quadratic programming for mathematical programs with linear complementarity constraints. In: Computational Techniques and Applications: CTAC95, pp. 663–668. World Scientific, Singapore (1996) · Zbl 0910.90253
[25] Ralph, D., Wright, S.J.: Some properties of regularization and penalization schemes for MPECs. Optim. Methods Softw. 19, 527–556 (2004) · Zbl 1097.90054 · doi:10.1080/10556780410001709439
[26] Scheel, H., Scholtes, S.: Mathematical programs with complementarity constraints: stationarity, optimality and sensitivity. Math. Oper. Res. 25, 1–22 (2000) · Zbl 1073.90557 · doi:10.1287/moor.
[27] Scholtes, S.: Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11, 918–936 (2001) · Zbl 1010.90086 · doi:10.1137/S1052623499361233
[28] Stein, O.: Lifting mathematical programs with complementarity constraints. Math. Program. (2010). doi: 10.1007/s10107-010-0345-y · Zbl 1250.90094
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.