Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Exact penalties for variational inequalities with applications to nonlinear complementarity problems

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

In this paper, we present a new reformulation of the KKT system associated to a variational inequality as a semismooth equation. The reformulation is derived from the concept of differentiable exact penalties for nonlinear programming. The best theoretical results are presented for nonlinear complementarity problems, where simple, verifiable, conditions ensure that the penalty is exact. We close the paper with some preliminary computational tests on the use of a semismooth Newton method to solve the equation derived from the new reformulation. We also compare its performance with the Newton method applied to classical reformulations based on the Fischer-Burmeister function and on the minimum. The new reformulation combines the best features of the classical ones, being as easy to solve as the reformulation that uses the Fischer-Burmeister function while requiring as few Newton steps as the one that is based on the minimum.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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. Auslender, A., Teboulle, M.: Lagrangian duality and related multiplier methods for variational inequality problems. SIAM J. Optim. 10(4), 1097–1115 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  2. Auslender, A., Teboulle, M.: Asymptotic Cones and Functions in Optimization and Variational Inequalities. Springer Monographs in Mathematics. Springer, New York (2003)

    MATH  Google Scholar 

  3. Bertsekas, D.: Constrained Optimization and Lagrange Multipliers. Academic Press, New York (1982)

    Google Scholar 

  4. Bertsekas, D.: Nonlinear Programming. Athena Scientific, Nashua (1995)

    MATH  Google Scholar 

  5. 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)

    Article  MATH  MathSciNet  Google Scholar 

  6. Di Pillo, G., Grippo, L.: A new class of augmented Lagrangians in nonlinear programming. SIAM J. Control Optim. 17(5), 618–628 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  7. Di Pillo, G., Grippo, L.: A continuously differentiable exact penalty function for nonlinear programming problems with inequality constraints. SIAM J. Control Optim. 23(1), 72–84 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  8. Di Pillo, G., Grippo, L.: Exact penalty functions in constrained optimization. SIAM J. Control Optim. 27(6), 1333–1360 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  9. Dirkse, S.P., Ferris, M.C.: Mcplib: A collection on nonlinear mixed complementarity problems. Optim. Methods Softw. 2, 319–345 (1995)

    Article  Google Scholar 

  10. Dirkse, S.P., Ferris, M.C.: Modeling and solution environments for MPEC: Gams & Matlab. In: Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing, Lausanne, 1997. Applied Optimization, vol. 22, pp. 127–147. Kluwer Academic, Norwell (1999)

    Google Scholar 

  11. Eckstein, J., Ferris, M.C.: Smooth methods of multipliers for complementarity problems. Math. Program. Ser. A 86(1), 65–90 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  12. Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer Series in Operations Research, vol. I. Springer, New York (2003)

    Google Scholar 

  13. Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer Series in Operations Research, vol. II. Springer, New York (2003)

    Google Scholar 

  14. Facchinei, F., Soares, J.: A new merit function for nonlinear complementarity problems and a related algorithm. SIAM J. Optim. 7(1), 225–247 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  15. Fischer, A.: A special newton-type optimization method. Optimization 24, 269–284 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  16. Fletcher, R.: A class of methods for nonlinear programming with termination and convergence properties. In: Integer and Nonlinear Programming, pp. 157–175. North-Holland, Amsterdam (1970)

    Google Scholar 

  17. Fletcher, R.: A class of methods for nonlinear programming. III. Rates of convergence. In: Numerical Methods for Nonlinear Optimization, Conf. Dundee, 1971, pp. 371–381. Academic Press, London (1972)

    Google Scholar 

  18. Fletcher, R.: An exact penalty function for nonlinear programming with inequalities. Math. Program. 5, 129–150 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  19. Fletcher, R., Lill, S.A.: A class of methods for nonlinear programming. II. Computational experience. In: Nonlinear Programming, Proc. Sympos., Univ. of Wisconsin, Madison, Wis., 1970, pp. 67–92. Academic Press, New York (1970)

    Google Scholar 

  20. Glad, T., Polak, E.: A multiplier method with automatic limitation of penalty growth. Math. Program. 17(2), 140–155 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  21. Kanzow, C.: C. Kanzow web site. http://www.mathematik.uni-wuerzburg.de/~kanzow/. Accessed in January 2007

  22. Kanzow, C., Petra, S.: On a semismooth least squares formulation of complementarity problems with gap reduction. Optim. Methods Softw. 19(5), 507–525 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  23. Kanzow, C., Petra, S.: Projected filter trust region methods for a semismooth least squares formulation of mixed complementarity problems. Optim. Methods Softw. 22(5), 713–735 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  24. Mukai, H., Polak, E.: A quadratically convergent primal-dual algorithm with global convergence properties for solving optimization problems with equality constraints. Math. Program. 9(3), 336–349 (1975)

    Article  MATH  MathSciNet  Google Scholar 

  25. Pennanen, T.: Dualization of generalized equations of maximal monotone type. SIAM J. Optim. 10(3), 809–835 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  26. Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18(1), 227–244 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  27. Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. Ser. A 58(3), 353–367 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  28. Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1, 97–116 (1976)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Instituto de Matemática e Estatística, University of São Paulo, São Paulo, Brazil

    Thiago A. de André & Paulo J. S. Silva

Authors
  1. Thiago A. de André
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paulo J. S. Silva
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Paulo J. S. Silva.

Additional information

T.A. de André was supported by FAPESP, grant 02/10942-9.

P.J.S. Silva was partially supported by CNPq, grants PQ 304133/2004-3, 477083/2006-4, and PRONEX—Optimization.

Rights and permissions

Reprints and permissions

About this article

Cite this article

de André, T.A., Silva, P.J.S. Exact penalties for variational inequalities with applications to nonlinear complementarity problems. Comput Optim Appl 47, 401–429 (2010). https://doi.org/10.1007/s10589-008-9232-3

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-008-9232-3

Keywords

Search

Navigation