Computing shadow prices with multiple Lagrange multipliers

Tao Jie; Gao Yan

doi:10.3934/jimo.2020070

Article Contents

2021, Volume 17, Issue 5: 2307-2329. Doi: 10.3934/jimo.2020070

This issue Previous Article Multi-criteria decision making method based on Bonferroni mean aggregation operators of complex intuitionistic fuzzy numbers Next Article Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming

Computing shadow prices with multiple Lagrange multipliers

Tao Jie and
Gao Yan^,

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

^* Corresponding author: Gao Yan
^* Corresponding author: Gao Yan

Received: July 31, 2019

Revised: October 31, 2019

Early access: March 2020

Published: September 2021

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

Abstract Full Text(HTML) Figure(5) / Table(2) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90C25, 90C30; Secondary: 90C31.

Citation:

FullText(HTML)

Figure 1. Numerical Example in Schttfkowski (1987)

Download: Full-size image PowerPoint slide

Figure 2. Relationship of Lagrange Multiplier and Shadow Price

Download: Full-size image PowerPoint slide

Figure 3. Numerical Example

Download: Full-size image PowerPoint slide

Figure 4. Convergence of the $ \mathcal{PFA} $ algorithm with different penalty parameters

Download: Full-size image PowerPoint slide

Figure 5. Example of Multiple Lagrange Multipliers

Download: Full-size image PowerPoint slide

Table 1. 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

| Show Table

DownLoad: CSV

Table 2. 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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.