# American Institute of Mathematical Sciences

• Previous Article
• JIMO Home
• This Issue
• Next Article
Multi-criteria decision making method based on Bonferroni mean aggregation operators of complex intuitionistic fuzzy numbers
September  2021, 17(5): 2307-2329. doi: 10.3934/jimo.2020070

## Computing shadow prices with multiple Lagrange multipliers

 516 Jungong Road, Business School, University of Shanghai for Science and Technology, Shanghai 200093, China

* Corresponding author: Gao Yan

Received  August 2019 Revised  November 2019 Published  September 2021 Early access  March 2020

Fund Project: Tao Jie is supported by National Natural Science Foundation of China grant No. 71601117 and Soft Science Foundation of Shanghai grant No. 19692104600

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.

Citation: Tao Jie, Gao Yan. Computing shadow prices with multiple Lagrange multipliers. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2307-2329. doi: 10.3934/jimo.2020070
##### References:
 [1] M. Akgul, A note on shadow prices in linear programming, Journal of the Operational Research Society, 35 (1984), 425-431. [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. [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. [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. [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. [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. [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.
Numerical Example in Schttfkowski (1987)
Relationship of Lagrange Multiplier and Shadow Price
Numerical Example
Convergence of the $\mathcal{PFA}$ algorithm with different penalty parameters
Example of Multiple Lagrange Multipliers
Computational Times of the $\mathcal{AGM}$ algorithm on Large - scale Data Sets
 $m$ $n$ 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
 $m$ $n$ 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
Result of the 2-phase Procedure with 23 Vertices of the Bounded Lagrange Multiplier Set
 Vertices Elements $v_1$ 0.0000 1.6118 0.0000 0.0000 0.0000 0.0000 0.4939 0.0000 0.0000 $v_2$ 0.0000 2.1057 0.4939 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 $v_3$ 0.0000 3.0834 0.0000 0.0000 0.1352 0.0000 0.0000 0.6957 0.0000 $v_4$ 0.0000 3.4207 0.0000 0.0000 0.0026 0.0000 0.0064 0.7603 0.1801 $v_5$ 0.0000 5.7145 0.0000 0.0000 3.1147 2.5431 3.6277 0.0000 0.0000 $v_6$ 0.0000 7.1430 0.0000 4.9601 0.9637 0.0000 1.9331 0.0000 0.0000 $v_7$ 0.0000 7.2983 0.0000 0.0000 0.0000 1.7188 3.3700 0.0000 2.6128 $v_8$ 0.0000 7.5898 0.0000 4.3192 0.0000 0.0000 2.0493 0.0000 1.0416 $v_9$ 0.0000 7.7043 2.9184 0.0000 2.4098 1.9675 0.0000 0.0000 0.0000 $v_{10}$ 0.0000 8.1361 1.7390 4.2912 0.8338 0.0000 0.0000 0.0000 0.0000 $v_{11}$ 0.0000 8.5707 1.8287 3.7067 0.0000 0.0000 0.0000 0.0000 0.8939 $v_{12}$ 0.0000 8.8386 2.7554 0.0000 0.0000 1.3515 0.0000 0.0000 2.0545 $v_{13}$ 0.0000 9.0761 0.0000 3.0271 0.9637 0.0000 0.0000 1.9331 0.0000 $v_{14}$ 0.0000 9.1971 0.0000 0.0000 1.9422 1.1568 0.0000 2.7039 0.0000 $v_{15}$ 0.0000 9.6392 0.0000 2.2699 0.0000 0.0000 0.0000 2.0493 1.0416 $v_{16}$ 0.0000 10.0534 0.0000 0.0000 0.0000 0.6918 0.0000 2.5809 1.6740 $v_{17}$ 0.0000 3.4315 0.0050 0.0000 0.0027 0.0000 0.0000 0.7627 0.1807 $v_{18}$ 0.6494 10.2980 0.0000 0.0000 0.0000 0.0000 0.0000 2.4700 1.5827 $v_{19}$ 1.0475 9.6669 0.0000 0.0000 1.7714 0.0000 0.0000 2.5142 0.0000 $v_{20}$ 1.2187 9.3956 2.5332 0.0000 0.0000 0.0000 0.0000 0.0000 1.8526 $v_{21}$ 1.5166 8.1461 0.0000 0.0000 0.0000 0.0000 3.0317 0.0000 2.3055 $v_{22}$ 1.6981 8.6358 2.5864 0.0000 2.0798 0.0000 0.0000 0.0000 0.0000 $v_{23}$ 2.1242 7.1628 0.0000 0.0000 2.6016 0.0000 3.1114 0.0000 0.0000
 Vertices Elements $v_1$ 0.0000 1.6118 0.0000 0.0000 0.0000 0.0000 0.4939 0.0000 0.0000 $v_2$ 0.0000 2.1057 0.4939 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 $v_3$ 0.0000 3.0834 0.0000 0.0000 0.1352 0.0000 0.0000 0.6957 0.0000 $v_4$ 0.0000 3.4207 0.0000 0.0000 0.0026 0.0000 0.0064 0.7603 0.1801 $v_5$ 0.0000 5.7145 0.0000 0.0000 3.1147 2.5431 3.6277 0.0000 0.0000 $v_6$ 0.0000 7.1430 0.0000 4.9601 0.9637 0.0000 1.9331 0.0000 0.0000 $v_7$ 0.0000 7.2983 0.0000 0.0000 0.0000 1.7188 3.3700 0.0000 2.6128 $v_8$ 0.0000 7.5898 0.0000 4.3192 0.0000 0.0000 2.0493 0.0000 1.0416 $v_9$ 0.0000 7.7043 2.9184 0.0000 2.4098 1.9675 0.0000 0.0000 0.0000 $v_{10}$ 0.0000 8.1361 1.7390 4.2912 0.8338 0.0000 0.0000 0.0000 0.0000 $v_{11}$ 0.0000 8.5707 1.8287 3.7067 0.0000 0.0000 0.0000 0.0000 0.8939 $v_{12}$ 0.0000 8.8386 2.7554 0.0000 0.0000 1.3515 0.0000 0.0000 2.0545 $v_{13}$ 0.0000 9.0761 0.0000 3.0271 0.9637 0.0000 0.0000 1.9331 0.0000 $v_{14}$ 0.0000 9.1971 0.0000 0.0000 1.9422 1.1568 0.0000 2.7039 0.0000 $v_{15}$ 0.0000 9.6392 0.0000 2.2699 0.0000 0.0000 0.0000 2.0493 1.0416 $v_{16}$ 0.0000 10.0534 0.0000 0.0000 0.0000 0.6918 0.0000 2.5809 1.6740 $v_{17}$ 0.0000 3.4315 0.0050 0.0000 0.0027 0.0000 0.0000 0.7627 0.1807 $v_{18}$ 0.6494 10.2980 0.0000 0.0000 0.0000 0.0000 0.0000 2.4700 1.5827 $v_{19}$ 1.0475 9.6669 0.0000 0.0000 1.7714 0.0000 0.0000 2.5142 0.0000 $v_{20}$ 1.2187 9.3956 2.5332 0.0000 0.0000 0.0000 0.0000 0.0000 1.8526 $v_{21}$ 1.5166 8.1461 0.0000 0.0000 0.0000 0.0000 3.0317 0.0000 2.3055 $v_{22}$ 1.6981 8.6358 2.5864 0.0000 2.0798 0.0000 0.0000 0.0000 0.0000 $v_{23}$ 2.1242 7.1628 0.0000 0.0000 2.6016 0.0000 3.1114 0.0000 0.0000
 [1] Karla L. Cortez, Javier F. Rosenblueth. Normality and uniqueness of Lagrange multipliers. Discrete and Continuous Dynamical Systems, 2018, 38 (6) : 3169-3188. doi: 10.3934/dcds.2018138 [2] Caiping Liu, Heungwing Lee. Lagrange multiplier rules for approximate solutions in vector optimization. Journal of Industrial and Management Optimization, 2012, 8 (3) : 749-764. doi: 10.3934/jimo.2012.8.749 [3] Zhongming Wu, Xingju Cai, Deren Han. Linearized block-wise alternating direction method of multipliers for multiple-block convex programming. Journal of Industrial and Management Optimization, 2018, 14 (3) : 833-855. doi: 10.3934/jimo.2017078 [4] Takeshi Fukao, Nobuyuki Kenmochi. Abstract theory of variational inequalities and Lagrange multipliers. Conference Publications, 2013, 2013 (special) : 237-246. doi: 10.3934/proc.2013.2013.237 [5] Mohammad Hassan Farshbaf-Shaker, Takeshi Fukao, Noriaki Yamazaki. Singular limit of Allen--Cahn equation with constraint and its Lagrange multiplier. Conference Publications, 2015, 2015 (special) : 418-427. doi: 10.3934/proc.2015.0418 [6] Annamaria Barbagallo, Rosalba Di Vincenzo, Stéphane Pia. On strong Lagrange duality for weighted traffic equilibrium problem. Discrete and Continuous Dynamical Systems, 2011, 31 (4) : 1097-1113. doi: 10.3934/dcds.2011.31.1097 [7] Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247 [8] Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial and Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723 [9] Yuying Zhou, Gang Li. The Toland-Fenchel-Lagrange duality of DC programs for composite convex functions. Numerical Algebra, Control and Optimization, 2014, 4 (1) : 9-23. doi: 10.3934/naco.2014.4.9 [10] Maria do Rosário de Pinho, Ilya Shvartsman. Lipschitz continuity of optimal control and Lagrange multipliers in a problem with mixed and pure state constraints. Discrete and Continuous Dynamical Systems, 2011, 29 (2) : 505-522. doi: 10.3934/dcds.2011.29.505 [11] Ana Bela Cruzeiro. Navier-Stokes and stochastic Navier-Stokes equations via Lagrange multipliers. Journal of Geometric Mechanics, 2019, 11 (4) : 553-560. doi: 10.3934/jgm.2019027 [12] Ying Gao, Xinmin Yang, Jin Yang, Hong Yan. Scalarizations and Lagrange multipliers for approximate solutions in the vector optimization problems with set-valued maps. Journal of Industrial and Management Optimization, 2015, 11 (2) : 673-683. doi: 10.3934/jimo.2015.11.673 [13] Yutian Lei, Zhongxue Lü. Axisymmetry of locally bounded solutions to an Euler-Lagrange system of the weighted Hardy-Littlewood-Sobolev inequality. Discrete and Continuous Dynamical Systems, 2013, 33 (5) : 1987-2005. doi: 10.3934/dcds.2013.33.1987 [14] Yuan Xu, Xin Jin, Saiwei Wang, Yang Tang. Optimal synchronization control of multiple euler-lagrange systems via event-triggered reinforcement learning. Discrete and Continuous Dynamical Systems - S, 2021, 14 (4) : 1495-1518. doi: 10.3934/dcdss.2020377 [15] Ronan Costaouec, Haoyun Feng, Jesús Izaguirre, Eric Darve. Analysis of the accelerated weighted ensemble methodology. Conference Publications, 2013, 2013 (special) : 171-181. doi: 10.3934/proc.2013.2013.171 [16] Pedro L. García, Antonio Fernández, César Rodrigo. Variational integrators for discrete Lagrange problems. Journal of Geometric Mechanics, 2010, 2 (4) : 343-374. doi: 10.3934/jgm.2010.2.343 [17] Giovanni Bonfanti, Arrigo Cellina. The validity of the Euler-Lagrange equation. Discrete and Continuous Dynamical Systems, 2010, 28 (2) : 511-517. doi: 10.3934/dcds.2010.28.511 [18] Menita Carozza, Jan Kristensen, Antonia Passarelli di Napoli. On the validity of the Euler-Lagrange system. Communications on Pure and Applied Analysis, 2015, 14 (1) : 51-62. doi: 10.3934/cpaa.2015.14.51 [19] Marco Castrillón López, Pablo M. Chacón, Pedro L. García. Lagrange-Poincaré reduction in affine principal bundles. Journal of Geometric Mechanics, 2013, 5 (4) : 399-414. doi: 10.3934/jgm.2013.5.399 [20] Marco Castrillón López, Pedro Luis García Pérez. The problem of Lagrange on principal bundles under a subgroup of symmetries. Journal of Geometric Mechanics, 2019, 11 (4) : 539-552. doi: 10.3934/jgm.2019026

2021 Impact Factor: 1.411