1. На главную
  2. Электронные версии
  3. Журнал вычислительной математики и математической физики
  4. T. 61, № 2, 2021

Журнал вычислительной математики и математической физики, 2021, T. 61, № 2, стр. 312-344

Численные методы для задачи распределения ресурсов в компьютерной сети

Е. А. Воронцова 1, А. В. Гасников 1, 2, 3, П. Е. Двуреченский 3, 2, А. С. Иванова 4, *, Д. А. Пасечнюк 1

1 Московский физико-технический институт (национальный исследовательский университет)
141701 Долгопрудный, М.о., Институтский пер., 9, Россия

2 Институт проблем передачи информации им. А.А. Харкевича РАН
127051 Москва, Большой Каретный пер., 19, стр. 1, Россия

3 Институт прикладного анализа и стохастики им. К. Вейерштрасса
Берлин, Германия

4 Национальный исследовательский университет “Высшая школа экономики”
109028 Москва, Покровский бульвар, 11, Россия

* E-mail: asivanova@hse.ru

Поступила в редакцию 29.11.2019
После доработки 10.09.2020
Принята к публикации 16.09.2020

Полный текст (PDF)

Аннотация

Рассматривается задача распределения ресурсов в компьютерных сетях с большим числом соединений. Соединения используют для своих целей потребители (пользователи), число которых также может быть очень большим. Для решения двойственной задачи предлагаются следующие численные методы оптимизации: быстрый градиентный метод, стохастический метод проекции субградиента, метод эллипсоидов и метод экстраполяции случайного градиента. Для каждого метода получена оценка скорости сходимости. Также приведены алгоритмы распределенного вычисления шагов рассматриваемых методов при условии приложения их к компьютерным сетям. Отдельное внимание уделено прямо двойственности предложенных алгоритмов. Библ. 38. Фиг. 1. Табл. 2.

Ключевые слова: распределение ресурсов, сети связи, максимизация полезности сети, прямо двойственность, быстрый градиентный метод, стохастический метод проекции субградиента, метод эллипсоидов, метод экстраполяции случайного градиента.

1. ВВЕДЕНИЕ

1.1. Мотивация

Рассматривается задача управления современными сетями связи с точки зрения оптимизации и стохастического моделирования. Для решения задач такого рода необходимо представить и проанализировать математическую модель, возникающую при симуляции процесса работы крупномасштабных широкополосных сетей. Ожидается, что в будущих сетях связи появятся приложения, которые смогут изменять свои скорости передачи данных в соответствии с доступной пропускной способностью в сети. В качестве примера такой сети можно привести TCP-трафик через сеть Интернет.

Ключевой вопрос, который мы рассматриваем в этой статье, касается того, как доступная пропускная способность в сети должна быть распределена между конкурирующими потоками. При этом контроль над использованием потребителями доступных пропускных способностей осуществляется посредством корректировки цены на соединение.

Таким образом, в работе рассматривается задача оптимизации распределения ресурсов в компьютерных сетях с большим числом соединений. Соединения используют для своих целей потребители (пользователи), число которых также может быть очень большим. Цель работы состоит в определении механизма управления ресурсами, которые в контексте данной задачи являются доступными пропускными способностями соединений. При этом необходимо обеспечить стабильную работу системы и предотвратить перегрузки. В качестве критерия оптимальности используется сумма полезностей всех пользователей компьютерной сети.

Первоначально стандартные задачи распределения ресурсов, сводящиеся к максимизации совокупной полезности производителей при совместном использовании имеющихся ресурсов, были рассмотрены в [1], также задача распределения ресурсов в компьютерных сетях исследовалась в недавней работе [2]. Предложенные в монографии [3] механизмы децентрализованного распределения ресурсов с тех пор привлекают большое внимание в экономических исследованиях, см., например, [4]–[6] и ссылки в них. В данной работе, следуя [7], [8], мы рассматриваем различные механизмы корректировки цен. Практическую ценность предложенные подходы имеют за счет своей децентрализованности, что означает, что для установления и корректировки цены в отдельном соединении необходима только реакция пользователей, которые используют это соединение, а не реакция всех пользователей сети. При таком механизме корректировки все соединения действуют независимо.

Кроме того, один из предложенных в статье подходов, основанный на использовании стохастического метода проекции субградиента, обходит следующую проблему, возникающую в реальных сетях. Дело в том, что в реальных сетях пакеты с данными, которые поступают от пользователей на соединение, приходят не одновременно, поэтому на практике суммарный трафик на соединении неизвестен. Для решения этой проблемы предлагается использовать стохастические методы, для работы которых требуется не точное значение суммарного трафика, а только его оценка, которую можно получить на основе трафика одного из пользователей. Идея использовать для решения данной проблемы стохастический метод проекции субградиента предложена в работе [2].

1.2. Содержание

Статья организована следующим образом. В разд. 2 описаны постановка задачи и построение двойственной к ней. Также приводятся все необходимые предположения для прямой задачи. В разд. 3 рассматривается решение предложенной задачи быстрым градиентным методом Нестерова [9], получена оценка сложности данного метода, которая имеет порядок $O\left( {\tfrac{1}{{\sqrt \varepsilon }}} \right)$. В разд. 4 описано решение данной задачи с использованием стохастического метода проекции субградиента и приведены оценки сложности, которые имеют порядок $O\left( {\tfrac{1}{{{{\varepsilon }^{2}}}}} \right)$.

В разд. 5 описано решение задачи с использованием метода эллипсоидов, который хорошо подходит для задач небольшой размерности, также приведен алгоритм построения сертификата точности для данного метода. Приведены оценки сложности, которые имеют порядок $O\left( {{{m}^{2}}ln\tfrac{1}{\varepsilon }} \right)$, где $m$ – число соединений в сети. В разд. 6 описана техника регуляризации, которая позволяет восстанавливать решение прямой задачи по решению двойственной для не прямо двойственного метода. В разд. 7 описано решение регуляризованной задачи с использованием метода экстраполяции случайного градиента. Приведены оценки сложности, которые имеют порядок $O\left( {\tfrac{1}{{\sqrt \varepsilon }}ln\tfrac{1}{\varepsilon }} \right)$, где логарифмический множитель возникает за счет регуляризации двойственной задачи.

В разд. 8 приведено описание вычислительных экспериментов, подтверждающих на практике теоретические результаты, полученные в предыдущих разделах.

Также для каждого алгоритма описано его распределенное вычисление в контексте рассматриваемой задачи.

2. ПОСТАНОВКА ЗАДАЧИ

Рассмотрим компьютерную сеть с $m$ соединениями и $n$ пользователями (или узлами), см. фиг. 1.

Фиг. 1.

Пример компьютерной сети с $m = 6$ и $n = 3$.

Пользователи обмениваются пакетами через фиксированный набор соединений. Структура сети задана матрицей маршрутизации $C = (C_{i}^{j}) \in {{{\mathbf{R}}}^{{m \times n}}}$. Столбцы матрицы ${{{\mathbf{C}}}_{i}} \ne 0$, $i = 1, \ldots ,n$ – булевы $m$-мерные векторы такие, что $C_{i}^{j} = 1$ в случае использования узлом $i$ соединения $j$, в противном случае $C_{i}^{j} = 0$. Ограничения на пропускную способность соединений задаются вектором ${\mathbf{b}} \in {{{\mathbf{R}}}^{m}}$ со строго положительными компонентами.

Пользователи оценивают качество работы сети с помощью функций полезности ${{u}_{k}}({{x}_{k}})$, $k = 1, \ldots ,n$, где ${{x}_{k}} \in {{{\mathbf{R}}}_{ + }}$ – скорость передачи данных $k$-го пользователя. За критерий оптимальности системы принята сумма функций полезностей для всех пользователей [1].

Задача максимизации суммарной полезности сети при заданных ограничениях на пропускную способность соединений формулируется следующим образом:

(1)
$\mathop {max}\limits_{\left\{ {C{\mathbf{x}} = \sum\limits_{k = 1}^n \,{{{\mathbf{C}}}_{k}}{{x}_{k}}} \right\} \leqslant {\mathbf{b}}} \left\{ {U({\mathbf{x}}) = \sum\limits_{k = 1}^n \,{{u}_{k}}({{x}_{k}})} \right\},$
где ${\mathbf{x}} = ({{x}_{1}}, \ldots ,{{x}_{n}}) \in \mathbb{R}_{ + }^{n}$. Решением данной задачи будет оптимальное распределение ресурсов ${\mathbf{x}}{\kern 1pt} *$.

Рассмотрим стандартный переход к двойственной задаче для (1). Пусть задан вектор двойственных множителей $\lambda = ({{\lambda }_{1}}, \ldots ,{{\lambda }_{m}}) \in \mathbb{R}_{ + }^{m}$, который можно интерпретировать как вектор цен соединений. Определим двойственную целевую функцию

(2)
$\varphi (\lambda ) = \mathop {max}\limits_{{\mathbf{x}} \in {\mathbf{R}}_{ + }^{n}} \left\{ {\sum\limits_{k = 1}^n \,{{u}_{k}}({{x}_{k}}) + \left\langle {\lambda ,{\mathbf{b}} - \sum\limits_{k = 1}^n \,{{{\mathbf{C}}}_{k}}{{x}_{k}}} \right\rangle } \right\} = \left\langle {\lambda ,{\mathbf{b}}} \right\rangle + \sum\limits_{k = 1}^n \,\left( {{{u}_{k}}({{x}_{k}}(\lambda )) - \left\langle {\lambda ,{{{\mathbf{C}}}_{k}}{{x}_{k}}(\lambda )} \right\rangle } \right),$
причем пользователи выбирают оптимальные скорости передачи информации ${{x}_{k}}$, решая следующую задачу оптимизации:
(3)
${{x}_{k}}(\lambda ) = \mathop {arg\,max}\limits_{{{x}_{k}} \in {{{\mathbf{R}}}_{ + }}} \,\left\{ {{{u}_{k}}({{x}_{k}}) - {{x}_{k}}\left\langle {\lambda ,{{{\mathbf{C}}}_{k}}} \right\rangle } \right\}.$
Обозначим также за ${\mathbf{x}}(\lambda )$ вектор с компонентами ${{x}_{k}}(\lambda )$. Тогда для нахождения оптимальных цен $\lambda {\kern 1pt} *$ требуется решить задачу

(4)
$\mathop {min}\limits_{\lambda \in {\mathbf{R}}_{ + }^{m}} \varphi (\lambda ).$

Предположим, что для прямой задачи выполняется условие Слейтера, тогда в силу сильной двойственности и прямая, и двойственная задачи будут иметь решение. Используя условие Слейтера, можно компактифицировать решение двойственной задачи. Будем предполагать, что для решения двойственной задачи верна следующая оценка:

${{\left\| {\lambda {\kern 1pt} *} \right\|}_{2}} \leqslant R.$
При этом значение $R$ никак не влияет на работу рассматриваемых алгоритмов, а только присутствует в оценках скорости их сходимости.

Основная идея данной работы заключается в применении различных оптимизационных методов для решения двойственной задачи (4) с добавлением прямо двойственного анализа этих методов, позволяющего также восстановить решение прямой задачи (1). В этом смысле мы развиваем подход наших предыдущих работ [10]–[21]. Основное отличие состоит в рассмотрении ограничений-неравенств, а также в анализе стохастических алгоритмов в смысле оценок с большой вероятностью, а не в среднем.

2.1. Сильно вогнутые функции полезности

В некоторых разделах мы будем предполагать, что функции полезности ${{u}_{k}}({{x}_{k}})$, $k = 1, \ldots ,n$, являются сильно вогнутыми с константой $\mu $. В данном подразделе опишем, какими свойствами будет обладать двойственная задача при таком предположении.

Утверждение 1 (Теорема Демьянова–Данскина–Рубинова, см. [22], [23]). Пусть для любого $\lambda \in {{\mathbb{R}}_{ + }}$ выполняется $\varphi (\lambda ) = \mathop {max}\limits_{{\mathbf{x}} \in X} F({\mathbf{x}},\lambda )$, где $F({\mathbf{x}},\lambda )$ – выпуклая и гладкая по $\lambda $ функция и максимум достигается в единственной точке $x(\lambda )$. Тогда $\nabla \varphi (\lambda ) = {{\nabla }_{\lambda }}F(x(\lambda ),\lambda )$.

Утверждение 2 (см. [24]). Пусть для любого $k = 1, \ldots ,n$ функции ${{u}_{k}}({{x}_{k}})$ являются $\mu $-сильно вогнутыми. Тогда функция (2), где ${{x}_{k}}(\lambda ),$ $k = 1, \ldots ,n$, являются решением задачи (3), будет $n{{m}^{2}}{\text{/}}\mu $-гладкой, т.е. градиент функции $\varphi (\lambda )$ будет удовлетворять условию Липшица с константой $L = n{{m}^{2}}{\text{/}}\mu $:

$\mathop {\left| {\left| {\nabla \varphi ({{\lambda }^{2}}) - \nabla \varphi ({{\lambda }^{1}})} \right|} \right|}\nolimits_2 \leqslant L{{\left\| {{{\lambda }^{2}} - {{\lambda }^{1}}} \right\|}_{2}}.$

Доказательство утверждения можно найти ниже в Приложении.

2.2. Вогнутые функции полезности

Теперь предположим, что функции полезности ${{u}_{k}}({{x}_{k}})$, $k = 1, \ldots ,n$, являются вогнутыми, но не сильно вогнутыми. Тогда двойственная задача не является гладкой. В данном подразделе описаны некоторые свойства субградиентов двойственной задачи при таких предположениях.

Субградиент двойственной задачи (4) определяется следующим образом:

$\nabla \varphi (\lambda ) = {\mathbf{b}} - C{\mathbf{x}}.$
Учитывая, что ${\mathbf{x}}$ – ограниченная скорость передачи информации и вектор ${\mathbf{b}}$ также ограничен, получаем, что субградиенты двойственной задачи в данном случае ограничены. Таким образом, существует такая положительная константа $M$, что верна следующая оценка:
(5)
${{\left\| {\nabla \varphi (\lambda )} \right\|}_{2}} \leqslant M.$
В качестве грубой оценки сверху для константы $M$ из (5) можно использовать $O(n\sqrt m )$. Множитель $n$ возникает из-за того, что есть $n$ слагаемых, а $\sqrt m $ используется как оценка зависимости $2$-нормы от размерности вектора $m$.

3. БЫСТРЫЙ ГРАДИЕНТНЫЙ МЕТОД

В данном разделе мы предполагаем, что функции полезности ${{u}_{k}}({{x}_{k}})$, $k = 1, \ldots ,n$, являются сильно вогнутыми с константой $\mu $, следовательно, двойственная задача будет гладкой.

Для решения двойственной задачи (4) применим быстрый градиентный метод (БГМ) Нестерова в следующем варианте (метод PDFGM, см. алгоритм 1).

Aлгоритм 1. Прямо двойственный быстрый градиентный метод (PDFGM)

Вход: ${{u}_{k}}({\mathbf{x}}),$ $k = 1, \ldots ,n$ – сильно вогнутые функции полезности для каждого пользователя; ${{\lambda }^{0}}$ – вектор начальных цен, ${{\alpha }_{t}}: = \tfrac{{t + 1}}{2}$, ${{A}_{{ - 1}}}: = 0$, ${{A}_{t}}: = {{A}_{{t - 1}}} + {{\alpha }_{t}} = \tfrac{{(t + 1)(t + 2)}}{4}$, ${{\tau }_{t}}: = \tfrac{{{{\alpha }_{{t + 1}}}}}{{{{A}_{{t + 1}}}}} = \tfrac{2}{{t + 3}}$, $t = 0,1, \ldots ,N - 1$.

1: for $t = 0,1, \ldots ,N - 1$

2:  Вычислить $\varphi ({{\lambda }^{t}})$, $\nabla \varphi ({{\lambda }^{t}})$

3:  ${{{\mathbf{y}}}^{t}}: = \mathop {\left[ {{{\lambda }^{t}} - \tfrac{1}{L}\left( {{\mathbf{b}} - \sum\nolimits_{k = 1}^n {{{{\mathbf{C}}}_{k}}{{x}_{k}}({{\lambda }^{t}})} } \right)} \right]}\nolimits_ + $

4:  ${{{\mathbf{z}}}^{t}}: = \mathop {\left[ {{{\lambda }^{0}} - \tfrac{1}{L}\sum\nolimits_{j = 0}^t {{{\alpha }_{j}}} \left( {{\mathbf{b}} - \sum\nolimits_{k = 1}^n {{{{\mathbf{C}}}_{k}}{{x}_{k}}({{\lambda }^{j}})} } \right)} \right]}\nolimits_ + .$

5:  ${{\lambda }^{{t + 1}}}: = {{\tau }_{t}}{{{\mathbf{z}}}^{t}} + (1 - {{\tau }_{t}}){{{\mathbf{y}}}^{t}}$

6:  ${{{\mathbf{\hat {x}}}}^{{t + 1}}}: = \tfrac{1}{{{{A}_{{t + 1}}}}}\sum\nolimits_{j = 0}^{t + 1} {{{\alpha }_{j}}{\mathbf{x}}({{\lambda }^{{\mathbf{j}}}})} $

7: end for

8: return ${{\lambda }^{N}}$, ${{{\mathbf{\hat {x}}}}^{N}}$

3.1. Распределенный метод

Для решения рассматриваемой задачи можно также применить БГМ в распределенном варианте, что означает, что каждое соединение может вычислять оптимальную скорость передачи данных только исходя из реакции пользователей, которые используют данное соединение, и никак не взаимодействовать с другими соединениями.

Опишем процесс, происходящий на $t$-й итерации для соединения $j$.

1. На основе информации, полученной от пользователей после предыдущей итерации с номером $t - 1$ (вектор ${{{\mathbf{x}}}^{t}} = {\mathbf{x}}({{\lambda }^{t}})$), соединение $j$ вычисляет

$y_{j}^{t} = \mathop {\left[ {\lambda _{j}^{t} - \frac{1}{L}\left( {{{b}_{j}} - \sum\limits_{k = 1}^n \,C_{k}^{j}x_{k}^{t}} \right)} \right]}\nolimits_ + .$
При этом $C_{k}^{j} \ne 0$ только для тех пользователей, которые используют соединение $j$. Поэтому для вычисления этого шага соединению нужна только информация от пользователей, которые используют это соединение.

2. Далее соединение $j$ аналогично вычисляет

$z_{j}^{t} = \mathop {\left[ {\lambda _{j}^{0} - \frac{{{{\alpha }_{j}}}}{L}\left( {{{b}_{j}} - \sum\limits_{k = 1}^n \,C_{k}^{j}x_{k}^{t}} \right)} \right]}\nolimits_ + .$

3. Получив значения на предыдущих двух шагах, соединение $j$ вычисляет цену для следующей итерации $t + 1$:

$\lambda _{j}^{{t + 1}} = {{\tau }_{t}}z_{j}^{t} + (1 - {{\tau }_{t}})y_{j}^{t}$
и посылает эту информацию всем пользователям, которые с ним соединены.

4. Далее пользователи вычисляют оптимальные скорости передачи информации ${{{\mathbf{\hat {x}}}}^{{t + 1}}}$, в частности, для пользователя $k$ получаем

${{x}_{k}}({{\lambda }^{{t + 1}}}) = \mathop {arg\,max}\limits_{{{x}_{k}} \in {{{\mathbf{R}}}_{ + }}} \,\left( {{{u}_{k}}({{x}_{k}}) - {{x}_{k}}\sum\limits_{j = 1}^m \,\lambda _{j}^{{t + 1}}C_{k}^{j}} \right),$
где в силу определения матрицы $C$ пользователю необходима информация только от соединений, которые он использует. Далее пользователь вычисляет оптимальную скорость

$\hat {x}_{k}^{{t + 1}} = \frac{{{{A}_{t}}\hat {x}_{k}^{t} + x_{k}^{{t + 1}}}}{{{{A}_{{t + 1}}}}}.$

Замечание 1. Минусом данного алгоритма является то, что каждому соединению необходимо знать реакции всех пользователей, которые его используют на каждой итерации. К сожалению, в реальных сетях пользователи отправляют данные неодновременно, поэтому достаточно сложно собрать данную информацию для соединения. Однако наличие полной информации о пользователях позволяет соединению быстрее устанавливать равновесную цену.

3.2. Оценка скорости сходимости БГМ

Прежде чем привести доказательство сходимости БГМ для рассматриваемой задачи, сформулируем ключевую лемму, необходимую для получения оценок невязки в ограничениях и зазора двойственности после работы прямо двойственного метода PDFGM.

Лемма 1. Пусть алгоритм 1 начинает свою работу с начальной точки ${{\lambda }^{0}}$, которая лежит в евклидовом шаре радиуса $R$ с центром в начале координат. Тогда после $N$ итераций алгоритма 1 будет выполняться следующее неравенство:

(6)
${{A}_{N}}\varphi ({{{\mathbf{y}}}^{N}}) - {{A}_{N}}U({{{\mathbf{\hat {x}}}}^{N}}) + 2\hat {R}{{A}_{N}}\mathop {\left\| {\mathop {(C{{{{\mathbf{\hat {x}}}}}^{N}} - {\mathbf{b}})}\nolimits_ + } \right\|}\nolimits_2 \leqslant \tfrac{{37L{{{\hat {R}}}^{2}}}}{9},$
где ${{{\mathbf{\hat {x}}}}^{N}} = \tfrac{1}{{{{A}_{N}}}}\sum\nolimits_{t = 0}^{N - 1} {{{\alpha }_{t}}{\mathbf{x}}({{\lambda }^{t}})} $ и $\hat {R} = 3R$.

Доказательство леммы можно найти в Приложении.

Теперь сформулируем теорему об оценке скорости сходимости алгоритма 1.

Теорема 1. Пусть алгоритм 1 начинает свою работу с начальной точки ${{\lambda }^{0}}$, которая лежит в евклидовом шаре радиуса $R$ с центром в начале координат. Тогда после

$N = \left\lceil {\frac{{2\hat {R}}}{3}\sqrt {\frac{{37L}}{\varepsilon }} } \right\rceil $
итераций алгоритма 1 будут выполняться следующие неравенства:
$U({\mathbf{x}}{\kern 1pt} *) - U({{{\mathbf{\hat {x}}}}^{N}}) \leqslant \varepsilon ,\quad \mathop {\left\| {\mathop {(C{{{{\mathbf{\hat {x}}}}}^{N}} - {\mathbf{b}})}\nolimits_ + } \right\|}\nolimits_2 \leqslant \frac{\varepsilon }{{\hat {R}}},$
где ${{{\mathbf{\hat {x}}}}^{N}} = \tfrac{1}{{{{A}_{N}}}}\sum\nolimits_{t = 0}^{N - 1} {{{\alpha }_{t}}{\mathbf{x}}({{\lambda }^{t}})} $, ${{{\mathbf{x}}}^{ * }}$ – оптимальное решение задачи (1), $\hat {R} = 3R$.

Доказательство. Обозначим оптимальное значение исходной прямой задачи (1) $\operatorname{Opt} [P]$, а оптимальное значение двойственной задачи (4) – $\operatorname{Opt} [D]$. В силу слабой двойственности имеем

$\operatorname{Opt} [D] \geqslant \operatorname{Opt} [P].$
Кроме того, для всех ${\mathbf{x}} \in \mathbb{R}_{ + }^{n}$ и оптимального решения двойственной задачи (4) $\lambda {\kern 1pt} *$ получаем
(7)
$\operatorname{Opt} [P] \geqslant U({\mathbf{x}}) - \left\langle {\lambda {\kern 1pt} *,\mathop {\left( {\sum\limits_{k = 1}^n \,{{{\mathbf{C}}}_{k}}{{x}_{k}} - {\mathbf{b}}} \right)}\nolimits_ + } \right\rangle \geqslant U({\mathbf{x}}) - \hat {R}\mathop {\left\| {\mathop {(C{\mathbf{x}} - {\mathbf{b}})}\nolimits_ + } \right\|}\nolimits_2 .$
Тогда
$\begin{gathered} \varphi ({{{\mathbf{y}}}^{N}}) - U({{{{\mathbf{\hat {x}}}}}^{N}}) = \varphi ({{{\mathbf{y}}}^{N}}) - U({{{{\mathbf{\hat {x}}}}}^{N}}) + \operatorname{Opt} \text{[}P] - \operatorname{Opt} [P] + \operatorname{Opt} [D] - \operatorname{Opt} [D] = \underbrace {(\operatorname{Opt} [D] - \operatorname{Opt} [P])}_{ \geqslant 0} + \\ \, + (\operatorname{Opt} [P] - U({{{{\mathbf{\hat {x}}}}}^{N}})) + \underbrace {(\varphi ({{{\mathbf{y}}}^{N}}) - \operatorname{Opt} [D])}_{ \geqslant 0}\;\mathop \geqslant \limits^{(7)} \; - {\kern 1pt} \left\langle {\lambda {\kern 1pt} *,{{{({\mathbf{b}} - C{{{{\mathbf{\hat {x}}}}}^{N}})}}_{ + }}} \right\rangle \geqslant - \hat {R}{\kern 1pt} {{\left\| {{{{(C{{{{\mathbf{\hat {x}}}}}^{N}} - {\mathbf{b}})}}_{ + }}} \right\|}_{2}}. \\ \end{gathered} $
После подстановки последнего неравенства в (6) получим следующую оценку:
$\hat {R}{{\left\| {{{{(C{{{{\mathbf{\hat {x}}}}}^{N}} - {\mathbf{b}})}}_{ + }}} \right\|}_{2}} \leqslant \frac{{37L{{{\hat {R}}}^{2}}}}{{9{{A}_{N}}}}.$
Следовательно, $\varphi ({{{\mathbf{y}}}^{N}}) - U({{{\mathbf{\hat {x}}}}^{N}}) \geqslant - \tfrac{{37L{{{\hat {R}}}^{2}}}}{{9{{A}_{N}}}}$. С другой стороны, из (6) следует, что $\varphi ({{{\mathbf{y}}}^{N}}) - U({{{\mathbf{\hat {x}}}}^{N}}) \leqslant \tfrac{{37L{{{\hat {R}}}^{2}}}}{{9{{A}_{N}}}}$. Поэтому
$\left| {\varphi ({{{\mathbf{y}}}^{N}}) - U({{{{\mathbf{\hat {x}}}}}^{N}})} \right| \leqslant \frac{{37L{{{\hat {R}}}^{2}}}}{{9{{A}_{N}}}}.$
Так как $\varphi ({{{\mathbf{y}}}^{N}}) \geqslant \operatorname{Opt} [D] = \varphi ({\mathbf{y}}{\kern 1pt} *) \geqslant \operatorname{Opt} [P] = U({\mathbf{x}}{\kern 1pt} *)$, выполняется следующее неравенство:
$U({\mathbf{x}}{\kern 1pt} *) - U({{{\mathbf{\hat {x}}}}^{N}}) \leqslant \frac{{37L{{{\hat {R}}}^{2}}}}{{9{{A}_{N}}}} = \frac{{148L{{{\hat {R}}}^{2}}}}{{9(N + 1)(N + 2)}} \leqslant \frac{{148L{{{\hat {R}}}^{2}}}}{{9{{N}^{2}}}} \leqslant \varepsilon .$
Выражая из последнего неравенства $N$, получаем оценку из условия теоремы.

4. СТОХАСТИЧЕСКИЙ МЕТОД ПРОЕКЦИИ СУБГРАДИЕНТА

Рассмотрим исходную задачу (1), но теперь предположим, что функции полезности ${{u}_{k}}({{x}_{k}})$, $k = 1, \ldots ,n$, вогнуты, но не сильно вогнуты. В этом случае двойственная задача (4) становится негладкой. Поэтому для ее решения предлагается применить стохастический метод проекции субградиента. Впервые идея использовать для решения данной проблемы стохастический метод проекции субградиента предложена в работе [2].

Рассмотрим вероятностное пространство $\left( {\Omega ,\mathcal{F},\mathbb{P}} \right)$. Пусть на нем определена последовательность независимых случайных величин $\{ {{\xi }^{t}}\} _{{t = 0}}^{\infty }$, равномерно распределенных на $\{ 1, \ldots ,n\} $, т.е.

$\mathbb{P}({{\xi }^{t}} = i) = \frac{1}{n},\quad i \in \{ 1, \ldots ,n\} .$

Если доступен оракул, выдающий стохастический субградиент двойственной функции $\nabla \varphi (\lambda ,\xi )$:

$\nabla \varphi (\lambda ,\xi ) = {\mathbf{b}} - n{{C}_{\xi }}{{x}_{\xi }}(\lambda ),$
то имеем

$\mathbb{E}{\kern 1pt} [{\mathbf{b}} - n{{C}_{{{{\xi }_{t}}}}}{{x}_{{{{\xi }_{t}}}}}({{\lambda }^{t}})\,{\text{|}}\,{{\xi }^{t}}] = {\mathbf{b}} - \sum\limits_{k = 1}^n \,{{{\mathbf{C}}}_{k}}{{x}_{k}}({{\lambda }^{t}}) = \nabla \varphi ({{\lambda }^{t}})$

Aлгоритм 2. Прямо двойственный стохастический метод проекции субградиента (PDSSGM), версия 1

Вход: ${{u}_{k}}({\mathbf{x}}),$ $k = 1, \ldots ,n$ – вогнутые функции полезности для каждого пользователя; $\beta $ – шаг метода.

1: ${{\lambda }^{0}}: = {\mathbf{0}}$

2: for $t = 1, \ldots ,N - 1$

3:  Вычислить $\nabla \varphi ({{\lambda }^{{t - 1}}},\xi )$

4:  ${{\lambda }^{t}}: = {{[{{\lambda }^{{t - 1}}} - \beta ({\mathbf{b}} - n{{C}_{{{{\xi }^{{t - 1}}}}}}{{x}_{{{{\xi }^{{t - 1}}}}}}({{\lambda }^{{t - 1}}}))]}_{ + }}$

5:  ${{{\mathbf{\hat {x}}}}^{{t + 1}}}: = \tfrac{1}{{t + 1}}\sum\nolimits_{j = 0}^t {{\mathbf{x}}({{\lambda }^{j}})} $

6:  ${{\hat {\lambda }}^{{t + 1}}}: = \tfrac{1}{{t + 1}}\sum\nolimits_{j = 0}^t {{{\lambda }^{j}}} $

7: end for

8: return ${{\hat {\lambda }}^{N}},\;{{{\mathbf{\hat {x}}}}^{N}}$

Следовательно, стохастический субградиент является несмещенной оценкой субградиента.

Оптимальное решение задачи (2) будем искать с помощью прямо двойственного стохастического метода проекции субградиента PDSSGM. Приведем описание двух версий данного метода, см. алгоритм 2 и алгоритм 3. В алгоритме 2 используется полная модель восстановления вектора ${\mathbf{x}}(\lambda )$ на каждой итерации. Однако вычисление вектора ${\mathbf{x}}(\lambda )$ по сложности практически эквивалентно вычислению полного субградиента $\varphi (\lambda )$. Поэтому основным алгоритмом является алгоритм 3, в котором для восстановления вектора ${\mathbf{x}}(\lambda )$ используется неполная, стохастическая модель, что означает, что на каждой итерации пересчитывается только одна компонента вектора ${\mathbf{x}}(\lambda )$, остальные остаются без изменений. При доказательстве теоремы сходимости мы сначала показываем оценку скорости сходимости для алгоритма 2, а затем показываем, что приближенное решение прямой задачи, полученное в алгоритме 3, близко по точности к решению, полученному в алгоритме 2.

Aлгоритм 3. Прямо двойственный стохастический метод проекции субградиента (PDSSGM), версия 2

Вход: ${{u}_{k}}({\mathbf{x}}),$ $k = 1, \ldots ,n$ – вогнутые функции полезности для каждого пользователя; $\beta $ – шаг метода.

1: ${{\lambda }^{0}}: = {\mathbf{0}}$

2: for $t = 1, \ldots ,N - 1$

3:  Вычислить $\nabla \varphi ({{\lambda }^{{t - 1}}},\xi )$

4:  ${{\lambda }^{t}}: = {{[{{\lambda }^{{t - 1}}} - \beta ({\mathbf{b}} - n{{C}_{{{{\xi }^{{t - 1}}}}}}{{x}_{{{{\xi }^{{t - 1}}}}}}({{\lambda }^{{t - 1}}}))]}_{ + }}$

5:  ${\mathbf{\tilde {x}}}_{{{{\xi }^{t}}}}^{{t + 1}}: = \tfrac{t}{{t + 1}}{\mathbf{\tilde {x}}}_{{{{\xi }^{t}}}}^{t} + \tfrac{1}{{t + 1}}n{{x}_{{{{\xi }^{t}}}}}({{\lambda }^{t}})$, ${\mathbf{\tilde {x}}}_{j}^{{t + 1}}: = {\mathbf{\tilde {x}}}_{j}^{t}$ при $j \ne {{\xi }^{t}}$

6:  ${{\hat {\lambda }}^{{t + 1}}}: = \tfrac{1}{{t + 1}}\sum\nolimits_{j = 0}^t {{{\lambda }^{j}}} $

7: end for

8: return ${{\hat {\lambda }}^{N}},\;{{{\mathbf{\tilde {x}}}}^{N}}$

4.1. Распределенный метод

Рассмотрим, как можно применить для решения рассматриваемой задачи стохастический метод проекции субградиента в распределенном варианте.

Опишем процесс, происходящий на $t$-й итерации для соединения $j$:

1. На основе информации, полученной от соединений после предыдущей итерации с номером $t - 1$, случайный пользователь ${{\xi }^{t}}$ передает данные с оптимальной скоростью

${{x}_{{{{\xi }^{t}}}}}({{\lambda }^{{t + 1}}}) = \mathop {arg\,max}\limits_{{{x}_{{{{\xi }^{t}}}}} \in {{{\mathbf{R}}}_{ + }}} \,\left( {{{u}_{{{{\xi }^{t}}}}}({{x}_{{{{\xi }^{t}}}}}) - {{x}_{{{{\xi }^{t}}}}}\sum\limits_{j = 1}^m \,\lambda _{j}^{{t + 1}}C_{{{{\xi }^{t}}}}^{j}} \right),$
где в силу определения матрицы $C$ пользователю необходима информация только от соединений, которые он использует.

2. Далее соединение $j$ вычисляет цену на следующую итерацию на основе реакции этого пользователя:

$\lambda _{j}^{{t + 1}} = {{[\lambda _{j}^{t} - \beta ({{b}_{j}} - nC_{{{{\xi }^{t}}}}^{j}x_{{{{\xi }^{t}}}}^{t})]}_{ + }}.$
При этом $C_{{{{\xi }^{t}}}}^{j} \ne 0$ только для тех пользователей, которые используют соединение $j$. Поэтому цена поменяется только для актуальных соединений пользователя, который передал данные.

Замечание 2. Главное преимущество данного метода заключается в том, что соединение меняет цену только на основе реакции одного пользователя, что гораздо больше приближает постановку задачи к ситуации в реальных сетях, в которых пользователи отправляют данные не одновременно.

4.2. Оценка скорости сходимости для стохастического метода проекции субградиента

Прежде чем перейти к доказательству основной теоремы об оценках скорости сходимости предложенных методов, приведем необходимые предположения для решаемой задачи. Предположим, что существует положительная константа $M = O(n\sqrt m )$ такая, что верна следующая оценка:

(8)
${{\left\| {\nabla \varphi (\lambda ,\xi )} \right\|}_{2}} \leqslant M.$
Данное предположение корректно в силу того, что скорость передачи информации ${\mathbf{x}}$ ограничена и вектор пропускных способностей ${\mathbf{b}}$ также ограничен в силу физических соображений. Поэтому, исходя из определения стохастического субградиента, он ограничен.

Также предположим, что

$\mathbb{E}\left[ {exp\left( {\frac{{\mathop {\left\| {\nabla \varphi (\lambda ,\xi ) - \nabla \varphi (\lambda )} \right\|}\nolimits_2^2 }}{{{{\sigma }^{2}}}}} \right)} \right] \leqslant exp(1),$
где $\sigma $ – положительная числовая константа, порядок зависимости от $n$ и $m$ такой же, как у $M$.

Для получения оценки скорости сходимости алгоритма 9 необходимо предположение о том, что функции ${{u}_{k}}({{x}_{k}}),k = 1, \ldots ,n$, являются липшицевыми с константой ${{M}_{{{{u}_{k}}}}}$, тогда функция $U({\mathbf{x}})$ будет липшицевой с некоторой константой ${{M}_{U}}$:

$\forall {\mathbf{x}},{\mathbf{y}}\quad \left| {U({\mathbf{x}}) - U({\mathbf{y}})} \right| \leqslant {{M}_{U}}{{\left\| {{\mathbf{x}} - {\mathbf{y}}} \right\|}_{2}},$
при этом ${{M}_{U}} = O(\sqrt n )$. Может оказаться, что функция ${{u}_{k}}({{x}_{k}})$ липшицева везде, кроме, например, точки $0$. Примером такой функции является одна из наиболее распространенных функций полезности пользователей ${{u}_{k}}({{x}_{k}}) = ln{{x}_{k}}$. Но в силу специфики рассматриваемой задачи всегда существуют $\bar {\varepsilon } > 0$, $\underline \varepsilon > 0$ такие, что $x_{k}^{*} \geqslant \underline \varepsilon $, $x_{k}^{*} \leqslant \bar {\varepsilon }$. Тогда задачу можно решать на компакте $Q = \left\{ {{\mathbf{x}}:\underline \varepsilon \leqslant {{x}_{k}} \leqslant \bar {\varepsilon },\;k = 1, \ldots ,n} \right\}$, и рассматриваемая функция ${{u}_{k}}({{x}_{k}}) = ln{{x}_{k}}$ становится липшицевой на $Q$. В общем случае вогнутая функция полезности $u(x)$ будет липшицевой на компакте, лежащем в относительной внутренности области определения $u(x)$.

Пусть

$\mathbb{E}\left[ {exp\left( {\frac{{\mathop {\left\| {{\mathbf{x}}(\lambda \lambda ,\xi ) - {\mathbf{x}}(\lambda )} \right\|}\nolimits_2^2 }}{{\sigma _{x}^{2}}}} \right)} \right] \leqslant exp(1),$
где ${{\sigma }_{x}} = O(\sqrt n )$ – положительная числовая константа и

${\mathbf{x}}(\lambda ,\xi ) = {{(0, \ldots ,n{{x}_{\xi }}(\lambda ), \ldots ,0)}^{{\text{т}}}}.$

Сформулируем ключевую лемму, необходимую для получения оценок скорости сходимости невязки в ограничениях и зазора двойственности после работы прямо двойственного метода PDSSGM.

Лемма 2. Пусть алгоритм 3 начинает свою работу с начальной точки ${{\lambda }^{0}} = 0$ и с шагом $\beta $. Тогда после $N$ итераций алгоритма 3 с вероятностью 1 – 4$\delta $ выполняется неравенство:

$\begin{gathered} \varphi ({{{\hat {\lambda }}}^{N}}) - U({{{{\mathbf{\tilde {x}}}}}^{N}}) + 2R\mathop {\left\| {{{{[C{{{{\mathbf{\tilde {x}}}}}^{N}} - {\mathbf{b}}]}}_{ + }}} \right\|}\nolimits_2 \leqslant {{C}_{1}}\frac{{{{R}^{2}}\sigma \sqrt {g(N)J} }}{{\sqrt N }} + \frac{{2{{R}^{2}}}}{{\beta N}} + \frac{{\beta {{M}^{2}}}}{2} + \\ \, + \frac{{\sqrt 2 \left( {1 + \sqrt {3ln\tfrac{1}{\delta }} } \right)}}{{\sqrt N }}\left( {{{M}_{U}}{{\sigma }_{x}} + 2R\left( {\sigma + {{\sigma }_{x}}\sqrt {{{\lambda }_{{{\text{max}}}}}({{C}^{{\text{т}}}}C)} } \right)} \right), \\ \end{gathered} $
где
${{\hat {\lambda }}^{N}} = \frac{1}{N}\sum\limits_{t = 0}^{N - 1} \,{{\lambda }^{t}}$
и
${{{\mathbf{\tilde {x}}}}^{N}} = \frac{1}{N}\sum\limits_{t = 0}^{N - 1} \,{\mathbf{x}}({{\lambda }^{t}},{{\xi }^{t}}),$
${{C}_{1}}$ – положительная числовая константа, $g(N) = ln\left( {\tfrac{N}{\delta }} \right) + lnln\left( {\tfrac{F}{f}} \right)$,
$F = 2{{\sigma }^{2}}N{{(2\beta )}^{N}}\left( {2{{R}^{2}} + 2{{\beta }^{2}}{{M}^{2}} + \beta {{R}^{2}} + 24ln\frac{N}{\delta }\beta {{\sigma }^{2}}N} \right),$
$f = {{\sigma }^{2}}{{R}^{2}}$ и
$J = max\left\{ {1,\quad \frac{1}{R}\beta {{C}_{1}}\sqrt {{{\sigma }^{2}}g(N)} + \sqrt {\frac{1}{{{{R}^{2}}}}{{\beta }^{2}}C_{1}^{2}{{\sigma }^{2}}g(N) + \frac{{2{{R}^{2}} + 2{{\beta }^{2}}{{M}^{2}}}}{{{{R}^{2}}}}} } \right\},$
а $R$ определяется условием ${{\left\| {\lambda {\kern 1pt} *} \right\|}_{2}} \leqslant R$.

Доказательство леммы приведено в Приложении.

Теперь сформулируем теорему об оценке скорости сходимости алгоритма 3.

Теорема 2. Пусть алгоритм 3 начинает свою работу с начальной точки ${{\lambda }^{0}} = 0$ и с шагом $\beta = \tfrac{R}{{M\sqrt N }}$. Обозначим

$A = \sqrt 2 \left( {1 + \sqrt {3ln\frac{1}{\delta }} } \right)\left( {{{M}_{U}}{{\sigma }_{x}} + 2R\left( {\sigma + {{\sigma }_{x}}\sqrt {{{\lambda }_{{{\text{max}}}}}({{C}^{{\text{т}}}}C)} } \right)} \right) + 2.5RM.$
Тогда после
$N = O\left( {\left\lceil {\frac{{{{A}^{2}}}}{{{{\varepsilon }^{2}}}}ln\left( {\frac{{MR}}{{\varepsilon \delta }}} \right)} \right\rceil } \right)$
итераций алгоритма 3 с вероятностью 1 – 4$\delta $ будут выполняться следующие неравенства:
$U({\mathbf{x}}{\kern 1pt} *) - U({{{\mathbf{\tilde {x}}}}^{N}}) \leqslant \varepsilon ,\quad \mathop {\left\| {{{{(C{{{{\mathbf{\tilde {x}}}}}^{N}} - {\mathbf{b}})}}_{ + }}} \right\|}\nolimits_2 \leqslant \frac{\varepsilon }{R},$
где ${{{\mathbf{\tilde {x}}}}^{N}} = \tfrac{1}{N}\sum\nolimits_{t = 0}^{N - 1} {{\mathbf{x}}({{\lambda }^{t}},{{\xi }^{t}})} $, ${\mathbf{x}}{\kern 1pt} *$ – оптимальное решение задачи (1).

Доказательство. Начало доказательства такое же, как в теореме 1, но с использованием оценки из леммы 2. В результате для шага $\beta = \tfrac{R}{{M\sqrt N }}$ получим, что

$\frac{{\sqrt 2 \left( {1 + \sqrt {3ln\tfrac{1}{\delta }} } \right)}}{{\sqrt N }}\left( {{{M}_{U}}{{\sigma }_{x}} + 2R\left( {\sigma + {{\sigma }_{x}}\sqrt {{{\lambda }_{{{\text{max}}}}}({{C}^{{\text{т}}}}C)} } \right)} \right) + \frac{{5RM}}{{2\sqrt N }} + {{C}_{1}}\frac{{{{R}^{2}}\sigma \sqrt {g(N)J} }}{{\sqrt N }},$
при этом с точностью до констант $g(N) \approx ln\left( {\tfrac{N}{\delta }} \right)$, $J \approx max\left\{ {1,\beta \sqrt {g(N)} } \right\}$. Далее найдем $N$, при котором оценка становится меньше $\varepsilon $.

Введем следующие обозначения:

$A = \sqrt 2 \left( {1 + \sqrt {3ln\frac{1}{\delta }} } \right)\left( {{{M}_{U}}{{\sigma }_{x}} + 2R\left( {\sigma + {{\sigma }_{x}}\sqrt {{{\lambda }_{{{\text{max}}}}}({{C}^{{\text{т}}}}C)} } \right)} \right) + 2.5RM,$
$B = {{C}_{1}}{{R}^{2}}\sigma .$
Необходимо получить минимальную оценку на число итераций $N$ для достижения заданной точности $\varepsilon $. Для $J = 1$ получаем, что
(9)
$\sqrt N = \left\lceil {\frac{{A + B\sqrt {ln\left( {\tfrac{N}{\delta }} \right)} }}{\varepsilon }} \right\rceil .$
Подставляя рекурсивно значение $N$, из (9) получим следующую оценку сложности:
$N = O\left( {\left\lceil {\frac{{{{A}^{2}}}}{{{{\varepsilon }^{2}}}}ln\left( {\frac{{MR}}{{\varepsilon \delta }}} \right)} \right\rceil } \right).$
Для $J = \beta \sqrt {g(N)} = \tfrac{{R\sqrt {g(N)} }}{{M\sqrt N }}$ потребуем, чтобы
$\frac{A}{{\sqrt N }} + \frac{{Bg(N)R}}{{MN}} = \frac{A}{{\sqrt N }} + \frac{{\bar {B}g(N)}}{N} \leqslant \varepsilon .$
Так как нам нужно найти минимальное $N$, то, заменив последнее неравенство на равенство и решая полученное уравнение, получаем, что
$\sqrt N = \left\lceil {\frac{{A + \sqrt {{{A}^{2}} + 4\varepsilon \bar {B}ln\left( {\tfrac{N}{\delta }} \right)} }}{{2\varepsilon }}} \right\rceil .$
Аналогично случаю $J = 1$ из последнего равенства получается следующая оценка:
$N = O\left( {\left\lceil {\frac{{{{A}^{2}}}}{\varepsilon }ln\left( {\frac{{MR}}{{\varepsilon \delta }}} \right)} \right\rceil } \right).$
Худшая из оценок сложности для $J = 1$ и для $J = \beta \sqrt {g(N)} $ и будет оценкой из условия теоремы.

5. МЕТОД ЭЛЛИПСОИДОВ

В этом разделе для решения исходной задачи (1) предлагается применить метод эллипсоидов [25]. Данный метод можно использовать при небольшой размерности ($m$) двойственной задачи или в случае, когда требуется высокая точность решения. Данный метод является прямо двойственным, т.е. по решению двойственной задачи можно восстановить решение прямой задачи.

Рассмотрим исходную задачу (1) и двойственную к ней (2). Как и в предыдущем разделе, считаем, что функции ${{u}_{k}}({{x}_{k}})$, $k = 1, \ldots ,n$, являются вогнутыми, но не сильно вогнутыми. Также предположим, что решение двойственной задачи лежит в евклидовом шаре радиуса $R$ с центром в начале координат, т.е. ${{\left\| {\lambda {\kern 1pt} *} \right\|}_{2}} \leqslant R$. В качестве начальной точки метода возьмем нулевой вектор: ${{\lambda }^{0}} = 0$. Задачу будем решать на множестве:

${{\Lambda }_{{2R}}} = \left\{ {\lambda \in \mathbb{R}_{ + }^{m}:{{{\left\| \lambda \right\|}}_{2}} \leqslant 2R} \right\}.$
Приведем описание метода эллипсоидов (алгоритм 4), который будем применять для решения двойственной задачи.

Aлгоритм 4. Метод эллипсоидов

Вход: ${{u}_{k}}({{x}_{k}}),k = 1, \ldots ,n$ – вогнутые функции полезностей

1: ${{B}_{0}}: = 2R \cdot {{I}_{n}}$, ${{I}_{n}}$ – единичная матрица

2: for $t = 0, \ldots ,N - 1$

3:  Вычислить $\nabla \varphi ({{\lambda }^{t}})$

4:  ${{{\mathbf{q}}}_{t}}: = B_{t}^{{\text{т}}}\nabla \varphi ({{\lambda }^{t}})$

5:  ${{{\mathbf{p}}}_{t}}: = \frac{{B_{t}^{{\text{т}}}{{{\mathbf{q}}}_{t}}}}{{\sqrt {{\mathbf{q}}_{t}^{{\text{т}}}{{B}_{t}}B_{t}^{{\text{т}}}{{{\mathbf{q}}}_{t}}} }}$

6:  ${{B}_{{t + 1}}}: = \frac{m}{{\sqrt {{{m}^{2}} - 1} }}{{B}_{t}} + \left( {\frac{m}{{m + 1}} - \frac{m}{{\sqrt {{{m}^{2}} - 1} }}} \right){{B}_{t}}{{{\mathbf{p}}}_{t}}{\mathbf{p}}_{t}^{{\text{т}}}$

7:  ${{\lambda }^{{t + 1}}}: = {{\lambda }^{t}} - \frac{1}{{m + 1}}{{B}_{t}}{{{\mathbf{p}}}_{t}}$

8: end for

9: return ${{\lambda }^{N}}$

Для восстановления решения прямой задачи по решению двойственной необходимо определить сертификат точности $\xi $ для метода эллипсоидов. Напомним, что сертификатом точности называется последовательность $\xi = \{ {{\xi }_{t}}\} _{{t = 0}}^{{N - 1}}$ весов таких, что

${{\xi }_{t}} \geqslant 0,\quad \sum\limits_{t = 0}^{N - 1} \,{{\xi }_{t}} = 1.$

Построение сертификата точности в нашем случае будет осуществляться в процессе работы метода эллипсоидов, см. алгоритм 12, общая схема которого такова [26]:

1. Находим “наиболее узкую полоску”, содержащую эллипсоид ${{Q}_{N}}$, остающийся после итерации $N$, т.e. такой вектор ${\mathbf{h}}$, что на ${{Q}_{N}}$ выполняется неравенство:

(10)
$\mathop {max}\limits_{\lambda \in {{Q}_{N}}} \left\langle {{\mathbf{h}},\lambda } \right\rangle - \mathop {min}\limits_{\lambda \in {{Q}_{N}}} \left\langle {{\mathbf{h}},\lambda } \right\rangle \leqslant 1.$
Для метода эллипсоидов все ${{Q}_{N}}$ представлены в виде
${{Q}_{N}} = \{ {{B}_{N}}{\mathbf{z}} + {{\lambda }^{N}}:{{{\mathbf{z}}}^{{\text{т}}}}{\mathbf{z}} \leqslant 1\} .$
Тогда для решения (10) необходимо сделать сингулярное разложение матрицы ${{B}_{N}} = UDV$, где $U$ и $V$ – ортогональные матрицы и $D$ – диагональная матрица с положительными элементами на диагонали. Далее искомый вектор ${\mathbf{h}}$ определяется следующим образом: ${\mathbf{h}} = 1{\text{/}}(2{{\sigma }^{i}}{\kern 1pt} *) \cdot U{{{\mathbf{e}}}^{i}}{\kern 1pt} *$, где ${{i}_{*}}$ – индекс наименьшего диагонального элемента матрицы $D$, ${{\sigma }^{i}}{\kern 1pt} *$ – соответствующее этому индексу значение элемента матрицы $D$, ${{{\mathbf{e}}}^{i}}$ – векторы стандартного базиса.

2. Для векторов ${{{\mathbf{h}}}^{ + }} = \left[ {{\mathbf{h}}, - \left\langle {{\mathbf{h}},{{\lambda }^{N}}} \right\rangle } \right]$ и ${{{\mathbf{h}}}^{ - }} = - {{{\mathbf{h}}}^{ + }}$ находим разложения следующего вида:

${{{\mathbf{h}}}^{ + }} = \sum\limits_{t = 0}^{N - 1} \,{{\nu }_{t}}\left[ {\nabla \varphi ({{\lambda }^{t}}), - \left\langle {\nabla \varphi ({{\lambda }^{t}}),{{\lambda }^{t}}} \right\rangle } \right] + {{{\mathbf{y}}}^{ + }},$
${{{\mathbf{h}}}^{ - }} = \sum\limits_{t = 0}^{N - 1} \,{{\mu }_{t}}\left[ {\nabla \varphi ({{\lambda }^{t}}), - \left\langle {\nabla \varphi ({{\lambda }^{t}}),{{\lambda }^{t}}} \right\rangle } \right] + {{{\mathbf{z}}}^{ + }},$
существование которых следует из утверждения 4.1 [26]. Этот шаг описывают п. 6–13 рассмотренного ниже алгоритма 5.

3. Из коэффициентов разложения ${{\nu }_{t}}$ и ${{\mu }_{t}}$ векторов ${{{\mathbf{h}}}^{ + }}$ и ${{{\mathbf{h}}}^{ - }}$, соответственно, получаем выражения для ${{\xi }_{t}},\;t \in {{I}_{N}}$, где

${{I}_{N}} = \{ t \leqslant N - 1:{{\lambda }^{t}} \in \operatorname{int} {{\Lambda }_{{2R}}}\} .$
Коэффициенты разложения определяются только для тех точек, получаемых в процессе работы алгоритма 5, которые принадлежат допустимому множеству.

Aлгоритм 5. Построение сертификата точности для метода эллипсоидов

Вход: $N - 1$ – номер итерации, на которой производится вычисление сертификата точности, $\mathop {\left\{ {{{B}_{t}},{{\lambda }^{t}},\nabla \varphi ({{\lambda }^{t}})} \right\}}\nolimits_{t = 0}^{N - 1} $ – протокол работы метода эллипсоидов после $N$ итераций

 1: если $\nabla \varphi ({{\lambda }^{{N - 1}}}) = 0,$ то

 2:  ${{\xi }_{t}}: = 0$ для всех $t = 0, \ldots ,N - 2$

 3:  ${{\xi }_{{N - 1}}}: = 1$

 4: иначе

 5:  ${\mathbf{h}}: = 1{\text{/}}(2{{\sigma }^{i}}{\kern 1pt} *) \cdot U{{{\mathbf{e}}}^{i}}{\kern 1pt} *$

 6:  ${{{\mathbf{g}}}_{\nu }}: = {\mathbf{h}},$ ${{{\mathbf{g}}}_{\mu }}: = - {\mathbf{h}}$

 7:  for $t = 0, \ldots ,N - 1$

 8:   ${\mathbf{q}}: = B_{t}^{{\text{т}}}\nabla \varphi ({{\lambda }^{t}})$

 9:   ${{\nu }_{t}}: = {{[{\mathbf{g}}_{\nu }^{{\text{т}}}{{B}_{t}}{\mathbf{q}}]}_{ + }}{\text{/}}\left\| {\mathbf{q}} \right\|_{2}^{2}$

10:   ${{{\mathbf{g}}}_{\nu }}: = {{{\mathbf{g}}}_{\nu }} - {{\nu }_{t}}\nabla \varphi ({{\lambda }^{t}})$

11:   ${{\mu }_{t}}: = {{[{\mathbf{g}}_{\mu }^{{\text{т}}}{{B}_{t}}{\mathbf{q}}]}_{ + }}{\text{/}}\left\| {\mathbf{q}} \right\|_{2}^{2}$

12:   ${{{\mathbf{g}}}_{\mu }}: = {{{\mathbf{g}}}_{\mu }} - {{\mu }_{t}}\nabla \varphi ({{\lambda }^{t}})$

13:  end for

14:  ${{\xi }_{t}}: = ({{\nu }_{t}} + {{\mu }_{t}}){\text{/}}\sum\nolimits_{i \in {{I}_{N}}}^{} {({{\nu }_{i}} + {{\mu }_{i}})} ,$ $t \in {{I}_{N}}$

15: end если

16: return $\mathop {\left\{ {{{\xi }_{t}}} \right\}}\nolimits_{t = 0}^{N - 1} $

Замечание 3. Отметим, что, в отличие от БГМ и стохастического метода проекции субградиента, в методе эллипсоидов для вычисления шагов 4–6 алгоритма 4 необходима информация о всех компонентах градиента, т.е. нужна информация от всех пользователей. Поэтому необходим общий центр для всех соединений, который будет собирать информацию со всех соединений и выполнять эти вычисления.

Сформулируем теорему об оценкe скорости сходимости метода эллипсоидов для решаемой задачи.

Теорема 3 (см. [26]). Пусть алгоритм 4 начинает свою работу с начальным шаром ${{B}_{0}} = \{ \lambda \in {{\mathbb{R}}^{m}}:\left\| \lambda \right\| \leqslant 2R\} $ и сертификат точности $\xi $ формируется в соответствии с алгоритмом 5. Тогда после

(11)
$N = 2m(m + 1)\left\lceil {ln\left( {\frac{{32 \cdot 4MR}}{\varepsilon }} \right)} \right\rceil $
итераций будут выполняться следующие неравенства:
$U({\mathbf{x}}{\kern 1pt} *) - U({{{\mathbf{\hat {x}}}}^{N}}) \leqslant \varepsilon ,\quad {{\left\| {{{{[C{{{{\mathbf{\hat {x}}}}}^{N}} - {\mathbf{b}}]}}_{ + }}} \right\|}_{2}} \leqslant \frac{\varepsilon }{R},$
где

${{{\mathbf{\hat {x}}}}^{N}} = \sum\limits_{t \in {{I}_{N}}} \,{{\xi }_{t}}{\mathbf{x}}({{\lambda }^{t}}),\quad {{I}_{N}} = \left\{ {t \leqslant N - 1:{{\lambda }^{t}} \in \operatorname{int} {{\Lambda }_{{2R}}}} \right\}.$

Доказательство теоремы можно найти ниже в Приложении.

6. РЕГУЛЯРИЗАЦИЯ ДВОЙСТВЕННОЙ ЗАДАЧИ

В предыдущих разделах мы рассматривали прямо двойственные методы для решения двойственной задачи. Однако существует стандартный подход, который позволяет по решению двойственной задачи не прямо двойственным методом восстанавливать решение прямой задачи. Ключевой идеей данного подхода является регуляризация двойственной задачи, которая гарантирует сильную выпуклость регуляризованной задачи. Далее опишем подробно предлагаемый подход и сформулируем леммы, связывающие решения прямой и двойственной задачи.

Регуляризуем функционал (2) по Тихонову

${{\varphi }_{\delta }}(\lambda ) = \varphi (\lambda ) + \frac{\delta }{2}\left\| \lambda \right\|_{2}^{2}$
и вместо задачи (4) будем решать регуляризованную задачу

$\mathop {min}\limits_{\lambda \in {\mathbf{R}}_{ + }^{m}} {{\varphi }_{\delta }}(\lambda ).$

Параметр $\delta $ будет оптимально подобран позже. Как и в предыдущем разделе, предполагается, что задача решается на множестве

${{\Lambda }_{{2R}}} = \{ \lambda \in \mathbb{R}_{ + }^{m}:{{\left\| \lambda \right\|}_{2}} \leqslant 2R\} .$
Для полученной регуляризованной функции сформулируем следующую лемму о гладкости регуляризованной задачи.

Лемма 3. Пусть функция $\varphi (\lambda )$ – $L$-гладкая, тогда регуляризованная функция ${{\varphi }_{\delta }}(\lambda )$ является $(L + \delta )$-гладкой, т.е. для любых ${{\lambda }^{1}}$, ${{\lambda }^{2}} \in {\mathbf{R}}_{ + }^{m}$

(12)
${{\left\| {\nabla {{\varphi }_{\delta }}({{\lambda }^{1}}) - \nabla {{\varphi }_{\delta }}({{\lambda }^{2}})} \right\|}_{2}} \leqslant (L + \delta ){{\left\| {{{\lambda }^{1}} - {{\lambda }^{2}}} \right\|}_{2}}.$

Доказательство. Градиент регуляризованной функции

$\nabla {{\varphi }_{\delta }}(\lambda ) = \nabla \varphi (\lambda ) + \delta \lambda .$
Следовательно, имеем оценку
${{\left\| {\nabla {{\varphi }_{\delta }}({{\lambda }^{1}}) - \nabla {{\varphi }_{\delta }}({{\lambda }^{2}})} \right\|}_{2}} = {{\left\| {\nabla \varphi ({{\lambda }^{1}}) - \nabla \varphi ({{\lambda }^{2}}) + \delta ({{\lambda }^{1}} - {{\lambda }^{2}})} \right\|}_{2}} \leqslant {{\left\| {\nabla \varphi ({{\lambda }^{1}}) - \nabla \varphi ({{\lambda }^{2}})} \right\|}_{2}} + \delta {{\left\| {{{\lambda }^{1}} - {{\lambda }^{2}}} \right\|}_{2}}.$
Откуда в силу утверждения 2 следует (12).

Также для оценки сходимости алгоритма для прямой задачи нам понадобится следующая вспомогательная лемма o связи между оценкой на градиент для двойственной задачи и оценками на сходимость по функции и невязку в ограничении для прямой задачи.

Лемма 4 (см. [10]). Пусть ${\mathbf{x}}{\kern 1pt} *$ – решение прямой задачи (1). Тогда выполняются следующие неравенства:

(13)
${{\left\| {C{\mathbf{x}}(\lambda ) - {\mathbf{b}}} \right\|}_{2}} \leqslant {{\left\| {\nabla {{\varphi }_{\delta }}(\lambda )} \right\|}_{2}} + \delta {{\left\| \lambda \right\|}_{2}},$
(14)
$U({\mathbf{x}}{\kern 1pt} *) - U({\mathbf{x}}(\lambda )) \leqslant {{\left\| {\nabla {{\varphi }_{\delta }}(\lambda )} \right\|}_{2}} \cdot {{\left\| \lambda \right\|}_{2}} + \delta \left\| \lambda \right\|_{2}^{2},$
где ${\mathbf{x}}(\lambda )$ определяется в (3).

Доказательство. В силу (3) имеем

$U({\mathbf{x}}(\lambda )) + \left\langle {\lambda ,{\mathbf{b}} - C{\mathbf{x}}(\lambda )} \right\rangle \geqslant U({\mathbf{x}}{\kern 1pt} {\text{*}}) + \left\langle {\lambda ,{\mathbf{b}} - C{\mathbf{x}}{\kern 1pt} {\text{*}}} \right\rangle \geqslant U({\mathbf{x}}{\kern 1pt} {\text{*}}).$
Откуда
$U({\mathbf{x}}(\lambda )) \geqslant U({\mathbf{x}}{\kern 1pt} *) - \left\langle {\lambda ,{\mathbf{b}} - C{\mathbf{x}}(\lambda )} \right\rangle = U({\mathbf{x}}{\kern 1pt} *) - \left\langle {\lambda ,\nabla \varphi (\lambda )} \right\rangle .$
Так как $\varphi (\lambda ) = {{\varphi }_{\delta }}(\lambda ) - \tfrac{\delta }{2}\left\| \lambda \right\|_{2}^{2}$, имеем
${{\left\| {\nabla \varphi (\lambda )} \right\|}_{2}} = {{\left\| {\nabla {{\varphi }_{\delta }}(\lambda ) - \delta \lambda } \right\|}_{2}} \leqslant \left\| {\nabla {{\varphi }_{\delta }}(\lambda )} \right\| + \delta {{\left\| \lambda \right\|}_{2}}.$
Из последнего неравенства, учитывая соотношение $\nabla \varphi (\lambda ) = {\mathbf{b}} - C{\mathbf{x}}(\lambda )$, получаем (13).

Далее, оценка (14) следует из

$\begin{gathered} U({\mathbf{x}}*) - U({\mathbf{x}}(\lambda )) \leqslant \left\langle {\lambda ,\nabla \varphi (\lambda )} \right\rangle \leqslant {{\left\| {\nabla \varphi (\lambda )} \right\|}_{2}} \cdot {{\left\| \lambda \right\|}_{2}} \leqslant \\ \, \leqslant {{\left\| \lambda \right\|}_{2}} \cdot \left( {\mathop {\left\| {\nabla {{\varphi }_{\delta }}(\lambda )} \right\|}\nolimits_2 + \delta \mathop {\left\| \lambda \right\|}\nolimits_2 } \right) \leqslant {{\left\| {\nabla {{\varphi }_{\delta }}(\lambda )} \right\|}_{2}} \cdot {{\left\| \lambda \right\|}_{2}} + \delta \left\| \lambda \right\|_{2}^{2}. \\ \end{gathered} $
Кроме этого, понадобится лемма о сходимости по градиенту для регуляризованной функции.

Лемма 5. Пусть $\lambda _{\delta }^{*}$ – решение регуляризованной двойственной задачи. Имеeт место следующее неравенство:

$\mathop {\left\| {\nabla {{\varphi }_{\delta }}({{\lambda }^{N}})} \right\|}\nolimits_2 \leqslant (L + \delta ){{\left\| {{{\lambda }^{N}} - \lambda _{\delta }^{*}} \right\|}_{2}}.$

Доказательство немедленно следует из леммы 3 и равенства

$\nabla {{\varphi }_{\delta }}(\lambda _{\delta }^{*}) = 0.$
Мы сформулировали необходимые леммы для регуляризованной задачи и в следующем разделе рассмотрим на примере применение этого подхода.

7. МЕТОД ЭКСТРАПОЛЯЦИИ СЛУЧАЙНОГО ГРАДИЕНТА

Рассмотрим метод экстраполяции случайного градиента [27]. Отметим, что данный метод не требует пересчета градиента на каждой итерации, необходимо пересчитывать только одну его компоненту на каждой итерации, что значительно сокращает вычисления, особенно для задач большой размерности. Так как данный метод не является прямо двойственным, то необходимо применять алгоритм 6 к регуляризованной задаче.

Параметры $\alpha $, $\eta $, $\tau $ и ${{\theta }_{t}}$ выбираются следующим образом:

(15)
$\bar {\alpha } = 1 - \frac{1}{{n + \sqrt {{{n}^{2}} + 16nL{\text{/}}\delta } }},$
(16)
$\alpha = n\bar {\alpha },\quad \eta = \frac{{\delta \bar {\alpha }}}{{1 - \bar {\alpha }}},\quad \tau = \frac{1}{{n(1 - \bar {\alpha })}} - 1,\quad {{\theta }_{t}} = \mathop {\bar {\alpha }}\nolimits^{ - t} .$

7.1. Распределенный метод

В данной секции опишем распределенную версию рассмотренного метода. Для начала отметим, что векторы $\mathop {\underline \lambda }\nolimits_1^0 , \ldots ,\mathop {\underline \lambda }\nolimits_n^0 $ хранятся у соответствующих пользователей и влияют на формирование оптимального значения трафика для соответствующего пользователя. Как было отмечено при описании распределенного БГМ, на определение оптимального трафика пользователя влияют только цены соединений, через которые данный пользователь обменивается пакетами. Поэтому можно считать, что в векторе $\mathop {\underline \lambda }\nolimits_k^t $ ненулевые только те компоненты, номера которых совпадают с номерами используемых соединений.

Aлгоритм 6. Метод экстраполяции случайного градиента (RGEM)

Вход: Параметры $\alpha $, $\eta $, $\tau $, $\{ {{\theta }_{t}}\} _{{t = 1}}^{N}$

 1: ${{\lambda }^{0}}: = {\mathbf{0}}$

 2: $\mathop {\underline \lambda }\nolimits_i^0 : = {{\lambda }^{0}}$, $i = 1, \ldots ,n$

 3: ${{y}_{{ - 1}}} = {{y}_{0}} = {\mathbf{0}}$

 4: for $t = 1, \ldots ,N$

 5:  Выбрать случайным образом ${{k}_{t}}$ из множества $\{ 1, \ldots ,n\} $ равномерно по всем значениям

 6:  ${\mathbf{\tilde {y}}}_{k}^{t}: = {\mathbf{y}}_{k}^{{t - 1}} + \alpha ({\mathbf{y}}_{k}^{{t - 1}} - {\mathbf{y}}_{k}^{{t - 2}}),$ $k = 1, \ldots ,n$

 7:  ${{\lambda }^{t}}: = \mathop {\left[ {\eta {{\lambda }^{{t - 1}}} - \tfrac{1}{n}\sum\nolimits_{k = 1}^n {{\mathbf{\tilde {y}}}_{k}^{t}} } \right]}\nolimits_ + {\text{/}}(\delta + \eta )$

 8:

 9:  $\mathop {\underline \lambda }\nolimits_{{{k}_{t}}}^t : = ({{\lambda }^{t}} + \tau \mathop {\underline \lambda }\nolimits_{{{k}_{t}}}^{t - 1} ){\text{/}}(1 + \tau )$

10:  $\mathop {\underline \lambda }\nolimits_k^t : = \mathop {\underline \lambda }\nolimits_k^{t - 1} $, $k \in \{ 1, \ldots n\} {\backslash }\{ {{k}_{t}}\} $

11:

12:  ${\mathbf{y}}_{{{{k}_{t}}}}^{t}: = {\mathbf{b}} - n{{{\mathbf{C}}}_{{{{k}_{t}}}}}{{x}_{{{{k}_{t}}}}}(\mathop {\underline \lambda }\nolimits_{{{k}_{t}}}^t )$

13:  ${\mathbf{y}}_{k}^{t}: = {\mathbf{y}}_{k}^{{t - 1}}$, $k \in \{ 1, \ldots ,n\} {\backslash }\{ {{k}_{t}}\} $

14: end for

15: ${{\bar {\lambda }}^{N}}: = \left( {\sum\nolimits_{t = 0}^{N - 1} {{{\theta }_{t}}{{\lambda }^{t}}} } \right){\text{/}}\sum\nolimits_{t = 1}^N {{{\theta }_{t}}} $

16: return ${{\bar {\lambda }}^{N}}$

Опишем распределенный алгоритм на $t$-й итерации.

1. Используя информацию, собранную с пользователей на предыдущей итерации, соединение $j$ вычисляет

$\tilde {y}_{{k,j}}^{t}: = y_{{k,j}}^{{t - 1}} + \alpha (y_{{k,j}}^{{t - 1}} - y_{{k,j}}^{{t - 2}}) = {{b}_{j}} - nC_{k}^{j}{{x}_{k}}(\mathop {\underline \lambda }\nolimits_k^{t - 1} ) + \alpha (nC_{k}^{j}{{x}_{k}}(\mathop {\underline \lambda }\nolimits_k^{t - 2} ) - nC_{k}^{j}{{x}_{k}}(\mathop {\underline \lambda }\nolimits_k^{t - 1} )).$
Заметим, что в силу определения матрицы $C$ соединению $j$ нужна информация только от пользователей, которые обмениваются пакетами через это соединение.

2. Далее соединение $j$ меняет цену по следующему правилу:

$\lambda _{j}^{t} = {{\left[ {\eta \lambda _{j}^{{t - 1}} - \frac{1}{n}\sum\limits_{k = 1}^n \,\tilde {y}_{{k,j}}^{t}} \right]}_{ + }}{\text{/}}(\delta + \eta ).$

3. Один из пользователей ${{k}_{t}}$ реагирует на изменение цен и в качестве локального вектора цен сохраняет

$\mathop {\underline \lambda }\nolimits_{{{k}_{t}}}^t = ({{\lambda }^{t}} + \tau \mathop {\underline \lambda }\nolimits_{{{k}_{t}}}^{t - 1} ){\text{/}}(1 + \tau ),$
остальные пользователи никак не изменяют локальные цены, т.е. $\mathop {\underline \lambda }\nolimits_{{{k}_{t}}}^t = \mathop {\underline \lambda }\nolimits_{{{k}_{t}}}^{t - 1} $.

4. Пользователь ${{k}_{t}}$ вычисляет

$x_{{{{k}_{t}}}}^{t}(\mathop {\underline \lambda }\nolimits_{{{k}_{t}},j}^t ) = \mathop {arg\,max}\limits_{{{x}_{k}} \in {{{\mathbf{R}}}_{ + }}} \,\left( {{{u}_{k}}({{x}_{k}}) - {{x}_{k}}\sum\limits_{j = 1}^m \,\mathop {\underline \lambda }\nolimits_{{{k}_{t}},j}^t C_{k}^{j}} \right)$
и отправляет эту информацию соединениям, которые использует.

5. Соединение $j$ обновляет у себя информацию для ${{k}_{t}}$ пользователя

$y_{{{{k}_{t}},j}}^{t} = {{b}_{j}} - nC_{{{{k}_{t}}}}^{j}{{x}_{{{{k}_{t}}}}}(\mathop {\underline \lambda }\nolimits_{{{k}_{t}}}^t ).$
Данную информацию соединение будет обновлять только в случае, когда через него обменивается пакетами пользователь ${{k}_{t}}$.

7.2. Оценка скорости сходимости метода экстраполяции случайного градиента

В данном разделе мы, так же, как в разд. 3, рассматриваем задачу (2) с $\mu $-сильно вогнутыми функциями затрат ${{u}_{k}}({{x}_{k}}),k = 1, \ldots ,n$. Напомним, что в силу сильной вогнутости функций затрат двойственная задача (4) будет гладкой с константой Липшица $L = \tfrac{{n{{m}^{2}}}}{\mu }$.

Для оценки скорости сходимости метода необходима следующая оценка для невязки по аргументу из теоремы 2.1 [27]:

(17)
$\mathbb{E}\left[ {\left\| {\lambda _{\delta }^{*} - {{\lambda }^{N}}} \right\|_{2}^{2}} \right] \leqslant \frac{{4\Delta {{{(\bar {\alpha })}}^{N}}}}{\delta },$
где $\Delta = \delta \left\| {\lambda _{\delta }^{*} - {{\lambda }^{0}}} \right\|_{2}^{2} + \tfrac{B}{{n\delta }} + {{\varphi }_{\delta }}({{\lambda }^{0}}) - {{\varphi }_{\delta }}(\lambda _{\delta }^{*})$, $B = \left\| {\mathbf{b}} \right\|_{2}^{2}$.

Используя (17), можно доказать теорему об оценке скорости сходимости метода непосредственно для задачи (11).

Теорема 4. Пусть для решения регуляризованной двойственной задачи (11) применяется метод RGEM c параметрами (15), (16) и $\delta = \tfrac{\varepsilon }{{8{{R}^{2}}}}$ для

$N = \left\lceil {2\left( {n + \sqrt {{{n}^{2}} + \frac{{128nL{{R}^{2}}}}{\varepsilon }} } \right)ln\left( {\frac{{4RA}}{\varepsilon }} \right)} \right\rceil $
итераций, где $A = 2\left( {LR + \tfrac{\varepsilon }{{8R}}} \right)\sqrt {6 + \tfrac{{16L{{R}^{2}}n + 8B}}{{n\varepsilon }}} $. Тогда

$\mathbb{E}{\kern 1pt} [U({\mathbf{x}}{\kern 1pt} *) - U({\mathbf{x}}({{\lambda }^{N}}))] \leqslant \varepsilon ,\quad \mathbb{E}\left[ {\mathop {\left\| {C{\mathbf{x}}({{\lambda }^{N}}) - {\mathbf{b}}} \right\|}\nolimits_2 } \right] \leqslant \frac{\varepsilon }{{2R}}.$

Доказательство. Из леммы 4 имеем оценки для невязки по ограничениям (13) и по целевой функции (14). Ввиду предположения $\lambda \in {{\Lambda }_{{2R}}}$, выполняются следующие неравенства:

(18)
${{\left\| {C{{{\mathbf{x}}}^{N}} - {\mathbf{b}}} \right\|}_{2}} \leqslant {{\left\| {\nabla {{\varphi }_{\delta }}({{\lambda }^{N}})} \right\|}_{2}} + 2\delta R,$
(19)
$U({\mathbf{x}}{\kern 1pt} *) - U({{{\mathbf{x}}}^{N}}) \leqslant 2R{{\left\| {\nabla {{\varphi }_{\delta }}({{\lambda }^{N}})} \right\|}_{2}} + 4\delta {{R}^{2}},$
где ${{{\mathbf{x}}}^{N}} = {\mathbf{x}}({{\lambda }^{N}})$. Из леммы 5 и неравенства (17) получаем следующую оценку для ${{\left\| {\nabla {{\varphi }_{\delta }}({{\lambda }^{N}})} \right\|}_{2}}$:
$\mathbb{E}\left[ {{{{\left\| {\nabla {{\varphi }_{\delta }}({{\lambda }^{N}})} \right\|}}_{2}}} \right] \leqslant 2(L + \delta )\sqrt {\frac{\Delta }{\delta }} {{(\bar {\alpha })}^{{N/2}}}.$
Оценим $\Delta $. Для функции ${{\varphi }_{\delta }}$ с липшицевым градиентом выполняется неравенство
${{\varphi }_{\delta }}({{\lambda }^{0}}) - {{\varphi }_{\delta }}(\lambda _{\delta }^{*}) \leqslant \left\langle {\nabla {{\varphi }_{\delta }}(\lambda _{\delta }^{*}),{{\lambda }^{0}} - \lambda {\kern 1pt} *} \right\rangle + \frac{{L + \delta }}{2}\left\| {\lambda _{\delta }^{*} - {{\lambda }^{0}}} \right\|_{2}^{2}.$
Учитывая, что $\nabla {{\varphi }_{\delta }}(\lambda _{\delta }^{*}) = 0$, получаем

$\Delta \leqslant \delta \left\| {\lambda _{\delta }^{*} - {{\lambda }^{0}}} \right\|_{2}^{2} + \frac{B}{{n\delta }} + \frac{{L + \delta }}{2}\left\| {\lambda _{\delta }^{*} - {{\lambda }^{0}}} \right\|_{2}^{2} \leqslant (6\delta + 2L){{R}^{2}} + \frac{B}{{n\delta }}.$

Пусть $\delta $ подбирается так, чтобы выполнялось $4\delta {{R}^{2}} = \tfrac{\varepsilon }{2}$, тогда $\delta = \tfrac{\varepsilon }{{8{{R}^{2}}}}$. Отсюда имеем

$4\delta {{R}^{2}} = \frac{\varepsilon }{2},\quad 2\delta R = \frac{\varepsilon }{{4R}}.$
Потребуем выполнения неравенства $U({\mathbf{x}}{\kern 1pt} *) - U({\mathbf{x}}({{\lambda }^{N}})) \leqslant \varepsilon $. Тогда, в силу (18), (19) должно выполняться неравенство:
${{\left\| {\nabla {{\varphi }_{\delta }}({{\lambda }^{N}})} \right\|}_{2}} \leqslant \frac{\varepsilon }{{4R}}.$
Откуда имеем
$2(L + \delta )\sqrt {\frac{\Delta }{\delta }} {{(\bar {\alpha })}^{{N/2}}} \leqslant \frac{\varepsilon }{{4R}}.$
Учитывая, что
$2(L + \delta )\sqrt {\frac{\Delta }{\delta }} \leqslant 2\left( {LR + \frac{\varepsilon }{{8R}}} \right)\sqrt {6 + \frac{{16L{{R}^{2}}n + 8B}}{{n\varepsilon }}} ,$
получаем следующую оценку на число итераций:
$N = \left\lceil {2\left( {n + \sqrt {{{n}^{2}} + \frac{{128nL{{R}^{2}}}}{\varepsilon }} } \right)ln\left( {\frac{{4RA}}{\varepsilon }} \right)} \right\rceil ,$
где $A = 2\left( {LR + \tfrac{\varepsilon }{{8R}}} \right)\sqrt {6 + \tfrac{{16L{{R}^{2}}n + 8B}}{{n\varepsilon }}} $.

Замечание 3. Отметим, что оценку сложности алгоритма 6 можно также представить в виде $O\left( {max\left\{ {n,\sqrt {nL{{R}^{2}}{\text{/}}\varepsilon } } \right\}ln\left( {\tfrac{1}{\varepsilon }} \right)} \right)$, где логарифмический множитель появляется за счет необходимости регуляризации двойственной задачи. При этом на каждой итерации вычисляется только одна компонента вектора реакции пользователя на изменение цены, соответственно, арифметическая сложность операции лучше, чем при вычислении всех компонент этих векторов. Для БГМ предположения для целевой функции аналогичны, но за счет того, что на каждой итерации необходимо вычислять полный градиент, стоимость работы алгоритма, соответственно, $O\left( {n\sqrt {L{{R}^{2}}{\text{/}}\varepsilon } } \right)$. Таким образом, несмотря на то, что теоретическая оценка скорости сходимости для RGEM имеет тот же порядок, что и для БГМ, на практике выигрыш получается за счет более дешевых вычислений в рамках одной итерации.

8. ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ

Программный код для численных экспериментов был написан на языках программирования Python версии 3.6 и С++ стандарта C++14. Исходный код для экспериментов и рассмотренных в статье методов опубликован на GitHub и доступен по ссылке: https://github.com/dmivilensky/network-resource-allocation. Измерение времени работы производилось на компьютере с 2-ядерным процессором Intel Core i5-5250U с тактовой частотой 1.6 ГГц на каждое ядро, ОЗУ компьютера составляла 8 Гб.

8.1. Сильно выпуклые (квадратичные) функции полезности

Рассмотрим задачу (1) для функций полезности следующего вида:

${{u}_{k}}({{x}_{k}}) = {{a}_{k}}{{x}_{k}} - \frac{{\sigma n}}{2}x_{k}^{2},\quad {{a}_{k}} \sim \mathcal{U}(0,100),\quad \sigma = 0.1,$
где ${{a}_{k}}$ – независимые и одинаково распределенные случайные величины. Тогда задачу (3) можно решить явно:

${\mathbf{x}}(\lambda ) = \frac{{{{{[{\mathbf{a}} - C\lambda ]}}_{ + }}}}{{n\sigma }}.$

Для малого числа пользователей ($n = 1500$) пропускные способности соединений выбираются одинаковыми (в данном случае ${\mathbf{b}} = {{(5, \ldots ,5)}^{{\text{т}}}}$), а спрос на передачу информации равномерен (${{c}_{{ij}}} = 1$ для любых $i,j$). Для большего числа пользователей вектор пропускных способностей генерируется случайно, так что ${{b}_{i}} \sim \mathcal{U}(1,6)$. Также случайно и независимо выбираются элементы матрицы спроса, так что ${{c}_{{ij}}} = 1$ с вероятностью $p = 0.5$ и ${{c}_{{ij}}} = 0$ с вероятностью $q = 0.5$.

В табл. 1 представлены число итераций и время работы быстрого градиентного метода (FGM) и метода экстраполяции случайного градиента (RGEM) для различных конфигураций сети (с числом соединений $m$), числа пользователей $n$ и требуемой точности $\varepsilon $. В таблице выделены те случаи, в которых метод экстраполяции случайного градиента сходится к решению за меньшее время, чем быстрый градиентный метод, несмотря на большее число итераций по сравнению с БГМ. Действительно, для $n \gg 0$ число требующихся запросов оптимального решения ${{x}_{k}}(\lambda )$ от пользователей, в случае метода экстраполяции случайного градиента, будет меньшим, чем при использовании других алгоритмов, так как за одну итерацию метода экстраполяции случайного градиента запрос отправляется только к одному случайному пользователю.

Таблица 1.  

Сравнение количества итераций и времени работы БГМ и метода экстраполяции случайного градиента для сильно выпуклых (квадратичных) функций полезности

Сеть FGM RGEM
Итерации Время Итерации Время
$m = 2$, $n = 1500$, $\varepsilon = {{10}^{{ - 2}}}$ 350 24.5 с 3000 21.1 с
$m = 5$, $n = 1500$, $\varepsilon = {{10}^{{ - 2}}}$ 380 42.7 с 6700 36.9 с
$m = 70$, $n = 5000$, $\varepsilon = {{10}^{{ - 2}}}$ 400 150.0 с 7800 132.6 с
$m = 70$, $n = 5000$, $\varepsilon = {{10}^{{ - 3}}}$ 1070 374.5 с 9180 283.7 с
$m = 100$, $n = 5000$, $\varepsilon = {{10}^{{ - 2}}}$ 417 175.1 с 8200 164.0 с
$m = 70$, $n = 7000$, $\varepsilon = {{10}^{{ - 2}}}$ 421 218.9 с 8600 206.4 с
$m = 100$, $n = 7000$, $\varepsilon = {{10}^{{ - 2}}}$ 427 290.3 с 9200 276.0 с
$m = 100$, $n = 7000$, $\varepsilon = {{10}^{{ - 3}}}$ 1120 761.6 с 10 130 638.2 с

8.2. Выпуклые (логарифмические) функции полезности

Рассмотрим работу стохастического субградиентного метода (алгоритм 9) и метода эллипсоидов (алгоритм 4) для функции полезности следующего вида:

${{u}_{k}}({{x}_{k}}) = ln{{x}_{k}}.$

В таком случае явное решение задачи (3) выглядит следующим образом (операция $1/ \cdot $ применительно к вектору понимается поэлементно):

${\mathbf{x}}(\lambda ) = \frac{1}{{C\lambda }}.$

Для малого числа пользователей ($n = 1500$) пропускные способности соединений выбираются одинаковыми (в данном случае ${\mathbf{b}} = {{(5, \ldots ,5)}^{{\text{т}}}}$), а спрос на передачу информации равномерен (${{c}_{{ij}}} = 1$ для любых $i,j$). Для большего числа пользователей вектор пропускных способностей генерируется случайно, так что ${{b}_{i}} \sim \mathcal{U}(1,6)$. Также случайно и независимо выбираются элементы матрицы спроса, так что ${{c}_{{ij}}} = 1$ с вероятностью $p = 0.5$ и ${{c}_{{ij}}} = 0$ с вероятностью $q = 0.5$.

В табл. 2 представлены число итераций и время работы стохастического субградиентного метода (SGM) и метода эллипсоидов для различных конфигураций сети, числа пользователей и требуемой точности. В таблице выделены те случаи, в которых стохастический субградиентный метод сходится к решению за меньшее время, чем метод эллипсоидов.

Таблица 2.  

Сравнение количества итераций и времени работы стохастического субградиентного метода и метода эллипсоидов для выпуклых (логарифмических) функций полезности

Сеть Метод эллипсоидов SGM
Итерации Время Итерации Время
$m = 2$, $n = 1500$, $\varepsilon = {{10}^{{ - 2}}}$ 40 0.02 с 2000 0.2 с
$m = 5$, $n = 1500$, $\varepsilon = {{10}^{{ - 2}}}$ 85 0.06 с 2500 0.3 с
$m = 70$, $n = 5000$, $\varepsilon = {{10}^{{ - 2}}}$ 120 1.9 с 4000 1.3 с
$m = 70$, $n = 5000$, $\varepsilon = {{10}^{{ - 3}}}$ 800 5.4 с 9020 2.4 с
$m = 100$, $n = 5000$, $\varepsilon = {{10}^{{ - 2}}}$ 300 9.0 с 5000 3.1 с
$m = 70$, $n = 7000$, $\varepsilon = {{10}^{{ - 2}}}$ 250 8.7 с 5590 5.5 с
$m = 100$, $n = 7000$, $\varepsilon = {{10}^{{ - 2}}}$ 380 19.0 с 6480 10.8 с
$m = 100$, $n = 7000$, $\varepsilon = {{10}^{{ - 3}}}$ 1830 91.5 с 17970 30.6 с

Отметим, что аналогично методу экстраполяции случайного градиента, стохастический субградиентный метод требует вычисления лишь одной компоненты вектора ${\mathbf{x}}(\lambda )$ реакций пользователей на установившиеся цены на каждой итерации. Таким образом, при большем числе итераций метода число вычисляемых компонент ${{x}_{k}}({{\lambda }^{t}})$ будет меньшим по сравнению с другими алгоритмами, например, с методом эллипсоидов, также как и коммуникационная сложность в случае распределенной реализации.

9. ЗАКЛЮЧЕНИЕ

В заключение отметим некоторые возможные развития данной работы и кратко опишем методы без подробного анализа оценки скорости сходимости.

В разд. 5 мы рассматривали метод эллипсоидов для задач небольшой размерности, который является прямо двойственным. Существуют и другие методы, которые дают высокую точность и хорошо подходят для задач небольшой размерности. Одним из таких методов является метод Вайды [28]. Однако для восстановления решения прямой задачи при решении двойственной задачи методом Вайды необходимо, чтобы была сходимость по норме градиента для двойственной задачи. Для этого требуется гладкость двойственной задачи, что порождается сильной выпуклостью целевой функции прямой задачи (утверждение 2). Если сильной выпуклости в прямой задаче нет, то ее можно регуляризовать, как было описано в разд. 6, но при этом оценка сходимости логарифмически ухудшится.

Также для решения двойственной задачи можно применить методы высокого порядка [29], [30], если двойственная задача достаточно гладкая. При этом шаги данных методов можно будет считать распределенно, так как в данной задаче рассматривается централизованная архитектура с точки зрения взаимодействия соединения и использующих его пользователей. Однако отметим, что оптимальные методы высокого порядка, требующие одномерного поиска и не обладающие прямо двойственностью, необходимо применять только после регуляризации двойственной задачи.

Еще одно направление – методы типа редукции дисперсии, например, [31], [32], которые являются промежуточными между стохастическим градиентным методом и БГМ. Однако данные методы тоже не прямо двойственные, поэтому их необходимо применять к предварительно регуляризованной двойственной задаче.

Особый интерес для авторов представляют метод Hogwild! [33] и методы с использованием мини-батчинга. Заметим, что при этом одновременно данные передают не все пользователи, но и не только один пользователь, как это получается при использовании стохастических методов. Выбирая в качестве размера батча количество пользователей, которые отправляют данные в один момент времени, можно учесть специфику работы реальных сетей.

Список литературы

  1. Kelly F.P., Maulloo A.K., Tan D.K.H. Rate control for communication networks: shadow prices, proportional fairness and stability // J. of the Operational Research Society. 1998. V. 49. 3. P. 237–252.

  2. Рохлин Д.Б. Распределение ресурсов в сетях связи с большим числом пользователей: стохастический метод градиентного спуска // Теория вероятностей и ее применения (в печати). 2019.

  3. Arrow K.J., Hurwicz L. Decentralization and computation in resource allocation. Stanford University, Department of Economics, 1958.

  4. Kakhbod A. Resource allocation in decentralized systems with strategicagents: an implementation theory approach. Springer Science & BusinessMedia, 2013.

  5. Campbell D.E. Resource allocation mechanisms. Cambridge University Press, 1987.

  6. Friedman E.J., Oren S.S. The complexity of resource allocation and price mechanisms under bounded rationality // Economic Theory. 1995. V. 6. 2. P. 225–250.

  7. Nesterov Yu., Shikhman V. Dual subgradient method with averaging for optimal resource allocation // European Journal of Operational Research. 2018. V. 270. 3. P. 907–916.

  8. Ivanova A., Dvurechensky P., Gasnikov A., Kamzolov D. Composite optimization for the resource allocation problem // arXiv preprint arXiv:1810.00595. 2018.

  9. Нестеров Ю.Е. Метод минимизации выпуклых функций со скоростью сходимости $O(1{\text{/}}{{k}^{2}})$ // Докл. АН СССР. 1983. Т. 269. 39. С. 543–547.

  10. Gasnikov A.V., Gasnikova E.V., Nesterov Yu.E., Chernov A.V. Efficient numerical methods for entropy-linear programming problems // Comput. Math. and Math. Phys. 2016. V. 56. 4. P. 514–524.

  11. Chernov A., Dvurechensky P., Gasnikov A. Fast Primal-Dual Gradient Method for Strongly Convex Minimization Problems with Linear Constraints // Discrete Optimization and Operations Research: 9th International Conference, DOOR 2016, Vladivostok, Russia, September 19–23, 2016 Proceedings. Springer International Publishing, 2016. P. 391–403.

  12. Dvurechensky P., Gasnikov A., Gasnikova E., Matsievsky S., Rodomanov A., Usik I. Primal-Dual Method for Searching Equilibrium in Hierarchical Congestion Population Games // Supplementary Proceedings of the 9th International Conference on Discrete Optimization and Operations Research and Scientific School (DOOR 2016) Vladivostok, Russia, September 19–23, 2016. P. 584–595. arXiv:1606.08988.

  13. Anikin A., Gasnikov A., Turin A., Chernov A. Dual approaches to the minimization of strongly convex functionals with asimple structure under affine constraints // Comput. Math. and Math. Phys. 2017. V. 57. № 8. P. 1262–1276.

  14. Dvurechensky P., Gasnikov A., Kroshnin A. Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn’s Algorithm // Proceedings of the 35th International Conference on Machine Learning. 2018. V. 80. P. 1367–1376. arXiv:1802.04367.

  15. Nesterov Yu., Gasnikov A., Guminov S., Dvurechensky P. Primal-dual accelerated gradient methods with small-dimensional relaxation oracle // arXiv:1809.05895. 2018.

  16. Guminov S., Dvurechensky P., Gasnikov A. On Accelerated Alternating Minimization // arXiv:1906.03622. 2019.

  17. Guminov S.V., Nesterov Yu.E., Dvurechensky P.E., Gasnikov A.V. Accelerated Primal-Dual Gradient Descent with Linesearch for Convex, Nonconvex, and Nonsmooth Optimization Problems // Doklady Mathematics. 2019. V. 99. P. 125–128.

  18. Kroshnin A., Tupitsa N., Dvinskikh D., Dvurechensky P., Gasnikov A., Uribe C.A. On the Complexity of Approximating Wasserstein Barycenters // Proceedings of the 36th International Conference on Machine Learning. 2019. V. 97. Eds. K. Chaudhuri, R. Salakhutdinov. California, USA: PMLR, 2019. P. 3530–3540. arXiv:1901.08686.

  19. Uribe C.A., Dvinskikh D., Dvurechensky P., Gasnikov A., Nedich A. Distributed Computation of Wasserstein Barycenters Over Networks // 2018 IEEE Conference on Decision and Control (CDC). 2018. P. 6544–6549. arXiv:1803.02933.

  20. Dvinskikh D., Gorbunov E., Gasnikov A., Dvurechensky P., Uribe C.A. On Primal and Dual Approaches for Distributed Stochastic Convex Optimization over Networks // 2019 IEEE Conference on Decision and Control (CDC). 2019. arXiv:1903.09844.

  21. Dvurechensky P., Dvinskikh D., Gasnikov A., Uribe C.A., Nedic A. Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters // Advances in Neural Information Processing Systems. 2018. V. 31. P. 10783–10793. arXiv:1806.03915.

  22. Данскин Д.М. Теория максмина. М.: Советское радио, 1970.

  23. Демьянов В.Ф., Малоземов В. Н. Введение в минимакс. М.: Наука, 1972.

  24. Nesterov Yu. Smooth minimization of non-smooth functions // Math. Programming. 2005. V. 103. P. 127–152.

  25. Юдин Д.Б., Немировский А.С. Информационная сложность и эффективные методы решения выпуклых экстремальных задач // Экономика и матем. методы. 1976. 2. С. 357–369.

  26. Nemirovski A., Onn S., Rothblum U.G. Accuracy certificates for computational problems with convex structure // Math. of Operations Research. 2010. V. 35. 1. P. 52–78.

  27. Lan G., Zhou Y. Random gradient extrapolation for distributed and stochastic optimization // SIAM Journal on Optimization. 2018. V. 28. 4. P. 2753–2782.

  28. Bubeck S. Convex optimization: Algorithms and complexity // Foundations and Trends in Machine Learning. 2015. V. 8. № 3/4. P. 231–357.

  29. Nesterov Yu. Implementable tensor methods in unconstrained convex optimization: tech. rep. Universite catholique de Louvain, Center for Operations Research and Econometrics (CORE). 2018.

  30. Gasnikov A., Dvurechensky P., Gorbunov E., Vorontsova E., Selikhanovych D., Uribe C.A., Jiang B., Wang H., Zhang S., Bubeck S., Jiang Q., Lee Y.T., Li Y., Sidford A. Near Optimal Methods for Minimizing Convex Functions with Lipschitz p-th Derivatives // Proceedings of the Thirty-Second Conference on Learning Theory. 2019. V. 99. P. 1392–1393. URL: http://proceedings.mlr.press/v99/gasnikov19b.html. arXiv:1809.00382.

  31. Zhou K., Shang F., Cheng J. A simple stochastic variance reduced algorithm with fast convergence rates // arXiv preprint arXiv:1806.11027. 2018.

  32. Zhou K. Direct acceleration of SAGA using sampled negative momentum //arXiv preprint arXiv:1806.11048. 2018.

  33. Niu F., Recht B., Re C., Wright S.J. Hogwild: A lock-free approach to parallelizing stochastic gradient descent // Advances in Neural Information Processing Systems. 2011. P. 693–701.

  34. Jin C., Netrapalli P., Ge R., Kakade S.M., Jordan M.I. A short note on concentration inequalities for random vectors with subgaussian norm // arXiv preprint arXiv:1902.03736. 2019.

  35. Juditsky A., Nemirovski A. Large deviations of vector-valued martin-gales in 2-smooth normed spaces: tech. rep. HAL: hal-00318071. 2008. URL: http://hal.archives-ouvertes.fr/hal-00318071/. arXiv:0809.0813.

  36. Nesterov Yu. Lectures on Convex Optimization. 2nd ed. Springer, 2018.

  37. Нестеров Ю.Е. Алгоритмическая выпуклая оптимизация: дисc. д.ф.-м.н.: 01.01.07. М.: МФТИ, 2013.

  38. Beck A. Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with MATLAB. SIAM, Philadelphia, 2014.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Журнал вычислительной математики и математической физики

Архивы выпусков Информация о журнале Отправить рукопись в журнал