Решение энтропийно-регуляризованной транспортной задачи при малом параметре регуляризации (1187428), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Восстановление потоков по ребрам из потоковпо путям задается задается преобразованием Θ: y = Θx,Θ = {δep }.Также введем удельные затраты на проезд по пути p Cp (x) =Pe∈E τe (ye )δep ,где τe (ye ) удельные затраты на проезд по ребру e.Рассмотрим популяционную игру, в которой имеется N однотипныхагентов. Множество чистых стратегий каждого агента - P, выигрышемот использования стратегии p ∈ P будут минус убытки (−Cp (x)).Перейдем к описанию динамики поведения агентов. Пусть в моментвремени t игрок использует стратегию p.

Вероятность того, что он перейдет на стратегию q в промежутке времени (t; t + ∆t) равна λpq (t)∆t +o(∆t).λpq (t) ≡ λpq = λPq ({Cp (x(t))}p∈P ),где λ - интенсивность смены стратегии агентами, а21(19)Pq ({Cp (x(t))}p∈P ) = P (q = arg min{Cp (x(t)) + ηp }).p∈P(20)Если ηp ≡ 0, то получим динамику наилучших ответов, то есть агенты, имея информацию в предыдущий день, выбирают наилучшую стратегию на её основании. А если ηp - независимые одинаково распределенные случайные величины с распределением Гумбеля, которое часто используется для прогнозирования экстремальных значений случайных ве−ηличин по известным экстремальным значениям: P (ηp < η) = exp(−e ω −E ),где ω ∈ (0, ω0 ], E ≈ 0.5772 - константа Эйлера (возникает в математическом ожидании распределения Гумбеля), а V ar[ηp ] =ω2 π26 ,то получаемлогит-динамику [7]:exp(−Cp (x(t))/ω)p∈P exp(−Cp (x(t))/ωPq ({Cp (x(t))}p∈P ) = P(21)Объяснение для такой динамики может быть следующее: каждыйагент имеет некоторое представление о загрузке транспортной сети, ноне наблюдает её точно или пытается спрогнозировать будущую загрузку.

Кроме того, люди являются мини-максерами по своей природе - онивыбирают наилучшую стратегию для самого худшего сценария из всехвозможных. Так обеспечивается гарантированный выигрыш, но, разумеется, выбранная стратегия может не являться оптимальной для реализующейся ситуации. Стоит отметить, что ω имеет размерность затрат,а при ω → 0+ происходит вырождение в динамику наиулучших ответов. В [8] показано, что стохастическое равновесие Нэша-Вардропа приPω → 0+ достигается в x∗ = arg minx p∈P xp ln xp .Как отмечалось ранее, задачe поиска равновесного распределения потоков по путям обычно сводят к эквивалентной оптимизационной задаче.В [8] была предложена, так называемая, облачная модель, дающая физическую интерпретацию оптимизационной задаче.224.2.3Облачная модельПусть все вершины, отвечающие источникам корреспонденций соединены ребрами с одной вспомогательной вершиной (облако 1).

Пусть также все вершины, соответствующие стокам соединены с другой вспомогательной вершиной (облако 2). На всех новых ребрах установим постоянные веса. Для ребер, исходящих из источников, веса λLi могут бытьпроинтерпретированны как средние затраты на проживание (в данномрайоне), а для источников веса λWi - уровень средней заработной платыв единицу времени. Будем считать, что равновесное распределение потоков по путям стационарно. Как отмечалось ранее, зная распределениепотоков по путям, можно отдельно не учитывать затраты по каждомуребру, но лишь для конкретной корреспонденции.Таким образом, мы получили взвешенный транспортный граф с одним источником и одним стоком во вспомогательных вершинках.

Остальные вершины соответствуют районам в модели расчета матрицы корреспонденций. Все ребра имеют постоянные(не зависит от загрузки) веса:для облаков λLi и λWi , для всех остальных Cij . При рассмотрении логитдинамики с ω =1β(β обратно пропорционально затратам) получим, чтопоиск равновесия приводит к задаче [8]:Pnmini,j=1 dij =1,dij ≥0nhXi,j=1dij ln dij +βnXdij Cij +βi,j=1nX(λLii=1nXj=1dij )−βnXj=1(λWjnXi=1(22)В такой интерпретации хоть λL , λW и похожи на множители Лагранжа, но в данной модели имеют другую интерпретацию, так как они быливведены на этапе построения графа. Здесь λLi и λWj стоит понимать какпотенциалы притяжения и отталкивания районов.23idij ) .5Задача энтропийно-линейного программирования5.1ВведениеЗадачи энтропийо-линейного программирования возникают в самыхразных приложениях.

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

Из-за этого шума в асимптотике появляется энтропия. Например, в первоначальных экспериментах по расчету Москвы исследователи заметили, что используемые модели не соответствуютреальным данным, но, если добавить энтропию, то модели будут соответствовать действительности.Рассмотрим задачу ЭЛП:f (x) =nXi=1где Sn (1) =ximin ,xi ln( ) →ηix∈Sn (1),Ax=bnx ∈ R : xi ≥ 0, i = 1, n,симплекс. Число строк матрицы A m << n.Построим двойственную задачу:24Pni=1 xi(23)= 1- единичныйnXxixi ln( ) =ηix∈Sn (1),Ax=bi=1nXxi + hλ, b − Axi =min maxmminx∈Sn (1) λ∈Rmax mini=1nXλ∈Rm x∈Sn (1)(24)xi + hλ, b − Axi =i=1max hλ, bi − lnnXλ∈Rmηi exp([A λ]i ) .Ti=1Двойственная задача примет вид:ϕ(λ) = hλ, bi − lnnXηi exp([AT λ]i ) → maxm .(25)λ∈Ri=1А решения прямой и двойственной задачи связаны следующим образом:ηi exp([AT λ]i )xi (λ) = Pn.T λ] )ηexp([Akkk=1(26)Под (εf , ε)-решением задачи (23) будем понимать такой вектор x, что:f (x) − f ∗ ≤ εf ,||Ax − b||2 ≤ ε,(27)где f ∗ = minx∈S1 (n),Ax=b f (x).В [9] показывается, что||∇ϕ(λ2 ) − ∇ϕ(λ1 )||2 ≤ L||λ2 − λ1 ||2 ,(28)где L = max1≤i≤n ||Ai ||2 2 , Ai - i-ый столбец матрицы A.Быстрый градиентный метод [10] для задачи (25) гарантирует, чтоpx(λ) является (εf , ε) - решением задачи (23) через O( LR2 /ε̄) итера2ε2fεций.

Здесь R = ||λ∗ ||2 - размер решения задачи (25), а ε̄ = min( 2L, 2LR2)25- точность решения задачи (25). Финальная оценка на число итерацийбудет иметь вид:LR LR2O(max{,}).εεf(29)Об улучшении этой оценки можно прочитать в [3].5.2Связь решений исходной и энтропийнорегуляризованной задачПусть поставлена задачаf (x) →min,(30)x∈Sn (1),Ax=bтогда энтропийно-регуляризованная задача будет иметь вид:fγ (x) = f (x) + γnXxk ln xk →k=1Оказывается, если γ ≤ε4 ln n ,min.(31)x∈Sn (1),Ax=bто из того, чтоεfγ (xN ) − fγ ∗ ≤ ,2следуетf (xN ) − f ∗ ≤ ε5.3Энтропийная регуляризация транспортной задачиДопустим, что решается транспортная задача (ограничения, записанные в таком виде, называются балансовыми):nXf (X) =i,j=1Cij Xij → Pnmin,PnX=L̃,X=W̃ijiijjj=1i=1Xij ≥0,i,j=1,nгде dim X = n2 ,Pni=1 L̃i =Pnj=1 W̃j26= 1.(32)Сложность решения такой задачи вообще говоря O(n3 ln n).

Исходяиз описанных соображений об энтропии, запишем регуляризованную задачу:fγ (X) =nXCij Xij + γi,j=1nXi,j=1Xij ln Xij → PnminPnj=1 Xij =L̃i ,.(33)i=1 Xij =W̃jXij ≥0,i,j=1,nЗдесь параметр γ - параметр регуляризации, по сути является корнемиз дисперсии шума, который возникает в системе.Это задача энтропийно-линейного программирования. В данной работе будет произведено сравнение алгоритма Синкхорна (балансировки),решающего задачу ЭЛП именно с балансовыми ограничениями с модификацией ускоренного градиентного метода (она носит название «методподобных треугольников»), которая может быть применена для задачиЭЛП с любыми афинными ограничениями.5.4Метод балансировкиДанный метод существенно использует вид ограничений и условиесохранения баланса.

Запишем двойственную задачуnXλi + µj − Cij) − hλ, L̃i − hµ, W̃ i → minϕ(x = (λ, µ)) = γ lnexp(λ,µγi,j=1(34)Необходимые условия достижения минимума:∇λ ϕ(λ∗ , µ∗ ) = 0∗∗∇µ ϕ(λ , µ ) = 0Посчитаем градиенты27(35)Pnλi +µj −Cij)∂ϕj=1 exp(γ= γ Pn− L̃i = 0, i = 1, nλ +µ −C∂λiγ i,j=1 exp( i γj ij )Pnλi +µj −Cij)∂ϕi=1 exp(γ= γ Pn− W̃j = 0, j = 1, nλ +µ −C∂µjγ i,j=1 exp( i j ij )(36)γВведем обозначениеq=nXexp(i,j=1λi + µj − Cij).γ(37)Тогдаnλi + µj − Cij1Xexp() = L̃iq j=1γn1Xλi + µj − Cijexp() = W̃jq i=1γХочется построить итерационный процесс такого вида:λk+1 = T1 (µk )µk=1 = T2 (λk )Для этого перепишем (38)nµj − Cijexp(λi /γ) Xexp() = L̃iqγj=1nexp(µj /γ) Xλi − Cijexp() = W̃jqγi=1Выражаем λi и µj28(38)nh 1 Xµj − Cij iλi = −γ lnexp() =γq L̃i j=1nh 1 Xµj − Cij i−γ lnexp() + γ ln qγL̃i j=1nh 1 Xλi − Cij i) =µj = −γ lnexp(γq W̃j i=1nh 1 Xλi − Cij i−γ lnexp() + γ ln qγW̃j i=1Стоит обратить внимание на особенность функционала (34):  11....(39)ϕ(λ + s1  .

Характеристики

Список файлов ВКР