
-
Previous Article
A two-stage solution approach for plastic injection machines scheduling problem
- JIMO Home
- This Issue
-
Next Article
Tabu search and simulated annealing for resource-constrained multi-project scheduling to minimize maximal cash flow gap
Computing shadow prices with multiple Lagrange multipliers
516 Jungong Road, Business School, University of Shanghai for Science and Technology, Shanghai 200093, China |
There is a wide consensus that the shadow prices of certain resources in an economic system are equal to Lagrange multipliers. However, this is misleading with respect to multiple Lagrange multipliers. In this paper, we propose a new type of Lagrange multiplier, the weighted minimum norm Lagrange multiplier, which is a type of shadow price. An attractive aspect of this type of Lagrange multiplier is that it conveys the sensitivity information when resources are required to be proportionally input. To compute the weighted minimum norm Lagrange multiplier, we propose two algorithms. One is the penalty function method with numeric stability, and the other is the accelerated gradient method with fewer arithmetic operations and a convergence rate of $ O(\frac{1}{k^2}) $. Furthermore, we propose a two-phase procedure to compute a particular subset of shadow prices that belongs to the set of bounded Lagrange multipliers. This subset is particularly attractive since all its elements are computable shadow prices. We report the numerical results for randomly generated problems.
References:
[1] |
M. Akgul, A note on shadow prices in linear programming, Journal of the Operational Research Society, 35 (1984), 425-431. Google Scholar |
[2] |
D. C. Aucamp and D. I. Steinberg, The computation of shadow prices in linear programming, Journal of the Operational Research Society, 33 (1982), 557-565.
doi: 10.1057/jors.1982.118. |
[3] |
M. S. Bazaraa, H. D. Sherali and C. M. Shetty, Nonlinear Programming: Theory and Algorithms, John Wiley & Sons Inc., Hoboken, NJ, 2006.
doi: 10.1002/0471787779. |
[4] |
D. P. Bertsekas, Convex Optimization Algorithms, Athena Scientific, Belmont, 2015. |
[5] |
D. P. Bertsekas, A. Nedi, A. E. Ozdaglar, et al., Convex Analysis and Optimization, Athena Scientific, Belmont, 2003. |
[6] |
D. P. Bertsekas and A. E. Ozdaglar,
Pseudonormality and a lagrange multiplier theory for constrained optimization, Journal of Optimization Theory and Applications, 114 (2002), 287-343.
doi: 10.1023/A:1016083601322. |
[7] |
J. P. Caulkins, D. Grass, G. Feichtinger and G. Tragler,
Optimizing counter-terror operations: Should one fight fire with"fir" or"wate"?, Computers & Operations Research, 35 (2008), 1874-1885.
doi: 10.1016/j.cor.2006.09.017. |
[8] |
T.-L. Chen, J. T. Lin and S.-C. Fang,
A shadow-price based heuristic for capacity planning of tft-lcd manufacturing, Journal of Industrial & Management Optimization, 6 (2010), 209-239.
doi: 10.3934/jimo.2010.6.209. |
[9] |
B. Col, A. Durnev and A. Molchanov,
Foreign risk, domestic problem: Capital allocation and firm performance under political instability, Management Science, 64 (2018), 1975-2471.
doi: 10.1287/mnsc.2016.2638. |
[10] |
M. E. Dyer,
The complexity of vertex enumeration methods, Mathematics of Operations Research, 8 (1983), 381-402.
doi: 10.1287/moor.8.3.381. |
[11] |
J. Gauvin,
Shadow prices in nonconvex mathematical programming, Mathematical Programming, 19 (1980), 300-312.
doi: 10.1007/BF01581650. |
[12] |
M. Hessel and M. Zeleny,
Optimal system design: towards new interpretation of shadow prices in linear programming, Computers & Operations Research, 14 (1987), 265-271.
doi: 10.1016/0305-0548(87)90063-3. |
[13] |
B. Jansen, J. De Jong, C. Roos and T. Terlaky,
Sensitivity analysis in linear programming: Just be careful!, European Journal of Operational Research, 101 (1997), 15-28.
doi: 10.1016/S0377-2217(96)00172-5. |
[14] |
T. T. Ke, Z.-J. M. Shen and J. M. Villas-Boas,
Search for information on multiple products, Management Science, 62 (2016), 3576-3603.
doi: 10.1287/mnsc.2015.2316. |
[15] |
R. Kutsuzawa, A. Yamashita, N. Takemura, J. Matsumoto, M. Tanaka and N. Yamanaka, Demand response minimizing the impact on the consumers' utility towards renewable energy, in Smart Grid Communications (SmartGridComm), 2016 IEEE International Conference on, IEEE, 2016, 68–73.
doi: 10.1109/SmartGridComm.2016.7778740. |
[16] |
J. Kyparisis,
On uniqueness of kuhn-tucker multipliers in nonlinear programming, Mathematical Programming, 32 (1985), 242-246.
doi: 10.1007/BF01586095. |
[17] |
C.-Y. Lee and P. Zhou, Directional shadow price estimation of co2, so2 and nox in the united states coal power industry 1990–2010, Energy Economics, 51 (2015), 493-502. Google Scholar |
[18] |
O. L. Mangasarian,
Uniqueness of solution in linear programming, Linear Algebra and Its Applications, 25 (1979), 151-162.
doi: 10.1016/0024-3795(79)90014-4. |
[19] |
W. Meng and X. Wang,
Distributed energy management in smart grid with wind power and temporally coupled constraints, IEEE Transactions on Industrial Electronics, 64 (2017), 6052-6062.
doi: 10.1109/TIE.2017.2682001. |
[20] |
K. Schittkowski, More Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems, 282. Springer-Verlag, Berlin, 1987.
doi: 10.1007/978-3-642-61582-5. |
[21] |
N. Walter, Microeconomic Theory: Basic Principles and Extensions., Nelson Education, Canada, 2005. Google Scholar |
[22] |
Q. Wei and H. Yan,
A method of transferring polyhedron between the intersection-form and the sum-form, Computers & Mathematics with Applications, 41 (2001), 1327-1342.
doi: 10.1016/S0898-1221(01)00100-6. |
[23] |
L. Zhang, D. Feng, J. Lei, C. Xu, Z. Yan, S. Xu, N. Li and L. Jing,
Congestion surplus minimization pricing solutions when lagrange multipliers are not unique, IEEE Transactions on Power Systems, 29 (2014), 2023-2032.
doi: 10.1109/TPWRS.2014.2301213. |
show all references
References:
[1] |
M. Akgul, A note on shadow prices in linear programming, Journal of the Operational Research Society, 35 (1984), 425-431. Google Scholar |
[2] |
D. C. Aucamp and D. I. Steinberg, The computation of shadow prices in linear programming, Journal of the Operational Research Society, 33 (1982), 557-565.
doi: 10.1057/jors.1982.118. |
[3] |
M. S. Bazaraa, H. D. Sherali and C. M. Shetty, Nonlinear Programming: Theory and Algorithms, John Wiley & Sons Inc., Hoboken, NJ, 2006.
doi: 10.1002/0471787779. |
[4] |
D. P. Bertsekas, Convex Optimization Algorithms, Athena Scientific, Belmont, 2015. |
[5] |
D. P. Bertsekas, A. Nedi, A. E. Ozdaglar, et al., Convex Analysis and Optimization, Athena Scientific, Belmont, 2003. |
[6] |
D. P. Bertsekas and A. E. Ozdaglar,
Pseudonormality and a lagrange multiplier theory for constrained optimization, Journal of Optimization Theory and Applications, 114 (2002), 287-343.
doi: 10.1023/A:1016083601322. |
[7] |
J. P. Caulkins, D. Grass, G. Feichtinger and G. Tragler,
Optimizing counter-terror operations: Should one fight fire with"fir" or"wate"?, Computers & Operations Research, 35 (2008), 1874-1885.
doi: 10.1016/j.cor.2006.09.017. |
[8] |
T.-L. Chen, J. T. Lin and S.-C. Fang,
A shadow-price based heuristic for capacity planning of tft-lcd manufacturing, Journal of Industrial & Management Optimization, 6 (2010), 209-239.
doi: 10.3934/jimo.2010.6.209. |
[9] |
B. Col, A. Durnev and A. Molchanov,
Foreign risk, domestic problem: Capital allocation and firm performance under political instability, Management Science, 64 (2018), 1975-2471.
doi: 10.1287/mnsc.2016.2638. |
[10] |
M. E. Dyer,
The complexity of vertex enumeration methods, Mathematics of Operations Research, 8 (1983), 381-402.
doi: 10.1287/moor.8.3.381. |
[11] |
J. Gauvin,
Shadow prices in nonconvex mathematical programming, Mathematical Programming, 19 (1980), 300-312.
doi: 10.1007/BF01581650. |
[12] |
M. Hessel and M. Zeleny,
Optimal system design: towards new interpretation of shadow prices in linear programming, Computers & Operations Research, 14 (1987), 265-271.
doi: 10.1016/0305-0548(87)90063-3. |
[13] |
B. Jansen, J. De Jong, C. Roos and T. Terlaky,
Sensitivity analysis in linear programming: Just be careful!, European Journal of Operational Research, 101 (1997), 15-28.
doi: 10.1016/S0377-2217(96)00172-5. |
[14] |
T. T. Ke, Z.-J. M. Shen and J. M. Villas-Boas,
Search for information on multiple products, Management Science, 62 (2016), 3576-3603.
doi: 10.1287/mnsc.2015.2316. |
[15] |
R. Kutsuzawa, A. Yamashita, N. Takemura, J. Matsumoto, M. Tanaka and N. Yamanaka, Demand response minimizing the impact on the consumers' utility towards renewable energy, in Smart Grid Communications (SmartGridComm), 2016 IEEE International Conference on, IEEE, 2016, 68–73.
doi: 10.1109/SmartGridComm.2016.7778740. |
[16] |
J. Kyparisis,
On uniqueness of kuhn-tucker multipliers in nonlinear programming, Mathematical Programming, 32 (1985), 242-246.
doi: 10.1007/BF01586095. |
[17] |
C.-Y. Lee and P. Zhou, Directional shadow price estimation of co2, so2 and nox in the united states coal power industry 1990–2010, Energy Economics, 51 (2015), 493-502. Google Scholar |
[18] |
O. L. Mangasarian,
Uniqueness of solution in linear programming, Linear Algebra and Its Applications, 25 (1979), 151-162.
doi: 10.1016/0024-3795(79)90014-4. |
[19] |
W. Meng and X. Wang,
Distributed energy management in smart grid with wind power and temporally coupled constraints, IEEE Transactions on Industrial Electronics, 64 (2017), 6052-6062.
doi: 10.1109/TIE.2017.2682001. |
[20] |
K. Schittkowski, More Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems, 282. Springer-Verlag, Berlin, 1987.
doi: 10.1007/978-3-642-61582-5. |
[21] |
N. Walter, Microeconomic Theory: Basic Principles and Extensions., Nelson Education, Canada, 2005. Google Scholar |
[22] |
Q. Wei and H. Yan,
A method of transferring polyhedron between the intersection-form and the sum-form, Computers & Mathematics with Applications, 41 (2001), 1327-1342.
doi: 10.1016/S0898-1221(01)00100-6. |
[23] |
L. Zhang, D. Feng, J. Lei, C. Xu, Z. Yan, S. Xu, N. Li and L. Jing,
Congestion surplus minimization pricing solutions when lagrange multipliers are not unique, IEEE Transactions on Power Systems, 29 (2014), 2023-2032.
doi: 10.1109/TPWRS.2014.2301213. |





Computational Time | ||
500 | 5000 | 10.7504 |
500 | 10000 | 11.4222 |
500 | 20000 | 12.5574 |
500 | 50000 | 15.5700 |
1000 | 5000 | 21.4259 |
1000 | 10000 | 21.8054 |
1000 | 20000 | 22.2733 |
1000 | 50000 | 25.2937 |
5000 | 5000 | 101.1437 |
5000 | 10000 | 102.1762 |
5000 | 20000 | 106.8786 |
5000 | 50000 | 107.3515 |
Computational Time | ||
500 | 5000 | 10.7504 |
500 | 10000 | 11.4222 |
500 | 20000 | 12.5574 |
500 | 50000 | 15.5700 |
1000 | 5000 | 21.4259 |
1000 | 10000 | 21.8054 |
1000 | 20000 | 22.2733 |
1000 | 50000 | 25.2937 |
5000 | 5000 | 101.1437 |
5000 | 10000 | 102.1762 |
5000 | 20000 | 106.8786 |
5000 | 50000 | 107.3515 |
Vertices | Elements | ||||||||
0.0000 | 1.6118 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.4939 | 0.0000 | 0.0000 | |
0.0000 | 2.1057 | 0.4939 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | |
0.0000 | 3.0834 | 0.0000 | 0.0000 | 0.1352 | 0.0000 | 0.0000 | 0.6957 | 0.0000 | |
0.0000 | 3.4207 | 0.0000 | 0.0000 | 0.0026 | 0.0000 | 0.0064 | 0.7603 | 0.1801 | |
0.0000 | 5.7145 | 0.0000 | 0.0000 | 3.1147 | 2.5431 | 3.6277 | 0.0000 | 0.0000 | |
0.0000 | 7.1430 | 0.0000 | 4.9601 | 0.9637 | 0.0000 | 1.9331 | 0.0000 | 0.0000 | |
0.0000 | 7.2983 | 0.0000 | 0.0000 | 0.0000 | 1.7188 | 3.3700 | 0.0000 | 2.6128 | |
0.0000 | 7.5898 | 0.0000 | 4.3192 | 0.0000 | 0.0000 | 2.0493 | 0.0000 | 1.0416 | |
0.0000 | 7.7043 | 2.9184 | 0.0000 | 2.4098 | 1.9675 | 0.0000 | 0.0000 | 0.0000 | |
0.0000 | 8.1361 | 1.7390 | 4.2912 | 0.8338 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | |
0.0000 | 8.5707 | 1.8287 | 3.7067 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.8939 | |
0.0000 | 8.8386 | 2.7554 | 0.0000 | 0.0000 | 1.3515 | 0.0000 | 0.0000 | 2.0545 | |
0.0000 | 9.0761 | 0.0000 | 3.0271 | 0.9637 | 0.0000 | 0.0000 | 1.9331 | 0.0000 | |
0.0000 | 9.1971 | 0.0000 | 0.0000 | 1.9422 | 1.1568 | 0.0000 | 2.7039 | 0.0000 | |
0.0000 | 9.6392 | 0.0000 | 2.2699 | 0.0000 | 0.0000 | 0.0000 | 2.0493 | 1.0416 | |
0.0000 | 10.0534 | 0.0000 | 0.0000 | 0.0000 | 0.6918 | 0.0000 | 2.5809 | 1.6740 | |
0.0000 | 3.4315 | 0.0050 | 0.0000 | 0.0027 | 0.0000 | 0.0000 | 0.7627 | 0.1807 | |
0.6494 | 10.2980 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 2.4700 | 1.5827 | |
1.0475 | 9.6669 | 0.0000 | 0.0000 | 1.7714 | 0.0000 | 0.0000 | 2.5142 | 0.0000 | |
1.2187 | 9.3956 | 2.5332 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 1.8526 | |
1.5166 | 8.1461 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 3.0317 | 0.0000 | 2.3055 | |
1.6981 | 8.6358 | 2.5864 | 0.0000 | 2.0798 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | |
2.1242 | 7.1628 | 0.0000 | 0.0000 | 2.6016 | 0.0000 | 3.1114 | 0.0000 | 0.0000 |
Vertices | Elements | ||||||||
0.0000 | 1.6118 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.4939 | 0.0000 | 0.0000 | |
0.0000 | 2.1057 | 0.4939 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | |
0.0000 | 3.0834 | 0.0000 | 0.0000 | 0.1352 | 0.0000 | 0.0000 | 0.6957 | 0.0000 | |
0.0000 | 3.4207 | 0.0000 | 0.0000 | 0.0026 | 0.0000 | 0.0064 | 0.7603 | 0.1801 | |
0.0000 | 5.7145 | 0.0000 | 0.0000 | 3.1147 | 2.5431 | 3.6277 | 0.0000 | 0.0000 | |
0.0000 | 7.1430 | 0.0000 | 4.9601 | 0.9637 | 0.0000 | 1.9331 | 0.0000 | 0.0000 | |
0.0000 | 7.2983 | 0.0000 | 0.0000 | 0.0000 | 1.7188 | 3.3700 | 0.0000 | 2.6128 | |
0.0000 | 7.5898 | 0.0000 | 4.3192 | 0.0000 | 0.0000 | 2.0493 | 0.0000 | 1.0416 | |
0.0000 | 7.7043 | 2.9184 | 0.0000 | 2.4098 | 1.9675 | 0.0000 | 0.0000 | 0.0000 | |
0.0000 | 8.1361 | 1.7390 | 4.2912 | 0.8338 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | |
0.0000 | 8.5707 | 1.8287 | 3.7067 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.8939 | |
0.0000 | 8.8386 | 2.7554 | 0.0000 | 0.0000 | 1.3515 | 0.0000 | 0.0000 | 2.0545 | |
0.0000 | 9.0761 | 0.0000 | 3.0271 | 0.9637 | 0.0000 | 0.0000 | 1.9331 | 0.0000 | |
0.0000 | 9.1971 | 0.0000 | 0.0000 | 1.9422 | 1.1568 | 0.0000 | 2.7039 | 0.0000 | |
0.0000 | 9.6392 | 0.0000 | 2.2699 | 0.0000 | 0.0000 | 0.0000 | 2.0493 | 1.0416 | |
0.0000 | 10.0534 | 0.0000 | 0.0000 | 0.0000 | 0.6918 | 0.0000 | 2.5809 | 1.6740 | |
0.0000 | 3.4315 | 0.0050 | 0.0000 | 0.0027 | 0.0000 | 0.0000 | 0.7627 | 0.1807 | |
0.6494 | 10.2980 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 2.4700 | 1.5827 | |
1.0475 | 9.6669 | 0.0000 | 0.0000 | 1.7714 | 0.0000 | 0.0000 | 2.5142 | 0.0000 | |
1.2187 | 9.3956 | 2.5332 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 1.8526 | |
1.5166 | 8.1461 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 3.0317 | 0.0000 | 2.3055 | |
1.6981 | 8.6358 | 2.5864 | 0.0000 | 2.0798 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | |
2.1242 | 7.1628 | 0.0000 | 0.0000 | 2.6016 | 0.0000 | 3.1114 | 0.0000 | 0.0000 |
[1] |
Imam Wijaya, Hirofumi Notsu. Stability estimates and a Lagrange-Galerkin scheme for a Navier-Stokes type model of flow in non-homogeneous porous media. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1197-1212. doi: 10.3934/dcdss.2020234 |
[2] |
Huiying Fan, Tao Ma. Parabolic equations involving Laguerre operators and weighted mixed-norm estimates. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5487-5508. doi: 10.3934/cpaa.2020249 |
[3] |
Martin Heida, Stefan Neukamm, Mario Varga. Stochastic homogenization of $ \Lambda $-convex gradient flows. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 427-453. doi: 10.3934/dcdss.2020328 |
[4] |
Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2021012 |
[5] |
Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136 |
[6] |
Editorial Office. Retraction: Xiao-Qian Jiang and Lun-Chuan Zhang, Stock price fluctuation prediction method based on time series analysis. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 915-915. doi: 10.3934/dcdss.2019061 |
[7] |
Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2021, 17 (1) : 101-116. doi: 10.3934/jimo.2019101 |
[8] |
Zongyuan Li, Weinan Wang. Norm inflation for the Boussinesq system. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020353 |
[9] |
Yuxin Zhang. The spatially heterogeneous diffusive rabies model and its shadow system. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020357 |
[10] |
Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115 |
[11] |
Ferenc Weisz. Dual spaces of mixed-norm martingale hardy spaces. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020285 |
[12] |
Paul E. Anderson, Timothy P. Chartier, Amy N. Langville, Kathryn E. Pedings-Behling. The rankability of weighted data from pairwise comparisons. Foundations of Data Science, 2021 doi: 10.3934/fods.2021002 |
[13] |
Elvio Accinelli, Humberto Muñiz. A dynamic for production economies with multiple equilibria. Journal of Dynamics & Games, 2021 doi: 10.3934/jdg.2021002 |
[14] |
Andreas Koutsogiannis. Multiple ergodic averages for tempered functions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1177-1205. doi: 10.3934/dcds.2020314 |
[15] |
Gabrielle Nornberg, Delia Schiera, Boyan Sirakov. A priori estimates and multiplicity for systems of elliptic PDE with natural gradient growth. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3857-3881. doi: 10.3934/dcds.2020128 |
[16] |
Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020 doi: 10.3934/naco.2020054 |
[17] |
Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 |
[18] |
Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020 doi: 10.3934/jdg.2021001 |
[19] |
Dmitry Dolgopyat. The work of Sébastien Gouëzel on limit theorems and on weighted Banach spaces. Journal of Modern Dynamics, 2020, 16: 351-371. doi: 10.3934/jmd.2020014 |
[20] |
Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272 |
2019 Impact Factor: 1.366
Tools
Article outline
Figures and Tables
[Back to Top]