Максимин

численные методы- раздел вычислительной математики, посвященный решению максиминных (минимаксных) задач. Задачи вычисления максиминов и минимаксов часто возникают в исследовании операций и теории игр, напр. при использовании минимакса принципа или наибольшего гарантированного результата принципа. Исходной является задача вычисления М.: [img: http://localhost:8080/file/031403-8.jpg] возникающая, напр., при решении антагонистич. игр с полной информацией. Ее естественным обобщением является задача нахождения М. со "связанными" переменными: [img: http://localhost:8080/file/031403-9.jpg] причем множество В(х).часто задается в виде [img: http://localhost:8080/file/031403-10.jpg] для всякого [img: http://localhost:8080/file/031403-11.jpg] Эта задача оказывается основной в теории игр двух лиц с обменом информацией (см., напр., Игра с иерархической структурой). Итерирование исходной задачи приводит к задаче кратного, или последовательного, М.: [img: http://localhost:8080/file/031403-12.jpg] к-рая связана с решением нек-рых динамич. игр. Представляют интерес стохастич. задачи вычисления М., а также минимаксные задачи оптимального управления. В основе большинства способов решения минимаксных задач лежит градиентный метод или штрафных функций метод. При применении первого из них задачу (1) рассматривают как задачу оптимального программирования [img: http://localhost:8080/file/031403-13.jpg] где [img: http://localhost:8080/file/031403-14.jpg] Построение численных методов решения задачи (4) - (5) связано с дифференцируемостью по направлению функции минимума (5). Если [img: http://localhost:8080/file/031403-15.jpg] - компакт в [img: http://localhost:8080/file/031403-16.jpg] - производная по направлению [img: http://localhost:8080/file/031403-17.jpg] (см [1] - [3]), [img: http://localhost:8080/file/031403-18.jpg] то в случае конечного множества Yформула (6) позволяет построить итеративную последовательность x1, х2,..., в к-рой [img: http://localhost:8080/file/031403-19.jpg] для k=0,1,... и к-рая при нек-рых дополнительных предположениях сходится к точке, удовлетворяющей необходимому условию М. При использовании метода штрафных функций задача (1) для непрерывной на произведении компакта [img: http://localhost:8080/file/031403-20.jpg] и единичного куба [img: http://localhost:8080/file/031403-21.jpg] функции F(x, у).сводится к нахождению [img: http://localhost:8080/file/031403-22.jpg] где [img: http://localhost:8080/file/031403-23.jpg] (u - вспомогательная переменная). При этом если пара (u(с), х(с)).реализует максимум [img: http://localhost:8080/file/031403-24.jpg] то любая предельная точка (u*, х*).последовательности [img: http://localhost:8080/file/031403-25.jpg] дает величину [img: http://localhost:8080/file/031403-26.jpg] М.(1) и одну из оптимальных стратегий х*, для к-рой [img: http://localhost:8080/file/031403-27.jpg] (см. [4]). Тем самым решение задачи (1) с любой точностью сводится к отысканию максимума функции (7) при достаточно больших значениях штрафа с. Избежать трудностей, связанных с вычислением интегралов в (7), позволяет метод стохастич. градиента (см. [5], [8]): [img: http://localhost:8080/file/031403-28.jpg] где [img: http://localhost:8080/file/031403-29.jpg] - стохастич. градиент функции [img: http://localhost:8080/file/031403-30.jpg] т. е. случайная величина, математич. ожидание к-рой совпадает с [img: http://localhost:8080/file/031403-31.jpg] При нек-рых условиях, налагаемых на последовательности {ak} и {ck}и функцию F(х, у), для любого начального приближения (х 1, у 1).последовательность, определяемая процессом (8), с вероятностью 1 сходится к множеству решений задачи нахождения М. (1). Избежать больших значений параметра штрафа св (7) позволяет т. н. "метод невязок" (см. [61), представляющий собой еще один способ преобразования задачи (1). При этом величина и* М. (1) определяется как максимальное значение и, для к-рого [img: http://localhost:8080/file/031403-32.jpg] где [img: http://localhost:8080/file/031403-33.jpg] Здесь значение х*, реализующее [img: http://localhost:8080/file/031403-34.jpg] дает оптимальную стратегию в задаче (1). Отыскивать наибольший корень и* уравнения (9) можно, используя градиентные методы минимизации функции Ф по х. Методы преобразования задач, основанные на методе штрафных функций, позволяют приближение сводить к задачам на максимум минимаксные задачи со связанными переменными (2) (см. [7], [8]). Экстремальные задачи, к-рые получаются при сведении минимаксных задач к задачам на максимум, весьма сложны, и их решение известными методами сопряжено с большими, подчас непреодолимыми для современных ЭВМ трудностями. В особенности это относится к проблеме отыскания последовательных М. из (3) при большой кратности. Наряду с указанными общими подходами к решению минимаксных задач имеется ряд приемов, ориентированных на те или иные частные классы задач, напр. на задачи теории игр двух лиц с передачей информации (см. [6]).