Автоматика и телемеханика, Л- 5, 2007
РАС Б 2.50.-1% 02.60.Pri
© 2007 г. А.И. КИВЗУН, д-р физ.-мат. наук (Московский авиационный институт)
РАСПАРАЛЛЕЛИВАНИЕ АЛГОРИТМОВ ОПТИМИЗАЦИИ ФУНКЦИИ КВАНТИЛИ1
Исследуется задача оптимизации для функции потерь, выпуклой отдельно по стратегии и по случайному вектору. Для решения задачи используется доверительный метод, с помощью которого получается верхняя оценка функции квантили. Рассматриваются два способа, с помощью которых можно получить искомую верхнюю оценку. Оба способа позволяют распараллелить процесс вычисления оценки, а задача сводится к решению набора задач выпуклого программирования.
1. Введение
В многочисленных задачах экономики и авиационной техники возникает функция квантили [1. 2]. которая характеризует гарантированные с заданной вероятностью потери. Например, такими критериями являются гарантированная с заданной вероятностью терминальная точность приведения некоторого объекта в цель и потери некоторого инвестора, непревышение которых гарантируется с заданной вероятностью, и др. Функция квантили с математической точки зрения оказывается довольно сложным объектом в отличие, скажем, от математического ожидания. Например, если функция потерь выпукла по стратегии, то из этого не следует выпуклость функции квантили, в то время как критерий в виде математического ожидания в этом случае оказывается выпуклым [3]. Поэтому трудно предложить эффективные вычислительные процедуры для решения задачи квантильной оптимизации. Для преодоления этой проблемы был предложен в [2] доверительный метод, сводящий задачу квантильной оптимизации к некоторой минимаксной. Этот метод, по сути, является методом регуляризации исходной стохастической задачи, некорректной. так как небольшие погрешности при вычислении вероятности приводят к значительным изменениям значения функции квантили.
Основные свойства функции квантили, а также разнообразные методы ее оптимизации. в том числе доверительный метод, приведены в [1]. В основе изложенных в [1] алгоритмов кваитилыюй оптимизации лежит построение стохастического квазиградиента вида [3]. а сами алгоритмы являются, по сути, рекуррентными, очень медленно сходящимися. Как известно, рекуррентные алгоритмы нельзя в принципе распараллелить, т.е. ускорить процесс решения, используя современную вычислительную технику.
В данной статье предлагаются два алгоритма получения верхних оценок для оптимального значения функции квантили, которые удается распараллелить. При
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (гранты № 04-01-00758, 05-08-17963).
этом рассматривается случай, когда функция потерь выпукла отдельно по стратегии и по случайному вектору, который имеет нормальное распределение. При этом исходно невыпуклая задача квантильной оптимизации сводится к решению набора задач выпуклого программирования, которые можно решать независимо друг от друга.
2. Постановка задачи
Пусть задана функция потерь Ф(и, х) : Мт х М" ^ М1, определенная для каждой стратегии и € и С Мт и каждой реализации х € М" случайного вектора X с известной функцией распределения Гх (х).
Рассмотрим функцию вероятности Р^(и) : и ^ [0,1], равную вероятности такого события, при котором потери Ф(и,Х) те превысят допустимый порог <р € М1:
(1) Р„(и) 4 Р{Х : Ф(и, X) < у}.
Рассмотрим также функцию квантили Фа(и) : и ^ М1, определяющую максимальные потери, непревышение которых гарантируется с вероятностью а € (0,1):
(2) Фа(и) = шт{у : Р„(и) > а}.
Пусть задача оптимизации заключается в минимизации функции квантили
(3) иа = а^штФа(и)
п^и
в предположении существования оптимальной стратегии иа.
Свойства непрерывности и полунепрерывности функций Р^(и), Фа(и), а также условия существования решений задачи (3) установлены в [1].
Для решения задачи (3) можно воспользоваться стохастическим квазиградиентным алгоритмом, введенным в [3] для минимизации средних потерь, следующего вида.
Пусть Хг, { = 1,^, - выборка объема N случайного вектора X ~ (х). По ней сформируем выборку Ф(и,Хг), { = 1,^ для фиксированной стратегии и € и. Построим вариационный ряд для полученной выборки
Ф^(и) < Ф^(и) < ... < ф^)(и).
Определим выборочную оценку функции квантили
(4) ФN (и) 4 Ф^]+1,
где [•] - означает целую часть.
Рассмотрим случайную последовательность
(5) ик+1 = Пи (ик — рк £к), к = 1, 2,...,
где Пи - оператор проецирования па множество и, рк - длина рабочего шага алгоритма, - стохастический квазиградиент:
£к 4 (ик1 ,...,ико + 5к ,...,икт )-Ф^ (ик ,...,ик6— 4 ,...,икт) е3 ,
к 3=1
где Nk - объем выборки на к-м шаге алгоритма, 5к - длина пробного шага, €3 - единичный орт, направленный вдоль з'-й оси, и>к^ з = 1,т, — независимые равномерно распределенные на [ик. — 5к ,ик. + 6к] случайные величины. Справедливо следующее утверждение [1].
Теорема 1. Пусть выполнены, следующие условия: (^ функция квантили Фа(и) выпукла на выпуклом компакте и; (И) функция квантили непрерывно дифференцируема на и; (Ш) последовательности рк удовлетворяет условиям:
ж
2
Рк > ° ^Рк = < ж
к=1 к=1 (гу) последовательности 5к и Nk удовлетворяют условиям
к(1+£)
5к ^ 0, Nk ^ ж, -р^--> 0 при к ^ж при некотором е > 0.
Ч^к
Тогда ик иа.
Замечание 1. Условия (1) и (и) труднопроверяемы. Но даже при их выполнении алгоритм (5) крайне медленно сходится, так как должны выполняться условия (ш) и (пт), накладываемые на последовательности рк,5кNк. Более того, стохастический квазиградиентный алгоритм (5) в принципе нельзя ускорить, используя какую-либо технику распараллеливания вычислений, так как он рекуррентный. Например если выбрать две начальные точки для алгоритма (5), то получатся две независимые задачи. Но так как в обеих задачах минимум один и тот же, то продолжительность работы такой пары алгоритмов будет определяться наиболее медленно сходящейся последовательностью в связи с тем, что заранее нельзя отдать предпочтение какому-либо алгоритму из двух. Рассмотрим другие способы решения задачи (3), позволяющие распараллелить процесс поиска оптимальной стратегии иа.
3. Доверительный метод
В [1] установлено, что задача (3) эквивалентна следующей минимаксной
(6) Фа(иа) = шт ф(Б,иБ),
где Та 4 {Б € Т, V(Б) ^ а} - семейство доверительных множеств, Т — а-алгебра борелевских множеств,
(7) Ф(Б,и) 4 яир Ф(и, х),
хея
(8) иБ = а^шш ф(Б,и).
п^и
Сведение задачи квантильной оптимизации (3) к эквивалентной минимаксной (6) (8) называется в [1] доверительным, методом. Заметим, что минимум в (6) достигается на оптимальном доверительном множестве
Ба 4 {х : Ф(иа,х) ^ Фа(иа)},
которое, правда, заранее неизвестно.
Важно, что для любого доверительного множества Б € Та можно получить минимаксную оценку сверху для неизвестного оптимального значения функции квантили
(9) Фа(иа) < ф(Б,ив) УБ €Та.
Замечание 2. Задача (8) записана при предположении, что ее решение пБ существует. Но доверительный метод справедлив и в более общем случае, когда не существуют па и пБ, а вместо задач (3) и (8) рассматриваются последовательности стратегий для поиска нижних граней соответствующих функций.
Перебирая различные Я € Та можно улучшать верхнюю оценку для Фа(па). Степень близости верхней оценки ф(Я,пБ) к Фа(па) можно определить, если известна нижняя оценка для Фа (па). С этой целью рассмотрим частный случай.
Пусть случайный вектор X имеет нормальное распре деление N (0,1), где I -единичная матрица, и функция потерь Ф(п, х) выпукла по х € К" для всех п € и.
Рассмотрим два шара Вр и Вп с центрами в начале координат и с радиусами р и К, удовлетворяющими условиям
(10) Р(Вп) = а, Р(XI < р) = а,
где Х1 - первая компонента вектора X ~ N(0, I). Таким образом, р - квантиль уровня а стандартного нормального распределения N(0,1), а Вп - доверительный шар, у которого радиус К определяется путем решения трансцендентного уравнения [1]
п
1 С .п-1
J е-1 ехр(-г2/2)сИ =
о
2("-2)/2Г(п/2)
где Г(-) - гамма функция.
В [1] содержится следующее утверждение.
Теорема 2. Если Ф(п,х) выпукла на К" для всех п € и, а X ~ N(0,1), то справедливы, следующие оценки
(И) ф(Вр,пр) < Фа(па) < ф(Вп,пп),
где пр и пп - решения минимаксной задачи (8) для множеств Вр и Вп соответственно, пр ич ем.
ф(Вп, пп) - ф(Вр ,пр) ^ 0 при а ^ 1.
Таким образом, по величине ф(Вп, пп)-ф(Вр, пр) можно судить о точности верхней оценки ф(Вп, пп). Более того, разница между этой верхней оценкой и минималь-
а
Замечание 3. Отметим, что приведенные нижняя и верхняя оценки для Фа (па) оказываются достигаемыми. Например, пусть
Ф(п, х) = ЬТ(п)х + с(п),
где Ь(п) - некоторая п-мерная векторная функция, а с(п) - скалярная функция. Тогда легко показать, что
ф(Вр, п) = тах Ф(п, х) = ||Ь(п)||р + с(п),
х£Бр
так как максимум рассматриваемой функции Ф(п, х) на Вр достигается в точке * = Ь(п)
х ЦЬ(п)Ц Р■
Кроме того, согласно [1] в данном случае можно найти явное выражение для функции квантили
Фа (и) = \\Ь(п)\\р + С(и).
Тогда нижняя оценка ф(Бр,ир) совпадет с оптимальным значением функции квантили
ф(Бр, иР) = Фа(иа), иР = иа. Рассмотрим теперь функцию потерь вида Ф(и,х) = Ь(и)д(\\х\\),
где д(-) : [0, то) ^ [0, то) - строго возрастающая функция, а Ь(и) > 0 - некоторая строго положительная функция. Тогда оптимальным доверительным множеством Ба будет шар Бп, так как
-1 ( Фа (и)
^а = {x : b(u)g(\\x\\) < Фа(и)} = { ||xH < ^ ( -g^L ) \ = Br
где нз условия нормировки найдено
я = д-' ( %г
Ь(и)
Значит, согласно (6)
Фа (и) = ф(Яа, и) = ф(Бп, и).
Поэтому верхняя оценка ф(Бп, ип) совпадает с оптимальным значением функции квантили
Фа(иа ) = ф(Бп,иП), иП = иа.
4. Алгоритм улучшения верхней оценки квантили
Пусть функция потерь Ф(и, x) выпукла отдельно по и G U и по x G 1". Примером такой функции может служить
I
(12) Ф(и, x) = max У^ (и)д^(x),
J ' г=1
где все (и), i = 1,1, j = 1, J, выпуклы по и G U и неотрицательны и все gij(x), i = 1,1, j = 1,J, выпуклы no x G 1" и неотрицательны. В частности, такими свойствами обладает кусочно-линейная функция
(13) Ф(и, x) = max {a1: и + bTx + еЛ ,
j=i,J j
где aj - вектор размерности т, a bj - вектор размерности п. Дан
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.