
-
Previous Article
Compensation plan, pricing and production decisions with inventory-dependent salvage value, and asymmetric risk-averse sales agent
- JIMO Home
- This Issue
-
Next Article
Disaster relief routing in limited capacity road networks with heterogeneous flows
A power penalty method for a class of linearly constrained variational inequality
1. | School of Applied Mathematics, Xiamen University of Technology, Xiamen 361024, China |
2. | School of Mathematics and Statistics, Wuhan University, Wuhan 430072, China |
This paper establishes new convergence results for the power pena-lty method for a mixed complementarity problem(MiCP). The power penalty method approximates the MiCP by a nonlinear equation containing a power penalty term. The main merit of the method is that it has an exponential convergence rate with the penalty parameter when the involved function is continuous and ξ-monotone. Under the same assumptions, we establish a new upper bound for the approximation error of the solution to the nonlinear equation. We also prove that the penalty method can handle general monotone MiCPs. Then the method is used to solve a class of linearly constrained variational inequality(VI). Since the MiCP associated with a linearly constrained VI does not ξ-monotone even if the VI is ξ-monotone, we establish the new convergence result for this MiCP. We use the method to solve the asymmetric traffic assignment problem which can be reformulated as a class of linearly constrained VI. Numerical results are provided to demonstrate the efficiency of the method.
References:
[1] |
M. Chen and C. C. Huang,
A power penalty method for the general traffic assignment problem with elastic demand, Journal of Industrial and Management Optimization, 10 (2014), 1019-1030.
doi: 10.3934/jimo.2014.10.1019. |
[2] |
F. Facchinei and J. S. Pang,
Finite-Dimensional Variational Inequalities and Complementarity Problems Springer-Verlag, New York, 2003.
doi: 10.1007/b97543. |
[3] |
B. S. He and L. Z. Liao,
Improvements of some projection methods for monotone nonlinear variational inequalities, Journal of Optimization Theory & Applications, 112 (2002), 111-128.
doi: 10.1023/A:1013096613105. |
[4] |
C. C. Huang and S. Wang,
A power penalty approach to a nonlinear complementarity problem, Operations Research Letters, 38 (2010), 72-76.
doi: 10.1016/j.orl.2009.09.009. |
[5] |
C. C. Huang and S. Wang,
A penalty method for a mixed nonlinear complementarity problem, Nonlinear Analysis: Theory, Methods & Applications, 75 (2012), 588-597.
doi: 10.1016/j.na.2011.08.061. |
[6] |
S. Lawphongpanich and D. Hearn,
Simplical decomposition of the asymmetric traffic assignment problem, Transportation Research Part B: Methodological, 18 (1984), 123-133.
doi: 10.1016/0191-2615(84)90026-2. |
[7] |
T. D. Luca, F. Facchinei and C. Kanzow,
A semismooth equation approach to the solution of nonlinear complementarity problems, Mathematical Programming, 75 (1996), 407-439.
doi: 10.1007/BF02592192. |
[8] |
B. Panicucci, M. Pappalardo and M. Passacantando,
A path-based double projection method for solving the asymmetric traffic network equilibrium problem, Optimization Letters, 1 (2007), 171-185.
doi: 10.1007/s11590-006-0002-9. |
[9] |
P. Patriksson, The Traffic Assignment Problem: Models and Methods VSP, Utrecht, 1994. Google Scholar |
[10] |
M. V. Solodov and B. F. Svaiter,
A new projection method for variational inequality problems, SIAM Journal on Control & Optimization, 37 (1999), 765-776.
doi: 10.1137/S0363012997317475. |
[11] |
K. Taji, M. Fukushima and T. Ibaraki,
A globally convergent newton method for solving strongly monotone variational inequalities, Mathematical Programming, 58 (1993), 369-383.
doi: 10.1007/BF01581276. |
[12] |
S. Wang,
A penalty method for a finite-dimensional obstacle problem with derivative constraints, Optimization Letters, 8 (2014), 1799-1811.
doi: 10.1007/s11590-013-0651-4. |
[13] |
S. Wang,
A penalty approach to a discretized double obstacle problem with derivative constraints, Journal of Global Optimization, 62 (2015), 775-790.
doi: 10.1007/s10898-014-0262-3. |
[14] |
S. Wang and C. S. Huang,
A power penalty method for solving a nonlinear parabolic complementarity problem, Nonlinear Analysis: Theory, Methods & Applications, 69 (2008), 1125-1137.
doi: 10.1016/j.na.2007.06.014. |
[15] |
S. Wang and X. Q. Yang,
A power penalty method for a bounded nonlinear complementarity problem, Optimization: A Journal of Mathematical Programming and Operations Research, 64 (2015), 2377-2394.
doi: 10.1080/02331934.2014.967236. |
[16] |
S. Wang and X. Q. Yang,
A power penalty method for linear complementarity problems, Operations Research Letters, 36 (2008), 211-214.
doi: 10.1016/j.orl.2007.06.006. |
[17] |
S. Wang, X. Q. Yang and K. L. Teo,
Power penalty method for a linear complementarity problem arising from American option valuation, Journal of Optimization Theory & Applications, 129 (2006), 227-254.
doi: 10.1007/s10957-006-9062-3. |
show all references
References:
[1] |
M. Chen and C. C. Huang,
A power penalty method for the general traffic assignment problem with elastic demand, Journal of Industrial and Management Optimization, 10 (2014), 1019-1030.
doi: 10.3934/jimo.2014.10.1019. |
[2] |
F. Facchinei and J. S. Pang,
Finite-Dimensional Variational Inequalities and Complementarity Problems Springer-Verlag, New York, 2003.
doi: 10.1007/b97543. |
[3] |
B. S. He and L. Z. Liao,
Improvements of some projection methods for monotone nonlinear variational inequalities, Journal of Optimization Theory & Applications, 112 (2002), 111-128.
doi: 10.1023/A:1013096613105. |
[4] |
C. C. Huang and S. Wang,
A power penalty approach to a nonlinear complementarity problem, Operations Research Letters, 38 (2010), 72-76.
doi: 10.1016/j.orl.2009.09.009. |
[5] |
C. C. Huang and S. Wang,
A penalty method for a mixed nonlinear complementarity problem, Nonlinear Analysis: Theory, Methods & Applications, 75 (2012), 588-597.
doi: 10.1016/j.na.2011.08.061. |
[6] |
S. Lawphongpanich and D. Hearn,
Simplical decomposition of the asymmetric traffic assignment problem, Transportation Research Part B: Methodological, 18 (1984), 123-133.
doi: 10.1016/0191-2615(84)90026-2. |
[7] |
T. D. Luca, F. Facchinei and C. Kanzow,
A semismooth equation approach to the solution of nonlinear complementarity problems, Mathematical Programming, 75 (1996), 407-439.
doi: 10.1007/BF02592192. |
[8] |
B. Panicucci, M. Pappalardo and M. Passacantando,
A path-based double projection method for solving the asymmetric traffic network equilibrium problem, Optimization Letters, 1 (2007), 171-185.
doi: 10.1007/s11590-006-0002-9. |
[9] |
P. Patriksson, The Traffic Assignment Problem: Models and Methods VSP, Utrecht, 1994. Google Scholar |
[10] |
M. V. Solodov and B. F. Svaiter,
A new projection method for variational inequality problems, SIAM Journal on Control & Optimization, 37 (1999), 765-776.
doi: 10.1137/S0363012997317475. |
[11] |
K. Taji, M. Fukushima and T. Ibaraki,
A globally convergent newton method for solving strongly monotone variational inequalities, Mathematical Programming, 58 (1993), 369-383.
doi: 10.1007/BF01581276. |
[12] |
S. Wang,
A penalty method for a finite-dimensional obstacle problem with derivative constraints, Optimization Letters, 8 (2014), 1799-1811.
doi: 10.1007/s11590-013-0651-4. |
[13] |
S. Wang,
A penalty approach to a discretized double obstacle problem with derivative constraints, Journal of Global Optimization, 62 (2015), 775-790.
doi: 10.1007/s10898-014-0262-3. |
[14] |
S. Wang and C. S. Huang,
A power penalty method for solving a nonlinear parabolic complementarity problem, Nonlinear Analysis: Theory, Methods & Applications, 69 (2008), 1125-1137.
doi: 10.1016/j.na.2007.06.014. |
[15] |
S. Wang and X. Q. Yang,
A power penalty method for a bounded nonlinear complementarity problem, Optimization: A Journal of Mathematical Programming and Operations Research, 64 (2015), 2377-2394.
doi: 10.1080/02331934.2014.967236. |
[16] |
S. Wang and X. Q. Yang,
A power penalty method for linear complementarity problems, Operations Research Letters, 36 (2008), 211-214.
doi: 10.1016/j.orl.2007.06.006. |
[17] |
S. Wang, X. Q. Yang and K. L. Teo,
Power penalty method for a linear complementarity problem arising from American option valuation, Journal of Optimization Theory & Applications, 129 (2006), 227-254.
doi: 10.1007/s10957-006-9062-3. |

O-D pair | Minimum cost | Route flow | Route cost |
1-12 | 22.540478 | 51.1269 | 22.540478 |
170.1978 | 22.540478 | ||
21.8757 | 22.540478 | ||
21.5513 | 22.540478 | ||
35.2483 | 22.540478 | ||
9-4 | 22.006421 | 222.7626 | 22.006421 |
121.4219 | 22.006421 | ||
55.8155 | 22.006421 | ||
12-1 | 22.591574 | 88.8082 | 22.591574 |
189.4446 | 22.591574 | ||
18.6029 | 22.591574 | ||
24.3365 | 22.591574 | ||
28.8078 | 22.591574 | ||
4-9 | 21.965890 | 195.8051 | 21.965890 |
99.6358 | 21.965890 | ||
54.5591 | 21.965890 |
O-D pair | Minimum cost | Route flow | Route cost |
1-12 | 22.540478 | 51.1269 | 22.540478 |
170.1978 | 22.540478 | ||
21.8757 | 22.540478 | ||
21.5513 | 22.540478 | ||
35.2483 | 22.540478 | ||
9-4 | 22.006421 | 222.7626 | 22.006421 |
121.4219 | 22.006421 | ||
55.8155 | 22.006421 | ||
12-1 | 22.591574 | 88.8082 | 22.591574 |
189.4446 | 22.591574 | ||
18.6029 | 22.591574 | ||
24.3365 | 22.591574 | ||
28.8078 | 22.591574 | ||
4-9 | 21.965890 | 195.8051 | 21.965890 |
99.6358 | 21.965890 | ||
54.5591 | 21.965890 |
m | h | posi-h | E | total costs | |
5 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
10 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
15 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
20 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
25 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
30 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
35 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
40 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
45 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
50 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
m | h | posi-h | E | total costs | |
5 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
10 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
15 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
20 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
25 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
30 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
35 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
40 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
45 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
50 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
m | h | posi-h | E | total costs | |
1 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
2 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
3 | 5 | 18 | 16 | 1.31E-10 | 31159.8244 |
4 | 6 | 17 | 16 | 2.43E-12 | 31159.8244 |
m | h | posi-h | E | total costs | |
1 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
2 | 5 | 16 | 16 | 3.83E-11 | 31159.8244 |
3 | 5 | 18 | 16 | 1.31E-10 | 31159.8244 |
4 | 6 | 17 | 16 | 2.43E-12 | 31159.8244 |
[1] |
Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271 |
[2] |
Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056 |
[3] |
Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021 |
[4] |
Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463 |
[5] |
Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020401 |
[6] |
Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151 |
[7] |
Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261 |
[8] |
Rongchang Liu, Jiangyuan Li, Duokui Yan. New periodic orbits in the planar equal-mass three-body problem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2187-2206. doi: 10.3934/dcds.2018090 |
[9] |
David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002 |
[10] |
Sergi Simon. Linearised higher variational equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (11) : 4827-4854. doi: 10.3934/dcds.2014.34.4827 |
[11] |
Nikolaz Gourmelon. Generation of homoclinic tangencies by $C^1$-perturbations. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 1-42. doi: 10.3934/dcds.2010.26.1 |
[12] |
Xue-Ping Luo, Yi-Bin Xiao, Wei Li. Strict feasibility of variational inclusion problems in reflexive Banach spaces. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2495-2502. doi: 10.3934/jimo.2019065 |
[13] |
Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781 |
[14] |
Carlos Fresneda-Portillo, Sergey E. Mikhailov. Analysis of Boundary-Domain Integral Equations to the mixed BVP for a compressible stokes system with variable viscosity. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3059-3088. doi: 10.3934/cpaa.2019137 |
[15] |
Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327 |
[16] |
Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006 |
[17] |
Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017 |
[18] |
Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018 |
[19] |
Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002 |
[20] |
Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]