Поиск локально оптимальных стратегий в линейной игровой задаче с благоприятными ситуациями

Поиск локально оптимальных стратегий в линейной игровой задаче с благоприятными ситуациями

Маматов А. Р.
Дискретный анализ и исследование операций, 31, 3, 123–143 (2024)
Скачать статью

УДК 519.8+519.6 
DOI: 10.33048/daio.2024.31.782

Аннотация:

Рассматривается линейная игровая задача двух игроков. Два игрока поочерёдно выбирают свои стратегии из соответствующих множеств. Сначала первый игрок выбирает свою стратегию, затем, зная стратегию первого игрока, второй игрок выбирает свою стратегию. Множество стратегий второго игрока зависит от стратегии первого игрока. Целью первого игрока является выбор стратегии для того, чтобы максимизировать выпуклую кусочно линейную функцию (функцию минимума по стратегии второго игрока). Цель второго игрока — минимизировать линейную функцию. Предложен алгоритм, позволяющий строить стратегии для этой, а также для двойственной задачи, удовлетворяющие необходимым условиям оптимальности «высокого порядка». Этот алгоритм использует формулу приращения целевой функции двойственной задачи. Доказаны теоремы о конечности предложенного алгоритма и его модификации. Приведён пример, иллюстрирующий работу алгоритма. Также приведены результаты численного эксперимента по построению стратегий, удовлетворяющих необходимым условиям оптимальности «высокого порядка» в задачах, элементы которых генерировались датчиком случайных чисел. По результатам численного эксперимента можно сделать вывод, что при исполнении предложенного алгоритма зачастую имеется возможность перехода от одной локально оптимальной стратегии первого игрока к другой стратегии, обеспечивающей возрастание целевой функции. 
Табл. 1, ил. 1, библиогр. 21.

Литература:
  1. Пшеничный Б. Н. Необходимые условия экстремума. М.: Наука, 1982. 144 с.
     
  2. Мордухович Б. Ш. К необходимым условиям экстремума в негладкой оптимизации // Докл. АН СССР. 1985. Т. 283, № 4. С. 816–822.
     
  3. Кларк Ф. Оптимизация и негладкий анализ. М.: Гл. ред. физ.-мат. литры, 1988. 288 с.
     
  4. Демьянов В. Ф., Рубинов А. М. Основы негладкого анализа и квазидиффеpенциальное исчисление. М.: Наука, 1990. 431 с.
     
  5. Гоpоxовик B. B. Выпуклые и негладкие задачи векторной оптимизации. Mн.: Навyка i тэxнiка, 1990. 239 c. 
     
  6. Иоффе А. Д. О необходимых условиях минимума // Фундамент. и прикл. математика. 2014. Т. 19, № 4. С. 121–152.
     
  7. Фёдоров В. В. Численные методы максимина. М.: Наука, 1979. 280 c.
     
  8. Габасов Р., Шилкина Е. И. Прямой точный метод решения одного класса минимаксных задач // Докл. АН БССР. 1981. Т. 25, № 11. С. 971–973.
     
  9. Азизов И. Конечный алгоритм решения линейной максиминной задачи со связанными переменными и результаты численного эксперимента. Мн., 1984. 20 с. (Препр. / Ин-т математики АН БССР; № 18 (203)). 
     
  10. Габасов Р., Кириллова Ф. М., Костина Е. А. Глобальная максимизация специальных классов выпуклых функций на выпуклом многогранном множестве // Журн. вычисл. математики и мат. физики. 1992. Т. 32, № 8. С. 1313–1320.
     
  11. Гольштейн Е. Г. Теория двойственности в математическом программировании и её приложения. М.: Наука, 1971. 352 c.
     
  12. Габасов Р., Кириллова Ф. М., Тятюшкин А. И. Конструктивные методы оптимизации. Ч. 1. Линейные задачи. Мн.: Университетское, 1984. 214 с.
     
  13. Иванилов Ю. П. Двойственные полуигры // Изв. АН СCCР. Тех. кибернетика. 1972. № 4. С. 3–9.
     
  14. Гермейер Ю. Б. Игры с непротивоположными интересами. М.: Наука, 1976. 327 с.
     
  15. Лозовану Д. Д. Максиминные задачи со связанными переменными и их применения к исследованию и решению циклических игр // Изв. АН Респ. Молдова. Математика. 1990. № 2. С. 22–29.
     
  16. Falk J. E. Linear max-min problem // Math. Program. 1973. V. 5, No. 2. P. 169–188. DOI: 10.1007/BF01580119. 
     
  17. Liu J., Hong Y., Zheng Y. A branch and bound-based algorithm for the weak linear bilevel programming problems // Wuhan Univ. J. Nat. Sci. 2018. V. 23, No. 6. P. 480–486. DOI: 10.1007/s11859-018-1352-8.
     
  18. Маматов А. Р. Двойственный алгоритм вычисления локального оптимума одной максиминной задачи со связанными переменными // Узб. журн. «Пробл. информатики и энергетики». 2000. № 1. С. 7–12.
     
  19. Маматов А. Р. Необходимые условия оптимальности «высокого порядка» в линейной максиминной задаче со связанными переменными // Журн. вычисл. математики и мат. физики. 2010. Т. 50, № 6. С. 1017–1022.
     
  20. Маматов А. Р. Алгоритм решения одной игры двух лиц с передачей информации // Журн. вычисл. математики и мат. физики. 2006. Т. 46, № 10. С. 1784–1789.
     
  21. Габасов Р., Кириллова Ф. М., Альсевич В. В., Калинин А. И., Крахотко В. В., Павлёнок Н. С. Методы оптимизации. Мн.: Четыре четверти, 2011. 472 с.

Исследование выполнено за счёт бюджета Самаркандского государственного университета им. Ш. Рашидова.

Маматов Акмал Равшанович
  1. Самаркандский гос. университет им. Ш. Рашидова, 
    Университетский б-р, 15, 140104 Самарканд, Узбекистан

E-mail: akmm1964@rambler.ru

Статья поступила 16 августа 2023 г.
После доработки — 17 января 2024 г.
Принята к публикации 22 марта 2024 г.

Abstract:

A linear game problem for two players is considered. The two players alternately choose their strategies from their respective sets. First, player 1 chooses his/her strategy, then player 2, knowing the strategy of player 1, does the same. The set of strategies of player 2 depends on the strategy of player 1. The goal of player 1 is to choose a strategy to maximize a convex and piecewise linear function (the minimum function of the strategy of player 2). The goal of player 2 is to minimize the linear function. An algorithm is proposed that allows constructing strategies in this problem, as well as strategies in the dual problem, that satisfy necessary “higher-order” optimality conditions. This algorithm uses a formula for the increment of the objective function in the dual problem. Theorems that assert the finiteness of the proposed algorithm and its modification are proved. An example illustrating the operation of the algorithm is given. The results of a numerical experiment on the construction of strategies that satisfy the necessary “higher-order” optimality conditions in problems whose elements were generated by a random number generator are also presented. Based on the results of the numerical experiment, we can conclude that with the proposed algorithm, it is often possible to switch from one locally optimal strategy of player 1 to another one increasing the objective function. 
Tab. 1, illustr. 1, bibliogr. 21.

References:
  1. B. N. Pshenichnyi, Necessary Conditions for Extremum (Nauka, Moscow, 1982) [Russian].
     
  2. B. Sh. Mordukhovich, On necessary conditions for an extremum in nonsmooth optimization, Dokl. Akad. Nauk SSSR 283 (4), 816–822 (1985) [Russian] [Soviet Math. Dokl. 32, 215–220 (1985)].
     
  3. F. H. Clarke, Optimization and Nonsmooth Analysis (John Wiley & Sons, New York, 1983; Nauka, Moscow, 1988 [Russian]).
     
  4. V. F. Demyanov and A. M. Rubinov, Nonsmooth Analysis Foundations and Quasi-Differential Calculus (Nauka, Moscow, 1990) [Russian].
     
  5. V. V. Gorokhovik, Convex and Nonsmooth Vector Optimization Problems (Nauka Tekh., Minsk, 1990) [Russian]. 
     
  6. A. D. Ioffe, On necessary conditions for a minimum, Fundam. Prikl. Mat. 19 (4), 121–152 (2014) [Russian].
     
  7. V. V. Fyodorov, Numerical Maximin Methods (Nauka, Moscow, 1979) [Russian].
     
  8. R. Gabasov and E. I. Shilkina, A direct exact method for solving one class of minimax problems, Dokl. Akad. Nauk BSSR 25 (11), 971–973 (1981) [Russian].
     
  9. I. Azizov, A finite algorithm for solving a linear maximin problem with bound variables and results of a numerical experiment (Inst. Mat. AN BSSR, Minsk, 1984) (Prepr. № 18 (203)) [Russian].
     
  10. R. Gabasov, F. M. Kirillova, and E. A. Kostina, Global maximization of special classes of convex functions on a convex polyhedral set, Zh. Vychisl. Mat Mat. Fiz. 32 (8), 1313–1320 (1992) [Russian] [Comput. Math. Math. Phys. 32 (8), 1171-1177 (1992)].
     
  11. E. G. Golshtein, Duality Theory in Mathematical Programming and Its Aplications (Nauka, Moscow, 1971) [Russian].
     
  12. R. Gabasov, F. M. Kirillova, and A. I. Tyatyushkin, Constructive Optimization Methods. Pt. 1. Linear Problems (Universitetskoe, Minsk, 1984) [Russian].
     
  13. Yu. P. Ivanilov, Dual semi-games, Izv. Akad. Nauk SSSR, Tekh. Kibern., No. 4, 3–9 (1972) [Russian].
     
  14. Yu. B. Germeier, Games with Non-Opposite Interests (Nauka, Moscow, 1976) [Russian].
     
  15. D. D. Lozovanu, Maximin linear problems with connected variables and their applications to the study and solution of cyclic games, Bul. Acad. Ştiinţe Repub. Mold., Mat., No. 2, 22–29 (1990) [Russian].
     
  16. J. E. Falk, Linear max-min problem, Math. Program. 5 (2), 169–188 (1973), DOI: 10.1007/BF01580119.
     
  17. J. Liu, Y. Hong, and Y. Zheng, A branch and bound-based algorithm for the weak linear bilevel programming problems, Wuhan Univ. J. Nat. Sci. 23 (6), 480–486 (2018), DOI: 10.1007/s11859-018-1352-8.
     
  18. A. R. Mamatov, A dual algorithm for computing a local optimum in a linear maximin problem with coupled variables, Uzb. Zh. “Probl. Inform. Energ.”, No. 1, 7–12 (2000) [Russian].
     
  19. A. R. Mamatov, High-order necessary optimality conditions in a linear maxmin problem with coupled variables, Zh. Vychisl. Mat. Mat. Fiz. 50 (6), 1017–1022 (2010) [Russian] [Comput. Math. Math. Phys. 50 (6), 963–968 (2010)].
     
  20. A. R. Mamatov, An algorithm for solving a two-person game with information transfer, Zh. Vychisl. Mat. Mat. Fiz. 46 (10), 1784–1789 (2006) [Russian] [Comput. Math. Math. Phys. 46 (10), 1699–1704 (2006)].
     
  21. R. Gabasov, F. M. Kirillova, V. V. Alsevich, A. I. Kalinin, V. V. Krakhotko, and N. S. Pavlyonok, Optimization Methods (Chetyre Chetverti, Minsk, 2011) [Russian].