A DECOMPOSITION APPROACH ON THE BASE OF BROWNIAN ITERATION FOR THE LINEAR PROGRAMMING WHERE ALL BASIS MATRICES ARE M-MATRIX

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

A new scheme for solving a problem for linear programming is proposed. The main property that distinguishes the considered problem is that the basis sub-matrices of its matrix are composed of only M-matrices. Based on the possibility created by this property, a matrix game with the same structure and size as its matrix is set against the given problem, and the possibility of constructing the optimal basis of the problem by partially executing the Brownian iteration leading to the optimal strategy of the second player is shown. Thus, we decompose the solution of the problem into the execution of a finite number of Brownian iterations. The areas of application of the solution scheme are shown. A numerical example illustrates the scheme. The possibility of replacing the game matrix with an integer-element matrix is also shown. This property allows Brownian iteration to be performed exactly. Bibl. 38.

About the authors

R. H Hamidov

Baku State University

Author for correspondence.
Email: shekhamidov@gmail.com
Baku, Azerbaijan

M. M Mutallimov

Institute of Applied Mathematics, Baku State University; Institute of Information Technologies, Ministry of Science and Education of Azerbaijan; Azerbaijan Technical University

Email: mmutallimov@yahoo.com
Baku, Azerbaijan; Baku, Azerbaijan; Baku, Azerbaijan

F. A Aliev

Institute of Applied Mathematics, Baku State University; Institute of Information Technologies, Ministry of Science and Education of Azerbaijan

Email: f_aliev@yahoo.com
Baku, Azerbaijan; Baku, Azerbaijan

References

  1. Tsurkov V.I. Decomposition in large scale problems. Moscow: Nauka, 1981.
  2. Tsurkov V.I. Dynamic problems of large dimension. Moscow: Nauka, 1988.
  3. Abade J.M., Williams A.C. Dual and parametric methods in decomposition. Recent advances math. program. N.Y. Mc. Graw-Hill, 1963.
  4. Belenkiy V.Z. On problems of mathematical programming with a minimal points // RAS USSR. 1968. V. 183. № 1. P. 15–19.
  5. Benders J.C. Partitioning procedures for solving mixed variables programming problems // Numer. math. 1962, № 4, P. 238–252.
  6. Berger U. Fictions Play in 2 × n Games // Journal of Economic Theory. 2005. V. 120. P. 139–154.
  7. Brown G.W. Iterative solutions of game by fictions play. In Activity Analysis of Productions and allocation, T.C. Koopmans (ED). New York: Wiley, 1951.
  8. Champolle A., Pock T. A first – order primal – dual algorithm for convex problems with application in imaging // Journal of mathematical imaging and vision. 2011. V. 40. I. 1. P. 120–145.
  9. Dantzig G.B. Wolfe P. Decomposition algorithm for linear programs // Econometrica. 1961. V. 29. I. 4. P. 767–778.
  10. Dantzig G.B., Wolf P. Decomposition algorithm for linear programming // Mathematics. 1964. V. 8. I. 1. P. 73–79.
  11. Dantzig G.B. Wolfe P. Decomposition principle for linear programs // Oper. Res. 1960. V. 8, I. 1. P. 101–111.
  12. Gale D. Theory of linear economic models. New York: McGraw-Hill. 1960.
  13. Geoffrion A.M. Relaxation and the dual method in mathematical programming. Working paper 135. Western management science institute. Los Angeles: University of California. 1968.
  14. Gilpin A., Pena J., Sandholm T. First – order algorithm with 0(ln(1/2)) convergence for ε – equilibrium in two – person zero – sum games // Mathematical programming. 2012. V. 133. I. 1. P. 279–298.
  15. He B. and Yuan X. Convergence analysis of primal – and dual algorithm for a saddle – point problem: from construction perspective // SIAM Journal and Imagines Sciences. 2012. V. 5. I. 1. P. 119–149.
  16. Hui – Min Li., Ke – Cun Zhang. A decomposition algorithm for solving large – scale quadratic programming problems // Applied mathematics and computations. 2006. V. 173. I. 1 P. 394–403.
  17. Kornai I., Liptak T. Planning on two levels // Application of mathematics in economic studies. 1965. V. 3.
  18. Krishna V., Sjostrom T. On the convergence of fictions play // Math. Operations Res. 1998. V. 23. P. 479–511.
  19. Lasdon L. Optimization of large systems. Moscow: Nauka,1975.
  20. Lin T., Ma S., Ye Y., Zang S. An Alternating Direction Method of Multipliers algorithm – based interior – point method for large – scale linear programming // Optimization Method and Software. 2021. V. 36. No. 2–3. P. 389–424.
  21. Malitsky Y., Pock T. A first – order primal dual algorithm with line search // SIAM Journal an Optimization. 2018. V. 28. No. 1. P. 411–432.
  22. Meerov M.V. Research and optimization of multivariable control systems. Moscow: Nauka, 1986.
  23. Nachbar J. “Evaluationary” Selection Dynamics in Games. Convergence and limit properties // International Journal of Game Theory. 1990. V. 19. P. 59–89.
  24. Owen G. Game theory. M., Moscow: MIR, 1971.
  25. Pervozvanskaya T.N., Pervozvanskiy A.A. Algorithm search for optimal distribution of centralized resources. Proceedings of AS USSR. Technical Cybernetics, 3, 55–67 (1966).
  26. Robinson J. An iterative method of solving a game // Annals of Mathematics. 1951. V. 54. P. 296–301.
  27. Rosen J.B. Convex partition programming, in recent advances in mathematical programming. New York: McGraw-Hill, 1963.
  28. Shchennikov B.A. Aggregation methods for solving a system of linear equations // RAS USSR. 1967. V. 173. № 4. P. 781–784.
  29. Volkonsky V.A. Optimal planning in conditions of large dimension. Iterative methods and the principled decomposition // Economical and mathematical method. 1965. V. 1. No. 2. P. 195–219.
  30. Qiao D., Wang X.K., Wang J.Q., Li L. Maximum entropy-based method for extracting the underlying probability distributions of Z-number // Applied and Computational Mathematics. 2024. V. 23. No. 2. P. 201–218.
  31. Aliev F.A., Hajiyeva N.S., Mutallimov M.M., Velieva N.I., Namazov A.A. Algorithm for solution of linear quadratic optimization problem with constraint in the form of equalities on control // Applied and Computational Mathematics. 2024. V. 23. No. 3. P. 404–414.
  32. Ozbay H., Srikant R. Yuskei S. Preface of the special issue: control, teams, and games // Applied and Computational Mathematics. 2024. V. 23. No. 3. P. 281–281.
  33. Hamidov S.I. Effective trajectories of economic dynamics models on graphs // Applied and Computational Mathematics. 2023. V. 22. No. 2. P. 215–224.
  34. Aliev F.A., Hajiyeva N.S. Discrete linear quadratic optimization problem with constraints in the form of equalities on control action // TWMS J. App. and Eng. Math. 2024. V. 14. No. 4. P. 1466–1472.
  35. Aliev F., Hajiyeva N., Velieva N., Mutallimov M., Tagiyev R. Constructing Optimal Regulator for Discrete Linear Quadratic Optimization Problem with Constraints on Control Action // Proceedings of the 9 th International Conference on Control and Optimization with Industrial Applications (COIA 2024). 2024. P. 194–197.
  36. Aliev F.A., Jamalbayov M.A., Valiyev N.A., Handajiyeva N.S. Computer model of pump–well–reservoir system based on the new concept of imitational modeling of dynamic systems // International Applied Mechanics. 2023. V. 59. No. 3. P. 352–362.
  37. Aliev F., Mutallimov M., Hajiyeva N., Velieva N., Abbasov A., Ismayilov N.A. Optimal Regulators for Multipoint Problems of Dynamic Systems // Proceedings of the 9 th International Conference on Control and Optimization with Industrial Applications (COIA 2024). 2024. P. 332–335.
  38. Aliev F., Hajiyeva N., Velieva N., Mutallimov M., Tagiyev R. Constructing Optimal Regulator for Discrete Linear Quadratic Optimization Problem with Constraints on Control Action, Proceedings of the 9 th International Conference on Control and Optimization with Industrial Applications (COIA 2024). 2024. P. 194–197.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 Russian Academy of Sciences