Автоматика и телемеханика, № 5, 2015
© 2015 г. Б.С. ДАРХОВСКИЙ, д-р физ.-мат. наук (darbor2004@mail.ru), Ю.С. ПОПКОВ, д-р техн. наук (popkov@isa.ru) (Институт системного анализа РАН, Москва, Московский физико-технический институт, Национальный исследовательский университет Высшая школа экономики, Москва), А.Ю. ПОПКОВ, канд. техн. наук (apopkov@isa.ru) (Институт системного анализа РАН, Москва, Московский физико-технический институт)
МЕТОД ПАКЕТНЫХ ИТЕРАЦИЙ МОНТЕ-КАРЛО: ВЕРОЯТНОСТНЫЕ ХАРАКТЕРИСТИКИ1
Предлагается метод приближенного решения систем нелинейных алгебраических уравнений и неравенств путем компьютерной генерации последовательности значений невязок этой системы, вычисляемых по наборам случайных векторов, генерируемых на каждом шаге алгоритма. Метод основан на пакетных итерациях, использующих простые испытания Монте-Карло. Доказывается сходимость почти наверное указанной последовательности к глобальному минимуму невязки с экспоненциальной скоростью. Получены вероятностные оценки отклонения значения невязки от ее глобального минимума для конечного числа итераций. Метод может применяться для приближенного решения систем уравнений и неравенств с алгоритмически заданными функциями, удовлетворяющими условию Гельдера.
1. Введение
Многие задачи теории управления, оценивания и прогнозирования сводятся к решению систем уравнений и неравенств, заданных алгоритмически. Последнее исключает возможность их аналитического исследования и постулирования каких-либо их количественных характеристик. В этой ситуации единственно возможным методом исследования является вычисление значений входящих в систему функций и анализ последовательности этих значений. Для генерирования таких последовательностей привлекается метод Монте-Карло, чему посвящены многочисленные публикации [1—8].
В данной статье предлагается метод формирования последовательности значений невязок исходной системы уравнений и неравенств, вычисляемых по наборам случайных векторов, генерируемых на каждом шаге алгоритма. Новизна и потенциальная эффективность метода состоит в следующем:
• метод ориентирован на приближенное решение систем алгебраических уравнений и неравенств с алгоритмически вычисляемыми функциями, удовлетворяющими условию Гёльдера, но с неизвестными константами;
1 Работа выполнена при поддержке Российского фонда фундаментальных исследований (проект № 13-07-00129).
• метод использует пакетные итерации (т.е. генерацию на каждом шаге алгоритма набора (пакета) независимых и равномерно распределенных на единичном кубе случайных векторов; при этом количество векторов в пакете увеличивается с увеличением номера шага алгоритма по определенному закону) и основан на предлагаемой (на базе априорных оценок) модели поведения декрементов невязок.
Для предлагаемого метода доказывается сходимость пакетных итераций почти наверное по функционалу с экспоненциальной скоростью, дана вероятностная оценка отклонения значения невязки от своего глобального минимума при конечном числе итераций и приведена оценка среднего времени работы алгоритма.
2. Общая идея метода
Продемонстрируем идею метода для задачи приближенного решения системы нелинейных алгебраических уравнений в случае, когда система неравенств задает единичный куб (далее будут указаны особенности метода для случая, когда система неравенств задана непрерывными функциями). Рассмотрим систему уравнений
(2.1) f(z)= 0, f € Rd, z € Z+ С Rd, на множестве
(2.2) Z+ = {z : 0 < z < 1}. Ставится задача
(2.3) F(z) =f ||f(z)||^ min на множестве Z+.
Функцию F(z) назовем невязкой системы (2.1) на множестве (2.2). Точку глобального минимума в задаче (2.3) естественно считать приближенным решением системы (2.1) на множестве (2.2). Отметим, что поскольку существование решения системы (2.1) на множестве (2.2) априори не известно, то значение глобального минимума в поставленной задаче также не известно.
Пусть функция F(z) удовлетворяет условию Гёльдера, т.е. существуют (но не известны) константы L и s такие, что модуль непрерывности
(2.4) w(h) = max |F(v) - F(y)| < Lhs.
(v,y)eZ+ :||v-y|Kh
Метод решения поставленной задачи представляет собой итерационную процедуру формирования последовательности значений минимумов и последовательности их декрементов.
На k-м шаге процедуры (k = 0,1,2,...) генерируется пакет Zk из Nk =f (Mk)d независимых и равномерно распределенных на Z+ случайных векторов {z1,..., zNk). Здесь Mk — число независимых и равномерно распределенных на отрезке [0, 1] случайных величин, которые на k-м шаге
датчик случайных чисел независимо генерирует по каждой из (I координат. Для к-го пакета вычисляются значения функции ^(г-7), ] = 1,^-, находится ее минимальное значение Г* и аргумент z*;. В силу случайного характера МК-испытаний значение целевой функции Г* — случайное.
Переход к (к + 1)-му шагу состоит в увеличении количества случайных векторов по правилу
(2.5) Мк+1 = аМк, а > 1,
и в нахождении нового минимума Г*+1 для (к + 1)-го пакета.
Наряду с последовательностью "квазиглобальных" минимумов формируется последовательность их декрементов
(2.6) и = {«!,..., ик,... },
где и = -
Процедура останавливается, когда последовательность случайных величин ик в течение р шагов остается в заданной ¿-окрестности нуля, т.е. количество шагов до остановки процедуры
(2.7) т = тт < к : тах ив ^ 5
к—р^в^к
Под решением задачи (2.3) понимается набор
(2.8) 5 = {Г* ъ*Т ,г+, Р(Е„+)},
где
• Г*, 2** — значения невязки и ее аргумента соответственно в момент остановки алгоритма;
• г+ — оценка отклонения невязки от ее глобального минимума в момент остановки алгоритма;
• событие
(2.9) Ег+т = {Г* - Г* < гТ+},
где Г * — значение глобального минимума невязки на множестве Z+;
• Р(£„+) — оценка вероятности события (2.9).
' т
Замечание 1. В реальном алгоритме используется строго монотонно убывающая подпоследовательность F* последовательности Т*. Приводимый далее теоретический анализ основан на исследовании последовательности Т*, для которой будут установлены почти наверное сходимость с экспоненциальной скоростью к теоретическому значению минимума Г * в задаче (2.3) и будут даны вероятностные оценки отклонения приближенного значения минимума от Г * в момент остановки алгоритма. В силу того что F* является подпоследовательностью Т*, эти выводы качественно не изменятся и для подпоследовательности F*.
3. Теоретический анализ свойств итерационной процедуры
3.1. Вероятностные характеристики пакета
Источником формирования пакета 2 является датчик случайных чисел, который на к-м шаге генерирует независимо по каждой из й координат массив из Мд независимых и равномерно распределенных на отрезке [0, 1] случайных величин (вариант простых испытаний Монте-Карло). В результате на к-м шаге формируется пакет (Мд)а случайных векторов, равномерно распределенных в единичном кубе.
Рассмотрим единичный куб Z+ (2.2) и его разбиение на элементарные кубы с помощью виртуальной равномерной решетки с шагом
(3.1) Пк = М-9 (0 <7 < д < в< 1)
по каждой из его й координат.
Обозначим через Р(Мд, й, д) вероятность того, что найдется элементарный виртуальный куб, который не содержит ни одного из (Мд)а сгенерированных на к-м шаге случайных векторов. Оценка для этой вероятности определяется следующей леммой.
Лемма 1. Имеет место оценка
( \ мк
(3.2) Р(Л4, (1, д) < ( Л/;.' + 1)<* И - = С} (А//,. (1, д). При к ^ то
(3.3) д(Мк, й, д) - Q(Mk, й, д) = М^ ехр (-Мд
Доказательство. Рассмотрим некоторый виртуальный элементарный куб объема (пдТак как генерируемые случайные векторы имеют равномерное распределение на единичном кубе и независимы, а их число на к-м шаге равно (Мкто вероятность того, что в данный элементарный виртуальный куб не попадет ни один из этих векторов, равна
мк 1
(3.4) (1 -(Щу ) ' = 1-
мк
М
А- ,
Пусть В — событие, состоящее в том, что такой элементарный виртуальный куб найдется. Тогда
(3.5) Р(В) < д(к, й, д) = (М9 + 1)М 1 -
\ мк 1 \
М?,
поскольку (Мд + 1)^ — верхняя оценка числа элементарных виртуальных
кубов со стороной щ = ттд по каждой координате.
мк
Так как
Um üf^ = 1,
x—
то в (3.5) при k ^ ж имеет место неравенство
(3.6) P(B) < Q(k, d, q) - Mkdq exp [~Mk(1-q)d) ,
что и требовалось установить.
Следствие 1. C вероятностью не менее чем 1 — Q(Mk, d, q) в каждый элементарный куб со стороной M-q попадает хотя бы один из сгенерированных на k-м шаге случайных векторов пакета.
3.2. Вероятностные свойства последовательности F*
Рассмотрим последовательность "квазиглобальных" минимумов F* = = {F*,..., F*... } и последовательность соответствующих аргументов Z* =
= {z*,...,z*,... }.
Пусть Z* — множество точек глобального минимума функции F(■) на единичном кубе. Введем расстояние l(-) от произвольной точки z до множества Z* (учитывая, что оно компактно):
(3.7) 1(z, Z*) d=f min ||z — y||.
yez*
Лемма 2. С вероятностью не менее чем 1 — Q(Mk, d, q) имеет место оценка
(3.8) 0 < Fk — F* < w(hk),
где w(-) — модуль непрерывности функции F(z) и hk = Щ Vd/2 (напомним, что F* — (неизвестное) значение глобального минимума функции F(■) на множестве Z+d).
Доказательство. Пусть z — ближайщая (в смысле введенного расстояния (3.7)) к множеству Z* точка из совокупности сгенерированных на k-м шаге случайных точек.
Так как в каждый виртуальный элементарный куб со стороной Пк попадает с вероятностью не менее чем 1 — Q(Mk, d, q) хотя бы одна из сгенерированных точек, то расстояние
Vd
(3.9) hk = ||z* -z|| ^ Пк— ■
Это произойдет, если точка z* € Z*, на которой реализуется расстояние до множества Z*, находится в центре куба со стороной щ, а ближайшие случайные точки расположились в вершинах этого куба, так что выполняется условие, что в каждом кубе есть хотя бы одна случайная точка.
Тогда в силу условия Гёльдера
(3.10) 0 < F(z) - F* < w(hfc). С другой стороны,
(3.11) F* = F(z*) = min F(z) < min F* < F* < F(z).
Из (3.11) получаем, что
(3.12) 0 < F* - F* < F(z) - F*. Окончательно (3.12) и (3.10) дают соотношение
(3.13) 0 < F* - F* < w(h*)
с вероятностью не менее чем 1 - Q(M*, d, q).
Следствие 2. Для функций, удовлетворяющих усл
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.