An improved LQP-based method for solving nonlinear complementarity problems

Abstract

The well-known logarithmic-quadratic proximal (LQP)method has motivated a number of efficient numerical algorithms for solving nonlinear complementarity problems (NCPs). In this paper,we aim at improving one of them, i.e., the LQP-based interior prediction-correction method proposed in [He, Liao and Yuan, J. Comp. Math., 2006, 24(1): 33–44], via identifying more appropriate step-sizes in the correction steps. Preliminary numerical results for solving some NCPs arising in traffic equilibrium problems are reported to verify the theoretical assertions.

Keywords

Logarithmic-quadratic proximal method / nonlinear complementarity problems / prediction-correction / step-size

References

[1] Auslender A., Haddou M. An interior proximal point method for convex linearly constrained problems and its extension to variational inequalities. Mathematical Programming, 1995, 71: 77-100.

[2] Auslender A., Teboulle M., Ben-Tiba S. A logarithmic-quadratic proximal method for variational inequalities. Computational Optimization and Applications, 1999, 12: 31-40.

[3] Bnouhachem A., Yuan X. M. Extended LQP method for monotone nonlinear complementarity problems. Journal of Optimization Theory and Applications, 2007, 135: 343-353.

[4] Burachik R. S., Lopes J. O., Da Silva G. J. P. An inexact interior point proximal method for the variational inequality problem. Computational and Applied Mathematics, 2009, 28(1): 15-36.

[5] Burachik R. S., Svaiter B. F. A relative error tolerance for a family of generalized proximal point methods. Mathematics of Operations Research, 2001, 26(4): 816-831.

[6] Ferris M. C., Pang J. -S. Engineering and economic applications of complementarity problems. SIAM Review, 1997, 39: 669-713.

[7] He B. S., Liao L. -Z., Yuan X. M. A LQP based interior prediction-correction method for nonlinear complementarity problems. Journal of Computational Mathematics, 2006, 24(1): 33-44.

[8] He B S, Xu W, Yang H, Yuan X M. Solving over-production and supply-guarantee problems in economic equilibria. Networks and Spatial Economics, 2009 (to appear)

[9] He B. S., Xu Y., Yuan X. M. A Logarithmic-Quadratic Proximal prediction-correction method for structured monotone variational inequalities. Computational Optimization and Applications, 2006, 35(1): 19-46.

[10] Li M., Shao H., He B. S. An inexact logarithmic-quadratic proximal augmented Lagrangian method for a class of constrained variational inequalities. Mathematical Methods of Operations Research, 2007, 66(2): 183-201.

[11] Martinet B. Regularization d’inequations variationelles par approximations sucessives. Revue Francaise d’Informatique et de Recherche Opérationelle, 1970, 4: 154-159.

[12] Meng Q., Huang Y. K., Chu R. L. Competitive facility location on decentralized supply chains. European Journal of Operational Research, 2009, 196: 487-499.

[13] Nagurney A., Zhang D. Projected Dynamical Systems and Variational Inequalities with Applications, 1996, Boston, Dordrecht, London: Kluwer Academic Publishers.

[14] Rockafellar R. T. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 1976, 14: 877-898.

[15] Xu M. H., Yuan X. M., Huang Q. L. An improved general extra-gradient method with refined step size for nonlinear monotone variational inequalities. Journal of Global Optimization, 2007, 39: 155-169.

[16] Xu Y., He B. S., Yuan X. M. A hybrid inexact Logarithmic-Quadratic Proximal method for nonlinear complementarity problems. Journal of Mathematical Analysis and Applications, 2006, 322(1): 276-287.

[17] Yang H., Huang H. J. Mathematical and Economic Theory of Road Pricing, 2005, Oxford: Elsevier.

[18] Yuan X. M. The prediction-correction approach to nonlinear complementarity problems. European Journal of Operational Research, 2007, 176: 1357-1370.

[19] Yuan X. M. A new criterion for the inexact Logarithmic-Quadratic Proximal method and its derived hybrid methods. Journal of Global Optimization, 2008, 40(4): 529-543.