Skip to main content
SpringerLink
Log in

Lifting mathematical programs with complementarity constraints

  • Full Length Paper
  • Published:
Mathematical Programming Submit manuscript

Abstract

We present a new smoothing approach for mathematical programs with complementarity constraints, based on the orthogonal projection of a smooth manifold. We study regularity of the lifted feasible set and, since the corresponding optimality conditions are inherently degenerate, introduce a regularization approach involving a novel concept of tilting stability. A correspondence between the C-index in the original problem and the quadratic index in the lifted problem is shown. In particular, a local minimizer of the mathematical program with complementarity constraints may numerically be found by minimization of the lifted, smooth problem. We report preliminary computational experience with the lifting approach.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Anitescu M.: On using the elastic mode in nonlinear programming approaches to mathematical programs with complementarity constraints. SIAM J. Optim. 15, 1203–1236 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  2. Anitescu M., Tseng P., Wright S.J.: Elastic-mode algorithms for mathematical programs with equilibrium constraints: global convergence and stationarity properties. Math. Program. 110, 337–371 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  3. Benson H.Y., Sen A., Shanno D.F., Vanderbei R.J.: Interior point algorithms, penalty methods and equilibrium problems. Comput. Optim. Appl. 34, 155–182 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bouza Allende, G.: Mathematical programs with equilibrium constraints: solution techniques from parametric optimization, Ph.D. thesis, University of Twente (2006)

  5. de Miguel A., Friedlander M., Nogales F., Scholtes S.: An interior-point method for MPECS. SIAM J. Optim. 16, 587–609 (2005)

    Article  MathSciNet  Google Scholar 

  6. Facchinei F., Jiang H., Qi L.: A smoothing method for mathematical programs with equilibrium constraints. Math. Program. 85, 81–106 (1999)

    Article  MathSciNet  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  8. Fukushima M., Pang J.: Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: Théra, M., Tichatschke, R. (eds) Ill-posed Variational Problems and Regularization Techniques. Lecture Notes in Economics and Mathematical Systems, vol. 447, pp. 99–110, pp. 99–110. Springer, Heidelberg (1999)

    Google Scholar 

  9. Fukushima M., Tseng P.: An implementable active-set algorithm for computing a b-stationary point of a mathematical program with linear complementarity constraints. SIAM J. Optim. 12, 724–739 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  10. Giallombardo G., Ralph D.: Multiplier convergence in trust region methods with application to convergence of decomposition methods for MPECs. Math. Program. 112, 335–369 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  11. Hu X., Ralph D.: Convergence of a penalty method for mathematical programming with complementarity constraints. J. Optim. Theory Appl. 123, 365–390 (2004)

    Article  MathSciNet  Google Scholar 

  12. Huang X.X., Yang X.Q., Zhu D.L.: A sequential smooth penalization approach to mathematical programs with complementarity constraints. Numer. Funct. Anal. Optim. 27, 71–98 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  13. Jiang H., Ralph D.: QPECgen, a MATLAB generator for mathematical programs with quadratic objectives and affine variational inequality constraints. Comput. Optim. Appl. 13, 25–59 (1999)

    Article  MathSciNet  Google Scholar 

  14. Jiang H., Ralph D.: Extension of quasi-newton methods to mathematical programs with complementarity constraints. Comput. Optim. Appl. 25, 123–150 (2002)

    Article  MathSciNet  Google Scholar 

  15. Jongen H.Th., Jonker P., Twilt F.: Critical sets in parametric optimization. Math. Program. 34, 333–353 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  16. Jongen H.Th., Meer K., Triesch E.: Optimization Theory. Kluwer, Boston (2004)

    MATH  Google Scholar 

  17. Jongen H.Th., Möbert T., Rückmann J.-J., Tammer K.: On inertia and Schur complement in optimization. Linear Algebra Appl. 95, 97–109 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  18. Jongen H.Th., Rückmann J.-J., Shikhman V.: On stability of the feasible set of a mathematical program with complementarity constraints. SIAM J. Optim. 20, 1171–1184 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  19. Jongen H.Th., Rückmann J.-J., Shikhman V.: MPCC: critical point theory. SIAM J. Optim. 20, 473–484 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  20. Kočvara M., Outrata J., Zowe J.: Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results. Kluwer, Dordrecht (1998)

    MATH  Google Scholar 

  21. Leyffer, S.: MacMPEC—ampl collection of Mathematical Programs with Equilibrium Constraints. http://wiki.mcs.anl.gov/leyffer/index.php/MacMPEC (2009)

  22. Lin G., Fukushima M.: Hybrid approach with active set identification for mathematical programs with complementarity constraints. J. Optim. Theory Appl. 128, 1–28 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  23. Liu X., Perakis G., Sun J.: A robust SQP method for mathematical programs with linear complementarity constraints. Comput. Optim. Appl. 34, 5–33 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  24. Luo Z.-Q., Pang J.S., Ralph D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)

    Book  Google Scholar 

  25. Luo Z.-Q., Pang J.S., Ralph D.: Piecewise sequential quadratic programming for mathematical programs with nonlinear complementarity constraints. In: Migdalas, A., Pardalos, P., Värbrand, P. (eds) Multilevel Optimization: Algorithms, Complexity, and Applications, pp. 209–229. Kluwer Academic Publishers, Dordrecht (1998)

    Chapter  Google Scholar 

  26. Ouellette D.V.: Schur complements and statistics. Linear Algebra Appl. 36, 187–295 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  27. Poliquin R.A., Rockafellar R.T.: Tilt stability of a local minimum. SIAM J. Optim. 8, 287–299 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  28. Raghunathan A.U., Biegler L.T.: Interior point methods for mathematical programs with complementarity constraints. SIAM J. Optim. 15, 720–750 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  29. Ralph, D., Stein, O.: Homotopy methods for quadratic programs with complementarity constraints. Preprint No. 120, Department of Mathematics - C, RWTH Aachen University (2006)

  30. Ralph D., Wright S.J.: Some properties of regularization and penalization schemes for MPECs. Optim. Methods Softw. 19, 527–556 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  31. Scheel H., Scholtes S.: Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity. Math. Oper. Res. 25, 1–22 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  32. Scholtes S.: Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11, 918–936 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  33. Scholtes S., Stöhr M.: Exact penalization of mathematical programs with equilibrium constraints. SIAM J. Control Optim. 37, 617–652 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  34. Stöhr M.: Nonsmooth trust region methods and their applications to mathematical programs with equilibrium constraints. Shaker-Verlag, Aachen (1999)

    Google Scholar 

  35. Wächter A., Biegler L.T.: Line search filter methods for nonlinear programming: motivation and global convergence. SIAM J. Optim. 16, 1–31 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  36. Wächter A., Biegler L.T.: Line search filter methods for nonlinear programming: local convergence. SIAM J. Optim. 16, 32–48 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  37. Zhang J., Liu G.: A new extreme point algorithm and its application in psqp algorithms for solving mathematical programs with linear complementarity constraints. J. Glob. Optim. 19, 335–361 (2001)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Operations Research, Karlsruhe Institute of Technology, Karlsruhe, Germany

    Oliver Stein

Authors
  1. Oliver Stein
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Oliver Stein.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Stein, O. Lifting mathematical programs with complementarity constraints. Math. Program. 131, 71–94 (2012). https://doi.org/10.1007/s10107-010-0345-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-010-0345-y

Keywords

Mathematics Subject Classification (2000)

Search

Navigation