• 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
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  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 & Management Optimization, 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. 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.  Google Scholar

[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.  Google Scholar

[4]

D. P. Bertsekas, Convex Optimization Algorithms, Athena Scientific, Belmont, 2015.  Google Scholar

[5]

D. P. Bertsekas, A. Nedi, A. E. Ozdaglar, et al., Convex Analysis and Optimization, Athena Scientific, Belmont, 2003.  Google Scholar

[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.  Google Scholar

[7]

J. P. CaulkinsD. GrassG. 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.  Google Scholar

[8]

T.-L. ChenJ. 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.  Google Scholar

[9]

B. ColA. 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.  Google Scholar

[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.  Google Scholar

[11]

J. Gauvin, Shadow prices in nonconvex mathematical programming, Mathematical Programming, 19 (1980), 300-312.  doi: 10.1007/BF01581650.  Google Scholar

[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.  Google Scholar

[13]

B. JansenJ. De JongC. 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.  Google Scholar

[14]

T. T. KeZ.-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.  Google Scholar

[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.  Google Scholar

[16]

J. Kyparisis, On uniqueness of kuhn-tucker multipliers in nonlinear programming, Mathematical Programming, 32 (1985), 242-246.  doi: 10.1007/BF01586095.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

L. ZhangD. FengJ. LeiC. XuZ. YanS. XuN. 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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[4]

D. P. Bertsekas, Convex Optimization Algorithms, Athena Scientific, Belmont, 2015.  Google Scholar

[5]

D. P. Bertsekas, A. Nedi, A. E. Ozdaglar, et al., Convex Analysis and Optimization, Athena Scientific, Belmont, 2003.  Google Scholar

[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.  Google Scholar

[7]

J. P. CaulkinsD. GrassG. 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.  Google Scholar

[8]

T.-L. ChenJ. 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.  Google Scholar

[9]

B. ColA. 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.  Google Scholar

[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.  Google Scholar

[11]

J. Gauvin, Shadow prices in nonconvex mathematical programming, Mathematical Programming, 19 (1980), 300-312.  doi: 10.1007/BF01581650.  Google Scholar

[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.  Google Scholar

[13]

B. JansenJ. De JongC. 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.  Google Scholar

[14]

T. T. KeZ.-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.  Google Scholar

[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.  Google Scholar

[16]

J. Kyparisis, On uniqueness of kuhn-tucker multipliers in nonlinear programming, Mathematical Programming, 32 (1985), 242-246.  doi: 10.1007/BF01586095.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

L. ZhangD. FengJ. LeiC. XuZ. YanS. XuN. 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.  Google Scholar

Figure 1.  Numerical Example in Schttfkowski (1987)
Figure 2.  Relationship of Lagrange Multiplier and Shadow Price
Figure 3.  Numerical Example
Figure 4.  Convergence of the $ \mathcal{PFA} $ algorithm with different penalty parameters
Figure 5.  Example of Multiple Lagrange Multipliers
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
$ 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
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
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]

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

[2]

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

[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]

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

[12]

Ferenc Weisz. Dual spaces of mixed-norm martingale hardy spaces. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020285

[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]

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

[19]

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

[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

Metrics

  • PDF downloads (70)
  • HTML views (332)
  • Cited by (0)

Other articles
by authors

[Back to Top]