ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ

Том 55

2019

Вып. 2

УДК 621.391 : 621.394/395.74

А.А. Пухальский

ГЕОМЕТРИЯ БОЛЬШИХ ОЧЕРЕДЕЙ

Предлагается подход к нахождению наиболее вероятных траекторий, веду-

щих к образованию длинных очередей в эргодической сети Джексона, основан-

ный на решении уравнений Гамильтона. Так как соответствующий гамильто-

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

использовать аппарат негладкого анализа. Обращение уравнений Гамильто-

на во времени приводит к уравнениям жидкостной динамики двойственной

сети. Соответственно, оптимальные траектории есть обращенные во времени

жидкостные траектории двойственной сети. Эти траектории с необходимостью

проходят через области, удовлетворяющие некоторому условию “существенно-

сти”. Результаты проиллюстрированы на примере сети Джексона из двух узлов.

Установлены также свойства субстохастических матриц, которые могут пред-

ставлять самостоятельный интерес.

Ключевые слова: теория массового обслуживания, сеть Джексона, большие

уклонения, принцип больших уклонений, оптимальные траектории, уравнения

Гамильтона, двойственные марковские процессы, жидкостная динамика.

DOI: 10.1134/S0555292319020050

§1. Оптимальные траектории в сети Джексона

и вариационные задачи с нефиксированным временем

Принцип больших уклонений позволяет находить грубые асимптотики вероятно-

стей достижения случайным процессом нетипичных значений и наиболее вероятные

сценарии осуществления редких событий. Для этого необходимо решить вариацион-

ную задачу минимизации функции уклонений (называемую также “функционалом

действия”) по траекториям, которые реализуют такие события. Как правило, ищет-

ся решение уравнения Эйлера - Лагранжа (см., например, [1, 2]). В данной статье

на примере сети Джексона изучаются возможности подхода, состоящего в решении

уравнений Гамильтона.

Рассматривается (экспоненциальная) сеть Джексона из K узлов с матрицей

маршрутизации P = (p_kℓ) спектрального радиуса меньше единицы, с интенсивно-

стями входящих потоков λ_k > 0 и интенсивностями обслуживания в узлах μ_k > 0

(см., например, [3]). Обозначим через Q_k(t) длину очереди в узле k в момент t,

и пусть Q(t) = (Q₁(t), . . . , Q_K (t))^T , где^T - оператор транспонирования. Для J ⊂

⊂ {1, 2, . . ., K} обозначим через F_J множество векторов x = (x₁, . . . , x_K)^T , таких

что x_i = 0 при i ∈ J и x_i > 0 при i ∈ J. Как обычно принято, J^c = {1, 2, . . . , K} \ J.

Обозначим также π(u) = u lnu - u + 1, если u > 0, и положим π(0) = 1. Пусть 1_Γ

представляет собой индикаторную функцию множества Γ, которая равна 1 на Γ

и 0 вне Γ. Обозначим через SK×K+ множество субстохастических (по строкам) мат-

риц размера K×K, через I - единичную матрицу размера K×K, а через D(R₊, RK+ ) -

пространство Скорохода непрерывных справа и имеющих пределы слева функций,

заданных на R₊ и принимающих значения в RK+ , снабженное метрикой, превраща-

ющей его в полное метрическое сепарабельное пространство (см., [4,5]). Следующий

результат получен в [6]. (Предполагается, что произведение функции π и числа 0

равно нулю, даже если аргумент функции π равен бесконечности, и что 0/0 = 0.)

Теорема 1. Пусть Q(0) = 0 ∈ RK+. Тогда при n → ∞ процессы (Q(nt)/n,

t ∈ R+) удовлетворяют принципу больших уклонений в D(R+, RK+) с фyнкцией

уклонений I(q), которая для абсолютно непрерывных функций q = (q(t), t ∈ R₊),

таких что q(0) = 0 ∈ RK+, имеет вид

∫∞

I(q) = L(q(t),

˙q(t)) dt,

где

∑

L(x, y) =

1FJ (x)L_J(y),

J⊂{1,2,...,K}

L_J(y) =

inf

ψ_J(a, d, ϱ)

(1.1)

(a,d,ϱ)∈RK+ ×RK+ ×SK×K+ :

y=a+(ϱ^T -I)d

∑

)

⁽a_k)

⁽d_k)

⁽d_k

ψ_J (a, d, ϱ) =

λ_k +

μ_k +

1(μk,∞)(dk)μk +

λ_k

μ_k

k=1

k∈J^c

k∈J

⎡

∑

⎞(

)⎤

^⎛1-

ϱ_kℓ

∑ K∑

)

∑

⁽ϱ_kℓ

+ d_k ⎣

p_kℓ

+π⎝ℓ=1

⎠ 1- p_kℓ ⎦.

(1.2)

p_kℓ

∑

k=1

ℓ=1

1- p_kℓ

ℓ=1

Если функция q не является абсолютно непрерывной или если q(0)

= 0, то

I(q) = ∞.

В развернутом виде утверждение теоремы означает следующее: множества

{q ∈ D(R₊, R^K) : I(q) ≤ u} являются компактами при всех u ≥ 0 и выполняют-

ся неравенства

lim inf

ln P(q ∈ G) ≥ - inf I(q)

n→∞ n

q∈G

при условии, что G - открытое подмножество D(R₊, RK+ ), и

lim sup

ln P(q ∈ F ) ≤ - inf I(q)

n→∞ n

q∈F

при условии, что F - замкнутое подмножество D(R₊, RK+ ). Заметим, что форму-

лируемый в теореме 1 принцип больших уклонений установлен также в [7, 8], где

функция L_J имеет другой вид.

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

рифм вероятности попадания процесса Q(nt)/n в заданное множество S на больших

интервалах времени близок к - inf I(q), где S^′ = {q : q(0) = 0, q(T ) ∈ S для неко-

q∈S^′

торого T > 0}. Если последний инфимум достигается единственной функцией q, то

попадание Q(nt)/n в множество S происходит с вероятностью, близкой к единице,

движением в малой окрестности этой функции. В данной статье основное внима-

ние уделяется вопросу нахождения для эргодической сети Джексона такой функ-

ции q, начинающейся в начале координат и достигающей фиксированной точки в

∫

некоторый момент T , для которой L(q(t),

˙q(t)) dt минимален. Показано, что обра-

щение во времени уравнений Гамильтона для оптимальных траекторий приводит

к уравнениям жидкостной динамики двойственной сети. Это наблюдение позволяет

подтвердить для эргодической сети Джексона справедливость “фольклорной” теоре-

мы, утверждающей, что наиболее вероятная траектория, обеспечивающая “большое

уклонение” эргодического марковского процесса, является обращенной во време-

ни траекторией жидкостного предела двойственного процесса (см., например, [9]).

(В статфизической литературе соответствующее свойство известно как обобщенный

принцип Онзагера - Махлупа: траектория флуктуации есть обращенная во време-

ни траектория релаксации двойственной динамики; см., например, [10].) Показано,

что найденная оптимальная траектория представляет собой предел (условного) за-

кона больших чисел при условии, что длины очередей в сети достигают аномально

больших значений. Найдено необходимое и достаточное условие, при выполнении

которого грань F_J может содержать часть оптимальной траектории, а следователь-

но, жидкостной траектории. В заключение на примере эргодической сети Джексона

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

траекторий. Кроме того, в статье установлены свойства субстохастических матриц,

которые могут представлять самостоятельный интерес.

Так как функции L_J (y) являются выпуклыми по лемме 4.2 в [6], то в силу нера-

венства Йенсена оптимальное движение в области с постоянной динамикой, т.е.

в грани F_J , происходит по прямой. Заметим также, что если J^′ ⊂ J^′′, то ψ_J′(a, d, ϱ) ≥

≥ ψ_J′′(a,d,ϱ), и как следствие, L_J′(y) ≥ L_J′′(y). Поэтому если начальная и конечная

точки участка траектории принадлежат F_J , то движение по прямой “выгоднее”, чем

движение через смежные области F_J′, где J^′ ⊂ J. Более того, будет показано, что оп-

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

граням F_J с убывающими по включению множествами J, если не считать конеч-

ную точку, для которой свойство убывания J может не выполняться. В частности,

каждая из граней F_J содержит не более одного отрезка.

Для нахождения оптимальных траекторий в гранях F_J будет использоваться

следующий общий результат. Для функции f(y), удовлетворяющей условию Лип-

шица локально, будем обозначать через ∂f(y) обобщенный градиент f в точке y

(см. [11]). Если f выпукла, что верно для приложений в данной статье, то обобщен-

ный градиент совпадает с субдифференциалом (см., например, [12]). Определение

конуса, нормального к непустому замкнутому множеству в точке этого множества,

как сопряженного к касательному конусу в этой точке можно найти в [11, с. 19].

Для случая выпуклого множества определение сводится к определению, данному

в [12, с. 32] как совокупности векторов, нормальных к множеству в рассматривае-

мой точке, где вектор z называется нормальным к выпуклому множеству S в точке

x ∈ S, если z · (y - x) ≤ 0 для всех y ∈ S. (Здесь и далее a · b используется для обо-

значения скалярного произведения векторов a и b. Кроме того, сокращение “п.в.”

означает “почти всюду по мере Лебега”.)

Лемма 1. Пусть L(x,y) - функция из Rk ×R^k в R, удовлетворяющая условию

Липшица по (x, y) локально и выпуклая по y. Предположим, что функция

H (x, p) = sup (p · y - L(x, y))

(1.3)

y∈R^k

удовлетворяет условию Липшица локально (по (x, p)). Пусть g(x) - полунепре-

рывная сверху функция, удовлетворяющая условию Липшица локально. Пусть S -

∫

выпуклое замкнутое подмножество R^k и x₀ ∈ R^k. Если минимум

L(x(t), x(t)) dt

по T ≥ 0 и по абсолютно непрерывным функциям x(t), таким что x(0) = x0,

x(T ) ∈ S и g(x(t)) ≤ 0 для всех t ≤ T , достигается для T = T^∗ и x(t) = x^∗(t), то

существуют мера μ на [0, T^∗], a также μ-измеримая функция γ(t) и абсолютно

непрерывная функция p(t), обе принимающие значения в R^k, такие что имеют

место следующие свойства:

1. γ(t) ∈ ∂^>g(x^∗(t)) для μ-почти всех t ∈ [0, T^∗], и носитель меры μ содержится

в множестве {t ∈ [0, T^∗] : ∂^>g(x^∗(t)) = ∅}, где ∂^>g(x) представляет собой вы-

пуклую оболочку пределов последовательностей γ_i, удовлетворяющих условиям

γ_i ∈ ∂g(x_i), x_i → x, g(x_i) > 0;

(

)

]

[

∫

− p(t)

∈ ∂H x^∗(t),p(t) + γ(s)dμ(s) п.в. на [0,T^∗];

x^∗(t)

(

)

∫

3. H x^∗(t), p(t) + γ(s)dμ(s)

= 0 на [0,T^∗];

∫T^∗

4. p(T^∗) + γ(s)dμ(s) ∈ -N_S(x^∗(T^∗)),

где N_S (x^∗(T^∗)) - нормальный конус к S в точке x^∗(T^∗).

Доказательство леммы см. в Приложении. Ее применение облегчается тем об-

стоятельством, что в отличие от лагранжиана L_J соответствующий гамильтониан

H_J (θ) = sup (θ ·y -L_J(y)), где θ ∈ R^K, имеет сравнительно простой вид. Пусть для

y∈R^K

θ = (θ₁,...,θ_K)^T и k = 1,2,...,K

(

)

∑

h_k(θ) = e-θk

(eθℓ - 1)p_kℓ + 1

- 1.

(1.4)

ℓ=1

Вычисления, приводимые в Приложении, показывают, что

(

)

∑

L_J(y) = sup

θ_ky_k - (eθk - 1)λ_k -

h_k(θ)⁺μk -

h_k(θ)μ_k

(1.5)

θ∈R^K k=1

k=1

k∈J

k∈J^c

где используется обозначение u⁺ = max(u, 0). Отсюда, в частности, вытекает, что

функция L_J выпукла и полунепрерывна снизу. Кроме того,

∑

H_J (θ) = (eθk - 1)λ_k + h_k(θ)⁺μ_k +

h_k(θ)μ_k.

(1.6)

k=1

k∈J

k∈J^c

Обозначим также

∑

H₀(θ) = H_∅(θ) = (eθk - 1)λ_k + h_k(θ)μ_k.

(1.7)

k=1

∑

Следующее утверждение вытекает из леммы 1 с L(x, y) = L_J (y) и g(x) =

x2i, так

что мера μ равна нулю.

i∈J

Лемма 2. Оптимальное движение в грани F_J происходит с постоянным им-

пульсом θ, таким что H_J (θ) = 0, а уравнение для оптимальной траектории имеет

вид

˙q(t) ∈ ∂H_J (θ) п.в.

(1.8)

Эта лемма оставляет открытым вопрос о существовании оптимальных траекто-

рий. К сожалению, в отличие от случая фиксированного интервала времени, в рас-

сматриваемой постановке существование оптимальной траектории не следует из

компактности множеств {q : I(q) ≤ u}, где u ≥ 0. Далее, как правило, будем предпо-

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

Существование и единственность будут доказаны с помощью ad hoc рассуждений.

§ 2. Свойства гамильтониана

В этом параграфе найдены кандидаты для оптимальных импульсов θ при движе-

нии в гранях F_J . Предварительно введем некоторые обозначения. Для квадратной

матрицы B через B(i | j) обозначается матрица, получающаяся из B выбрасыванием

i-й строки и j-го столбца. Аналогично, через b_·ℓ обозначим ℓ-й столбец матрицы B

без ℓ-го элемента, а через b_ℓ· - ℓ-ю строку без ℓ-го элемента.

(

)_T

Пусть вектор θ(m) =

θ(m)1, . . . , θ(m)K

= 0, где m ∈ {1, 2, . . ., K}, удовлетворяет

уравнениям h_k(θ(m)) = 0 при k = m и H₀(θ(m)) = 0. В силу (1.4) отношения a_mℓ =

= (eθℓm) - 1)/(eθmm) - 1) при m = ℓ удовлетворяют системе уравнений

∑

a_mk - a_mℓp_kℓ = p_km, k = m.

(2.1)

ℓ=m

(Заметим, что если θmm) = 0, то θ(m)k = 0 для всех k в силу (1.4).) Уравнения (2.1)

имеют единственное решение

(

)-1

a^Tm· =

(I - P )(m | m)

p_·m.

(2.2)

Кроме того, a_mm = 1. Числа a_mℓ определяются этими условиями единственным об-

разом и являются неотрицательными. Подстановка в условие H₀(θ(m)) = 0 (см. (1.7))

показывает, что

∑

1- a_mℓp_mℓ

ℓ=1

eθmm) =

μ_m.

(2.3)

∑

a_mℓλ_ℓ

ℓ=1

(

)_T

Обозначим θ^∗ =

θ⁽¹⁾¹, θ⁽²⁾², . . . , θ(K)K

ν = (I - P^T)-1λ,

(2.4)

где λ = (λ₁, . . . , λ_K )^T . В стационарном режиме ν = (ν₁, . . . , ν_K )^T - это вектор сред-

них потоков через узлы сети. Положим ρ_m = ν_m/μ_m, где m ∈ {1, 2, . . . , K}. Сле-

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

{θ : θ_m = θmm)} лежит на поверхности H₀(θ) = 0.

Теорема 2. Имеют место соотношения H₀(θ^∗) = 0 и e-θmm) = ρ_m для m ∈

∈ {1, 2, . . ., K}.

Предпошлем доказательству ряд лемм. Будем предполагать, что B = (b_ij ) -

(K × K)-матрицa с ненулевым определителем и ненулевыми главными минорами.

Ниже adj используется для обозначения присоединенной матрицы, det - для обо-

значения определителя, а через M_ij (ℓ | ℓ) обозначается минор (i, j)-го элемента мат-

рицы B(ℓ | ℓ). Для ℓ = m положим

^{e_m,

если m < ℓ,

f_mℓ =

(2.5)

em-1, если m > ℓ,

где e_i - i-й вектор стандартного базиса в RK-1.

Лемма 3. Если ℓ = m, то

f^Tmℓ adj(B(ℓ|ℓ))b_·ℓ = (-1)m+ℓ+1 det(B(ℓ|m)).

Доказательство. Пусть ℓ > m. Имеем

∑

e^Tm adj(B(ℓ|ℓ))b_·ℓ =

(-1)m+j M_jm(ℓ | ℓ)b_jℓ +

(-1)m+j-1Mj-1,m(ℓ | ℓ)b_jℓ.

j=1

j=ℓ+1

Так как M_jm(ℓ | ℓ) = Mj,ℓ-1(ℓ | m) при j ≤ ℓ - 1 и Mj-1,m(ℓ | ℓ) = Mj-1,ℓ-1(ℓ | m) при

j ≥ ℓ + 1, получаем, что eTm adj(B(ℓ|ℓ))b_·ℓ = (-1)m+ℓ+1 det(B(ℓ|m)).

Рассмотрим случай ℓ < m. Рассуждая аналогичным образом, получаем

∑

eTm-1 adj(B(ℓ|ℓ))b_·ℓ =

(-1)m+j-1Mj,m-1(ℓ | ℓ)b_jℓ +

j=1

∑

(-1)m+j Mj-1,m-1(ℓ | ℓ)b_jℓ =

(-1)m+j-1M_jℓ(ℓ | m)b_jℓ +

j=ℓ+1

j=1

∑

(-1)m+j Mj-1,ℓ(ℓ | m)b_jℓ = (-1)m+ℓ+1 det(B(ℓ | m)).

▴

j=ℓ+1

Лемма 4. Для произвольного ℓ ∈ {1,2,...,K} имеет место равенство

b_ℓℓ det(B(ℓ|ℓ)) - b_ℓ· adj(B(ℓ|ℓ))b_·ℓ = det(B).

Доказательство. Так как

∑

b_ℓ· adj(B(ℓ|ℓ))b_·ℓ =

b_ℓjf^Tjℓ adj(B(ℓ|ℓ))b_·ℓ,

j=ℓ

то применяя лемму 3, получаем

∑

b_ℓ· adj(B(ℓ|ℓ))b_·ℓ =

b_ℓj(-1)j+ℓ+1 det(B(ℓ|j)) = - det(B) + b_ℓℓ det(B(ℓ|ℓ)).

▴

j=ℓ

Лемма 5. Имеют место равенства

(

)-1

(

)-1

b_m·

B(m | m)

b_·m

∑

b_ℓmf^Tmℓ

B(ℓ | ℓ)

b_·ℓ

(

)-1

(

)-1

(2.6)

b_mm - b_m·

B(m | m)

b·mℓ=m b_ℓℓ - b_ℓ·

B(ℓ | ℓ)

b_·ℓ

b_mmf^Tℓm(B(m|m))-1b_·m

b_ℓm

b_mm - b_m·(B(m|m))-1b_·m

b_ℓℓ - b_ℓ·(B(ℓ|ℓ))-1b_·ℓ

∑

b_kmf^Tlk(B(k |k))-1b_·k

(2.7)

b_kk - b_k·(B(k |k))-1b_·k

k=ℓ,

k=m

Доказательство. Умножая числители и знаменатели в обеих частях (2.6) на

определители обращаемых матриц, видим, что (2.6) равносильно равенству

b_m· adj(B(m|m))b_·m

b_mm det(B(m|m)) - b_m· adj(B(m|m))b_·m

∑

b_ℓmf^Tmℓ adj(B(ℓ|ℓ))b_·ℓ

(2.8)

b_ℓℓ det(B(ℓ|ℓ)) - b_ℓ· adj(B(ℓ|ℓ))b_·ℓ

ℓ=m

По лемме 4 знаменатели в (2.8) равны det(B) = 0. Поэтому нужно доказать, что

∑

b_m· adj(B(m|m))b_·m =

b_ℓmf^Tmℓ adj(B(ℓ|ℓ))b_·ℓ.

ℓ=m

Применяя лемму 3, получаем

∑

b_ℓmf^Tmℓ adj(B(ℓ|ℓ))b_·ℓ =

b_ℓm(-1)m+ℓ+1 det(B(ℓ|m)) =

ℓ=m

= -det(B) + bmm det(B(m|m)),

что завершает доказательство (2.6) в силу леммы 4.

Аналогично доказательству (2.6) имеем, что (2.7) эквивалентно равенству

∑

-b_mmf^Tℓm adj(B(m|m))b_·m = -b_ℓm det(B(ℓ|ℓ)) +

b_kmf^Tlk adj(B(k |k))b_·k.

(2.9)

k=ℓ,

k=m

По лемме 3

∑

b_kmf^Tlk adj(B(k |k))b_·k =

b_km(-1)k+ℓ+1 det(B(k |ℓ)).

(2.10)

k=ℓ

∑

Так как

b_km(-1)k+ℓ det(B(k |ℓ)) = 0 в силу того, что сумма в левой части яв-

k=1

ляется определителем матрицы, получающейся из матрицы B заменой ℓ-го столбца

на m-й, то правая часть (2.10) равна b_ℓm det(B(ℓ | ℓ)). Полученное равенство эквива-

лентно (2.9). ▴

Доказательство теоремы 2. Будем доказывать сначала второе утвержде-

ние. Покажем, что

∑

a_kmp_km

=1+

(2.11)

∑

1- a_mℓp_mℓ

k=1 1 - a_kℓp_kℓ

ℓ=1

∑

a_mℓ

a_kℓp_km

при условии, что ℓ = m.

(2.12)

∑

a_mkpmkk=1 1 -

a_kℓ′ p_kℓ′

k=1

ℓ^′=1

Так как a_mm = 1, то равенство (2.11) можно представить в виде

^∑ a_mℓp_mℓ

ℓ=m

∑

a_kmp_km

∑

(2.13)

1-p_mm -

a_mℓp_mℓ

1-p_kk - a_kℓp_kℓ

k=m

ℓ=m

ℓ=k

В силу равенств (2.1), (2.2) и (2.5) имеем a_mℓ = f^Tℓm((I - P)(m|m))-1p_·m и a_km =

= f^Tmk((I - P)(k |k))-1p_·k. Это позволяет представить (2.13) в виде

(

)-1

(

)-1

p_m·

(I - P )(m | m)

p_·m

∑

p_kmf^Tmk

(I - P )(ℓ | ℓ)

p_·k

(

)-1

(

)-1

1-p_mm -p_m·

(I - P )(m | m)

p·mk=m 1 - p_kk - p_k·

(I - P )(ℓ | ℓ)

p_·k

что является частным случаем (2.6) в утверждении леммы 5 при B = I - P . Равен-

ство (2.11) доказано. Докажем (2.12). Перепишем это равенство в виде

a_mℓ(1 - p_mm)

p_ℓm

∑

1-p_mm - a_mkp_mk

1-p_ℓℓ -

a_ℓℓ′ p_ℓℓ′

k=m

ℓ^′=ℓ

∑

a_kℓp_km

∑

где ℓ = m.

(2.14)

1-p_kk -

a_kℓ′ p_kℓ

′

k=ℓ,

ℓ^′=k

k=m

Как и выше, в силу (2.2) и (2.5) равенство (2.14) эквивалентно соотношению

(1 - p_mm)f^Tℓm((I - P )(m | m))-1p_·m

p_ℓm

1 - p_mm - p_m·((I - P)(m|m))-1p_·m

1 - p_ℓℓ - p_ℓ·((I - P)(ℓ|ℓ))-1p_·ℓ

∑

p_kmf^Tlk((I - P)(k |k))-1p_·k

1 - p_kk - p_k·((I - P)(k |k))-1p_·k

k=ℓ,

k=m

и выполнено в силу (2.7) в утверждении леммы 5. Это завершает доказательство

равенства (2.12).

Положим

a_mk

c_mk =

(2.15)

∑

1- a_mℓp_mℓ

ℓ=1

и C = (c_mk). Покажем, что

C = (I - P^T)-1.

(2.16)

∑

В силу (2.15) соотношение (2.12) принимает вид c_mℓ =

p_kmc_kℓ, так что (m, ℓ)-эле-

k=1

менты матриц C и P^T C совпадают, если m = ℓ. Так как a_mm = 1, соотношение (2.15)

∑

позволяет переписать (2.11) в виде c_mm = 1+ p_kmc_km. Следовательно, диагональ-

k=1

ные элементы матриц C и I + P^T C совпадают. Таким образом, C = I + P^T C, что

∑

доказывает (2.16). Так как a_mm = 1, то в силу (2.15) имеем 1- a_mℓp_mℓ = 1/c_mm и

ℓ=1

c_mk

a_mk =

(2.17)

c_mm

∑

С учетом (2.3), (2.4) и (2.16) получаем eθmm) = μ_m

c_mkλ_k = μ_m/ν_m = 1/ρ_m.

k=1

Для завершения доказательства теоремы 2 заметим, что в силу (1.4), (1.7) и

определения θ^∗

(

)

∑(

)

∑

H₀(θ^∗) =

eθmm) - 1

λ_m + e-θkk)p_kmμ_k - e^-θm )

μ_m

m=1

k=1

∑

Так как e-θkk) = ν_k/μ_k и ν = λ + P^T ν, то λ_m +

e-θkk) p_kmμ_k - e-θmm) μ_m = 0.

▴

k=1

)_T

⁽θ(J)

θ(J)

Пусть

θ(J) =

,...,θ(J)K

задается соотношениями

= θ(k)k, если k ∈ J,

и h_k(θ(J)) = 0 при k ∈ J. Заметим, что если J = {1, 2, . . ., K} \ {m}, то

θ(J) = θ(m).

В силу (1.6) и (1.7)

H_J (θ(J)) = H₀(θ(J)).

(2.18)

Если движение происходит в гранях FJ1, . . . , F_J

со смещениями s₁, . . . , s_k в течение

промежутков времени t₁, . . . , t_k соответственно, то поскольку H₀(θ(J)) = 0, как будет

показано в лемме 6, а также поскольку

θ(J) ·x = θ^∗ ·x при x ∈ F_J и имеет место (2.18),

затраты равны

∑

(sℓ )

∑

)

⁽θ(Jℓ)_·s

t_lL_J

= sup (θ · s_ℓ - t_lH_J

ℓ

(θ)) ≥

ℓ - tlHJ_ℓ(θ(Jℓ))

^ℓ t

ℓ

θ∈R^K

ℓ=1

∑(

)

θ^∗ · s_ℓ - t_lH₀(θ(Jℓ))

= θ^∗ · (s₁ + ... + s_k) = θ^∗ · r,

(2.19)

ℓ=1

где через r обозначена точка, в которую необходимо попасть. В общем случае, если

q(0) = 0 и q(t) = r, то с учетом того, что

˙q_k(s) = 0 для k ∈ J п.в. на множестве

{s : q(s) ∈ F_J },

∫

∑

L(q(s),

˙q(s)) ds =

1FJ (q(s))L_J (

˙q(s)) ds ≥

∫

∑

)

⁽θ(J)

≥

1FJ (q(s))

q(s) - H₀(θ(J))

ds =

∫

∑

(

)

1FJ (q(s))

θ^∗ ·

q(s) - H₀(θ(J))

ds = θ^∗ · r.

(2.20)

Если траектория из O в r такова, что в (2.19) и (2.20) достигаются равенства, т.е. вы-

полнены равенства (1.8) с θ =

θ(J), то эта траектория оптимальна. С другой стороны,

поскольку функции H_J (θ) строго выпуклы, так что их производные инъективны, ес-

∫

ли для некоторого J с

1FJ (q(s))ds > 0 не выполнено соотношение (1.8) с θ =

θ(J),

то неравенство в (2.20) является строгим. Поэтому для достижения нижней грани-

цы в (2.20) необходимо, чтобы движение в грани F_J п.в. происходило с импульсом

θ=

θ(J).

Следующая лемма обобщает соотношение H₀(θ^∗) = 0.

Лемма 6. Имеет место равенство H₀(θ(J)) = 0.

Доказательство. В силу (1.4), (1.7), определения

θ(J) и равенства e-θmm) =

= ρ_m имеем

∑

H₀(θ(J)) =

(eθmm) - 1)λ_m +

(eθmJ) - 1)λ_m +

m∈J

(

)

∑

(∑

(m)

∑

e^-θkk)

(e^θm

− 1)p_km + (eθmJ) - 1)p_km + 1

-1

μ_k =

k∈J

m∈J

(

)

∑

(eθmm) - 1) λ_m +

e-θkk) p_kmμ_k - e^-θm )

μ_m

+ (eθmJ) - 1) ×

m∈J

k∈J

m∈J

(

)

(

)

∑

× λ_m + e^-θkk)pkmμk

= (e^θm)

- 1) λ_m + p_kmν_k - ν_m

k∈J

m∈J

k∈J

(

)

∑

+ (e^θm)

- 1) λ_m + p_kmν_k

(2.21)

m∈J

k∈J

∑

Так как ввиду определения ν (см. (2.4)) λ_m +

p_kmν_k = ν_m - p_kmν_k, то

k∈J

(

)

∑

(e^θm)

- 1) λ_m + p_kmν_k

m∈J

k∈J

∑

= (e^θm)

- 1)ν_m - ν_k (eθmJ) - 1)p_km.

(2.22)

m∈J

k∈J m∈J

Так как h_k(θ(J)) = 0 при k ∈ J, то

∑

(eθmJ) - 1)p_km = eθkJ) - 1 -

(eθmm) - 1)p_km.

(2.23)

m∈J

∑

Таким образом, правая часть (2.22) равна

(eθmm) - 1)

p_kmν_k. В силу (2.21)

m ∈J

k∈J

(

)

∑

H₀(θ(J)) =

(e^θm )

- 1) λ_m + p_kmν_k - ν_m

m∈J

k=1

∑

Так как λ_m + p_kmν_k - ν_m = 0 в силу (2.4), то H₀(θ(J)) = 0. ▴

k=1

§ 3. Существенные и несущественные грани

В этом параграфе исследуется движение в гранях и приводится основной ре-

зультат. Скажем, что грань F_J является существенной, если существует траектория,

проходящая через F_J и удовлетворяющая на этом множестве утверждению леммы 2

с θ(J). В противномслучае грань называетсянесущественной. Поскольку

˙q_k(t) = 0

п.в. при k ∈ J, если грань F_J существенна, то

0 ∈ ∂_kH_J(θ(J)) при k ∈ J,

(3.1)

где через ∂_kH_J (θ(J)) обозначено множество, получающееся проектированием мно-

жества ∂H_J (θ(J)) на k-ю координатную ось. Заметим (см. (1.4)), что

(

)

∑

∂_kh_k(θ) = -e-θk

p_kℓ +

e^θ

^ℓp_kℓ

(3.2)

ℓ=1

ℓ=k

∂_ℓh_k(θ) = e-θk eθℓ p_kℓ, ℓ = k.

(3.3)

Как следствие, получаем

∂_lh_k(θ) > 0, если ℓ = k и

∂_kh_k(θ) < 0.

(3.4)

Заметим также, что если h_k(θ) = 0, то ∂h_k(θ)⁺ - это множество векторов α∇h_k(θ),

где α ∈ [0, 1].

В силу (1.8) с θ =

θ(J), (3.2), (3.3) и равенства h_ℓ(θ(J)) = 0 при ℓ ∈ J, если грань F_J

является существенной, то существуют числа α(J)ℓ, ℓ ∈ J, из интервала [0, 1], такие

что при k ∈ J п.в.

∑

q_k(t) = eθkJ) λ_k +

∂_kh_ℓ(θ(J))μ_ℓ +

α(J)ℓ∂_kh_ℓ(θ(J))μ_ℓ =

ℓ∈J

∑

=eθkJ)λ_k +

e-θℓℓ) eθkJ) p_lkμ_ℓ +

α(J)ℓe-θℓJ) eθkJ) p_lkμ_ℓ -

ℓ ∈J

ℓ∈J,

ℓ=k

(

)

∑

-α(J)ke^-θkJ)

p_kℓ +

e^θℓJ)pkℓ μk.

ℓ=1

ℓ=k

Так как h_k(θ(J)) = 0, то

∑

p_kℓ +

eθℓJ) p_kℓ = eθkJ) (1 - p_kk).

(3.5)

ℓ=1

ℓ=k

Поэтому требуется, чтобы при k ∈ J

∑

λ_k + p_lkν_ℓ + α(J)ℓe-θℓJ) p_lkμ_ℓ - α(J)ke-θkJ) μ_k = 0.

ℓ ∈J

ℓ∈J

∑

Так как λ_k + p_lkν_ℓ = ν_k - p_lkν_ℓ, то эквивалентным образом

ℓ∈J

∑

α(J)ke-θkJ) μ_k -

α(J)ℓe-θℓJ) p_lkμ_ℓ = ν_k -

p_lkν_ℓ.

ℓ∈J

В векторной форме -

(I - P^T )(J^c | J^c)(α(J)ℓe-θℓJ) μ_ℓ, ℓ ∈ J)^T = (I - P^T )(J^c | J^c)(ν_ℓ, ℓ ∈ J)^T .

Здесь и далее используются следующие обозначения: для матрицы W через W(U |V )

обозначена матрица, получающаяся из W выбрасыванием строк и столбцов с номе-

рами из множеств U и V соответственно.

Так как матрица (I - P^T )(J^c | J^c) невырождена, то при ℓ ∈ J

α(J)ℓe-θℓJ) μ_ℓ = ν_ℓ.

(3.6)

Поэтому для того чтобы грань F_J была существенной, необходимо, чтобы

ρ(J)ℓ ≥ ρ_ℓ, ℓ ∈ J,

(3.7)

где использовано обозначение

ρ(J)ℓ = e-θℓJ) .

(3.8)

Так как в силу (2.23)

(I - P )(J^c | J^c)((ρ(J)ℓ)-1 - 1, ℓ ∈ J)^T = P (J^c | J)(ρ-1ℓ - 1, ℓ ∈ J)^T ,

то

(

)_T

(

)-1

(ρ(J)ℓ)-1 - 1, ℓ ∈ J

(I - P )(J^c | J^c)

P (J^c | J)(ρ-1ℓ - 1, ℓ ∈ J)^T .

(3.9)

(

)-1

Так как матрица

(I - P )(J^c | J^c)

P (J^c | J) неотрицательна, то ρ(J)ℓ ≤ 1 при ℓ ∈ J.

Кроме того, условие существенности (3.7) эквивалентно тому, что покомпонентно

(

)-1

(ρ-1ℓ - 1, ℓ ∈ J)^T ≥

(I - P )(J^c | J^c)

P (J^c | J)(ρ-1ℓ - 1, ℓ ∈ J)^T .

(3.10)

Если k ∈ J, то в силу (1.8) с θ =

θ(J), (2.4), (3.2), (3.3) и (3.6) для траектории

с импульсом

θ(J) в грани F_J имеем

∑

q_k(t) = eθkk) λ_k +

e-θℓℓ) eθkk) p_lkμ_ℓ +

α(J)ℓe-θℓJ) eθkk) p_lkμ_ℓ -

ℓ ∈J,

ℓ∈J

ℓ=k

(

)

(

)

∑

-e^-θkk)

p_kℓ +

e^θℓJ)pkℓ μk = ρ-1

λ_k + p_lkν_ℓ

ℓ=1

ℓ=k

ℓ=1

(

)

(

∑

1 + (e^θℓJ)

- 1)p_kℓ ν_k = μ_k -

1 + (ρ-1ℓ - 1)p_kℓ +

ℓ=1

ℓ ∈J

)

∑(

)

(ρ(J)ℓ)-1 - 1

p_kℓ ν_k.

(3.11)

ℓ∈J

Аналогичные рассуждения (или формальная подстановка J = ∅ в последнее выра-

жение в (3.11)) показывают, что для любого k

(

)

∑

∂_kH₀(θ^∗) = μ_k -

1 + (ρ-1

- 1)p_kℓ ν_k,

(3.12)

ℓ

ℓ=1

так что при k ∈ J

∑(

)

˙q_k(t) = ∂_kH₀(θ^∗) +

ρ-1ℓ - (ρ(J)ℓ)-1

p_kℓν_k.

(3.13)

ℓ∈J

Так как в силу (3.5) и (3.8) для k ∈ J равенство (3.12) может быть записано в виде

(

)

∑

(

)

∂_kH₀(θ^∗) =

ρ-1k - (ρ(J)k)-1

ν_k - p_kℓ

ρ-1ℓ - (ρ(J)ℓ)-1

ν_k

(3.14)

ℓ=1

˙q_k(t) = 0 п.в., то п.в. для k ∈ J

(

)

∑(

)

˙q_k(t) = ∂_kH₀(θ^∗) -

ρ-1k - (ρ(J)k)-1

ν_k +

ρ-1ℓ - (ρ(J)ℓ)-1

p_kℓν_k.

(3.15)

ℓ∈J

Напомним определение двойственной сети Джексона. В такой сети интенсивности

обслуживания в узлах те же, что в исходной сети. Потоки двойственной сети имеют

те же интенсивности, что и в исходной, но направлены в противоположную сторо-

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

но с верхней чертой, имеем μ_k = μ_k, ν_k = ν_k и ν_kp_kℓ = ν_ℓp_lk. Также меняются ме-

(

)

(

)

∑

стами входящие и выходящие потоки: λ_k = ν_k 1 - p_kℓ и λ_k = ν_k 1 - p_kℓ .

ℓ=1

(Следующее рассуждение показывает, что матрица P = (p_kℓ) является субстохасти-

∑

ческой. Так как ν = λ + P^T ν, то ν ≥ P^T ν покомпонентно. Поэтому ν_k ≥

p_lkν_ℓ,

ℓ=1

∑

т.е.

pkℓ⁼

p_lkν_ℓ/ν_k ≤ 1.) Если сеть Джексона находится в стационарном состо-

ℓ=1

янии, то обращение во времени приводит к стационарной двойственной сети.

В этих обозначениях в силу (3.13) и (3.15), если q(t) ∈ F_J , то п.в.

˙q(t) = ∇H₀(θ^∗) - (I - P^T )ϕ(J),

где

{

-1

(ρ

- (ρ(J)ℓ)-1)ν_ℓ, если ℓ ∈ J,

ℓ

ϕ(J)ℓ =

(3.16)

в противном случае.

Кроме того, (3.12) принимает вид

-∇H₀(θ^∗) = λ - (I - P^T )μ,

(3.17)

где μ = (μ₁, . . . , μ_K )^T . (Заметим, что правую часть также можно представить в ви-

де ∇H₀(0).) Пусть T > 0. Обозначая q(t) = q(T - t), где 0 ≤ t ≤ T , получаем,

что п.в.

q(t)=λ- (I - P^T )μ + (I - P^T )ϕ˙(t),

(3.18)

где

∑

ϕ(t) =

1FJ (q(t))ϕ(J).

(3.19)

Так как ϕ˙_k(t) = 0, если q_k(t) > 0, в силу (3.16), то (3.18) означает, что q(t) получа-

ется косым отражением функции q(T ) + (λ - (I - P^T )μ)t, т.е. является жидкостной

траекторией, начинающейся в конечной точке r, длин очередей в сети Джексона

с интенсивностями входных потоков λ_k, интенсивностями обслуживания μ_k и матри-

цей переходов P. Покажем обратное: если q - жидкостная траектория двойственной

системы, начинающаяся в конечной точке r, то ее обращение во времени является

оптимальной траекторией. Так как q - решение задачи косого отражения, то имеет

место (3.18), где ϕ(t) - покомпонентно неубывающая абсолютно непрерывная функ-

ция, такая что q_k(t)ϕ˙_k(t) = 0 п.в. Ввиду (3.17), если q(t) ∈ F_J , то для сужений векто-

ров на J и матриц на J ×J будет выполнено п.в. ϕ˙_J (t) = (I_J,J -P^TJ,J )-1(-∇H₀(θ^∗)_J ).

В силу (3.14) и (3.16) имеемϕ˙_J(t) = ϕ(J)J, т.е. выполнено (3.19). Таким образом, обра-

щение траектории q проходит через F_J с импульсом

θ(J). Поэтому грани F_J в (3.19)

существенные. Также получаем, что ϕ(J)ℓ ≥ 0 при ℓ ∈ J и что (3.7) не только необхо-

димо, но и достаточно для существенности F_J , поскольку жидкостная траектория,

начинающаяся в F_J , будет там находиться некоторое время, если выполнено (3.7).

Следовательно, обращение оптимальной траектории с импульсами

θ(J), которая по-

падает из некоторой точки A в некоторую точку B, является жидкостной траекто-

рией для попадания из B в A для двойственной сети, и наоборот.

Так как исходная сеть Джексона предполагается эргодической, то двойствен-

ная сеть тоже эргодична, так что жидкостная траектория двойственной сети, на-

чинающаяся в точке r, попадает в конце концов в начало координат. Более того,

соответствующая траектория состоит из конечного числа отрезков, принадлежа-

щих граням F_J с возрастающими по включению множествами J, кроме, возможно,

“одноточечного отрезка”, представляющего собой начальную точку (см., например,

[13, леммы 5.3, 5.4, с. 142, 143]). Поэтому оптимальная траектория из O в r существу-

ет, единственна и состоит из конечного числа отрезков, принадлежащих граням F_J

с убывающими по включению множествами J, кроме, возможно, “одноточечного от-

резка”, представляющего собой конечную точку (см. рис. 9 ниже). Пусть T^∗ - время,

за которое жидкостная траектория q(t), начинающаяся в конечной точке r, попа-

дает в начало координат. Положим q^∗(t) = q(T^∗ - t) при 0 ≤ t ≤ T^∗. (Напомним,

что q^∗ достигает нижней границы затрат, см. (2.19).) Нами доказана следующая

Теорема 3. Построенная траектория q^∗(t) является единственной опти-

мальной с точностью до времени, проведенного в начале координат. Движение

в существенной грани F_J происходит с импульсом

θ(J). Затраты на достижение

∫

точки r при движении по этой траектории равны L(q^∗(t), q˙^∗(t)) dt = θ^∗ · r.

Как следствие теоремы 3 получаем, что жидкостная траектория q двойственной

сети, начинающаяся в точке r, достигает начала координат, проходя через последо-

вательность существенных граней, в каждой из которых она проводит положитель-

ное время. Если начальное значение принадлежит несущественной грани, то траек-

тория сразу же уходит из этой грани. В существенной грани F_J движение происхо-

∑

дит в соответствии с уравнениями q_k(t) = -∂_kH₀(θ^∗) - (ρ-1ℓ - (ρ(J)ℓ)-1)p_kℓν_k, если

ℓ∈J

k ∈J,и

(t) = 0 п.в., если k ∈ J (см. (3.11), (3.13)). Заметим также, что поскольку

q(t) = λ + (P^T - I)d(J) при q(t) ∈ F_J , где через d(J) = (d(J)1, . . . , d(J)K)^T обозначен

вектор интенсивностей потоков, протекающих через узлы, то в силу (3.18) и (3.19)

имеем d(J) = μ - ϕ(J). В силу (3.16) имеем d(J)ℓ = μℓ, если ℓ ∈ J, и d(J)ℓ = (ρ(J)ℓ)-1νℓ,

если ℓ ∈ J. Так как 1 ≥ ρ(J)ℓ ≥ ρ_ℓ при условии, что грань F_J существенна, то в этом

(J)

случае ν_ℓ ≤ d

ℓ

≤ μ_ℓ. В силу (1.1) и (1.2) отсюда следует, что для двойственной

сети L_J(λ + (P^T - I)d(J)) = 0. Как следствие,

L(q(t), q(t)) = 0 п.в.

(3.20)

Условие существенности имеет более явный вид для случая полуоси. Если грань

F_J - это полуось x_m, то (3.9) принимает вид

(ρ(J)ℓ)-1 - 1 = a_mℓ(ρ-1m - 1), ℓ = m,

(3.21)

а (3.10) (с учетом (2.2)) -

ρ-1ℓ - 1 ≥ a_mℓ(ρ-1m - 1), ℓ = m.

(3.22)

(Разумеется, (3.22) можно получить напрямую из (3.6).) Подстановкой (3.21) в (3.11)

∑

с учетом того, что

a_mℓp_mℓ = 1-1/c_mm (как показано в доказательстве теоремы 2),

ℓ=1

убеждаемся, что если полуось x_m существенна, то

1-ρ_m

˙q^∗m(t) =

μ_m > 0,

c_mm

как и следовало ожидать. Следующее свойство матрицы C доказано в Приложении.

Лемма 7. Имеет место неравенство c_mℓ ≤ c_mm.

Из леммы 7, (2.17) и (3.22) следует, что если ρ_m максимально, то полуось x_m

является существенной, т.е. в случае попадания на нее оптимальная траектория

будет находиться там некоторое время.

Замечание 1. Из теоремы 2 следует, что θ^∗ > 0 покомпонентно, и как следствие,

нижняя граница в (2.19) и (2.20) положительна для всех r тогда и только тогда,

когда рассматриваемая сеть эргодична. Таким образом, для неэргодической сети

Джексона на оптимальность импульсов

θ(J) при движении из O в r рассчитывать

не приходится. С другой стороны, сделанное наблюдение, что обращение уравнений

Гамильтона приводит к жидкостным уравнениям, остается в силе, и оценки (2.19)

и (2.20) могут быть полезны. Например, если θ^∗ < 0 покомпонентно, то жидкост-

ные траектории двойственной сети убегают на бесконечность, а затраты на переход

исходной сети из точки r в начало координат равны -θ^∗ · r.

§4. Условные законы больших чисел. Обсуждение.

Как отмечено вначале, принцип больших уклонений позволяет получать лога-

рифмические асимптотики вероятностей редких событий и находить наиболее веро-

ятные сценарии, реализующие эти события. Следующие две леммы иллюстрируют

это утверждение. Напомним, что сеть предполагается эргодической.

Лемма 8. Для произвольного δ > 0

(



)

Q(nt)



Q(nT∗₎



lim lim sup P sup



- q^∗(t)

δ|



-r

= 0.

≥



≤

ε→0

n→∞

t≤T^∗

 n

Кроме того,

(



)

Q(nT∗)



lim lim sup

ln P



-r



≤

ε→0

n→∞ n

(



)

Q(nT∗)



= lim

lim inf

ln P



-r

= -θ^∗ · r.



≤

ε→0

n→∞ n

Доказательство. Для доказательства первого утверждения достаточно до-

казать, что

(



)

Q(nt)



Q(nT∗₎



lim sup lim sup

ln P sup



- q^∗(t)

δ|



-r

< 0.

(4.1)

≥



≤

ε→0

n→∞ n

t≤T^∗

 n

В силу принципа больших уклонений

(



)

Q(nT∗)



lim inf

ln P

-r

≥-

inf

I(q).

(4.2)



≤

n→∞ n

q: |q(T^∗)-r|≤ε/2

Продолжим q^∗ на интервал времени (T^∗, ∞) по закону больших чисел. Аналогично

∫

(3.20) имеем L(q^∗(t),

q^∗(t))dt = 0. Поэтому I(q^∗) = L(q^∗(t),

˙q^∗(t))dt. Так как

T^∗

функция I(q) компактна снизу и q^∗(T^∗) = r, то

∫

lim

inf

I(q) = inf I(q) ≤ I(q^∗) =

L(q^∗(t),

˙q^∗(t))dt.

(4.3)

ε→0

q: |q(T^∗)-r|≤ε/2

q: q(T^∗)=r

Аналогично,

(



)

Q(nt)



Q(nT∗₎



lim sup lim sup

ln P sup



- q^∗(t)

δ,



-r

≤

≥



≤

ε→0

n→∞ n

t≤T^∗

 n

≤-

inf

I(q).

q: sup |q(t)-q^∗(t)|≥δ,

t≤T∗

q(T^∗ )=r

∫

Пусть последний инфимум достигается в точке q. Так как inf

L(q(t),

˙q(t)) dt

q,T: q(T)=r 0

∫

достигается на единственной траектории q^∗ и q = q^∗, то I(q) ≥ L(q(t),q(t)) dt >

∫

> L(q^∗(t),

˙q^∗(t))dt. Таким образом,

(



)

Q(nt)



Q(nT∗₎



lim sup lim sup

ln P sup



- q^∗(t)

δ,



-r

≥



≤

ε→0

n→∞ n

t≤T^∗

 n

∫T^∗

<- L(q^∗(t),

˙q^∗(t))dt.

С учетом (4.2) и (4.3) получаем (4.1). Второе утверждение леммы следует, по суще-

ству, из (4.2). ▴

В качестве еще одного применения рассмотрим момент достижения суммарной

}

∑

очередью большого значения: τ_n = inf t :

Q_k(nt) ≥ nA . Определим r как точку

k=1

∑

минимума θ^∗ · x по всем x = (x₁, . . . , x_K )^T ∈ RK+ , таким что

x_k = A. “В общем

k=1

положении” такая точка r определяется единственным образом.

Лемма 9. Для всех достаточно больших T

lim

ln P(τ_n ≤ T ) = -θ^∗ · r

(4.4)

n→∞ n

(



)

Q(nt)



lim P sup



- q^∗(t)



δ|τ_n ≤T

= 1.

(4.5)

n→∞

 n

^<

t≤τn

Доказательство. Рассуждения аналогичны тем, которые использовались

при доказательстве леммы 8. Покажем, что для достаточно больших T

inf

I(q) =

inf

I(q) = θ^∗ · r.

(4.6)

∑

q: sup

q_k(t)>A

q: sup

q_k(t)≥A

t≤T k=1

Для ε > 0 обозначим через q^ε,∗ оптимальную траекторию для попадания из начала

координат в точку r(1 + ε), построенную в доказательстве теоремы 3. Предполага-

ется, что она продолжена в соответствии с законом больших чисел после попадания

в r(1 + ε). Поскольку q^ε,∗ до момента попадания в r(1 + ε) - это обращенная жид-

костная траектория двойственной системы, то существует

T > 0 такое, что все тра-

ектории q^ε,∗, соответствующие ε ∈ [0, 1], попадают в точку назначения к моменту

(см., например, [13, лемма 5.4, с. 143]). Для T ≥

T имеем

θ^∗ · r = I(q^∗) =

inf

I(q) ≤

inf

I(q) ≤

∑

∑ q_k(t)≥A для некоторого t>0

q: sup

q_k(t)≥A

k=1

t≤T k=1

≤

inf

I(q) ≤

inf

I(q) ≤ I(q^ε,∗) = θ^∗ · r(1 + ε).

∑

q: sup

q_k(t)>A

q: sup

q_k(t)≥A(1+ε)

t≤T k=1

Устремляя ε к нулю, получаем (4.6). Так как в силу принципа больших уклонений

(

)

Q(nt)

lim sup

ln P(τ_n ≤ T ) = lim sup

ln P sup

≥A ≤-

inf

I(q),

n→∞ n

t≤T

∑

q: sup

q_k(t)≥A

(

)

t≤T k=1

Q(nt)

lim inf

ln P(τ_n ≤ T ) = lim inf

ln P sup

≥A ≥-

inf

I(q),

n→∞ n

t≤T

∑

q: sup

q_k(t)>A

t≤T k=1

то (4.4) вытекает из (4.6).

Для доказательства (4.5) обозначим τ(q) = inf{t : q(t) ≥ A}, где q = (q(t), t ≥ 0) ∈

∈ D(R₊, RK+ ). Так как множество

{

}

∑

q ∈ D(R₊,RK+) : sup |q(t) - q^∗(t)| ≥ δ, sup

q_k(t) ≥ A

t≤τ (q)

t≤T k=1

содержит те свои предельные точки, которые являются непрерывными функциями,

и так как I(q) = ∞, если q разрывна, то

(



)

Q(nt)



lim sup

ln P sup

- q^∗(t)

δ, τ_n ≤ T

≤

≥

n→∞ n

t≤τn

 n

≤-

inf

I(q).

q: sup

|q(t)-q^∗(t)|≥δ,

t≤τ(q)

∑

q_k(t)≥A для некоторого t∈[0,T]

k=1

Так как множество, по которому берется инфимум, замкнуто, то эта нижняя грань

∑

достигается некоторой функцией q. Пусть число

T ∈ [0,T] таково, что

T) ≥ A.

∫T

k=1

Поскольку

inf

L(q(t),

˙q(t)) dt достигается в единственной точке (q, T ) =

(q,T ):

^∑q_k

(T )≥A

k=1

∫

= (q^∗, T^∗) и q = q^∗, то I(q) ≥ L(q(t),q(t)) dt > L(q∗(t),

˙q^∗(t))dt = θ^∗ · r. Поэтому

(



)

Q(nt)



lim sup

ln P sup



- q^∗(t)

δ, τ_n ≤ T

< -θ^∗ · r.

≥

n→∞ n

t≤τn

 n

Сопоставляя это неравенство с (4.4), получаем, что для всех достаточно больших T

(



)

Q(nt)



lim sup

ln P sup



- q^∗(t)

δ|τ_n ≤T

< 0,

≥

n→∞ n

t≤τn

 n

что влечет за собой (4.5). ▴

Есть примечательное объяснение тому, что q^∗ получается обращением времени

из q. Как и в [14] (см. также [15]), заметим, что

(



)

Q(nt)



Q(nT∗₎



P sup



- q^∗(t)

δ|



-r

≥



≤

t≤T^∗

 n

(



)

Q(n(T∗- t))



Q(nT∗₎



= P sup



- q^∗(T^∗ - t)

δ|



-r



≥



≤

t≤T^∗

(



)

Qn(nt)



Qn(0)



= P sup



- q(t)

δ|



-r



≥

≤

t≤T^∗

 n

где Qⁿ(t) = Q(nT^∗ - t). Если процесс Q(t) является стационарным, то процесс Qⁿ

также является стационарным и представляет собой процесс длин очередей в обра-

щенной по времени сети Джексона. В частности, его распределение не зависит от n.

Так как q(t) является жидкостным пределом эргодической сети Джексона, то стан-

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

при n → ∞ и ε → 0. Похожие рассуждения можно найти в [16], а также в [9], где

стационарность также играет ключевую роль. (Отметим, что ни одна из этих работ

не опубликована в рецензируемых журналах.)

Так как θ^∗ · r =

inf

I(q), то в соответствии с общей теорией (см. [1,2]),

q: q(0)=0, q(T)=r

для некоторого T

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

асимптотику стационарного распределения Q(t):

(



)

(



)

Q(nt)



Q(nt)



lim lim sup

ln P



-r

= lim

lim inf

ln P



-r

ε→0

^<

ε→0

^<

n→∞ n

 n

n→∞ n

 n

= -θ^∗ · r.

В данном случае это свойство, очевидно, выполнено, так как стационарное распреде-

∏

ление Q(t) известно явно: P(Q(t) = (i₁, . . . , i_K )) =

(1 - ρ_k)ρikk^{(см.,например,[3]).}

k=1

§ 5. Пример: эргодическая сеть из двух узлов

Проиллюстрируем общие результаты на примере эргодической сети из двух уз-

лов. В этом случае анализ удается сделать более наглядным. Имеем

(

)

h₁(θ) = e-θ1

(eθ1 - 1)p₁₁ + (eθ2 - 1)p₁₂ + 1

- 1,

(5.1)

(

)

h₂(θ) = e-θ2

(eθ1 - 1)p₂₁ + (eθ2 - 1)p₂₂ + 1

- 1,

(5.2)

H₁(θ) = (eθ1 - 1)λ₁ + (eθ2 - 1)λ₂ + h₁(θ)⁺μ₁ + h₂(θ)μ₂,

H₂(θ) = (eθ1 - 1)λ₁ + (eθ2 - 1)λ₂ + h₁(θ)μ₁ + h₂(θ)⁺μ₂,

(5.3)

H₀(θ) = (eθ1 - 1)λ₁ + (eθ2 - 1)λ₂ + h₁(θ)μ₁ + h₂(θ)μ₂.

Заметим, что h₁(θ) = 0 тогда и только тогда, когда (eθ1 -1)/(eθ2 -1) = p₁₂/(1-p₁₁),

т.е. θ1 и θ2 имеют один и тот же знак, и следовательно, график h1(θ) = 0 ле-

жит в I и III квадрантах. Кроме того, h₁(θ) > 0 над графиком и слева от него,

и h₁(θ) < 0 под графиком и справа от него. Задавая θ₂ как функцию θ₁ в первом

квадранте уравнением h₁(θ) = 0, получаем, дважды дифференцируя, что d²θ₂/dθ²¹ =

= (1 - p₁₁)/p₁₂eθ1-θ2 - ((1 - p₁₁)/p₁₂eθ1-θ2 )². Так как (1 - p₁₁)/p₁₂eθ1-θ2 = 1 +

+ (1 - p₁₁ - p₁₂)/p₁₂e-θ2 ≥ 1, то θ₂ является строго вогнутой функцией θ₁, если

p₁₁ +p₁₂ < 1, и является линейной функцией θ₁, если p₁₁ +p₁₂ = 1. Аналогично, гра-

фик h₂(θ) = 0 лежит в I и III квадрантах, h₂(θ) < 0 над графиком и слева от него,

h₂(θ) > 0 под графиком и справа от него, θ₂ является строго выпуклой функцией θ₁

на графике h₂(θ) = 0, если p₂₂ + p₂₁ < 1, и линейной функцией θ₁, если p₂₂ + p₂₁ = 1.

Так как (1 - p₁₁)/p₁₂ ≥ p₂₁/(1 - p₂₂), то в I квадранте график h₁(θ) = 0 лежит

над графиком h₂(θ) = 0, причем строго над ним, если (1 - p₁₁)/p₁₂ > p₂₁/(1 - p₂₂).

В III квадранте график h₁(θ) = 0 лежит под графиком h₂(θ) = 0, причем строго под

ним, если (1 - p₁₁)/p₁₂ > p₂₁/(1 - p₂₂).

Найдем оптимальное движение из (0, 0) в (1, 0) по прямой. Движение происходит

в соответствии с гамильтонианом H₂(θ) при дополнительном условии q₂(t) = 0. То-

гда по лемме 1, выбирая g(q) = q²², так что γ(t) = 0, имеем (q1(t), 0) = (q1(t),

˙q₂(t)) ∈

∈∂H₂(θ).Какследствие,0∈∂₂H₂(θ)и

˙q₁(t) ∈ ∂₁H₂(θ) (см. [11, предложение 2.3.15,

(θ) = 0

θ(p)

θ⁽¹⁾

h2(θ)<0

h2(

θ)=0

∇H0(^θ)

h2(θ)>0

Рис. 3. Предпочтительность движения по вектору r

друг друга. Они иллюстрируются на рис. 1 и 2 соответственно. (Вектор ∇H₀(0) изоб-

ражен по той причине, что принадлежность этого вектора III квадранту является

достаточным условием эргодичности сети.)

Рассмотрим оптимальные пути попадания из (0, 0) в r = (r₁, r₂). Сравним путь

по прямой и путь горизонтально и затем по прямой. Покажем, что в случае, ко-

гда движение сначала происходит горизонтально по некоторому вектору s = (s₁, 0)

с импульсом

θ= (θ1,θ2), таким что ∂₂H₀(^θ) = 0 и h₂(^θ) > 0, как на рис. 2, непо-

средственное движение по вектору r не хуже. Рис. 3 иллюстрирует приводимые рас-

суждения. Затраты на движение сначала по вектору s и затем по вектору p = r - s

равны

θ₁s₁ + θ(p) · p, где через θ(p) обозначена точка на кривой H₀(θ) = 0, в кото-

рой внешняя нормаль совпадает с вектором p. Обозначим также через

^θ точку на

кривой H₀(θ) = 0 с внешней нормалью r. Если r не лежит на оси абсцисс, то

^θ=

θ,

поскольку движение с

θ горизонтально. Затраты на движение сразу по вектору r

равны

θ·r =

θ·s+

θ· p. Так как s ортогонален кривой H₀(θ) = 0 в точке

θ и

функция H₀(θ) является строго выпуклой, то (θ -

θ) · s ≤ 0, причем неравенство

является строгим, если r не лежит на оси абсцисс и s = 0. Аналогично, так как p

ортогонален кривой H₀(θ) = 0 в точке θ(p), то (θ - θ(p)) · p ≤ 0. Таким образом,

θ· r ≤ θ · s + θ(p) · p, где неравенство является строгим, если r не лежит на оси

абсцисс, т.е. затраты при движении по негоризонтальному вектору r меньше затрат

при первоначальном движении по s.

Как и выше, пусть θ⁽¹⁾ - точка пересечения кривых H₀(θ) = 0 и h₂(θ) = 0,

и пусть θ⁽²⁾ - точка пересечения кривых H₀(θ) = 0 и h₁(θ) = 0. Как доказано

в теореме 2, прямые θ₁ = θ⁽¹⁾¹ и θ₂ = θ⁽²⁾² пересекаются в точке θ^∗, которая лежит на

кривой H₀(θ) = 0. Приведенный выше анализ показывает, что если ∂₂H₀(θ⁽¹⁾) > 0,

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

видно из дальнейшего, в этом случае движение вертикально, и затем пересечение

внутренности квадранта так, чтобы оказаться в нужном месте оси абсцисс, стоит

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

начальное вертикальное движение не является оптимальным, если ∂₁H₀(θ⁽²⁾) > 0.

101

∇

H0 (θ^∗)

θ⁽²⁾

θ^∗

H0(θ) = 0

h1(θ)=0

θ⁽¹⁾

h2(θ)=0

λ1 = 0,3,

λ2

= 0,5

∇H0(0)

μ1 = 1,97,

μ2 = 2,23

p11

= 0,23, p12 = 0,08

p21 = 0,3, p22 = 0,13

Рис. 4. Движение внутри квадранта направо и вверх

∇H0(θ)

H0(θ) = 0

θ^∗

CR=QR+QP ctg α

θ⁽¹⁾

Рис. 5. Оптимальность движения по нормали в θ^∗

Предположим, что ∂₂H₀(θ⁽¹⁾) ≤ 0 и ∂₁H₀(θ⁽²⁾) ≤ 0 (см. рис. 4). В этом случае

∂₁H₀(θ⁽¹⁾) > 0 и ∂₂H₀(θ⁽²⁾) > 0. Тогда оптимальным горизонтальным движени-

ем является движение с импульсом θ⁽¹⁾, а оптимальным вертикальным - движение

с импульсом θ⁽²⁾. Затраты на движение сначала по вектору s = (s₁, 0) горизон-

тально и затем по вектору p равны θ⁽¹⁾¹s₁ + θ(p) · p. Поэтому, как и на рис. 3, если

θ₁ ≤ θ⁽¹⁾¹, что имеет место, если наклон вектора r больше наклона нормали к кривой

H₀(θ) = 0 в точке θ^∗, и соответственно,

^θ находится слева от θ^∗, то движение по r

предпочтительней. Предположим, что наклон вектора r меньше наклона нормали

к кривой H₀(θ) = 0 в точке θ^∗, т.е.

θ находится справа от θ^∗. Найдем оптималь-

ное горизонтальное смещение s. Нужно минимизировать θ⁽¹⁾¹s₁ + θ(p) · p по θ(p) при

условии, что r = p + s и p пропорционален ∇H₀(θ(p)). Обозначая θ(p) через θ, а p

через p(θ), имеем θ⁽¹⁾¹s₁ +θ ·p(θ) = θ⁽¹⁾¹(r₁ -p₁(θ))+θ ·p(θ) = θ⁽¹⁾¹r₁ -θ⁽¹⁾¹p₁(θ)+θ ·p(θ),

где κ∇H₀(θ) = p(θ) для некоторого κ > 0. Так как p₂(θ) = r₂, то κ∂₂H₀(θ) = r₂.

Минимизируем -θ⁽¹⁾¹p₁(θ) + θ · p(θ) при ограничениях H₀(θ) = 0, κ∇H₀(θ) = p(θ),

(

)

κ∂₂H₀(θ) = r₂. Имеем -θ⁽¹⁾¹p₁(θ)+θ·p(θ) =

∂₁H₀(θ)/∂₂H₀(θ)(θ₁ -θ⁽¹⁾¹)+θ₂

r₂. Пока-

жем, что ∂₁H₀(θ)/∂₂H₀(θ)(θ₁ - θ⁽¹⁾¹) + θ₂ убывает на дуге [θ, θ^∗]. Предположим, что θ

находится между

θ и θ^∗. Рис. 5 иллюстрирует приводимые рассуждения. Точка P

соответствует переменному импульсу θ. Обозначим через α угол между нормалью к

H₀(θ) = 0 в точке P и горизонталью через точку θ. Имеем ∂₁H₀(θ)/∂₂H₀(θ) = ctg α.

102

Рис. 6. Оптимальные траектории для параметров рис. 4 в зависимости от конечной

точки

По свойству углов со взаимно перпендикулярными сторонами угол QCP между ка-

сательной к H₀(θ) = 0 в точке θ и вертикальной прямой с абсциссой θ⁽¹⁾¹ также

равен α. Поэтому отрезок CQ, соединяющий точку (θ⁽¹⁾¹, θ₂) и пересечение каса-

тельной с вертикальной прямой с абсциссой θ⁽¹⁾¹, равен (θ₁ - θ⁽¹⁾¹)ctg α. Поэтому

∂₁H₀(θ)/∂₂H₀(θ)(θ₁ - θ⁽¹⁾¹) + θ₂ - длина вертикального отрезка CR от точки пере-

сечения касательной с вертикальной прямой с абсциссой θ⁽¹⁾¹ до оси абсцисс. По

мере того как точка θ движется по кривой H₀(θ) = 0 от точки

θ против часовой

стрелки, длина этого отрезка уменьшается и достигает минимума, когда θ попадает

в точку θ^∗. Если продолжать движение за θ^∗ против часовой стрелки, то отрезок

опять начнет увеличиваться. Таким образом, если начать двигаться горизонталь-

но, то оптимальным является движение с импульсом θ⁽¹⁾ до тех пор, пока наклон

прямой, соединяющей движущуюся точку и точку r, не станет равным наклону

внешней нормали в точке θ^∗. После этого нужно двигаться прямолинейно с накло-

ном этой внешней нормали. Поскольку движение по r является частным случаем

начального движения горизонтально с s₁ = 0, в этом случае оптимальное движе-

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

вертикально и затем по направлению к точке r, то поскольку

θ₂ < θ∗2, ситуация

будет аналогична рассмотренному выше случаю, когда

θ₁ < θ∗1, т.е. сразу двигать-

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

абсцисс до того момента, пока прямая, соединяющая движущуюся точку и точ-

ку r, не будет иметь тот же наклон, что и нормаль к H₀(θ) = 0 в точке θ^∗. После

этого оптимальным является движение по направлению этой нормали. При этом

s₁ = r₁ - p₁ = r₁ - ∂₁H₀(θ^∗)/∂₂H₀(θ^∗)r₂ = r₂(r₁/r₂ - ∂₁H₀(θ^∗)/∂₂H₀(θ^∗)). Затраты

равны θ⁽¹⁾¹s₁ + θ^∗ · (r - s) = θ^∗ · r. Аналогично, если наклон вектора r больше на-

клона нормали в точке θ^∗, то нужно сначала двигаться вертикально, пока наклон

не сравняется с наклоном нормали, а затем идти по нормали в θ^∗. Затраты также

равны θ^∗ · r. Эти варианты иллюстрирует рис. 6.

Если ∂₂H₀(θ⁽¹⁾) ≤ 0 и ∂₁H₀(θ⁽²⁾) > 0, то точка θ^∗ находится левее точки θ⁽²⁾

(см. рис. 7). Так как оптимальное вертикальное движение будет происходить в со-

ответствии с апексом кривой H₀(θ) = 0, то оно будет уступать движению прямо

по направлению r. Геометрические рассуждения, аналогичные использованным вы-

ше, показывают, что в этом случае нужно двигаться горизонтально, пока наклон не

сравняется с наклоном внешней нормали в точке θ^∗, и после этого “возвращаться” по

этой нормали. Если ∂₂H₀(θ⁽¹⁾) > 0 и ∂₁H₀(θ⁽²⁾) ≤ 0 (см. рис. 8), то нужно двигаться

вертикально и потом “возвращаться”. Рис. 9 иллюстрирует оптимальные траектории

для параметров рис. 8. Ось абсцисс при этом является несущественной, так что опти-

мальная траектория, ведущая в точку на этой оси, проходит по оси ординат. Во всех

103

∇H0(θ^∗)

θ^∗

θ⁽²⁾

H0(θ) = 0

h1(θ)=0

h2(θ)=0

θ⁽¹⁾

λ1 = 0,51, λ2 = 0,07

∇H0(0)

μ1 = 2,6,

μ2 = 4,7

p11 = 0,47, p12 = 0,08

p21 = 0,07, p22 = 0,1

Рис. 7. Движение внутри квадранта налево и вверх

λ1 = 0,12, λ2 = 0,38

μ1 = 2,36, μ2 = 1,04

p11 = 0,21, p12 = 0,11

p21 = 0,45, p22 = 0,16

H0(θ) = 0

θ⁽¹⁾

θ⁽²⁾

θ^∗

∇H0(θ^∗)

∇H0(0)

Рис. 8. Движение внутри квадранта направо и вниз

случаях надо двигаться по одной из осей координат так, чтобы вектор, соединяю-

щий движущуюся точку с точкой назначения, стал коллинеарен нормали в точке θ^∗.

После этого нужно двигаться по прямой к точке назначения. Если система эргодич-

на, то одна из этих комбинаций знаков ∂₂H₀(θ⁽¹⁾) и ∂₁H₀(θ⁽²⁾) обязательно имеет

место. Затраты всегда равны θ^∗ ·r. Как следствие, если ∂₂H₀(θ⁽¹⁾) > 0 (соответствен-

но, ∂₁H₀(θ⁽²⁾) > 0), то первоначальное движение по горизонтали (соответственно, по

вертикали) не является частью оптимального пути, т.е. ось абсцисс (соответственно,

ось ординат) является несущественной. Кроме того, оптимальный маршрут можно

получить, двигаясь по антиградиенту H₀ в точке θ^∗ до пересечения с одной из осей

координат и затем двигаясь по этой оси в начало координат. Эта ось обязательно

является существенной. Рис. 10 и 11 иллюстрируют варианты оптимального движе-

104

Рис. 9. Оптимальные траектории при параметрах рис. 8

λ1 = 0,91,

λ2 = 0,6

μ1 = 2,8,

μ2 = 2,84

p11 = 0,13,

p12 = 0,52

p21 = 0,40,

p22 = 0,29

θ⁽²⁾

θ^∗

=θ⁽¹⁾

H0(θ) = 0

∇H0(θ^∗)

∇H0(0)

Рис. 10. Горизонтальное движение внутри квадранта

ния внутри I квадранта параллельно одной из осей координат. (Хотя вектор ∇H₀(0)

на рис. 10 не принадлежит III квадранту, выкладки показывают, что сеть тем не

менее эргодична.)

ПРИЛОЖЕНИЕ

∫

Доказательство леммы 1. Если минимум L(x(t), x(t)) dt по T ≥ 0 и по абсолют-

но непрерывным функциям x(t), таким что x(0) = x₀, (T, x(T )) ∈ S^′ и g(x(t)) ≤ 0

для всех t ≤ T , где S^′ - выпуклое замкнутое подмножество R × R^k, достигается

для времени T^∗ и функции x^∗(t), то существуют мера μ на [0, T^∗], μ-измеримая

функция γ(t) и абсолютно непрерывная функция p(t), такие что

1. γ(t) ∈ ∂^>g(x^∗(t)) для μ-почти всех t ∈ [0, T^∗], и носитель меры μ содержится

в множестве {t ∈ [0, T^∗] : ∂^>g(x^∗(t)) = ∅};

105

∇H

0(θ^∗)

θ^∗ =θ⁽²⁾

H0(θ) = 0

θ⁽¹⁾

λ1 = 1,25,

λ2 = 0,65

∇H0(0)

μ1 = 2,47,

μ2 = 3,45

p11 = 0,12,

p12 = 0,38

p21 = 0,16,

p22 = 0,24

Рис. 11. Вертикальное движение внутри квадранта

(

)

[

]

∫

− p(t)

∈ ∂H x^∗(t),p(t) + γ(s)μ(ds) п.в. на [0,T^∗];

x^∗(t)

3. Существует постоянная h, такая что

(

)

∫

H x^∗(t), p(t) + γ(s)μ(ds)

= h на [0,T^∗];

⎡

⎤

−h

⎢

∫

⎥

⎢

⎥

−N_S′(T^∗, x^∗(T^∗)).

⎣p(T∗₎₊ γ(t)μ(dt)⎦∈

Несколько более подробно: если множество S^′ имеет вид {T^′} × S^′′ для некоторых

T^′ > 0 и выпуклого замкнутого множества S^′′ ⊂ R^k, то утверждения 1 и 2 вытекают

из [17, теорема 10.2.1 и обсуждение, с. 362-364], а также из “гамильтоновой дуализа-

ции” (см. [17, теорема 7.6.5, с. 266]). Для общего выбора S^′ можно применить прием

сведения задачи с нефиксированным временем к задаче с фиксированным време-

нем, как в [11, доказательство следствия 3.6.1, с. 142] (см. также [17, теорема 8.2.1,

с. 290]). Можно также применить [11, следствие 3.6.1, с. 142], где функция f - это

значение дополнительной переменной, так что ζ - единичный (k + 2)-вектор, у ко-

торого последний элемент равен единице, а все остальные - нулю, откуда следует,

что число λ в [11, условие 4), с. 142] не влияет на значения первых k + 1 компо-

нент в левой части. Используется также утверждение [11, предложение 2.4.4, с. 55],

в соответствии с которым ∂d_S′(T^∗, x^∗(T^∗)) может быть заменено на N_S′(T^∗, x^∗(T^∗)).

В условиях леммы 1 имеем S^′ = R₊ × S. Поэтому первая компонента всех век-

торов из N_S′(T^∗, x^∗(T^∗)) равна нулю, например, согласно [11, теорема 2.5.6, с. 67].

Как следствие условия трансверсальности 4 имеем h = 0. Тот факт, что функ-

ция H из (1.3) может использоваться как функция H из [11, следствие 3.6.1, с. 142],

устанавливается рассуждениями, аналогичными использованным при доказатель-

стве теоремы 4.2.2 в [11, с. 156], где условие строгой липшицевости функции H

106

заменено на условие локальной липшицевости функции L. Результат, аналогичный

следствию 3.6.1 в [11, с. 142], содержится также в [17, теорема 10.5.1, с. 383]. ▴

Доказательство формулы (1.5). Заметим, что π(u) = sup(uθ - (e^θ - 1)), где u ≥ 0.

θ∈R

Как следствие, применяя теорему о минимаксе к (1.1), получаем

L_J(y) =

inf

ψ_J(a, d, ϱ) =

(a,d,ϱ)∈RK+ ×RK+ ×SK×K+ :

y=a+(ϱ^T -I)d

(

∑

(

)

inf

sup

θa_k - (e^θ - 1)λ_k

(a,d,ϱ)∈RK+ ×RK+ ×SK×K+ :

k=1

∑

y=a((ϱT -I)d

)

∑

(

)

+ sup

θd_k - (e^θ - 1)μ_k

+ sup

θd_k - (e^θ - 1)μ_k

1(μ

k,∞)(^dk⁾⁺

k∈J^c

k∈J

[

)

∑

(

)

( (_K∑

+ d_k sup

θϱ_kℓ - (e^θ - 1)p_kℓ

+ sup

ϱ_kℓ

k=1

ℓ=1

))])

∑

- (e^θ

− 1)

p_kℓ

ℓ=1

(

∑(

)

inf

sup

θ_ka_k - (eθk - 1)λ_k

(a,d,ϱ)∈RK+ ×RK+ ×SK×K+ :

θ_k,ϑ_k,σ_kℓ,τ_k,

k=1

k,ℓ∈{1,2,...,K}

y=a+(ϱ^T -I)d

∑

(

)

∑(

)

ϑ_kd_k - (eϑk - 1)μ_k

1(μk,∞)(dk) +

k∈J^c

k∈J

[

∑

∑(

)

∑ )

+ d_k

σ_kℓϱ_kℓ - (eσkℓ - 1)p_kℓ

+τ_k

ϱ_kℓ

k=1

ℓ=1

)])

∑

- (e^τ

^k - 1)

p_kℓ

ℓ=1

(

∑

= sup

inf

θ_ka_k +

ϑ_kd_k +

θ_k,ϑ_k,σ_kℓ,τ_k,

(a,d,ϱ)∈RK+ ×RK+ ×SK×K+ :

k=1

k∈J^c

k,ℓ∈{1,2,...,K}

y=a+(ϱ^T -I)d

)

∑

∑ ( K∑

+ ϑ_kd_k1(μ

d_k

σ_kℓϱ_kℓ +

d_kτ_k

ϱ_kℓ

k,∞)(^dk⁾⁺

k∈J

k=1

ℓ=1

k=1

ℓ=1

∑

(

)

− (eθk - 1)λ_k - (eϑk - 1)μ_k - (eϑk - 1)μ_k1

d_k > μ_k

k=1

k∈J^c

k∈J

))

∑

− d_k (eσkℓ - 1)p_kℓ - d_k(e^τk - 1)

p_kℓ

k=1

ℓ=1

k=1

ℓ=1

(

∑

∑∑

∑

= sup

inf

θ_ky_k -

θ_ℓϱ_kℓd_k +

θ_kd_k +

θ_k,ϑ_k,σ_kℓ,τ_k,

(d,ϱ)∈RK+ ×SK×K+ :

k=1

k=1 ℓ=1

k=1

k,ℓ∈{1,2,...,K}

y≥(ϱ^T -I)d

∑

∑ )

+ ϑ_kd_k + ϑ_kd_k1(μ

k,∞)(^dk⁾⁺

d_k

σ_kℓϱ_kℓ +

d_kτ_k

ϱ_kℓ

k∈J^c

k∈J

k=1

ℓ=1

k=1

ℓ=1

107

∑

(eθk - 1)λ_k -

(eϑk - 1)μ_k - (eϑk - 1)μ_k1(μ

k,∞)(^dk)-

k=1

k∈J^c

k∈J

))

∑

− d_k (eσkℓ - 1)p_kℓ - d_k(e^τk - 1)

p_kℓ

k=1

ℓ=1

k=1

ℓ=1

∑

Найдем инфимум по ϱ. Нужно минимизировать

∑ (-θ_ℓ + σ_kℓ - τ_k)d_kϱ_kℓ при

k=1 ℓ=1

∑

условии, что

ϱ_kℓd_k ≤ y_ℓ + d_ℓ, ϱ_kℓ ≥ 0 и

ϱ_kℓ ≤ 1. В соответствии с методом

k=1

ℓ=1

множителей Лагранжа (см., например, [18, теорема 6.2.4, с. 196]) существует неот-

рицательный вектор α = (α₁, . . . , α_K ), такой что достигается минимум выражения

∑(

)

-θ_ℓ + σ_kℓ - τ_k + α_ℓ

d_kϱ_kℓ

k=1 ℓ=1

∑

(

)

при условии, что ϱ_kℓ ≥ 0 и

ϱ_kℓ ≤ 1. Если min

-θ_ℓ + σ_kℓ - τ_k + α_ℓ

≤ 0, то нужно

ℓ

ℓ=1

)

взять ϱ_km = 1, где (-θ_m + σ_km - τ_k + α_m) = min(θℓ + σkℓ - τk + αℓ

и ϱ_kℓ = 0 при

(

)

ℓ

ℓ = m. Если min

-θ_ℓ + σ_kℓ - τ_k + α_ℓ

> 0, то ϱ_kℓ = 0. Получаем, что минимум равен

∑

(

ℓ

)

d_k min

-θ_ℓ + σ_kℓ - τ_k + α_ℓ

∧ 0, где использовано обозначение u ∧ 0 = min(u, 0).

ℓ

Максимум по α достигается при α = 0. Это и есть нужное α.

Таким образом, обозначая

)

∑

(

)

Vk = (eσkℓ - 1)pkℓ + (e^τk - 1)

p_kℓ

+ max

θ_ℓ - σ_kℓ

∨ (-τ_k),

(П.1)

ℓ

ℓ=1

где используется обозначение u ∨ v = max(u, v), получаем

(

∑

L_J(y) =

sup

inf

θ_ky_k -

V_kd_k +

θ_k,ϑ_k,σ_kℓ,τ_k,

d∈R^K

⁺ k=1

k=1

k,ℓ∈{1,2,...,K}

∑(

)

∑

(

)

∑

ϑ_k1(μ

d_k +

θ_k + ϑ_k

d_k - (eθk - 1)λ_k -

k,∞)(^dk)+θk

k∈J

k∈J^c

k=1

)

∑

− (eϑk - 1)μ_k - (eϑk - 1)μ_k1(μ

k,∞)(^dk⁾

k∈J^c

k∈J

(

∑

∑(

)

= sup

inf

θ_ky_k -

V_kd_k +

ϑ_k1(μ

d_k +

k,∞)(^dk)+θk

θ_k,ϑ_k,σ_kℓ,τ_k:

d∈R^K

⁺ k=1

k=1

k∈J

θ_k+ϑ_k≥V_k

∑

(

)

∑

θ_k + ϑ_k

d_k - (eθk - 1)λ_k -

(eϑk - 1)μ_k -

k∈J^c

k=1

k∈J^c

)

(

∑

(eϑk - 1)μ_k1(μ

= sup

θ_ky_k +

k,∞)(^dk⁾

θ_k,ϑ_k,σ_kℓ,τ_k:

k∈J

k=1

θ_k+ϑ_k≥V_k

)

∑

(

)

∑

+ μ_k

θ_k + ϑ_k - V_k - (eϑk - 1)

∧ 0 - (eθk - 1)λ_k -

(e^ϑ

^k - 1)μ_k

(П.2)

k∈J

k=1

k∈J^c

108

Поясним, как получается последне(равенство. Если брать и)фимум членов с dk по

d_k > μ_k для k ∈ J, то получится μ_k

-V_k + θ_k +ϑ_k - (eϑk - 1)

. Если брать инфимум

по d_k ≤ μ_k, то получится (k(θk - Vk) ∧ 0 . Поскольк)ϑk - (eϑk - 1) ≤ 0, то минимум

этих выражений равен μ_k

-V_k + θ_k + ϑ_k - (eϑk - 1)

∧ 0.

Проминимизируем V_k по σ_kℓ, τ_k. В силу (П.1) эта функция выпукла по (σ_kℓ, τ_k).

Если p_kℓ = 0 для некоторого ℓ, то можно положить σ_kℓ = ∞, что позволяет огра-

ничиться рассмотрением тех ℓ, для которых p_kℓ > 0. Аналогично можно исключить

∑

из рассмотрения τ_k, если

p_kℓ = 1, полагая τ_k = ∞. Поэтому минимум правой

ℓ=1

части (П.1) существует. В этой точке субдифференциал содержит нулевой вектор.

Обозначим через β_k значение максимума в правой части (П.1). Субдифферeнциал

правой части (П.1) по ((σ_kℓ, ℓ ∈ {1, 2, . . . , K}), τ_k) равен

(

))

∑

(eσkℓ p_kℓ, ℓ ∈ {1, 2, . . . , K}), e^τ

p_kℓ

ℓ=1

(

)

- co

(1_U (ℓ), {ℓ ∈ 1, 2, . . . , K}), 1_β

(-τ_k)

где co обозначает операцию взятия выпуклой оболочки, а U - множество (возможно,

пустое) тех ℓ, для которых θ_ℓ -σ_kℓ = β_k. Так как в точке минимума субдифференци-

ал содержит нулевой вектор, то U содержит все ℓ, такие что p_kℓ > 0, и τ_k = -β_k, если

∑ p_kℓ < 1. Поэтому существуют неотрицательные α₁,...,α_K,αK+1, сумма которых

ℓ=1

)

∑

равна 1, такие что eσkℓ p_kℓ - α_ℓ = 0 для ℓ ∈ U, α_ℓ = 0 для ℓ ∈ U, eτk 1- pkℓ

ℓ=1

-αK+1 = 0 при условии, что τ_k = -β_k, и αK+1 = 0 в противном случае. Таким об-

)

∑

разом, α_ℓ = eσkℓ p_kℓ для всех ℓ ∈ {1, 2, . . . , K} и αK+1 = eτk 1 - pkℓ . Получаем,

(

)

ℓ=1

∑

что eσkℓ p_kℓ + eτk 1- pkℓ

= 1. Так как θ_ℓ - σ_kℓ = β_k, если p_kℓ > 0, и τ_k = -β_k,

ℓ=1

)

∑

если 1 - p_kℓ > 0, то

e-βk+θℓ p_kℓ + e-βk

1- p_kℓ

= 1, т.е. eβk =

eθℓ p_kℓ +

ℓ=1

)

∑

+1 - p_kℓ. Окончательно получаем, что β_k = ln

eθℓ p_kℓ + 1 -

p_kℓ

, и мини-

ℓ=1

)

∑

мум V_k равен (e-βk+θℓ - 1)p_kℓ + (e-βk - 1) 1 - p_kℓ

+β_k =β_k.

ℓ=1

Таким образом, самое последнее выражение в (П.2) равно

(

∑

(

)

sup

θ_ky_k +

μ_k

θ_k + ϑ_k - β_k - (eϑk - 1)

∧0-

θ_k,ϑ_k: θ_k+ϑ_k≥β_k

k=1

k∈J

)

∑

− (eθk - 1)λ_k - (e^ϑ

^k - 1)μ_k

(П.3)

k=1

k∈J^c

Если θ_k - β_k ≥ 0, где k ∈ J, то выбор ϑ_k = 0 показывает, что супремум по ϑ_k

множителя при μ_k равен нулю. Поэтому (П.3) переписывается в виде

(

∑

(

)

sup

θ_ky_k +

1(-∞,βk)(θk)μk

θ_k + ϑ_k - β_k - (eϑk - 1)

∧0-

θ_k,ϑ_k: θ_k+ϑ_k≥β_k

k=1

k∈J

109

)

∑

(eθk - 1)λ_k -

(e^ϑ

^k - 1)μ_k

k=1

k∈J^c

Так как функция u - (e^u - 1) убывает при u ≥ 0, то супремум по ϑ_k для k ∈ J

достигается на границе области ограничений. Соотношение (1.5) следует теперь из

определения h_k(θ) в (1.4). ▴

Доказательство леммы 7. Так как C = (I - P^T )-1, то

c_mℓ =

(-1)m+ℓM_ℓm,

det(I - P^T )

где M_ℓm - (ℓ, m)-минор матрицы I -P^T . Заметим, что det(I -P^T ) > 0. Действитель-

но, det I = 1 и det(I - λP^T ) = 0 при λ ∈ [0, 1], поскольку спектральный радиус P

меньше единицы. По непрерывности det(I - P^T ) > 0. Таким образом, требуется до-

казать, что (-1)m+ℓM_ℓm ≤ M_mm. Предположим, что ℓ = m+1. Нужно доказать, что

Mmm + Mm+1,m ≥ 0. В силу мультилинейности детерминанта M_mm + Mm+1,m явля-

ется детерминантом матрицы

I-P, где

I - единичная ((K -1)×(K -1))-матрица,

P - ((K - 1) × (K - 1))-матрица, получающаяся из P^T сложением строк m и

m + 1 с последующим вычеркиванием m-го столбца. Так как матрица P^T является

субстохастической по столбцам, то матрица

P также является субстохастической по

столбцам. Следовательно, ее спектральный радиус не превосходит единицы. Отсюда

следует, что det

I-

P) ≥ 0, т.е. Mm+1,m + M_m,m ≥ 0. Пусть ℓ > m + 1. С помощью

последовательности транспозиций соседних строк и столбцов передвинем в матрице

I-P строку ℓ и столбец ℓ в положение строки m+1 и столбца m+1 соответственно,

сохраняя при этом взаимное расположение остальных строк и столбцов. Эта мат-

рица по-прежнему имеет вид

I-

P. В ней^M

m+1,m = (-1)ℓ-m-1Mℓm, так как знак

минора меняется только при транспозиции столбцов, иMmm = (-1)2(ℓ-m-1)M_mm.

Так как

Mmm ≥ (-1)^Mm+1,m, то Mmm ≥ (-1)ℓ-m-2Mℓm = (-1)ℓ+mMℓm. Случай

ℓ < m рассматривается аналогично. ▴

Автор выражает признательность С.А. Пирогову и А.Н. Рыбко за полезные об-

суждения и рекомендации по улучшению изложения.

СПИСОК ЛИТЕРАТУРЫ

1. Вентцель А.Д., Фрейдлин М.И. Флуктуации в динамических системах под действием

малых случайных возмущений. М.: Наука, 1979.

2. Shwartz A., Weiss A. Large Deviations for Performance Analysis: Queues, Communications,

and Computing. London: Chapman & Hall, 1995.

3. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение, 1979.

4. Жакод Ж., Ширяев А.Н. Предельные теоремы для случайных процессов. М.: Физмат-

лит, 1994.

5. Ethier S.N., Kurtz T.G. Markov Processes: Characterization and Convergence. New York:

Wiley, 1986.

6. Puhalskii A.A. The Action Functional for the Jackson Network // Markov Process. Related

Fields. 2007. V. 13. № 1. P. 99-136.

7. Atar R., Dupuis P. Large Deviations and Queueing Networks: Methods for Rate Function

Identification // Stochastic Process. Appl. 1999. V. 84. № 2. P. 255-296.

8. Ignatiouk-Robert I. Large Deviations of Jackson Networks // Ann. Appl. Probab. 2000.

V. 10. № 3. P. 962-1001.

9. Collingwood J. Path Properties of Rare Events. PhD Thesis. Univ. of Ottawa, Canada, 2015.

110

10. Bouchet F., Laurie J., Zaboronski O. Langevin Dynamics, Large Deviations and Instantons

for the Quasi-geostrophic Model and Two-Dimensional Euler Equations // J. Stat. Phys.

2014. V. 156. № 6. P. 1066-1092.

11. Кларк Ф. Оптимизация и негладкий анализ. М.: Наука, 1988.

12. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973.

13. Bramson M. Stability of Queueing Networks. Ecole d’Été de Probabilités de Saint-Flour

XXXVI-2006 // Lect. Notes Math. V. 1950. Berlin: Springer, 2008.

14. Anantharam V., Heidelberger R., Tsoukas P. Analysis of Rare Events in Continuous Time

Markov Chains via Time Reversal and Fluid Approximation. IBM Res. Rep. RC 16280.

Yorktown Heights, NY, 1990.

15. Shwartz A., Weiss A. Induced Rare Events: Analysis via Large Deviations and Time Re-

versal // Adv. in Appl. Probab. 1993. V. 25. № 3. P. 667-689.

16. Majewski K., Ramanan K. How Large Queue Lengths Build Up in a Jackson Network.

Preprint, 2008.

17. Vinter R.B. Optimal Control. Boston: Birkhäuser, 2000.

18. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М.: Мир,

1982.

Пухальский Анатолий Анатольевич

Поступила в редакцию

Институт проблем передачи информации

29.08.2018

им. А.А. Харкевича РАН

После доработки

puhalski@iitp.ru

14.01.2019

Принята к публикации

15.01.2019

111