\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Penalized NCP-functions for nonlinear complementarity problems and a scaling algorithm

  • * Corresponding author: Chao Gu

    * Corresponding author: Chao Gu 

This work is supported by National Natural Science Foundation of China grant 11971302

Abstract Full Text(HTML) Figure(10) / Table(5) Related Papers Cited by
  • In this paper, we systematically study the properties of penalized NCP-functions in derivative-free algorithms for nonlinear complementarity problems (NCPs), and give some regular conditions for stationary points of penalized NCP-functions to be solutions of NCPs. The main contribution is to unify and generalize previous results. Based on one of above penalized NCP-functions, we analyze a scaling algorithm for NCPs. The numerical results show that the scaling can greatly improve the effectiveness of the algorithm.

    Mathematics Subject Classification: Primary: 90C33, 90C30; Secondary: 65K05.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Performance profile for bertsekas(1)

    Figure 2.  Performance profile for colvdual(1)

    Figure 3.  Performance profile for colvnlp(2)

    Figure 4.  Performance profile for gafni(1)

    Figure 5.  Performance profile for kojshin(1)

    Figure 6.  Performance profile for sppe(1)

    Figure 7.  Performance profile on numbers of iterations

    Figure 8.  Performance profile on numbers of function evaluations

    Figure 9.  Performance profile on NIT (monotone vs. nonmonotone)

    Figure 10.  Performance profile on NF (monotone vs. nonmonotone)

    Table 1.  Algorithm 1 with $p = 1.1$

    Algorithm 1 ($\delta = 1$)Algorithm 1 ($\delta = \delta^{*}$)
    ProblemNITNF$\Psi_{\alpha, \theta, p}$NITNF$\Psi_{\alpha, \theta, p}$$\delta^{*}$
    bertsekas(1)8266243672.3812e-00912160121704.9639e-00727
    bertsekas(2)7891203369.9677e-00711695117029.1309e-00726
    bertsekas(3)-------
    colvdual(1)---17306553495.5376e-00914
    colvdual(2)-------
    colvnlp(1)-------
    colvnlp(2)---457771545.6383e-00930
    cycle10113.0849e-00910113.0849e-0091
    explcp75901.4837e-00775901.4837e-0071
    gafni(1)345691219759.1296e-0081121577.5602e-00715
    gafni(2)474041679781.0529e-007731024.0892e-0078
    gafni(3)519911843611.0342e-0071181655.0671e-00712
    hanskoop(1)-------
    hanskoop(2)-------
    hanskoop(3)---5555569.9791e-00718
    hanskoop(4)-------
    josephy(1)971761.3794e-00780825.2841e-0073
    josephy(2)2664438.8353e-00859623.7396e-0082
    josephy(3)154130812.4551e-0082904666.2118e-0075
    josephy(4)78915801.3789e-00832353.1777e-0072
    josephy(5)2534268.8353e-00829313.4038e-0073
    josephy(6)124124842.4521e-00873909.4225e-0072
    kojshin(1)112522502.6963e-00864741.8273e-0092
    kojshin(2)-------
    kojshin(3)---3635843.0811e-0077
    kojshin(4)1933312.5809e-00851541.8472e-0092
    kojshin(5)101220262.6726e-0081011034.1455e-0074
    kojshin(6)2154317.5751e-01049512.7706e-0087
    mathinum(1)-------
    mathinum(2)1221302.1945e-0081221302.1945e-0081
    mathinum(3)---5576003.3811e-0088
    mathinum(4)-------
    mathisum(1)87217161.1988e-0073794046.0656e-0075
    mathisum(2)2665124.1344e-0073394009.4181e-0074
    mathisum(3)---3033887.7901e-0073
    mathisum(4)---3403867.6970e-0074
    nash(1)1303465.8724e-00752627.3456e-00716
    nash(2)50000024267819.4354e-00457649.9217e-00716
    sppe(1)264631228549.7144e-007249125918.6671e-00722
    sppe(2)238321059014.9202e-007243125289.3475e-00722
    tobin(1)151033936.8669e-0074844912.8497e-00910
    tobin(2)183641267.5978e-0075435496.4011e-00810
     | Show Table
    DownLoad: CSV

    Table 2.  Algorithm 1 with $p = 1.5$

    Algorithm 1 ($\delta = 1$)Algorithm 1 ($\delta = \delta^{*}$)
    ProblemNITNF$\Psi_{\alpha, \theta, p}$NITNF$\Psi_{\alpha, \theta, p}$$\delta^{*}$
    bertsekas(1)26767893473.5032e-00720934307296.1796e-01116
    bertsekas(2)25115833553.5032e-00720864306476.1708e-01116
    bertsekas(3)-------
    colvdual(1)---21590674803.3568e-00910
    colvdual(2)-------
    colvnlp(1)-------
    colvnlp(2)---347477163.3348e-0099
    cycle891.1847e-009453.1656e-0102
    explcp26462.5022e-00712143.0423e-0073
    gafni(1)25223927842.0520e-00851843.2553e-00727
    gafni(2)297721089233.7445e-00859983.0945e-00727
    gafni(3)24233877736.3577e-00738637.9123e-00730
    hanskoop(1)-------
    hanskoop(2)37910226.4234e-0071392535.7983e-0072
    hanskoop(3)21231.5259e-00721231.5259e-0071
    hanskoop(4)23321.8634e-00724256.3337e-0082
    josephy(1)3597203.9772e-00813159.7292e-0076
    josephy(2)4208413.4525e-00823248.8124e-0076
    josephy(3)76414682.2183e-0073285909.5774e-00730
    josephy(4)4237732.2183e-00726281.5330e-0075
    josephy(5)4087482.2183e-00714169.7662e-0076
    josephy(6)4208423.4825e-00819211.0946e-0078
    kojshin(1)3507022.7028e-00785876.1427e-0086
    kojshin(2)-------
    kojshin(3)70814122.6187e-0073706449.5223e-00726
    kojshin(4)2784705.2362e-00844496.1203e-0085
    kojshin(5)3226462.6572e-0071121135.9773e-00811
    kojshin(6)42812.2097e-00712152.5547e-0075
    mathinum(1)1732929.5496e-00762784.9068e-0073
    mathinum(2)921298.1284e-00750651.1306e-0073
    mathinum(3)---60845.1237e-0072
    mathinum(4)---991073.3206e-0074
    mathisum(1)---1401956.6254e-0084
    mathisum(2)---1782677.5195e-0083
    mathisum(3)---2342527.1548e-0089
    mathisum(4)---1752206.6787e-0084
    nash(1)32410213.0684e-0071211721.7734e-00815
    nash(2)43270217962314.9703e-0111391927.6530e-00719
    sppe(1)7514287622.4311e-008215525824.0753e-00927
    sppe(2)7532282547.6481e-009211025513.2455e-00928
    tobin(1)1382965.3730e-007911002.0161e-0095
    tobin(2)3807869.9524e-00778884.8676e-0085
     | Show Table
    DownLoad: CSV

    Table 3.  Algorithm 1 with p = 5

    Algorithm 1 ($\delta = 1$)Algorithm 1 ($\delta = \delta^{*}$)
    ProblemNITNF$\Psi_{\alpha, \theta, p}$NITNF$\Psi_{\alpha, \theta, p}$$\delta^{*}$
    bertsekas(1)-------
    bertsekas(2)-------
    bertsekas(3)---138420991.4364e-00922
    colvdual(1)---22642709803.3306e-00910
    colvdual(2)---33701943133.3442e-00930
    colvnlp(1)---212839417.9056e-00929
    colvnlp(2)---383186853.7521e-00910
    cycle455.2542e-019455.2542e-0191
    explcp38742.0424e-00811142.0714e-0072
    gafni(1)19223677552.0788e-0081302499.9662e-00730
    gafni(2)21722768903.5635e-008992246.5953e-00711
    gafni(3)20366724893.5055e-0083416831.0469e-00719
    hanskoop(1)26432.3821e-01027333.7916e-0074
    hanskoop(2)751277.0665e-01023248.5594e-0094
    hanskoop(3)575.3588e-007575.3588e-0071
    hanskoop(4)47882.2551e-01211121.6245e-0134
    josephy(1)30612.8350e-0078102.8479e-00711
    josephy(2)3657312.7223e-00817195.2938e-0076
    josephy(3)32662.8351e-00710142.8479e-00711
    josephy(4)3216442.4569e-00818197.2910e-0076
    josephy(5)24512.3684e-00716189.2798e-0076
    josephy(6)531061.8162e-00717196.1620e-0076
    kojshin(1)2925863.1499e-00767695.3961e-0087
    kojshin(2)3116233.0988e-00757684.6426e-0085
    kojshin(3)2945913.1499e-00754634.7443e-0085
    kojshin(4)---46505.1553e-0085
    kojshin(5)---1191206.1836e-00813
    kojshin(6)531023.3305e-00843456.5165e-0085
    mathinum(1)751258.7344e-00742531.6740e-0073
    mathinum(2)40559.0882e-00747482.6675e-0075
    mathinum(3)851411.0574e-00740419.8855e-0076
    mathinum(4)771192.0889e-00747584.0341e-0073
    mathisum(1)------
    mathisum(2)---4245787.2195e-00814
    mathisum(3)---5807367.1810e-00821
    mathisum(4)-------
    nash(1)1494705.1348e-0071392184.0121e-00913
    nash(2)24481.6145e-00717321.1904e-0162
    sppe(1)10560437061.5941e-008225226062.5723e-00929
    sppe(2)7731290141.4354e-008212124593.1054e-00929
    tobin(1)3437011.8828e-0071091121.2528e-0096
    tobin(2)3436959.9819e-00796981.0439e-0078
     | Show Table
    DownLoad: CSV

    Table 4.  Algorithm 1 with monotone line search

    $ p=1.1 $ $ p=1.5 $ $ p=5 $
    Problem NIT NF NIT NF NIT NF
    bertsekas(1) 12125 41027 21659 74329 - -
    bertsekas(2) - - 22409 78381 - -
    bertsekas(3) - - - - - -
    colvdual(1) - - - - - -
    colvdual(2) - - - - - -
    colvnlp(1) - - - - - -
    colvnlp(2) - - - - - -
    cycle 10 11 8 9 4 5
    explcp 80 100 27 48 39 76
    gafni(1) 304691 1207169 24788 89141 25304 91005
    gafni(2) 144756 557579 25562 91844 25020 89860
    gafni(3) 269424 1058494 26240 94133 25002 89336
    hanskoop(1) - - - - - -
    hanskoop(2) - - - - - -
    hanskoop(3) - - - - 5 7
    hanskoop(4) - - - - 16 27
    josephy(1) 111 197 376 751 - -
    josephy(2) 1082 2160 420 841 365 731
    josephy(3) 1602 3204 446 891 - -
    josephy(4) 29 49 98 194 374 749
    josephy(5) 20 33 30 59 26 54
    josephy(6) 1241 2484 420 842 51 102
    kojshin(1) - - 476 953 24 46
    kojshin(2) - - - - - -
    kojshin(3) - - - - - -
    kojshin(4) 22 31 35 68 18 35
    kojshin(5) 1010 2020 288 577 274 550
    kojshin(6) - - 46 91 48 96
    mathinum(1) - - 158 358 81 176
    mathinum(2) - - 116 236 88 230
    mathinum(3) - - - - 122 323
    mathinum(4) - - - - 101 237
    mathisum(1) - - - - - -
    mathisum(2) - - - - - -
    mathisum(3) 1372 2701 - - - -
    mathisum(4) - - - - - -
    nash(1) 500000 2560023 250 502 73 149
    nash(2) 500000 2678901 432702 1796231 24 48
    sppe(1) 7828 26193 6076 22833 5156 18401
    sppe(2) 7887 26310 7178 27719 5081 18251
    tobin(1) 2166 4875 395 801 461 930
    tobin(2) 2524 5702 477 972 493 993
     | Show Table
    DownLoad: CSV

    Table 5.  Algorithm 1 with nonmonotone line search (p = 5)

    $ M=5, s=1 $ $ M=5, s=5 $ $ M=10, s=1 $ $ M=10, s=5 $
    Problem NIT NF NIT NF NIT NF NIT NF
    bertsekas(1) - - - - - - - -
    bertsekas(2) - - - - 26236 90444 20236 90444
    bertsekas(3) - - - - - - - -
    colvdual(1) - - - - - - - -
    colvdual(2) - - - - - - - -
    colvnlp(1) - - - - - - - -
    colvnlp(2) - - - - - - - -
    cycle 4 5 4 5 4 5 4 5
    explcp 38 74 38 74 38 74 38 74
    gafni(1) - - 19223 67755 7250 25114 4346 15115
    gafni(2) 21722 76890 21722 76890 28597 104363 28597 104363
    gafni(3) 20366 72489 20366 72489 27454 100831 27454 100831
    hanskoop(1) - - 26 43 161 287 171 434
    hanskoop(2) - - 75 127 175 341 - -
    hanskoop(3) 13 16 5 7 11 12 5 7
    hanskoop(4) 17 24 47 88 - - 46 86
    josephy(1) 67 124 30 61 - - 435 819
    josephy(2) 365 731 365 731 365 731 365 731
    josephy(3) 167 295 32 66 990 1820 523 985
    josephy(4) 36 71 321 644 872 1629 321 644
    josephy(5) 45 87 24 51 1058 2009 651 1225
    josephy(6) 53 106 53 106 513 967 513 967
    kojshin(1) 67 126 292 586 959 1647 292 586
    kojshin(2) 311 623 311 623 311 623 311 623
    kojshin(3) 138 237 294 591 1227 2091 294 591
    kojshin(4) 69 122 - - 913 1552 - -
    kojshin(5) 75 135 - - 936 1594 - -
    kojshin(6) 106 202 53 102 932 1604 913 1557
    mathinum(1) 69 111 75 125 76 119 123 192
    mathinum(2) 77 110 40 55 106 154 40 55
    mathinum(3) 116 199 85 141 259 457 128 203
    mathinum(4) 86 134 77 119 203 340 94 142
    mathisum(1) - - - - - - - -
    mathisum(2) - - - - - - - -
    mathisum(3) - - - - - - - -
    mathisum(4) - - - - - - - -
    nash(1) - - 149 470 - - 1163 3868
    nash(2) 24 48 24 48 71 150 24 48
    sppe(1) 9429 38110 10560 43706 28627 140093 27303 130659
    sppe(2) 7822 28858 7731 29014 29515 144976 26991 129993
    tobin(1) 377 771 343 701 355 728 330 667
    tobin(2) 147 297 343 695 417 871 350 704
     | Show Table
    DownLoad: CSV
  • [1] B. ChenX. Chen and C. Kanzow, A penalized Fischer-Burmeister NCP-function, Math. Programm., 88 (2000), 211-216.  doi: 10.1007/PL00011375.
    [2] J.-S. ChenH.-T. Gao and S. Pan, An $R$-linearly convergent derivative-free algorithm for the NCPs based on the generalized Fischer-Burmeister merit function, J. Comput. Appl. Math., 232 (2009), 455-471.  doi: 10.1016/j.cam.2009.06.022.
    [3] J.-S. ChenZ.-H. Huang and C.-Y. She, A new class of penalized NCP-functions and its properties, Comput. Optim. Appl., 50 (2001), 49-73.  doi: 10.1007/s10589-009-9315-9.
    [4] J.-S. Chen and S. Pan, A family of NCP functions and a descent method for the nonlinear complementarity problem, Comput. Optim. Appl., 40 (2008), 389-404.  doi: 10.1007/s10589-007-9086-0.
    [5] X. ChiM. Gowda and J. Tao, The weighted horizontal linear complementarity problem on a Euclidean Jordan algebra, J. Glob. Optim., 73 (2019), 153-169.  doi: 10.1007/s10898-018-0689-z.
    [6] X. ChiY. WangZ. Zhu and Z. Wan, Jacobian consistency of a one-parametric class of smoothing Fischer-Burmeister functions for SOCCP, Comput. Appl. Math., 37 (2018), 439-455.  doi: 10.1007/s40314-016-0352-6.
    [7] X. ChiZ. WanZ. Zhu and L. Yuan, A nonmonotone smoothing Newton method for circular cone programming, Optim., 65 (2016), 2227-2250.  doi: 10.1080/02331934.2016.1217861.
    [8] T. De LucaF. Facchinei and C. Kanzow, A semismooth equation approach to the solution of nonlinear complementarity problems, Math. Programm., 75 (1996), 407-439.  doi: 10.1007/BF02592192.
    [9] S. P. Dirkse and M. Ferris, MCPLIB: A collection of nonlinear mixed complementarity problems, Optim. Methods Softw., 5 (1995), 319-345.  doi: 10.1080/10556789508805619.
    [10] M. C. Ferris and J. S. Pang, Engineering and economic applications of complementarity problems, SIAM Rev., 39 (1997), 669-713.  doi: 10.1137/S0036144595285963.
    [11] C. Geiger and C. Kanzow, On the resolution of monotone complementarity problems, Comput. Optim. Appl., 5 (1996), 155-173.  doi: 10.1007/BF00249054.
    [12] L. GrippoF. Lampariello and S. Ludidi, A nonmonotone line search technique for Newton's method, SIAM J. Numer. Anal., 23 (1986), 707-716.  doi: 10.1137/0723046.
    [13] C. GuD. Zhu and Y. Pei, A new inexact SQP algorithm for nonlinear systems of mixed equalities and inequalities, Numer. Algor., 78 (2018), 1233-1253.  doi: 10.1007/s11075-017-0421-y.
    [14] W.-Z. Gu and L.-Y. Lu, The linear convergence of a derivative-free descent method for nonlinear complementarity problems, J. Indust. Manag. Optim., 13 (2017), 531-548.  doi: 10.3934/jimo.2016030.
    [15] Z. HaoZ. Wan and X. Chi, A power penalty method for second-order cone nonlinear complementarity problems, J. Comput. Appl. Math., 290 (2015), 136-149.  doi: 10.1016/j.cam.2015.05.007.
    [16] P. T. Harker and J.-S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications, Math. Programm., 48 (1990), 161-220.  doi: 10.1007/BF01582255.
    [17] S.-L. HuZ.-H. Huang and J.-S. Chen, Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems, J. Comput. Appl. Math., 230 (2009), 69-82.  doi: 10.1016/j.cam.2008.10.056.
    [18] C. Huang and S. Wang, A penalty method for a mixed nonlinear complementarity problem, Nonlinear Anal. Theory Methods Appl., 75 (2012), 588-597.  doi: 10.1016/j.na.2011.08.061.
    [19] C. Huang and S. Wang, A power penalty approach to a nonlinear complementarity problem, Oper. Res. Lett., 38 (2010), 72-76.  doi: 10.1016/j.orl.2009.09.009.
    [20] C.-H. HuangK.-J. WengJ.-S. ChenH.-W. Chu and M.-Y. Li, On four discrete-type families of NCP-functions, J. Nonlinear Convex Anal., 20 (2019), 283-306. 
    [21] C. Kanzow and H. Kleinmichel, A new class of semismooth Newton-type methods for nonlinear complementarity problems, Comput. Optim. Appl., 11 (1998), 227-251.  doi: 10.1023/A:1026424918464.
    [22] P.-F. MaJ.-S. ChenC.-H. Huang and C.-H. Ko, Discovery of new complementarity functions for NCP and SOCCP, Comput. Appl. Math., 37 (2018), 5727-5749.  doi: 10.1007/s40314-018-0660-0.
    [23] J.-S. Pang, Complementarity problems, Handbook of Global Optimization, 271–338, Nonconvex Optim. Appl., 2, Kluwer Acad. Publ., Dordrecht, (1995). doi: 10.1007/978-1-4615-2025-2_6.
    [24] J. M. Peng, Derivative-free methods for monotone variational inequality and complementarity problems, J. Optim. Theory Appl., 99 (1998), 235-252.  doi: 10.1023/A:1021712513685.
    [25] K. Su and D. Yang, A smooth Newton method with 3-1 piecewise NCP function for generalized nonlinear complementarity problem, Int. J. Comput. Math., 95 (2018), 1703-1713.  doi: 10.1080/00207160.2017.1329531.
    [26] S. Wang and C.-S. Huang, A power penalty method for solving a nonlinear parabolic complementarity problem, Nonlinear Anal. Theory Methods Appl., 69 (2008), 1125-1137.  doi: 10.1016/j.na.2007.06.014.
    [27] S. Wang and X. Yang, A power penalty method for a bounded nonlinear complementarity problem, Optim., 64 (2015), 2377-2394.  doi: 10.1080/02331934.2014.967236.
    [28] S. Wang and X. Yang, A power penalty method for linear complementarity problems, Oper. Res. Lett., 36 (2008), 211-214.  doi: 10.1016/j.orl.2007.06.006.
    [29] S. WangX. Q. Yang and K. L. Teo, Power penalty method for a linear complementarity problem arising from American option valuation, J. Optim. Theory Appl., 129 (2006), 227-254.  doi: 10.1007/s10957-006-9062-3.
    [30] S. Wang and K. Zhang, An interior penalty method for a finite-dimensional linear complementarity problem in financial engineering, Optim. Lett., 12 (2018), 1161-1178.  doi: 10.1007/s11590-016-1050-4.
    [31] K. Yamada, N. Yamashita and M. Fukushima, A new derivative-free descent method for the nonlinear complementarity problems, in: G.D. Pillo, F. Giannessi (Eds.), Nonlinear Optimization and Related Topics, Kluwer Academic Publishers, Netherlands, (2000), 463–487. doi: 10.1007/978-1-4757-3226-9_25.
    [32] K. Zhang and S. Wang, Convergence property of an interior penalty approach to pricing American option, J. Indust. Manag. Optim., 7 (2011), 435-447.  doi: 10.3934/jimo.2011.7.435.
    [33] J. ZhuH. LiuC. Liu and W. Cong, A nonmonotone derivative-free algorithmfor nonlinear complementarity problems based on the new generalized penalized Fischer-Burmeister merit function, Numer. Algor., 58 (2011), 573-591.  doi: 10.1007/s11075-011-9471-8.
  • 加载中

Figures(10)

Tables(5)

SHARE

Article Metrics

HTML views(659) PDF downloads(474) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return