Решение энтропийно-регуляризованной транспортной задачи при малом параметре регуляризации (1187428), страница 5
Текст из файла (страница 5)
, µ + s2 . ) = ϕ(λ, µ)11PPЗдесь используетя, что ni=1 L̃i = nj=1 W̃j = 1. Таким образом, точка минимума является вырожденной и находится с точностью до сдвига.Поэтому, перейдя в другую систему, мы занулим аддитивное слагаемоеγ ln q, и это не повлияет на качество решения по функции.В итоге итеративная процедура примет вид:nh 1 Xµkj − Cij iexp()= −γ lnγL̃i j=1nh 1 Xλki − Cij i= −γ lnexp()γW̃j i=1λk+1iµk+1j(40)Решение исходной задачи находится следующим преобразованием:XijNNexp(λNi + µj − Cij )=q29(41)5.5Обсуждение метода балансировкиСущественным минусом балансировки является невозможность её применения при параметре γ → 0. При таких значениях параметра методсначала начинает слишком долго работать, а впоследствии выходит запределы машинной точности.
Но в природе обычно возникают частоЭЛП маленькие γ. Это наблюдается и во многих транспортных задачах, и в задаче поиска барицентра Вассерштейна. Обоснованием этогоможет служить подразумевающаяся близость стохастического равновесия, за которое отвечает энтропия, и равновесия Нэша. Дело в том, чтоагенты сети принимают решения, основываясь на зашумленных альтернативах, так как они не могут наблюдать абсолютно точное состояниетранспортной сети. Параметр γ является характеристикой этого шума.Кроме того, метод балансировки не гарантирует нахождение решения снаименьшей нормой, в отличие от следующего метода.Продемонстрируем процесс схождения метода балансировки к решению.
Для этого будем использовать матрицу C попарных евклидовых расстояний, нормированных на среднее значение, а вектора L и Wвозьмем одинаковыми с элементами1n.Относительную точность возь-мем 0.05, n = 400. Получился искусственный пример поиска расстояниямежду одинаковыми векторами. Процесс схождения к решению можнонаблюдать на следующем графике.30Рис. 1: Процесс нахождения расстояния между одинаковыми векторамиметодом балансировки5.6ASTMВ данном разделе будет обсуждаться модификация быстрого градиентного метода, предложенная Ю.Е. Нестеровым. Будет дана оценкаскорости сходимости ASTM и мотивация к его применению в задачахэнтропийно-линейного программирования.Рассматривается задача оптимизацииmin ϕ(λ),λ∈Λ(42)где Λ - замкнутое выпуклое множество, ϕ(λ) - выпуклая функция слипшецовым градиентом с константой L.Введем проксимальную структуру, которую часто используют в проксимальных градиентных методах [11].
Выберем некоторую норму k · k в31пространстве λ и прокс-функцию d(λ) (непрерывную и выпуклую на Λ).Кроме того, d(λ)1. допускает непрерывность по λ ∈ Λ0 выбора субградиентов ∇d(λ),где λ ∈ Λ0 ⊆ Λ - множество всех λ, при которых ∇d(λ) существует;2. сильно выпукла в 1-норме на Λ, то есть для любого λ ∈ Λ0 , η ∈ Λ,d(η) − d(λ) − h∇d(λ), η − λi ≥ 12 kη − λk2 .Также определим расстояние Брэгмана: V [ζ](λ) := d(λ) − d(ζ) −h∇d(ζ), λ − ζi, λ ∈ Λ, ζ ∈ Λ0 .
Легко видеть, что1V [ζ](λ) ≥ kλ − ζk2 ,232λ ∈ Λ, ζ ∈ Λ0 .(43)5.6.1Алгоритм и анализ сложностиАлгоритм 1 Адаптивный метод подобных треугольников (ASTM)Input: начальная точка λ0 ∈ Λ0 , начальное значение L0 > 0, prox-setup:d(λ) – сильная выпуклость по 1-норме k · k, V [ζ](λ) := d(λ) − d(ζ) −h∇d(ζ), λ − ζi, λ ∈ Λ, ζ ∈ Λ0 .1:Присваиваем k = 0, C0 = α0 = 0, η0 = ζ0 = λ0 .2:repeat3:Set Mk = Lk /2.4:repeatПрисваиваем Mk = 2Mk , находим αk+1 как наибольший корень5:уравнения2Ck + αk+1 = Mk αk+1.(44)Ck+1 = Ck + αk+1(45)и6:Высчитываемλk+1 =7:αk+1 ζk + Ck ηk.Ck+1(46)Высчитываемζk+1 = arg min{V [ζk ](λ)+αk+1 (ϕ(λk+1 )+h∇ϕ(λk+1 ), λ−λk+1 i)}. (47)λ∈Λ8:Высчитываемηk+1 =9:αk+1 ζk+1 + Ck ηk.Ck+1untilϕ(ηk+1 ) ≤ ϕ(λk+1 )+h∇ϕ(λk+1 ), ηk+1 −λk+1 i+10:11:(48)Mkkηk+1 −λk+1 k2 .
(49)2Присваиваем Lk+1 = Mk /2, k = k + 1.until ...Output: Точка ηk+1 .Лемма 1. Алгоритм 1 корректно определен в том смысле, что внутренний цикл конечен.33Доказательство. Количество циклов в каждом шаге конечно. Это следует из того, что на каждом шаге цикла мы увеличиваем Lk+1 в 2 раза,а значит Lk+1 через конечное количество шагов станет больше L, поэтому из L - липшевости ∇fj (x) будет через конечное количество шаговвыполнено условие выходы и цикла.Лемма 2.
Пусть последовательности {λk , ηk , ζk , αk , Ck }, k ≥ 0 сгенерированны Алгоритмом 1. Тогда для всех λ ∈ Λ, это означает, чтоαk+1 h∇ϕ(λk+1 ), ζk − λi ≤ Ck+1 (ϕ(λk+1 ) − ϕ(ηk+1 )) + V [ζk ](λ) − V [ζk+1 ](λ).(50)Доказательство. Заметим, что из оптимальности условия в (62), длялюбого λ ∈ Λ, мы имеемh∇V [ζk ](ζk+1 ) + αk+1 ∇ϕ(λk+1 ), λ − ζk+1 i ≥ 0.(51)По определению V [ζ](λ), мы получаем для любого λ ∈ Λ,V [ζk ](λ) − V [ζk+1 ](λ) − V [ζk ](ζk+1 )(52)=d(λ) − d(ζk ) − h∇d(ζk ), λ − ζk i− (d(λ) − d(ζk+1 ) − h∇d(ζk+1 ), λ − ζk+1 i)− (d(ζk+1 ) − d(ζk ) − h∇d(ζk ), ζk+1 − ζk i)= h∇d(ζk ) − ∇d(ζk+1 ), ζk+1 − λi= h−∇V [ζk ](ζk+1 ), ζk+1 − λi.Далее для любого λ ∈ Λ,34(53)αk+1 h∇ϕ(λk+1 ), ζk −λi = αk+1 h∇ϕ(λk+1 ), ζk −ζk+1 i+αk+1 h∇ϕ(λk+1 ), ζk+1 −λi(51)≤ αk+1 h∇ϕ(λk+1 ), ζk − ζk+1 i + h−∇V [ζk ](ζk+1 ), ζk+1 − λi(53)= αk+1 h∇ϕ(λk+1 ), ζk − ζk+1 i + V [ζk ](λ) − V [ζk+1 ](λ) − V [ζk ](ζk+1 )(43)1≤ αk+1 h∇ϕ(λk+1 ), ζk − ζk+1 i + V [ζk ](λ) − V [ζk+1 ](λ) − kζk − ζk+1 k22C2(61),(63)= Ck+1 h∇ϕ(λk+1 ), λk+1 −ηk+1 i+V [ζk ](λ)−V [ζk+1 ](λ)− k+1kλk+1 −ηk+1 k222α k+1Mk(60),(45)= Ck+1 h∇ϕ(λk+1 ), λk+1 − ηk+1 i −kλk+1 − ηk+1 k2 +V [ζk ](λ)−V [ζk+1 ](λ)2(64)≤ Ck+1 (ϕ(λk+1 ) − ϕ(ηk+1 )) + V [ζk ](λ) − V [ζk+1 ](λ).Лемма 3.
Пусть последовательности {λk , ηk , ζk , αk , Ck }, k ≥ 0 сгенерированны Алгоритмом 1. Тогда для любого λ ∈ Λ, это означает, чтоCk+1 ϕ(ηk+1 ) − Ck ϕ(ηk ) ≤ αk+1 (ϕ(λk+1 ) + h∇ϕ(λk+1 ), λ − λk+1 i)+V [ζk ](λ) − V [ζk+1 ](λ).(54)Доказательство. Для любого λ ∈ Λ,αk+1 h∇ϕ(λk+1 ), λk+1 −λi = αk+1 h∇ϕ(λk+1 ), λk+1 −ζk i+αk+1 h∇ϕ(λk+1 ), ζk −λi(61)= Ck h∇ϕ(λk+1 ), ηk − λk+1 i + αk+1 h∇ϕ(λk+1 ), ζk − λi≤ Ck (ϕ(ηk ) − ϕ(λk+1 )) + αk+1 h∇ϕ(λk+1 ), ζk − λi(50)≤ Ck (ϕ(ηk ) − ϕ(λk+1 ))+Ck+1 (ϕ(λk+1 ) − ϕ(ηk+1 ))+V [ζk ](λ)−V [ζk+1 ](λ)= αk+1 ϕ(λk+1 ) + Ck ϕ(ηk ) − Ck+1 ϕ(ηk+1 ) + V [ζk ](λ) − V [ζk+1 ](λ).Перегруппируя слагаемые, мы получим утверждение леммы.Теорема 1. Пусть последовательности {λk , ηk , ζk , αk , Ck }, k ≥ 0 сгенерированны Алгоритмом 1.
Тогда, для любого k ≥ 0, это означает,35чтоCk ϕ(ηk ) ≤ min( kXλ∈Λ)αi (ϕ(λi ) + h∇ϕ(λi ), λ − λi i) + V [ζ0 ](λ) .(55)i=0Число вызовов оракула на итерации k ≥ 0 не превышает4k + 2 log2 (2L)L0(56)Доказательство. Поменяяем переменную счетчик в Лемме 2 с k на i, ипросуммируем все неравенства i = 0, ..., k − 1. Тогда для любого λ ∈ Λ,Ck ϕ(ηk )−C0 ϕ(η0 ) ≤k−1Xαi+1 (ϕ(λi+1 ) + h∇ϕ(λi+1 ), λ − λi+1 i)+V [ζ0 ](λ)−V [ζk ](λ).i=0(57)Откуда, C0 = α0 = 0 and V [ζk ](λ) ≥ 0, λ ∈ Λ,Ck ϕ(ηk ) ≤kXαi (ϕ(λi ) + h∇ϕ(λi ), λ − λi i) + V [ζ0 ](λ),λ ∈ Λ.(58)i=0Взяв минимум правой части по λ ∈ Λ, получим первое утверждениетеоремыLk ≤ 2LЭто следует из того, что мы выйдем из цикла ранее, чем Lk станет больше2L.Оценим общее число обращений за значениями функций.
Пусть jk - количество дополнительных циклов k-ого шага. Тогда общее количествообращений за значениями всех функций fj (x) равноNXk=12(jk + 1) =NX2((jk − 1) + 2) =k=1= 4N + 2 log2 (NXk=12(log2 (Lk) + 2) =Lk−1LN2L) ≤ 4N + 2 log2 ( )L0L0Второе равенство следует из того, что Lk = 2jk Lk−12 . Поэтому мы получаем, что в среднем на каждом шаге мы будем считать значение всех36функций 4 раза. Можно показать, что градиент всех функций fj (x) мыв среднем будем считать на каждом шаге 2 раза.Следствие 1. Пусть последовательности {λk , ηk , ζk , αk , Ck }, k ≥ 0 сгенерированны Алгоритмом 1.
Тогда, для всех k ≥ 0, это означает, чтоϕ(ηk ) − min ϕ(λ) ≤λ∈ΛV [ζ0 ](λ∗ ),Ck(59)где λ∗ - решение minλ∈Λ ϕ(λ) s.t. V [ζ0 ](λ∗ ) минимально среди всех решений.Доказательство. Пусть λ∗ - решение minλ∈Λ ϕ(λ) s.t. V [ζ0 ](λ∗ ) - минимально среди всех решений. Используя выпуклость ϕ, из Теоремы 1,получаемCk ϕ(ηk ) ≤kXαi ϕ(λ∗ ) + V [ζ0 ](λ∗ ).i=0Поскольку Ck =Pki=0 αi ,получим утверждение Следствия.Лемма 4. Пусть для последовательности αk выполненоAk =kXαii=0α0 = 0Ak = Lαk2Тогда верно следующее рекуррентное соотношение ∀k ≥ 0αk+11=+2Lr1+ αk224Lи ∀k ≥ 1k+12L(k + 1)2Ak ≥4Lαk ≥37Доказательство.2Lαk+1= Ak+12Lαk+1= Ak + αk2Lαk+1− αk+1 − Ak = 0Решая данное квадратное уравнение получаем, чтоp1 ± 1 + 4LAkαk+1 =2Lrr111Ak1αk+1 =++=++ αk2222L4LL2L4LЕсли k = 0, то получаем, что α1 = L1 и A1 ≥ L1 , база индукции верна.Пусть данная лемма верна для k, докажем для k + 1:r112 ≥ 1 +ααk+1 =++αkk2L4L22LИз того, чтоαk ≥k+1,2Lполучаем:αk+1 ≥иAk+1 =f (xN ) − f (x∗ ) ≤2Lαk+1k+22L(k + 2)2≥4L4LR2(N +1)2Просуммируем нер-во из леммы по k = 0, ..., N − 1AN f (xN ) − A0 f (x0 ) + V (u, uN ) − V (u, u0 ) ≤ (AN − A0 )f (u)AN f (xN ) + V (u, uN ) − V (u, u0 ) ≤ AN f (u)Возьмем u = x∗ , воспользуемся тем, что V (x∗ , uN ) ≥ 0 и u0 = x0 ,тогдаdefAN (f (xN ) − f∗ ) ≤ R2 { = V (x∗ , x0 )}38Следствие 2.
Рассмотрим неравенствоAN f (xN ) + V (u, uN ) − V (u, u0 ) ≤ AN f (u)Возьмем u = x∗ , воспользуемся тем, что f (xN ) ≥ f (x∗ ), тогдаV (x∗ , uN ) ≤ V (x∗ , u0 )То есть последовательность uN ограничена.1kx∗ − uN k2 ≤ V (x∗ , uN ) ≤ R22По индукции:2αu+Ax11k+1k+1kk2 =x−kx∗ − xk+1 k = ∗22Ak+121α(x−u)+A(x−x)k+1 ∗k+1k ∗k ≤= 2Ak+11 αk+11 Ak≤kx∗ − uk+1 k2 +kx∗ − xk k2 ≤ R22 Ak+12 Ak+1То есть последовательность, генерированная методом, ограничена.В следущей главе использовался прямо-двойственный вариант ASTM.39Алгоритм 2 Прямо-двойственный адаптивный метод подобных треугольников (PDASTM)Input: стартовая точка λ0 = 0, L0 > 0, точности граничных условийεf , εeq , εin > 0.1:Присваиваем k = 0, C0 = α0 = 0, η0 = ζ0 = λ0 = 0.2:repeat3:Присваиваем Mk = Lk /2.4:repeat5:Присваиваем Mk = 2Mk , находим αk+1 как самый большой корень уравнения2Ck+1 := Ck + αk+1 = Mk αk+1.6:Вычисляем(1)(2)λk+1 = (λk+1 , λk+1 )T =7:αk+1 ζk + Ck ηk.Ck+1(1)(2)(ζk+1 , ζk+1 )Tn1kλ − ζk k22 +λ∈Λ2oαk+1 (ϕ(λk+1 ) + h∇ϕ(λk+1 ), λ − λk+1 i) .= arg min(62)Вычисляем(1)(2)ηk+1 = (ηk+1 , ηk+1 )T =9:(61)Вычисляемζk+1 =8:(60)αk+1 ζk+1 + Ck ηk.Ck+1(63)untilϕ(ηk+1 ) ≤ ϕ(λk+1 )+h∇ϕ(λk+1 ), ηk+1 −λk+1 i+40Mkkηk+1 −λk+1 k22 .
(64)2Присваиваем10:x̂k+1 =k+1XCk+1i=0αi x(λi ) =αk+1 x(λk+1 ) + Ck x̂k.Ck+1Присваиваем Lk+1 = Mk /2, k = k + 1.11:12:1until |f (x̂k+1 ) + ϕ(ηk+1 )| ≤ ε̃f , kA1 x̂k+1 − b1 k2 ≤ ε̃eq , ρ(A2 x̂k+1 −b2 , −K) ≤ ε̃in .Output: Точки x̂k+1 , ηk+1 .5.7Сравнение ASTM и метода балансировкиВсе эксперименты проводились на ЭВМ с процессором Intel Core i52410M 2.3 ГГц и оперативной памятью 4Гб с помощью языка программирования Python 2.7 (без вставок на языке программирования C)подуправлением оперативной системы Ubuntu 14.04 (64 разрядная).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
