A new smoothing method for nonlinear complementarity problems involving P0-function

  • El Hassene OSMANI INSA-IRMAR Rennes and Laboratory of Fundamental and Numerical Mathematics, University Ferhat Abbas of Setif 1, Setif, Algeria.
  • Mounir Haddou Insa Rennes and IRMAR
  • Naceurdine Bensalem Laboratory of Fundamental and Numerical Mathematics, University Ferhat Abbas of Setif 1, Setif, Algeria.
  • Lina Abdallah Lebanese University, Tripoli, Lebanon.
DOI: https://doi.org/10.19139/soic-2310-5070-1493
Keywords: Nonlinear complementarity problems, Newton’s method, smoothing functions, P0-matrix, interior-point methods

Abstract

In this paper, we present a family of smoothing methods to solve nonlinear complementarity problems (NCPs) involving P0-function. Several regularization or approximation techniques like Fisher-Burmeister’s method, interior-point methods (IPMs) approaches, or smoothing methods already exist. All the corresponding methods solve a sequence of nonlinear systems of equations and depend on parameters that are difficult to drive to zero. The main novelty of our approach is to consider the smoothing parameters as variables that converge by themselves to zero. We do not need any complicated updating strategy, and then obtain nonparametric algorithms. We prove some global and local convergence results and present several numerical experiments, comparisons, and applications that show the efficiency of our approach.

References

L. Abdallah, M. Haddou, and T. Migot, Solving absolute value equation using complementarity and smoothing functions, Journal of Computational and Applied Mathematics, vol. 327, pp. 1196–207, 2018.

A. Auslender, R. Cominetti, and M. Haddou, Asymptotic analysis for penalty and barrier methods in convex and linear programming, Mathematics of Operations Research, vol. 22, no. 1, pp. 43–62, 1997.

M. Bergounioux, and M. Haddou, A new relaxation method for a discrete image restoration problem, Journal of Convex Analysis , vol. 17, no. 3, pp. 861–883, 2010.

F. Bonnans, Optimisation continue: cours et probl`emes corrig´es, Math´ematiques appliqu´ees pour le Master, Dunod, 2006.

F. Bonnans, Optimisation continue: cours et probl`emes corrig´es, Math´ematiques appliqu´ees pour le Master, Dunod, 2006.

X. Chen, B. Chen, and C. Kanzow, A penalized Fischer-Burmeister NCP function: theoretical investigation and numerical results, Int. fur Angewandte Mathmatik der Univ. Mathematical Programming, 1997.

C. Chen, and O. L. Mangasarian, A class of smoothing functions for nonlinear complementarity problems, Computational Optimization and Applications, vol. 5, pp. 97–138, 1996.

E. D. Dolan, and J. J. Mor´e, Benchmarking optimization software with performance profiles, Mathematical Programming, vol. 91, pp. 201–213, 2002.

L. Dong-hui, and Z. Jin-ping, A penalty technique for nonlinear problems, Journal of Computational Mathematics, vol. 16, no. 1, pp. 40–50, 1998

F. Facchinei, and J. S. Pang, Finite-dimensional Variational Inequalities and Complementarity Problem, Springer Series in Operations Research, Springer-Verlag, New York, vol. 1-2, 2003.

M. C. Ferris, and J. S. Pang, Engineering and economic applications of complementarity problems, Society of Inian Automobile Manufacturers Review, vol. 39, no. 4, pp. 669–713, 1997.

A. Fischer, Solution of monotone complementarity problems with locally Lipschitz functions, Mathematical Programming, vol. 76, no. 2, pp. 513–532, 1997.

A. Fischer, A special Newton-type optimizaton method, Optimization, vol. 24, no. 3-4, pp. 269–284, 1992.

M. E. Ghami, New primal-dual interior-point methods based on kernel functions, PhD thesis, 2005.

C. Geiger, and C. Kanzow, On the solution of monotone complementarity problems, Computational Optimization and Applications, vol. 5, pp. 155–173, 1996.

P. T. Harker, Accelerating the convergence of the diagonalization and projection algorithms for finite-dimensional variational inequalities, Mathematical Programming, vol. 41, pp. 29–59, 1988.

M. Haddou, A new class of smoothing methods for mathematical programs with equilibrium constraints, Pacific Journal of Optimization, vol. 5, pp. 87–95, 2009.

M. Haddou, and P. Maheux, Smoothing methods for nonlinear complementarity problems, Journal of Optimization Theory and Applications, vol. 160, pp. 711–729, 2014.

M. Haddou, T. Migot, and J. Omer, A generalized direction in interior-point method for monotone linear complementarity problems, Optimization Letters, vol. 13, pp. 35–53, 2019.

P. T. Harker, and J. S. Pang, Finite dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications, Mathematical Programming, vol. 48, pp. 161–220, 1990.

C. Huang, and S. Wang, A power penalty approach to a Nonlinear Complementarity Problem, Operations Research Letters, vol. 38, no. 1, pp. 72–76, 2010.

C. Kanzow, N.Yamashita, and M.Fukushima, New NCP functions and their properties, Journal of Optimization Theory and Applications, vol. 94, pp. 115–135, 1997.

C. Kanzow, Some equation-based methods for the nonlinear complementarity problem, Optimization Methods and Software, vol. 3, pp. 327–340, 1994.

C. Kanzow, and H. Pieper, Jacobian smoothing methods for nonlinear complementarity problems, SIAM Journal on Optimization, vol. 9, no. 2, pp. 342–373, 1999.

N. Krejic, and S. Rapaji, Globally convergent Jacobian smoothing inexact Newton methods for NCP, Computational Optimization and Applications, vol. 41, pp. 243–261, 2008.

M. Kojima, and S. Shindo, Extensions of Newton and quasi-Newton methods to systems of PC1 equations, Journal of the Operations Research Society of Japan, vol. 29, pp. 352–374, 1986.

C.F. Ma, P. Y. Nie, and G. P. Liang, A new smoothing equations approach to the nonlinear complementarity problems, Journal of Computational Mathematics, vol. 21, pp. 747–758, 2003.

MATLAB, version R2020. Natick, Massachusetts: The Math Works Inc, 2019.

J. J. Mor´e, Global methods for nonlinear complementarity problems, Mathematics of Operations Research, vol. 21, no. 3, pp. 589–614, 1996.

P. Y. Nie, A null space approach for solving nonlinear complementarity problems, Acta Mathematicae Applicatae Sinica, vol. 22, no. 1, pp. 9–20, 2006.

J. S. Pang, A B-differentiable equations based, globally and locally quadratically convergent algorithm for nonlinear programming, complementarity, and variational inequality problems, Mathematical Programming, vol. 51, pp. 101–131, 1991.

J. S. Pang, and S. A. Gabriel, NE-SQP: A robust algorithm for nonlinear complementarity problem, Mathematical Programming, vol. 60, pp. 295–337, 1993.

L. Qi, and D. H. Li, A smoothing Newton method for nonlinear complementarity problems, Advanced Modeling and Optimization, vol. 13, no. 2, pp. 141–152, 2011.

T. Migot, Contributions aux m´ethodes num´eriques pour les probl`emes de compl´ementarit´e et probl`emes d’optimisation sous contraintes de compl`ementarite´, Ph.D. thesis, INSA Rennes, 2017.

T Migot, and Jocelyne Erhel, Analyse meth´ematique de mod`eles g´eochimiques, Rapport de recherche, INRIA Rennes, ´equope SAGE, 2014.

D. T. S. Vu, I.B. Gharbia, M. Haddou, and Q. H. Tran, A new approach for solving nonlinear algebraic systems with complementarity conditions, Mathematics and Computers in Simulation, vol. 190, pp. 1243–1274, 2021.

N. Yamashita, and M. Fukushima, Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems, Mathematical Programming, vol. 76, pp. 469–491, 1997.

W. Zhong, Y. Min, and W. Chang, A partially smoothing Jacobian method for nonlinear complementarity problems with P0 function, Journal of Computational and Applied Mathematics, vol. 286, pp. 158–171, 2015.

L. Zhang, J. Han, and Z. Huang, Superlinear quadratic one step smoothing Newton method for P0 NCP, Acta Mathematica Sinica, vol. 21, no. 2, pp. 117–128, 2005.

http://dm.unife.it/pn2o/software/Extragradient/test-problems.html.

Published
2022-09-29
How to Cite
OSMANI, E. H., Haddou, M., Bensalem, N., & Abdallah, L. (2022). A new smoothing method for nonlinear complementarity problems involving P0-function. Statistics, Optimization & Information Computing, 10(4), 1267-1292. https://doi.org/10.19139/soic-2310-5070-1493
Issue
Vol 10 No 4 (2022)
Section
Research Articles
Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
    2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
    3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).