Convergence of a non-interior smoothing method for variational inequality problems

详细信息    查看全文

• 作者：Xiuyun Zheng (1) xyzhengxd@gmail.com
  Hongwei Liu (2)
  Jianguang Zhu (2)
• 关键词：Variational inequality problem &#8211 ; Non ; interior method &#8211 ; Smoothing method &#8211 ; Global linear convergence &#8211 ; Local quadratic convergence
• 刊名：Journal of Applied Mathematics and Computing
• 出版年：2012
• 出版时间：October 2012
• 年：2012
• 卷：40
• 期：1-2
• 页码：341-355
• 全文大小：501.7 KB
• 参考文献：1. Ahn, B.: Iterative methods for linear complementarity problems with upperbounds and lowerbounds. Math. Program. 26, 265–315 (1983)
  2. Burke, J., Xu, S.: The global linear convergence of a non-interior path-following algorithm for linear complementarity problems. Math. Oper. Res. 23, 719–734 (1998)
  3. Chen, B., Harker, P.T.: A non-interior-point continuation method for linear complementarity problems. SIAM J. Matrix Anal. Appl. 14, 1168–1190 (1993)
  4. Chen, X., Qi, L., Sun, D.: Global and superlinear convergence of the smoothing Newton method and its application to general box-constrained variational inequalities. Math. Comput. 67, 519–540 (1998)
  5. Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)
  6. Facchinei, F., Fischer, A., Kanzow, C.: A semismooth newton method for variational inequalities: the case of box constraints. In: Ferris, M.C., Pang, J.-S. (eds.) Complementarity and Variational Problems: State of the Art, pp. 76–90. SIAM, Philadelphia (1997)
  7. Gowda, M.S., Sznajder, J.J.: Weak univalence and connectedness of inverse images of continuous functions. Math. Oper. Res. 24, 255–261 (1999)
  8. Han, D., Lo, H.K.: Two new self-adaptive projection methods for variational inequality problems. Comput. Math. Appl. 43, 1529–1537 (2002)
  9. Harker, P.T., Pang, J.: Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithm and applications. Math. Program. 48, 161–220 (1990)
  10. He, B.: A class of projection and contraction methods for monotone variational inequalities. Appl. Math. Optim. 35, 69–76 (1997)
  11. Huang, Z.: The global linear and local quadratic convergence of a non-interior continuation algorithm for the LCP. IMA J. Numer. Anal. 25, 670–684 (2005)
  12. Huang, Z., Qi, L., Sun, D.: Sub-quadratic convergence of a smoothing Newton algorithm for the P 0 and monotone LCP. Math. Program. 99, 423–441 (2004)
  13. Kanzow, C.: Some noninterior continuation methods for complementarity problems. SIAM J. Matrix Anal. Appl. 17, 851–868 (1996)
  14. Kanzow, C., Jiang, H.: A continuation method for (strongly) monotone variational inequalities. Math. Program. 81, 103–126 (1998)
  15. Mifflin, R.: Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15, 957–972 (1977)
  16. Murty, K.: Linear Complementarity, Linear and Nonlinear Programming. Heldermann, Berlin (1988)
  17. Noor, M.: A modified projection method for monotone variational inequalities. Appl. Math. Lett. 12, 83–87 (1999)
  18. Qi, H.D.: A regularized smoothing newton method for box constrained variational inequality problems with P 0-functions. SIAM J. Optim. 10, 315–330 (2000)
  19. Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227–244 (1993)
  20. Qi, L., Sun, D., Zhou, G.: A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems. Math. Program. 87, 1–35 (2000)
  21. Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993)
  22. Ravindran, G., Gowda, M.: Regularization of P 0-functions in box variational inequality problems. SIAM J. Optim. 11, 748–760 (2001)
  23. Sharif-Mokhtarian, F., Goffin, J.L.: Long-step interior-point algorithms for a class of variational inequalities with monotone operators. J. Optim. Theory Appl. 97, 181–210 (1998)
  24. Sun, J., Zhao, G.: Quadratic convergence of a long-step interior-point method for nonlinear monotone variational inequality problems. J. Optim. Theory Appl. 97, 471–491 (1998)
  25. Taji, K., Fukushima, M., Ibaraki, T.: A globally convergent newton method for solving strongly monotone variational inequalities. Math. Program., Ser. A 58, 369–383 (1993)
  26. Xiao, B., Harker, P.T.: A nonsmooth newton method for variational inequalities II: numerical results. Math. Program. 65, 195–216 (1994)
  27. Zheng, X., Liu, H.: A smoothing inexact Newton method for variational inequality problems. Int. J. Comput. Math. 88, 1283–1293 (2011)
  28. Zhao, N., Wu, W.: Convergence of a smoothing-type algorithm for the monotone affine variational inequality problem. Appl. Math. Comput. 202, 820–827 (2008)
• 作者单位：1. School of Science, Xi鈥檃n University of Architecture and Technology, Xi鈥檃n, 710055 China2. Department of Mathematics, Xidian University, Xi鈥檃n, 710071 China
• ISSN：1865-2085

文摘

The variational inequality problem can be reformulated as a system of equations. One can solve the reformulated equations to obtain a solution of the original problem. In this paper, based on a symmetric perturbed min function, we propose a new smoothing function, which has some nice properties. By which we propose a new non-interior smoothing algorithm for solving the variational inequality problem, which is based on both the non-interior continuation method and the smoothing Newton method. The proposed algorithm only needs to solve at most one system of equations at each iteration. In particular, we show that the algorithm is globally linearly and locally quadratically convergent under suitable assumptions. The preliminary numerical results are reported.