Some results on the filter method for nonlinear complementary problems. (English) Zbl 1504.90159
Summary: Recent studies show that the filter method has good numerical performance for nonlinear complementary problems (NCPs). Their approach is to reformulate an NCP as a constrained optimization solved by filter algorithms. However, they can only prove that the iterative sequence converges to the KKT point of the constrained optimization. In this paper, we investigate the relation between the KKT point of the constrained optimization and the solution of the NCP. First, we give several sufficient conditions under which the KKT point of the constrained optimization is the solution of the NCP; second, we define regular conditions and regular point which include and generalize the previous results; third, we prove that the level sets of the objective function of the constrained optimization are bounded for a strongly monotone function or a uniform \(P\)-function; finally, we present some examples to verify the previous results.
Keywords:
inequality constrained optimization; filter method; nonlinear complementarity problems; KKT point; regular conditionsReferences:
| [1] | Billups, S. C.; Dirkse, P. S.; Ferris, M. C., A comparison of large scale mixed complementarity problem solvers, Comput. Optim. Appl., 7, 3-25 (1997) · Zbl 0883.90116 · doi:10.1023/A:1008632215341 |
| [2] | Chen, B. L.; Ma, C. F., Superlinear/quadratic smoothing Broyden-like method for the generalized nonlinear complementarity problem, Nonlinear Anal., Real World Appl., 12, 1250-1263 (2011) · Zbl 1207.65077 · doi:10.1016/j.nonrwa.2010.09.021 |
| [3] | Chen, J. S., The semismooth-related properties of a merit function and a descent method for the nonlinear complementarity problem, J. Glob. Optim., 36, 565-580 (2006) · Zbl 1144.90493 · doi:10.1007/s10898-006-9027-y |
| [4] | Chen, J. S.; Gao, H. T.; Pan, S. H., An R-linearly convergent derivative-free algorithm for the NCPs based on the generalized Fischer-Burmeister merit function, J. Comput. Appl. Math., 232, 455-471 (2009) · Zbl 1175.65070 · doi:10.1016/j.cam.2009.06.022 |
| [5] | Chen, J. S.; Pan, S. H., A family of NCP functions and a descent method for the nonlinear complementarity problem, Comput. Optim. Appl., 40, 389-404 (2008) · Zbl 1153.90542 · doi:10.1007/s10589-007-9086-0 |
| [6] | Chen, X., Smoothing methods for complementarity problems and their applications: a survey, J. Oper. Res. Soc. Jpn., 43, 32-47 (2000) · Zbl 0998.90078 |
| [7] | Chen, Y.; Sun, W., A dwindling filter line search method for unconstrained optimization, Math. Comput., 84, 187-208 (2015) · Zbl 1307.65085 · doi:10.1090/S0025-5718-2014-02847-0 |
| [8] | Chin, C. M.; Abdul Rashid, A. H.; Nor, K. M., Global and local convergence of a filter line search method for nonlinear programming, Optim. Methods Softw., 22, 365-390 (2007) · Zbl 1193.90192 · doi:10.1080/10556780600565489 |
| [9] | De Luca, T.; Facchinei, F.; Kanzow, C., A semismooth equation approach to the solution of nonlinear complementarity problems, Math. Program., 75, 407-439 (1996) · Zbl 0874.90185 |
| [10] | Dirkse, S. P.; Ferris, M., MCPLIB: a collection of nonlinear mixed complementarity problems, Optim. Methods Softw., 5, 319-345 (1994) · doi:10.1080/10556789508805619 |
| [11] | Facchinei, F.; Soares, J., A new merit function for nonlinear complementarity problems and a related algorithm, SIAM J. Optim., 7, 225-247 (1997) · Zbl 0873.90096 · doi:10.1137/S1052623494279110 |
| [12] | Ferris, M. C.; Pang, J. S., Engineering and economic applications of complementarity problems, SIAM Rev., 39, 669-713 (1997) · Zbl 0891.90158 · doi:10.1137/S0036144595285963 |
| [13] | Fletcher, R.; Leyffer, S., Nonlinear programming without a penalty function, Math. Program., 91, 239-269 (2002) · Zbl 1049.90088 · doi:10.1007/s101070100244 |
| [14] | Geiger, C.; Kanzow, C., On the resolution of monotone complementarity problems, Comput. Optim. Appl., 5, 155-173 (1996) · Zbl 0859.90113 · doi:10.1007/BF00249054 |
| [15] | Gu, C.; Zhu, D., A secant algorithm with line search filter method for nonlinear optimization, Appl. Math. Model., 35, 879-894 (2011) · Zbl 1205.90007 · doi:10.1016/j.apm.2010.07.042 |
| [16] | Gu, C.; Zhu, D., Global convergence of a three-dimensional dwindling filter algorithm without feasibility restoration phase, Numer. Funct. Anal. Optim., 37, 324-341 (2016) · Zbl 1338.90392 · doi:10.1080/01630563.2015.1133643 |
| [17] | Gu, W. Z.; Lu, L. Y., The linear convergence of convergence of a derivative-free descent method for nonlinear complementarity problems, J. Ind. Manag. Optim., 12, 531-548 (2017) · Zbl 1364.90327 |
| [18] | Harker, P. T.; Pang, J. S., Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications, Math. Program., 48, 161-220 (1990) · Zbl 0734.90098 · doi:10.1007/BF01582255 |
| [19] | Hu, S. L.; Huang, Z. H.; Chen, J. S., Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems, J. Comput. Appl. Math., 230, 69-82 (2009) · Zbl 1172.65029 · doi:10.1016/j.cam.2008.10.056 |
| [20] | Huang, C. H.; Weng, K. J.; Chen, J.-S.; Chu, H. W.; Li, M. Y., On four discrete-type families of NCP-functions, J. Nonlinear Convex Anal., 20, 283-306 (2019) · Zbl 1472.90140 |
| [21] | Lai, M. Y.; Nie, P. Y.; Zhang, P. A.; Zhu, S. J., A new SQP approach for nonlinear complementarity problems, Int. J. Comput. Math., 86, 1222-1230 (2009) · Zbl 1171.65046 · doi:10.1080/00207160701798780 |
| [22] | Long, J.; Ma, C. F.; Nie, P. Y., A new filter method for solving nonlinear complementarity problems, Appl. Math. Comput., 185, 705-718 (2007) · Zbl 1113.65062 |
| [23] | Lu, L. Y.; Huang, Z. H.; Hu, S. L., Properties of a family of merit functions and a merit function method for the NCP, Appl. Math. J. Chin. Univ., 25, 379-390 (2010) · Zbl 1240.90443 · doi:10.1007/s11766-010-2179-z |
| [24] | Ma, P. F.; Chen, J.-S.; Huang, C. H.; Ch, K., Discovery of new complementarity functions for NCP and SOCCP, Comput. Appl. Math., 37, 5727-5749 (2018) · Zbl 1438.90358 · doi:10.1007/s40314-018-0660-0 |
| [25] | Mangasarian, O. L.; Solodov, M. V., A linearly convergent derivative-free descent method for strongly monotone complementarity problems, Comput. Optim. Appl., 14, 5-16 (1999) · Zbl 1017.90115 · doi:10.1023/A:1008752626695 |
| [26] | More, J. J., Global methods for nonlinear complementarity problems, Math. Oper. Res., 21, 589-614 (1996) · Zbl 0868.90127 · doi:10.1287/moor.21.3.589 |
| [27] | Nie, P. Y., A filter method for solving nonlinear complementarity problems, Appl. Math. Comput., 167, 677-694 (2005) · Zbl 1082.65062 |
| [28] | Pang, J. S.; Horst, R.; Pardalos, P., Complementarity problems, Handbood of Global Optimization (1995), Boston: Kluwer Academic, Boston · Zbl 0833.90114 |
| [29] | Rui, S. P.; Xu, C. X., A smoothing inexact Newton method for nonlinear complementarity problems, J. Comput. Appl. Math., 233, 2332-2338 (2015) · Zbl 1204.65069 · doi:10.1016/j.cam.2009.10.018 |
| [30] | Su, K., A globally and superlinearly convergent modified SQP-filter method, J. Glob. Optim., 41, 203-217 (2008) · Zbl 1153.90023 · doi:10.1007/s10898-007-9219-0 |
| [31] | Su, K.; Cai, H. P., A modified SQP-filter method for nonlinear complementarity problem, Appl. Math. Model., 33, 2890-2896 (2009) · Zbl 1205.90283 · doi:10.1016/j.apm.2008.10.019 |
| [32] | Su, K.; Yang, D., A smooth Newton method with 3-1 piecewise NCP function for generalized nonlinear complementarity problem, Int. J. Comput. Math., 95, 1703-1713 (2018) · Zbl 1499.90254 · doi:10.1080/00207160.2017.1329531 |
| [33] | Ulbrich, M.; Ulbrich, S.; Vicente, L. N., A globally convergent primal-dual interior-point filter method for nonconvex nonlinear programming, Math. Program., 100, 379-410 (2004) · Zbl 1070.90110 · doi:10.1007/s10107-003-0477-4 |
| [34] | Wächter, A.; Biegler, L. T., Line search filter methods for nonlinear programming: motivation and global convergence, SIAM J. Optim., 6, 1-31 (2005) · Zbl 1114.90128 · doi:10.1137/S1052623403426556 |
| [35] | Wächter, A.; Biegler, L. T., Line search filter methods for nonlinear programming: local convergence, SIAM J. Optim., 6, 32-48 (2005) · Zbl 1115.90056 · doi:10.1137/S1052623403426544 |
| [36] | Wang, H.; Pu, D. G., A kind of nonmonotone filter method for nonlinear complementarity problem, J. Appl. Math. Comput., 36, 27-40 (2011) · Zbl 1220.90140 · doi:10.1007/s12190-010-0386-7 |
| [37] | Yamada, K.; Yamashita, N.; Fukushima, M.; Pillo, G. D.; Giannessi, F., A new derivative-free descent method for the nonlinear complementarity problem, Nonlinear Optimization and Related Topics, 463-489 (2000), Dordrecht: Kluwer Academic, Dordrecht · Zbl 0996.90085 · doi:10.1007/978-1-4757-3226-9_25 |
| [38] | Yang, Y. F.; Qi, L. Q., Smoothing trust region methods for nonlinear complementarity problems with P0-functions, Ann. Oper. Res., 133, 99-117 (2005) · Zbl 1119.90062 · doi:10.1007/s10479-004-5026-x |
| [39] | Zhou, Y., A smoothing conic trust region filter method for the nonlinear complementarity problem, J. Comput. Appl. Math., 229, 248-263 (2009) · Zbl 1167.65037 · doi:10.1016/j.cam.2008.10.057 |
| [40] | Zhu, J. G.; Liu, H. W.; Liu, C. H.; Cong, W. J., A nonmonotone derivative-free algorithm for nonlinear complementarity problems based on the new generalized penalized Fischer-Burmeister merit function, Numer. Algorithms, 58, 573-591 (2011) · Zbl 1279.90173 · doi:10.1007/s11075-011-9471-8 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
