American Institute of Mathematical Sciences

Advanced
doi: 10.3934/jimo.2021171
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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

Jueyu Wang 1, , Chao Gu 1,, and  Guoqiang Wang 2,

1. 

School of Statistics and Mathematics, Shanghai Lixin University of Accounting and Finance, Shanghai 201209, China
2. 

College of Fundamental Studies, Shanghai University of Engineering Science, Shanghai 201620, China

* Corresponding author: Chao Gu

Received  April 2021 Revised  August 2021 Early access October 2021

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

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.

Keywords: Nonlinear complementarity problem, penalized NCP-function, regular condition, scaling, derivative-free algorithm.
Mathematics Subject Classification: Primary: 90C33, 90C30; Secondary: 65K05.
Citation: Jueyu Wang, Chao Gu, Guoqiang Wang. Penalized NCP-functions for nonlinear complementarity problems and a scaling algorithm. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2021171
References:
[1]

B. Chen, X. Chen and C. Kanzow, A penalized Fischer-Burmeister NCP-function, Math. Programm., 88 (2000), 211-216.  doi: 10.1007/PL00011375.  Google Scholar

[2]

J.-S. Chen, H.-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.  Google Scholar

[3]

J.-S. Chen, Z.-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.  Google Scholar

[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.  Google Scholar

[5]

X. Chi, M. 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.  Google Scholar

[6]

X. Chi, Y. Wang, Z. 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.  Google Scholar

[7]

X. Chi, Z. Wan, Z. Zhu and L. Yuan, A nonmonotone smoothing Newton method for circular cone programming, Optim., 65 (2016), 2227-2250.  doi: 10.1080/02331934.2016.1217861.  Google Scholar

[8]

T. De Luca, F. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

C. Geiger and C. Kanzow, On the resolution of monotone complementarity problems, Comput. Optim. Appl., 5 (1996), 155-173.  doi: 10.1007/BF00249054.  Google Scholar

[12]

L. Grippo, F. 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.  Google Scholar

[13]

C. Gu, D. 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.  Google Scholar

[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.  Google Scholar

[15]

Z. Hao, Z. 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.  Google Scholar

[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.  Google Scholar

[17]

S.-L. Hu, Z.-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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

C.-H. Huang, K.-J. Weng, J.-S. Chen, H.-W. Chu and M.-Y. Li, On four discrete-type families of NCP-functions, J. Nonlinear Convex Anal., 20 (2019), 283-306.   Google Scholar

[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.  Google Scholar

[22]

P.-F. Ma, J.-S. Chen, C.-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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[29]

S. Wang, X. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[33]

J. Zhu, H. Liu, C. 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.  Google Scholar

show all references

References:
[1]

B. Chen, X. Chen and C. Kanzow, A penalized Fischer-Burmeister NCP-function, Math. Programm., 88 (2000), 211-216.  doi: 10.1007/PL00011375.  Google Scholar

[2]

J.-S. Chen, H.-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.  Google Scholar

[3]

J.-S. Chen, Z.-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.  Google Scholar

[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.  Google Scholar

[5]

X. Chi, M. 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.  Google Scholar

[6]

X. Chi, Y. Wang, Z. 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.  Google Scholar

[7]

X. Chi, Z. Wan, Z. Zhu and L. Yuan, A nonmonotone smoothing Newton method for circular cone programming, Optim., 65 (2016), 2227-2250.  doi: 10.1080/02331934.2016.1217861.  Google Scholar

[8]

T. De Luca, F. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

C. Geiger and C. Kanzow, On the resolution of monotone complementarity problems, Comput. Optim. Appl., 5 (1996), 155-173.  doi: 10.1007/BF00249054.  Google Scholar

[12]

L. Grippo, F. 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.  Google Scholar

[13]

C. Gu, D. 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.  Google Scholar

[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.  Google Scholar

[15]

Z. Hao, Z. 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.  Google Scholar

[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.  Google Scholar

[17]

S.-L. Hu, Z.-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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

C.-H. Huang, K.-J. Weng, J.-S. Chen, H.-W. Chu and M.-Y. Li, On four discrete-type families of NCP-functions, J. Nonlinear Convex Anal., 20 (2019), 283-306.   Google Scholar

[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.  Google Scholar

[22]

P.-F. Ma, J.-S. Chen, C.-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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[29]

S. Wang, X. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[33]

J. Zhu, H. Liu, C. 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.  Google Scholar

Figure 1.  Performance profile for bertsekas(1)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Performance profile for colvdual(1)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Performance profile for colvnlp(2)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Performance profile for gafni(1)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Performance profile for kojshin(1)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  Performance profile for sppe(1)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  Performance profile on numbers of iterations
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 8.  Performance profile on numbers of function evaluations
Figure Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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
Table Options

Download as excel

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
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
Table Options

Download as excel

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
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
Table Options

Download as excel

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
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
Table Options

Download as excel

$ 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
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
Table Options

Download as excel

$ 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
[1]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030
[2]

Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050
[3]

Yu-Lin Chang, Jein-Shan Chen, Jia Wu. Proximal point algorithm for nonlinear complementarity problem based on the generalized Fischer-Burmeister merit function. Journal of Industrial & Management Optimization, 2013, 9 (1) : 153-169. doi: 10.3934/jimo.2013.9.153
[4]

Jun Takaki, Nobuo Yamashita. A derivative-free trust-region algorithm for unconstrained optimization with controlled error. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 117-145. doi: 10.3934/naco.2011.1.117
[5]

Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911
[6]

Gaohang Yu. A derivative-free method for solving large-scale nonlinear systems of equations. Journal of Industrial & Management Optimization, 2010, 6 (1) : 149-160. doi: 10.3934/jimo.2010.6.149
[7]

Dong-Hui Li, Xiao-Lin Wang. A modified Fletcher-Reeves-Type derivative-free method for symmetric nonlinear equations. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 71-82. doi: 10.3934/naco.2011.1.71
[8]

Yigui Ou, Wenjie Xu. A unified derivative-free projection method model for large-scale nonlinear equations with convex constraints. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021125
[9]

Jianling Li, Chunting Lu, Youfang Zeng. A smooth QP-free algorithm without a penalty function or a filter for mathematical programs with complementarity constraints. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 115-126. doi: 10.3934/naco.2015.5.115
[10]

A. M. Bagirov, Moumita Ghosh, Dean Webb. A derivative-free method for linearly constrained nonsmooth optimization. Journal of Industrial & Management Optimization, 2006, 2 (3) : 319-338. doi: 10.3934/jimo.2006.2.319
[11]

Liang Zhang, Wenyu Sun, Raimundo J. B. de Sampaio, Jinyun Yuan. A wedge trust region method with self-correcting geometry for derivative-free optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169
[12]

Jiayue Zheng, Shangbin Cui. Bifurcation analysis of a tumor-model free boundary problem with a nonlinear boundary condition. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4397-4410. doi: 10.3934/dcdsb.2020103
[13]

Dorina Mitrea, Marius Mitrea, Sylvie Monniaux. The Poisson problem for the exterior derivative operator with Dirichlet boundary condition in nonsmooth domains. Communications on Pure & Applied Analysis, 2008, 7 (6) : 1295-1333. doi: 10.3934/cpaa.2008.7.1295
[14]

Christina A. Hollon, Jeffrey T. Neugebauer. Positive solutions of a fractional boundary value problem with a fractional derivative boundary condition. Conference Publications, 2015, 2015 (special) : 615-620. doi: 10.3934/proc.2015.0615
[15]

Zheng-Hai Huang, Shang-Wen Xu. Convergence properties of a non-interior-point smoothing algorithm for the P*NCP. Journal of Industrial & Management Optimization, 2007, 3 (3) : 569-584. doi: 10.3934/jimo.2007.3.569
[16]

Hongming Yang, C. Y. Chung, Xiaojiao Tong, Pingping Bing. Research on dynamic equilibrium of power market with complex network constraints based on nonlinear complementarity function. Journal of Industrial & Management Optimization, 2008, 4 (3) : 617-630. doi: 10.3934/jimo.2008.4.617
[17]

Donatella Danielli, Marianne Korten. On the pointwise jump condition at the free boundary in the 1-phase Stefan problem. Communications on Pure & Applied Analysis, 2005, 4 (2) : 357-366. doi: 10.3934/cpaa.2005.4.357
[18]

Haodong Chen, Hongchun Sun, Yiju Wang. A complementarity model and algorithm for direct multi-commodity flow supply chain network equilibrium problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2217-2242. doi: 10.3934/jimo.2020066
[19]

Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585
[20]

R.G. Duran, J.I. Etcheverry, J.D. Rossi. Numerical approximation of a parabolic problem with a nonlinear boundary condition. Discrete & Continuous Dynamical Systems, 1998, 4 (3) : 497-506. doi: 10.3934/dcds.1998.4.497

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (70)
  • HTML views (90)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy