On regularity conditions for complementarity problems

详细信息    查看全文

• 作者：A. F. Izmailov (1)
  A. S. Kurennoy (1)
  
• 关键词：Mixed complementarity problem ; Nonlinear complementarity problem ; KKT system ; Natural residual function ; Fischer ; Burmeister function ; BD ; regularity ; CD ; regularity ; Strong regularity ; Semistability ; b ; regularity ; Quasi ; regularity
• 刊名：Computational Optimization and Applications
• 出版年：2014
• 出版时间：April 2014
• 年：2014
• 卷：57
• 期：3
• 页码：667-684
• 全文大小：637 KB
• 参考文献：1. Billups, S.C.: Algorithms for complementarity problems and generalized equations. Technical Report 95-14, Computer Sciences Department, University of Wisconsin, Madison (August 1995). Ph.D. thesis
  2. Bonnans, J.F.: Local analysis of Newton-type methods for variational inequalities and nonlinear programming. Appl. Math. Optim. 29, 161-86 (1994) CrossRef
  3. Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)
  4. Daryina, A.N., Izmailov, A.F., Solodov, M.V.: A class of active-set Newton methods for mixed complementarity problems. SIAM J. Optim. 15, 409-29 (2004) CrossRef
  5. Daryina, A.N., Izmailov, A.F., Solodov, M.V.: Mixed complementary problems: regularity, estimates of the distance to the solution, and Newton’s methods. Comput. Math. Math. Phys. 44, 45-1 (2004)
  6. Dontchev, A.L., Rockafellar, R.T.: Implicit Functions and Solution Mappings. Springer, New York (2009) CrossRef
  7. 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-0. SIAM, Philadelphia (1997)
  8. Facchinei, F., Fischer, A., Kanzow, C.: On the accurate identification of active constraints. SIAM J. Optim. 9, 14-2 (1999) CrossRef
  9. Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)
  10. Ferris, M.C., Kanzow, C., Munson, T.S.: Feasible descent algorithms for mixed complementarity problems. Math. Program. 86, 475-97 (1999) CrossRef
  11. Ferris, M.C., Pang, J.-S.: Engineering and economic applications of complementarity problems. SIAM Rev. 39, 669-13 (1997) CrossRef
  12. Harker, P.T., Pang, J.-S.: Finite-dimensional variational inequality problems: a survey of theory, algorithms and applications. Math. Program. 48, 161-20 (1990) CrossRef
  13. Izmailov, A.F., Solodov, M.V.: Karush-Kuhn-Tucker systems: regularity conditions, error bounds and a class of Newton-type methods. Math. Program. 95, 631-50 (2003) CrossRef
  14. Josephy, N.H.: Newton’s method for generalized equations. Technical Summary Report no.?1965, Mathematics Research Center, University of Wisconsin, Madison (1979)
  15. Kanzow, C., Fukishima, M.: Solving box constrained variational inequalities by using the natural residual with D-gap function globalization. Oper. Res. Lett. 23, 45-1 (1998) CrossRef
  16. Kanzow, C., Kleinmichel, H.: A new class of semismooth Newton-type methods for nonlinear complementarity problems. Comput. Optim. Appl. 11, 227-51 (1998) CrossRef
  17. Kummer, B.: Newton’s method for nondifferentiable functions. In: Guddat, J., Bank, B., Hollatz, H., Kall, P., Klatte, D., Kummer, B., Lommalzsch, K., Tammer, L., Vlach, M., Zimmerman, K. (eds.) Advances in Mathematical Optimization, vol. 45, pp. 114-25. Akademie-Verlag, Berlin (1988)
  18. Kummer, B.: Newton’s method based on generalized derivatives for nonsmooth functions. In: Oettli, W., Pallaschke, D. (eds.) Advances in Optimization, pp. 171-94. Springer, Berlin (1992) CrossRef
  19. De Luca, T., Facchinei, F., Kanzow, C.: A theoretical and numerical comparison of some semismooth algorithms for complementarity problems. Comput. Optim. Appl. 16, 173-05 (2000) CrossRef
  20. Ouellette, D.V.: Schur complements and statistics. Linear Algebra Appl. 36, 187-95 (1981) CrossRef
  21. Pang, J.-S., Gabriel, S.A.: NE/SQP: a robust algorithm for the nonlinear complementarity problem. Math. Program. 60, 295-38 (1993) CrossRef
  22. Pourciau, B.H.: Analysis and optimization of Lipschitz continuous mappings. Engineering and economic applications of complementarity problems. JOTA 22, 311-51 (1977) CrossRef
  23. Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227-44 (1993) CrossRef
  24. Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353-67 (1993) CrossRef
  25. Robinson, S.M.: Strongly regular generalized equations. Math. Oper. Res. 5, 43-2 (1980) CrossRef
  
• 作者单位：A. F. Izmailov (1)
  A. S. Kurennoy (1)
  
  1. VMK Faculty, OR Department, Moscow State University, MSU, Uchebniy Korpus 2, Leninskiye Gory, 119991, Moscow, Russia
  
• ISSN：1573-2894

文摘

In the context of complementarity problems, various concepts of solution regularity are known, each of them playing a certain role in the related theoretical and algorithmic developments. Despite the existence of rich literature on this subject, it appears that the exact relations between some of these regularity concepts remained unknown. In this note, we not only summarize the existing results on the subject but also establish the missing relations filling all the gaps in the current understanding of how different regularity concepts relate to each other. In particular, we demonstrate that strong regularity is in fact equivalent to nonsingularity of all matrices in the natural outer estimates of the generalized Jacobians of the most widely used residual mappings for complementarity problems. On the other hand, we show that CD-regularity of the natural residual mapping does not imply even BD-regularity of the Fischer–Burmeister residual mapping. As a result, we provide the complete picture of relations between the most important regularity conditions for mixed complementarity problems, with a special emphasis on those conditions used to justify the related numerical methods. A special attention is paid to the particular cases of a nonlinear complementarity problem and of a Karush–Kuhn–Tucker system.