Skip to main content
SpringerLink
Log in

Hybrid Approach with Active Set Identification for Mathematical Programs with Complementarity Constraints

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

We consider a mathematical program with complementarity constraints (MPCC). Our purpose is to develop methods that enable us to compute a solution or a point with some kind of stationarity to MPCC by solving a finite number of nonlinear programs. We apply an active set identification technique to a smoothing continuation method (Ref. 1) and propose a hybrid algorithm for solving MPCC. We develop also two modifications: one makes use of an index addition strategy; the other adopts an index subtraction strategy. We show that, under reasonable assumptions, all the proposed algorithms possess a finite termination property. Further discussions and numerical experience are given as well

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. Fukushima M., Pang J. S., Convergence of a Smoothing Continuation Method for Mathematical Problems with Complementarity Constraints, Ill-Posed Variational Problems and Regularization Techniques, Edited by M. Théra and R. Tichatschke, Lecture Notes in Economics and Mathematical Systems, Springer Verlag, Berlin, Germany, Vol. 477, pp. 105–116, 1999.

  2. Z.Q. Luo J.S. Pang D. Ralph (1996) Mathematical Programs with Equilibrium Constraints Cambridge University Press Cambridge, United Kingdom

    Google Scholar 

  3. Y. Chen M. Florian (1995) ArticleTitleThe Nonlinear Bilevel Programming Problem: Formulation, Regularity, and Optimality Conditions Optimization 32 193–209 Occurrence Handle96c:90100

    MathSciNet  Google Scholar 

  4. M. Fukushima Z. Q. Luo J. S. Pang (1998) ArticleTitleA Globally Convergent Sequential Quadratic Programming Algorithm for Mathematical Programs with Linear Complementarity Constraints Computational Optimization and Applications 10 5–34 Occurrence Handle10.1023/A:1018359900133 Occurrence Handle99e:90088

    Article  MathSciNet  Google Scholar 

  5. H. Jiang D. Ralph (2000) ArticleTitleSmooth SQP Methods for Mathematical Programs with Nonlinear Complementarity Constraints SIAM Journal on Optimization 10 779–808 Occurrence Handle10.1137/S1052623497332329 Occurrence Handle2001f:90073

    Article  MathSciNet  Google Scholar 

  6. X. Chen M. Fukushima (2004) ArticleTitleA Smoothing Method for a Mathematical Program with P-Matrix Linear Complementarity Constraints Computational Optimization and Applications 27 223–246 Occurrence Handle10.1023/B:COAP.0000013057.54647.6d Occurrence Handle2005a:90159

    Article  MathSciNet  Google Scholar 

  7. X. Hu D. Ralph (2004) ArticleTitleConvergence of a Penalty Method for Mathematical Programming with Equilibrium Constraints Journal of Optimization Theory and Applications 123 365–390 Occurrence Handle10.1007/s10957-004-5154-0 Occurrence Handle2005f:90120

    Article  MathSciNet  Google Scholar 

  8. X. X. Huang X. Q. Yang D. L. Zhu (2001) A Sequential Smooth Penalization Approach to Mathematical Programs with Complementarity Constraints, Manuscript Department of Applied Mathematics, Hong Kong Polytechnic University Hong Kong

    Google Scholar 

  9. G. H. Lin M. Fukushima (2003) ArticleTitleSome Exact Penalty Results for Nonlinear Programs and Their Applications to Mathematical Programs with Equilibrium Constraints Journal of Optimization Theory and Applications 118 67–80 Occurrence Handle2004e:90127

    MathSciNet  Google Scholar 

  10. M. Fukushima P. Tseng (2002) ArticleTitleAn Implementable Active-Set Algorithm for Computing a B-Stationary Point of the Mathematical Program with Linear Complementarity Constraints SIAM Journal on Optimization 12 724–739 Occurrence Handle10.1137/S1052623499363232 Occurrence Handle2003e:90082

    Article  MathSciNet  Google Scholar 

  11. F Facchinei H Jiang L Qi (1999) ArticleTitleA Smoothing Method for Mathematical Programs with Equilibrium Constraints Mathematical Programming 85 107–134 Occurrence Handle10.1007/s101070050048 Occurrence Handle2000f:90065

    Article  MathSciNet  Google Scholar 

  12. G. H. Lin M. Fukushima (2005) ArticleTitleA Modified Relaxation Scheme for Mathematical Programs with Complementarity Constraints Annals of Operations Research 133 63–84 Occurrence Handle2005i:90080

    MathSciNet  Google Scholar 

  13. G. H. Lin M. Fukushima (2003) ArticleTitleNew Relaxation Method for Mathematical Programs with Complementarity Constraints Journal of Optimization Theory and Applications 118 81–116 Occurrence Handle2004g:90109

    MathSciNet  Google Scholar 

  14. S. Scholtes (2001) ArticleTitleConvergence Properties of a Regularization Scheme for Mathematical Programs with Complementarity Constraints SIAM Journal on Optimization 11 918–936 Occurrence Handle10.1137/S1052623499361233 Occurrence Handle1010.90086 Occurrence Handle2002g:90138

    Article  MATH  MathSciNet  Google Scholar 

  15. S. Scholtes M. Stöhr (2001) ArticleTitleHow Stringent Is the Linear Independence Assumption for Mathematical Programs with Complementarity Constraints Mathematics of Operations Research 26 851–863 Occurrence Handle10.1287/moor.26.4.851.10007 Occurrence Handle2002k:90141

    Article  MathSciNet  Google Scholar 

  16. Scheel, H., and Scholtes, S., Mathematical Programs with Complementarity Constraints: Stationarity, Optimality, and Sensitivity, Mathematics of Operations Research, Vol. 25, pp. 1–22, 2000.

  17. Burke, J. V., On the Identification of Active Constraints, II: The Nonconvex Case, SIAM Journal on Numerical Analysis, Vol. 27, pp. 1081–1102, 1990.

  18. Burke, J. V., and Moré, J. J., On the Identification of Active Constraints, SIAM Journal on Numerical Analysis, Vol. 25, pp. 1197–1211, 1988.

  19. Facchinei, F., Fischer, A., and Kanzow, C., On the Accurate Identification of Active Constraints, SIAM Journal on Optimization, Vol. 9, pp. 14–32, 1998.

  20. Facchinei, F., Fischer, A., and Kanzow, C., On the Identification of Zero Variables in an Interior-Point Framework, SIAM Journal on Optimization, Vol. 10, pp. 1058–1078, 2000.

  21. Yamashita, N., Dan, H., and Fukushima, M., On the Identification of Degenerate Indices in the Nonlinear Complementarity Problem with the Proximal Point Algorithm, Mathematical Programming, Vol. 99, pp. 377–397, 2004.

  22. Tseng, P., Growth Behavior of a Class of Merit Functions for the Nonlinear Complementarity Problem, Journal of Optimization Theory and Applications, Vol. 89, pp. 17–37, 1996.

  23. S. Leyffer, MacMPEC: AMPL Collection of MPECs, Technical Report; see http://www-unix.mcs.anl.gov/∼leyffer/MacMPEC/, 2000.

  24. Jiang, H., and Ralph, D., QPECgen, a MATLAB Generator for Mathematical Programs with Quadratic Objectives and Affine Variational Inequality Constraints, Computational Optimization and Applications, Vol. 13, pp. 25–59, 1999.

  25. Lin G.H., and Fukushima, M., A Hybrid Algorithms with Active Set Identification for Mathematical Programs with Complementarity Constraints, Technical Report 2002-008, Deparment of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto, Japan, 2002.

  26. Lin, G.H., and Fukushima, M., Hybrid Algorithms with Index Addition and Subtraction Strategies for Solving Mathematical Programs with Complementarity Constraints, Technical Report 2003-003, Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto, Japan, 2003.

Download references

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, Dalian University of Technology, Dalian, China

    G. H. Lin

  2. Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto, Japan

    M. Fukushima

Authors
  1. G. H. Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. Fukushima
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by P. Tseng

This work was supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science, Sports, and Culture of Japan. The authors are grateful to Professor Paul Tseng for helpful suggestions on an earlier version of the paper.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lin, G.H., Fukushima, M. Hybrid Approach with Active Set Identification for Mathematical Programs with Complementarity Constraints. J Optim Theory Appl 128, 1–28 (2006). https://doi.org/10.1007/s10957-005-7549-y

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-005-7549-y

Keywords

Search

Navigation