Figure 1.
Road Network
-
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
October
2018, 14(4): 1381-1396.
doi: 10.3934/jimo.2018012
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.
Keywords:
Variational inequality,
mixed complementarity problem,
power penalty method,
traffic assignment problem,
column generation.
Mathematics Subject Classification:
Primary: 90C33, 90B20; Secondary: 90B10.
Citation:
Ming Chen, Chongchao Huang. A power penalty method for a class of linearly constrained variational inequality. Journal of Industrial and Management Optimization,
2018, 14
(4)
: 1381-1396.
doi: 10.3934/jimo.2018012
![]()
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. |
| [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. |
| [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. |
Table 1.
Computational Results
| 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 |
Table 2.
Computational results when $k = 2$
| 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 |
Table 3.
Computational results when $\lambda = 5$
| 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] |
Ming Chen, Chongchao Huang. A power penalty method for the general traffic assignment problem with elastic demand. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1019-1030. doi: 10.3934/jimo.2014.10.1019 |
| [2] |
Yarui Duan, Pengcheng Wu, Yuying Zhou. Penalty approximation method for a double obstacle quasilinear parabolic variational inequality problem. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022017 |
| [3] |
Gang Qian, Deren Han, Lingling Xu, Hai Yang. Solving nonadditive traffic assignment problems: A self-adaptive projection-auxiliary problem method for variational inequalities. Journal of Industrial and Management Optimization, 2013, 9 (1) : 255-274. doi: 10.3934/jimo.2013.9.255 |
| [4] |
Junfeng Yang. Dynamic power price problem: An inverse variational inequality approach. Journal of Industrial and Management Optimization, 2008, 4 (4) : 673-684. doi: 10.3934/jimo.2008.4.673 |
| [5] |
Yekini Shehu, Olaniyi Iyiola. On a modified extragradient method for variational inequality problem with application to industrial electricity production. Journal of Industrial and Management Optimization, 2019, 15 (1) : 319-342. doi: 10.3934/jimo.2018045 |
| [6] |
Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial and Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485 |
| [7] |
Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911 |
| [8] |
S. J. Li, Z. M. Fang. On the stability of a dual weak vector variational inequality problem. Journal of Industrial and Management Optimization, 2008, 4 (1) : 155-165. doi: 10.3934/jimo.2008.4.155 |
| [9] |
Francis Akutsah, Akindele Adebayo Mebawondu, Hammed Anuoluwapo Abass, Ojen Kumar Narain. A self adaptive method for solving a class of bilevel variational inequalities with split variational inequality and composed fixed point problem constraints in Hilbert spaces. Numerical Algebra, Control and Optimization, 2021 doi: 10.3934/naco.2021046 |
| [10] |
Bettina Klaus, Frédéric Payot. Paths to stability in the assignment problem. Journal of Dynamics and Games, 2015, 2 (3&4) : 257-287. doi: 10.3934/jdg.2015004 |
| [11] |
Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial and Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259 |
| [12] |
T. A. Shaposhnikova, M. N. Zubova. Homogenization problem for a parabolic variational inequality with constraints on subsets situated on the boundary of the domain. Networks and Heterogeneous Media, 2008, 3 (3) : 675-689. doi: 10.3934/nhm.2008.3.675 |
| [13] |
Jianlin Jiang, Shun Zhang, Su Zhang, Jie Wen. A variational inequality approach for constrained multifacility Weber problem under gauge. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1085-1104. doi: 10.3934/jimo.2017091 |
| [14] |
Ouafa Belguidoum, Hassina Grar. An improved projection algorithm for variational inequality problem with multivalued mapping. Numerical Algebra, Control and Optimization, 2022 doi: 10.3934/naco.2022002 |
| [15] |
Ming-Zheng Wang, M. Montaz Ali. Penalty-based SAA method of stochastic nonlinear complementarity problems. Journal of Industrial and Management Optimization, 2010, 6 (1) : 241-257. doi: 10.3934/jimo.2010.6.241 |
| [16] |
Liqun Qi, Zheng yan, Hongxia Yin. Semismooth reformulation and Newton's method for the security region problem of power systems. Journal of Industrial and Management Optimization, 2008, 4 (1) : 143-153. doi: 10.3934/jimo.2008.4.143 |
| [17] |
Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123 |
| [18] |
Kai Zhang, Xiaoqi Yang, Song Wang. Solution method for discrete double obstacle problems based on a power penalty approach. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1261-1274. doi: 10.3934/jimo.2021018 |
| [19] |
Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial and Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431 |
| [20] |
Bastian Gebauer, Nuutti Hyvönen. Factorization method and inclusions of mixed type in an inverse elliptic boundary value problem. Inverse Problems and Imaging, 2008, 2 (3) : 355-372. doi: 10.3934/ipi.2008.2.355 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]