close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Численные методы решения задачи монополиста в модели железнодорожных
грузовых перевозок
Гасников А.В.
ФУПМ, ПреМоЛаб
МФТИ
[email protected]
Лагуновская А.А.
ИПМ РАН
[email protected]
Шананин А.А
ФУПМ МФТИ
[email protected]
грузовые
железнодорожные
перевозки,
вырос
порожний пробег и простой вагонов, что увеличило
нагрузку на инфраструктуру. Для сегментированной
экономики России, в которой наряду с эффективными и
высокорентабельными нефтегазовыми и частично
горнорудными
компаниями,
присутствуют
депрессивные
низко
прибыльные
предприятия
обрабатывающего
сектора
неограниченная
либерализация, как правило, приводит к росту тарифов,
инфляции потребительских цен в целом и неизбежным
дополнительным социальным проблемам. Поэтому
государственная политика часто в целях борьбы с
инфляцией включает ограничение роста тарифов на
услуги естественных монополий. С другой стороны,
ограничение тарифов негативно сказывается на
развитии естественных монополий. Поэтому вопрос
формирования тарифов на грузоперевозки крайне
актуален для современной России не только с точки
зрения самой железнодорожной инфраструктуры
(увеличение-уменьшение трафика), но и с точки зрения
среднесрочных экономико-социальных последствий.
В препринте 1 проведён анализ на языке
математических моделей проблемы формирования
тарифов
на
железнодорожные
грузоперевозки.
Настоящая статья посвящена выработке численного
метода решения задачи монополиста 1. В п. 2 дается
описание простейшего варианта модели конкурентного
равновесия. В п. 3 описывается поведение
монополиста. В п. 4 описываются численные методы
решения задач из пп. 2, 3. Технические моменты
вынесены в приложение.
Аннотация
Необходимость решения задачи монополиста в
предложенной недавно модели грузоперевозок на
железнодорожном транспорте 1 приводит к изучению
задач многоуровневой оптимизации (как правило,
двухуровневой). Специфика рассматриваемой нами
задачи такова, что в общем случае не позволяет
напрямую использовать технику, развиваемую,
например, в работах С.Демпе, А. Шапиро и др.,
обеспечивающую выпуклость итоговой задачи. В
результате мы не можем гарантировать выпуклость
нашей
задачи.
Таким
образом,
возникает
необходимость решать задачу глобальной (не
выпуклой) оптимизации. Причем специфика задачи
такова, что мы также не можем посчитать
субградиент функционала. Более того, мы можем
посчитать значения функционала в любой наперед
заданной точке лишь с ограниченной точностью.
Причем чем выше эта точность, тем более затратно
вычисление этого значения. Возникает необходимость
развивать
численные
методы
безградиентной
оптимизации с неточным оракулом. Причем мы
можем играть на точности оракула, с целью
минимизации общего объема вычислений. В данной
статье предлагается такой метод. Рассматривается
приложение метода к решению задачи монополиста.
Ключевые слова: конкурентное равновесие Вальраса,
седловая
точка,
прямо-двойственный
метод,
безградиентная оптимизация, метод зеркального
спуска.
2. Конкурентное равновесие в модели
1. Введение
железнодорожных грузоперевозок
Результаты реформы ОАО РЖД, которая началась в
2001 г., вызвали неоднозначную реакцию. С одной
стороны, привлечение на рынок грузовых перевозок
частных
операторов
существенно
увеличило
инвестиционную привлекательность отрасли. Удалось
решить вопрос острого дефицита парка вагонов,
возникший в начале 2000-х годов на фоне
восстановления промышленности после кризиса 1998 г.
С другой стороны, обнаружились негативные эффекты
рыночных механизмов: резко выросли тарифы на
Рассмотрим модель, в которой выделены m видов
товаров 1, пункты потребления товаров I , пункты
производства J . Обозначим K = {1,..., m} , через
X ik количество k -го товара, потупившее в пункт
При идентификации модели железнодорожных грузоперевозок,
выделяемые товары могут классифицироваться по типам
железнодорожных вагонов, используемых для их перевозки.
1
11
потребления i ∈ I , а через Y j количество k -го товара


Y jk ≥ ∑ zijk , pˆ kj  Y jk − ∑ zijk  =
0,
i∈I
i∈I


5)
для любых i ∈ I , j ∈ J , k ∈ K
k
вывезенное из пункта производства j ∈ J . Будем
считать, что от поступивших товаров в пункте
потребления
получается
доход 2
i∈I
Fi ( X ,..., X
1
i
m
i
),
а
себестоимость
производства
j∈J
в количестве
товаров в пункте производства
pik ≤ pˆ kj + cijk , zijk ≥ 0, zijk ( pˆ kj + cijk − pik ) =
0.
Замечание. Предлагаемое понятие конкурентного
равновесия в модели железнодорожных грузоперевозок
соответствует вальрасовской концепции совершенного
конкурентного равновесия, в которой
субъекты
экономики максимизируют свои прибыли, считая
своими решениями они не влияют на сложившиеся
цены на товары, а цены устанавливаются так, чтобы
спрос на каждый вид товаров соответствовал его
предложению. В отличии от традиционных постановок
задач о грузоперевозках в модели учитывается
эластичность спроса и предложения по ценам.
Вычисление конкурентного равновесия может быть
сведено к решению следующего вариационного
неравенства (стандартной задачи дополнительности).
Рассмотрим множество
(Y ,..., Y ) равна G (Y ,..., Y ) . Предположим, что
1
j
k
j
1
j
j
k
j
эти
функции
удовлетворяют
неоклассическим
требованиям, т.е. непрерывны, монотонно не убывают
по
своим
вогнуты,
аргументам,
а
выпуклы.
затраты в денежном выражении
Обозначим через c
перевозку
Fi ( X i1 ,..., X im )
G j (Y j1 ,..., Y jm )
функции
k
ij
на
функции
единицы
k -го товара из пункта
k
производства j в пункт потребления i , через zij
объём перевозок k -го товара из j -го пункта
N
R=
+
k
i
производства в
i -ый пункт потребления, через p
цену k -го товара в i -ом пункте потребления, через
pˆ kj цену k -го товара в j -ом пункте производства.
{X
, Y , z , p , pˆ i ∈ I , j ∈ J , k ∈ K }
k
j
k
ij
k
i
k
j
конкурентным
равновесием
в
железнодорожных грузоперевозок, если
1)
для любого i ∈ I
(Y ,..., Y ) ∈ Arg min ∑ pˆ
m
1
j
m
j
3)
 k =1
k
j
Функцию
k ∈ K , i ∈ I , j ∈ J ) ≥ 0}
k
ij
}
k ∈ K,i ∈ I, j ∈ J ) .
вогнутой
в
Здесь
∂Fi ( • )
функции
Fi ( • ) ,
является
∂Gi ( • ) субдифференциал выпуклой функции Gi ( • ) .
модели
Напомним, что решением стандартной задачи
дополнительности
(R
N
+
( z
k
ij
)
, P ( zijk k ∈ K , i ∈ I , j ∈ J ) называется
точка
k ∈ K , i ∈ I , j ∈ J ) ∈ R+N , для которой найдётся
точка
j∈J
(P
k
ij
k ∈ K , i ∈ I , j ∈ J ) ∈ P ( zijk k ∈ K , i ∈ I , j ∈ J ) ,
такая, что Pij ≥ 0, Pij zij = 0
k
Для
решения
для любых i ∈ I , k ∈ K
производственную функцию в
k
ij
{( z
супердифференциал

y kj − G j ( y1j ,..., y mj ) ( y1j ,..., y mj ) ≥ 0  ,

Fi ( X i1 ,..., X im )
{( P
N
R=
(R


X ik ≤ ∑ zijk , pik  X ik − ∑ zijk  =
0,
j∈J
j∈J


4)
для любых j ∈ J , k ∈ K
2
N
R=
+
Из
( X ,..., X ) ∈ Arg max  Fi ( xi1 ,..., xim ) − ∑ pik xik ( xi1 ,..., xim ) ≥ 0 ,
k =1


для любого
отображение



 k
1
k
k
m
k 
k 
k
( pˆ j − pi + cij k ∈ K , i ∈ I , j ∈ J ) ( pˆ j ,..., pˆ j ) ∈ ∂G  ∑ zij  −∂F  ∑ zij  + cij 
 i∈I 
 j



m
i
2)
многозначное
P ( zijk k ∈ K , i ∈ I , j ∈ J ) =
m
1
i
k ∈ K , i ∈ I , j ∈ J ) ≥ 0} .
k
ij
Определим
Рассмотрим сначала функционирование отрасли в
условиях
совершенной
конкуренции,
когда
экономические агенты не могут влиять своим
поведением на цены и максимизируют свою прибыль
при заданных ценах.
Определение. Будем говорить, что набор
неотрицательных
чисел
k
i
{( z
N
+
k
k
(k ∈ K,i ∈ I, j ∈ J ) .
эффективного анализа
вариационного
, P ( zijk k ∈ K , i ∈ I , j ∈ J )
)
и
численного
неравенства
построим
пару
взаимно двойственных задач выпуклой оптимизации,
по решениям которых строится конкурентное
равновесие.
Рассмотрим задачу о максимизации прибыли
экономической системы с учётом затрат на
грузоперевозки:
можно интерпретировать как
i -ом пункте потребления.
12
∑ F ( X ,..., X ) − ∑ G (Y ,..., Y ) − ∑
i
i∈I
m
i
1
i
j∈J
m
j
1
j
j
i∈I , j∈J , k∈K
(2.1)
X ≤∑z
(i ∈ I , k ∈ K ) ,
Y ≥∑z
( j ∈ J, k ∈ K ),
(2.3)
(i ∈ I , j ∈ J , k ∈ K ).
(2.4)
k
i
k
ij
j∈J
k
j
i∈I
k
ij
zijk ≥ 0
двойственной
задачи
(2.7)-(2.8).
При
этом
оптимальные значения функционалов в задачах (2.1)(2.4) и (2.7)-(2.8) равны.
Из теоремы 2.1 следует, что конкурентное
равновесие в модели железнодорожных перевозок
является экономически эффективным.
cijk zijk → max
(2.2)
Несовершенная конкуренция
3.
Функция прибыли i -го потребителя равна


pim ) sup  Fi ( X i1 ,..., X im ) − ∑ pik X ik ( X i1 ,..., X im ) ≥ 0  .
Π i ( pi1 ,...,
=
k∈K


Появление на рынке услуг по перевозке грузов
частных компаний, инвестировавших средства в
обновление вагонного парка потенциально может
привести к повышению тарифов
и сокращению
объёмов перевозок. Для оценки возникающей угрозы
рассмотрим задачу, в которой «перевозчик», пользуясь
услугами ОАО РЖД по перевозке k -го товара из j -го
i -ый пункт потребления по
k
и предоставляя
«РЖД» cij
Функция прибыли j -го производителя равна
пункта производства в


π j ( pˆ 1j ,..., pˆ mj ) =
sup  ∑ pˆ kj Y jk − G j (Y j1 ,..., Y jm ) (Y j1 ,..., Y jm ) ≥ 0  .
 k∈K

принадлежащие ему вагоны, назначает свой тариф на
тарифу
ОАО
услугу cij в целях максимизации своего дохода
k
Π i ( pi1 ,..., pim )
Нетрудно видеть, что функция
является
непрерывной,
выпуклой,
невозрастающей
функцией
по
монотонно
переменным
( p ,..., p ) на множестве R , а
π ( pˆ ,..., pˆ ) является непрерывной,
m
+
m
i
1
i
1
j
j
∑ (c
k∈K ,i∈I , j∈J
Здесь функции спроса на z
( pˆ ,..., pˆ ) на множестве
m
i
m
+ .
R
c=
По теореме Фенхеля-
(
i∈I
m
i
j∈J
)(
)
{X
j
(2.7)
c = {cijk i ∈ I , j ∈ J , k ∈ K }
m
j
1
j
, Y , z , p , pˆ i ∈ I , j ∈ J , k ∈ K }
k
ij
k
i
конкурентным
железнодорожных
достаточно,
{X
k
i
{ p , pˆ
k
i
равновесием
грузоперевозок
чтобы
k
j
задачи
i ∈ I , j ∈ J , k ∈ K}
являлся
равных
значениям
Таким образом, анализ монопольного извлечения
сверхприбыли перевозчиком сводится к анализу
двухуровневой
задачи
оптимизации.
В
силу
в
модели
необходимо и
набор
(2.1)-(2.4),
и
субдифференциал функции Λ ( • ) .
являлся
k
j
− cijk ) zijk ( c )
аргумента функции Λ ( c ) . Кроме того,
(2.8)
( zijk ( c ) i ∈ I , j ∈ J , k ∈ K ) ∈ −∂Λ ( c ) , где ∂Λ ( •)
выпуклости
, Y jk , zijk i ∈ I , j ∈ J , k ∈ K } являлся решением=
Φ (c)
экстремальной
k
ij
оптимальному значению функционала задачи (2.1)-(2.4)
при
значениях
параметров
Теорема 2.1 (см. 1). Для того чтобы набор
неотрицательных
векторов
k
j
∑ (c
=
Φ (c)
Функция Λ ( c ) является выпуклой, её значение равно
pik ≤ pˆ kj + cijk , pik ≥ 0, pˆ kj ≥ 0 ( i ∈ I , j ∈ J , k ∈ K )
k
i
i ∈ I , j ∈ J , k ∈ K} .

min ∑ Π i ( pi1 ,..., pim ) + ∑ π j ( pˆ 1j ,..., pˆ mj ) + ∑ τ ijk ( cijk + pˆ kj − pik )
j∈J
i∈I , j∈J , k∈K
 i∈I
k
k
k
pi ≥ 0, pˆ j ≥ 0,τ ij ≤ 0 ( i ∈ I , j ∈ J , k ∈ K )} .
∑ Π ( p ,..., p ) + ∑ π ( pˆ ,..., pˆ ) → min
1
i
k
ij
Λ ( cijk i ∈ I , j ∈ J , k ∈ K ) =
Двойственной по Фенхелю экстремальной задачей к
задаче
(2.1)-(2.4)
является
задача
выпуклого
программирования [1]:
i
( • ) услуги по перевозке
k∈K ,i∈I , j∈J

 (2.5)
Fi ( X i1 ,..., X im ) =
inf Π i ( pi1 ,..., pim ) + ∑ pik X ik ( pi1 ,..., pim ) ≥ 0  ,
k∈K




G j Y j1 ,..., Y jm =
sup  ∑ pˆ kj Y jk − π j pˆ 1j ,..., pˆ mj pˆ 1j ,..., pˆ mj ≥ 0  .
 k∈K
 (2.6)
)
{c
Положим
Моро (см. [11]) имеем, что
(
(3.1)
определяются из решения семейства задач (2.1)-(2.4)
при
различных
значениях
тарифов
выпуклой,
монотонно неубывающей функцией по переменным
1
i
cijk ≥ cijk
k
ij
функция
m
j
− cijk ) zijk ( c ) → max.
k
ij
а
функции
∑ (c
k∈K ,i∈I , j∈J
k
ij
Λ (c)
имеем,
что
− cijk ) zijk ( c ) ≤ Λ ( c ) − Λ ( c ) .
Величина Φ ( c ) равна сверхприбыли (доходу от
решением
13
инвестиций), которую получает посредник на рынке
грузоперевозок, назначающий повышенные тарифы
c=
c =
{c
{c
k
ij
k
ij
i ∈ I , j ∈ J , k ∈ K}
вместо
здесь этого делать, отметим лишь, что эта процедура
(точнее, ее более современный аналог 5) в чем-то
напоминает “нащупывание” Вальраса 6.
Резюмируем сказанное выше. Задача поиска
конкурентного равновесия за счет выпукло-вогнутой
структуры может быть эффективно приближенно
решена. Другими словами, если мы зададимся
вектором c , то довольно быстро мы сможем найти
тарифов
i ∈ I , j ∈ J , k ∈ K } , величина Λ ( c ) − Λ ( c )
равна
совокупным
убыткам
потребителей
и
производителей в результате изменения тарифов.
Отношение
θ=
приближенное значение zij ( c ) , возникающее в задаче
k
Φ (c)
Λ ( c ) − Λ ( c )
монополиста (3.1). К сожалению, нет гарантий, что
зависимость zij ( c ) будет гладкой, и что функционал в
k
является показателем общесистемных потерь в
результате изменения тарифов. Если θ = 1 , то
сверхприбыль посредника равна совокупным убыткам
потребителей и производителей и общесистемные
потери отсутствуют. Если θ < 1 , то повышение
тарифов приводит не только к перераспределению
доходов,
но
снижает
эффективность
функционирования экономической системы в целом.
Чем меньше θ , тем больше доля общесистемных
потерь по сравнению с величиной перераспределяемой
прибыли.
задаче (3.1) будет вогнутым. Также процедура
вычисления градиента функционала (3.1) в точках
гладкости, по сути сводящаяся к вычислению
градиента zij ( c ) , крайне чувствительна к точности
k
решения задачи на поиск равновесия (см. выше) и к
ошибкам округления (конечности длины мантиссы).
Другими словами, использовать для решения задачи
(3.1) методы первого порядка (требующие вычисления
градиента
функционала
на
итерациях)
не
представляется уместным в данном случае.
Обсудим подробнее задачу (3.1). Как уже
отмечалось ранее задача (3.1), вообще говоря, не
вогнутая, как следствие, градиентный и, тем более,
безградиентный метод решения этой задачи не
обязательно сойдется к точке максимума. Далее мы
опишем, как можно с этим бороться.
Во-первых, необходимо компактифицировать
4.
Численные методы поиска
конкурентных равновесий (решений
вариационных неравенств) и решение
задачи монополиста
множество допустимых
Рассмотрим сначала задачу п. 2. В п. 2 показано как
поиск равновесия приводится к решению монотонного
вариационного неравенства. Более того, специфика
задач такова, что они сводятся к поиску седловой точки
в соответствующей выпукло-вогнутой задаче. Если
функционалы гладкие, то можно использовать для
численного решения этих задач прокси-метод А.С.
Немировского 2 (экстраградиентный метод) или метод
сглаживания Ю.Е. Нестерова 3. В обоих случаях
скорость сходимости будет как у обычного
градиентного метода для гладких задач: после N
это сделать таким образом:
∑
( k ,i , j )∈K ⊗ I ⊗ J
где Η = Ο ( n ) , n =
k
ij
K ⊗ I ⊗ J ≤ K I J . Смысл у
xijk =( cijk − cijk ) Η ,
переменные
можно
не
ограничивая общности считать, что оптимизация (3.1)
ведется на единичном симплексе (или его
внутренности)
нашем случае это означает, что зазор двойственности,
то есть разница между функционалом прямой и
двойственной задачи, после N итераций (на каждой
итерации мы считаем градиенты функций F и G в

S n (1) =
x ≥ 0 :

где
двух разных точках) будет Ο (1 N ) . Если же мы не
x = {x p }
можем гарантировать гладкость функций F и G , то
тогда прямо-двойственный метод Ю.Е. Нестерова 4
(частный случай которого МЗС упоминается в
приложении) будет сходиться (в том же смысле) со
(
− cijk ) =
Η,
(c
этого ограничения такой: нельзя собрать денег за
перевозки больше, чем есть в системе Η . Введя новые
итераций невязка будет убывать, как Ο (1 N ) . В
скоростью Ο 1
c = {cijk } . Нам будет удобно
n
p =1
:= { xijk }
k∈K
i∈I , j∈J
=
n
∑x
i
i =1
{( c
k
ij

=
1 ,

}
− cijk ) Η
k∈K
i∈I , j∈J
.
Причем можно также переписать исходную задачу
(3.1), как задачу минимизации (в численных методах
это более популярная форма представления). Вовторых, хотелось бы иметь локально сходящийся
безградиентный метод, то есть метод, сходящийся, если
стартовать достаточно близко от точки минимума
(настолько близко, чтобы иметь гарантии выпуклости
функции в окрестности старта).
Тогда, в виду
)
N . При этом на каждой итерации
мы считаем субградиенты функций F и G в одной
точке. Более того, прямо-двойственный метод может
быть содержательно проинтерпретирован. Мы не будем
14
специфики задачи, которая сводится, грубо говоря, к
ограниченности субградиента f ( x ) :
монотонности и липшицевости отображения z ( c ) (все
вычислять
значения
zijk ( c )
из
∞
≤M
– в некоторой окрестности множества S n (1) . В нашем
это порождает либо выпуклый случай, либо случай с
небольшим числом глубоких экстремумов), можно
использовать наработки глобальной оптимизации 7
(такие, как, например, метод мультистарта, который
хорошо распараллеливается), чтобы на базе локально
сходящегося метода попытаться построить уже
глобально сходящийся метод. В-третьих, в реальности
задачу (3.1) решают «живые люди», которые, как
правило,
существенно
ограничены
в
своих
вычислительных (математических) возможностях.
Типичное поведение экономического агента – сделать
действие, посмотреть на эффект, если эффект
положительный, продолжить двигаться в том же
направлении (продолжить действовать похожим
образом), если эффект отрицательный, поменять
направления (начать действовать противоположным
образом). Все это приведет экономического агента при
правильной политике выбора масштаба (шага)
действия к какому-то из локальных минимумов (в
зависимости от точки старта), и из-за ограниченности и
не возможности делать большие шаги он там и
останется, довольствуясь тем, что имеет. Вся эта
философия
может
быть
формализована
(и
содержательно
проинтерпретирована)
в
безградиентном методе поиска минимума. Однако, в
нашем случае, требуется, чтобы этот безградиентный
метод мог работать и со значениями функции,
заданными с небольшими ошибками (вообще говоря,
не случайной природы). Готового метода мы не нашли
в литературе, поэтому в приложении описан такой
метод. Он имеет содержательную интерпретацию, и
оптимальным образом сходится (то есть работает по
известным нижним оценкам числа итераций). Но самое
главное (в этом как раз и заключается новизна), что
предложенный метод “подсказывает” насколько точно
надо
∇f ( x )
M = Ο (n) .
случае
Решать
задачу
(4.1)
мы
вынуждены
безградиентным
методом.
Причем
вычисление значения функции в любой запрошенной
точке осуществляется с погрешностью δ (вообще
говоря, не случайной природы). А целью оптимизации
является найти такую точку xε ( ε -решение), что
f ( xε ) − min f ( x ) ≤ ε .
x∈Sn (1)
В приложении будет предложен безградиентый метод с
(
δ = ε 4 , требующий Ο ( M 2 n 2 ln n ) ε 2
) итераций,
на каждой итерации с точностью Ο ( ε ) необходимо
найти
=
c
{c
k
ij
конкурентное
+ Ηx
k
ij
равновесие
при
} . В случае гладких функций
заданных
Fи G
(точнее с Ο (1) - липшицевым градиентом в 1-норме,
причем этот градиент можно быстро явно посчитать)
это можно сделать, в свою очередь, за
Ο ( n2 ε )
итераций на каждой из которых производится Ο ( n )
элементарных
арифметических
операций
типа
умножения или сложения двух чисел типа double. То
есть итого получается Ο
(( n
7
)
ln n ) ε 3 операций. На
ε-
эту формулу лучше посмотреть, когда искать
решение прошкалированного функционала:
∑
f ( x ) := f ( x ) Η = −
k∈K ,i∈I , j∈J
xijk zijk
({c
l
pq
)
+ Ηx lpq } .
Тогда общее число затраченных арифметических
операций будет Ο
решения
(( n
4
)
ln n ) ε 3 . Причем, для наших
для
целей вполне достаточно точности ε ~ 10
прошкалированного функционала. Таким образом,
вспомогательной задачи. Тут идет игра: чем точнее
вычислять это значение, тем более затратным будет
один шаг, с другой стороны, чем точнее вычислять
−1
3
3
4
число арифметических операций будет ~ 10 n .
Следовательно,
метод
может
гарантировано
z ( c ) тем, по идее, меньше должно быть сделано
k
ij
шагов. На самом деле это не совсем так. Приложение
дает аккуратный ответ на вопрос о том, как оптимально
играть в эту игру.
Формализуем сказанное выше. Мы сводим
задачу (3.1) к решению задачи
эффективно
работать
при
n ~ 102 − 103
(один
9
процессор современного PC выполняет ~ 10
арифметических операций в секунду, доступные
3
(4.1)
кластеры содержат ~ 10 таких процессоров). Здесь
уместно напомнить, что в рассматриваемом нами
При этом предполагаем выпуклость f ( x ) , поскольку
Приведенные выше оценки на самом деле
оказываются сильно завышенными. Как следствие,
могут рассматриваться лишь только как оценки сверху.
f ( x ) → min ,
x∈Sn (1)
f ( x ) = −Η
∑
k∈K ,i∈I , j∈J
k k
ij ij
x z
({c
l
pq
+ Ηx
l
pq
случае n ≤ K I J , где K > 4 , I > J > 20 .
}) .
мы нацелены на построение локально сходящегося
метода, стартующего из выпуклой окрестности точки
минимума.
Нам
также
понадобится
условие
3
И на практике, то есть когда мы содержательно интерпретируем
безградиентный спуск, как процесс «нащупывания» экономическим
агентом с ограниченными вычислительными возможностями
локального оптимума.
15
Хотя бы потому, что в этих оценках не учитывается
следующее обстоятельство: если мы уже нашли
{ z ( c )} ,
k
ij
то найти
{ z ( c )} ,
k
ij
где
2. Существует
в Ο
(( M n )
2 3
ε2
)
(( M
2
Eη
Далее везде мы будем использовать обозначения
обычного градиента для векторов, которые мы
назвали здесь субградиентами. В частности, если
мы имеем дело с обычным субградиентом, то
запись ∇ x f ( x;η ) в вычислительном контексте
(например, в итерационной процедуре МЗС,
описанной ниже) означает какой-то его элемент (не
важно какой именно), а если в контексте проверки
условий (например, в условии 3 ниже), то
∇ x f ( x;η ) пробегает все элементы субградиента
(говорят также, субдифференциала);
∇ x f ( x;η )
3.
∞
≤M
–
(равномерно,
с
вероятностью 1) ограниченный субградиент.
Для справедливости части утверждений
достаточно требовать одно из следующих
(более слабых) условий:
а) Eη  ∇ x f ( x;η )



б) Eη  exp 




)
 ≤ M2;

2
∇ x f ( x;η ) ∞  
  ≤ exp (1) .

M2

2
∞
Для
решения
задачи
П.1
воспользуемся
адаптивным методом зеркального спуска (точнее
двойственных усреднений) в форме 4, 8. Положим
.
=
t 1,..., N − 1 .
xi1 = 1 n , i = 1,..., n . Пусть
метод
Алгоритм МЗС-адаптивный
 1 t ∂f ( x k ;η k ) 
−

exp
 βt +1 ∑

∂xi
Рассмотрим задачу стохастической оптимизации 4
k =1
M t

 , i 1,...,
t +1
=
=
=
xi
n, βt
.
n
k
k
n
 1 t ∂f ( x ;η ) 
ln n


xi =
1
 f x;η  → min , S n 1 =

x ≥ 0 :
∑ exp  − β ∑

x∈Sn (1)
∂xl
t +1 k 1
i =1

 =l 1 =


(
,
(П.1)
η
– случайная величина, Eη
ожидание “взятое по
 f ( x;η ) 
{η }
k
Здесь
–
независимые
одинаково
распределенные (также как η ) случайные величины.
Рассуждая подобно 4, 8, 9, 10, можно получить
следующий результат.
Теорема. Пусть справедливы условия 1, 2, 3.а,
тогда
Eη  f ( x;η )  – выпуклая функции (по x ),
для этого достаточно выпуклости по x
функций f ( x;η ) ;
1.
Здесь
∑
()
)
при следующих условиях:
4
∇ x f ( x;η ) ,
Eη ∇ x f ( x;η )  ≡ ∇ x Eη  f ( x;η )  ,
n 2 ln n ) ε 2 перейдет
Приложение. Безградиентный
зеркального спуска
вектор
который будем называть субградиентом, что
c близко к c ,
намного проще, чем решать задачу поиска
конкурентного равновесия – есть хороший кандидат на
точку старта. С другой стороны, мы свели исходную
задачу к задаче минимизации на единичном симплексе.
К сожалению, точной информацией об Η мы можем
не располагать. В таком случае можно лишь говорить
о внутренности единичного симплекса. В более общем
случае, компакт, на котором осуществляется
минимизация, может быть существенно отличным от
симплекса. К сожалению, это несколько ухудшит
приведенные выше оценки. А именно, предлагаемый
нами в приложении метод существенным образом
подточен под то, что оптимизация идет именно на
симплексе. Этот метод есть, по-сути, безградиентный
аналог
(в
котором
градиент
заменяется
соответствующей
конечной
разностью)
метода
проекции градиента. За счет специфики задачи
(минимизации на симплексе), оказывается эффективнее
проектировать градиент на симплекс не в евклидовом
смысле, а в смысле расстояния Кульбака–Лейблера,
причем это проектирование осуществляется по явным
формулам,
соответствующим
экспоненциальному
взвешиванию компонент градиента. Все это было
подмечено еще в конце 70-х годов XX века в работах
А.С. Немировского. Однако если не использовать
специфику симплекса и проектироваться в методе из
приложения в обычном (евклидовом) смысле, то
оценка числа итераций Ο
такой
 1
Ef 
 N
– математическое
η ”, то есть при фиксированном x , при этом
допускается, что x может быть случайным вектором, но
математическое ожидание берётся только по η . Если
Ω≥0
математическое ожидание берётся в том числе и по x (первое
неравенство в теореме ниже), то нижний индекс η опускаем.
5
16
Запись
N

∑ x ;η  − min( ) Eη  f ( x;η ) ≤ 2M
k
k =1

x∈Sn 1
ln n
.
N
Пусть справедливы условия 1, 2, 3, тогда 5 при

Px1 ,..., x N  Eη

 1
f 
 N
N

∑ x ;η  − min( ) Eη  f ( x;η ) ≥
k
x∈Sn 1

k =1
2M
N
(
Возьмем

ln n + 8Ω  ≤ exp ( −Ω ) .

функции
)
Замечание. Если вместо условия 3 имеет место более
слабое условие 3.б, то последняя формула останется
верной, при небольшой корректировке:
(
2M
N
)
M
N
ln n + 8Ω → C
(
в
качестве
где константа C ~ 10 .
Рассмотрим далее задачу оптимизации (6.1) (при
изложении мы существенным образом будем опираться
на работы 11, 12):
и с вероятностью 1
x∈Sn (1)
достаточно
большом
шаре
в
1-норме
∞
≤M –в
(1-шаре),
и
условие
f ( x)
δ =ε 4,
(
{x }
с вероятностью
которой функцию
версией
последовательности
g µ ( x; e )
∞
≤ Mn .
мы не можем точно вычислить
g µ ( x; e )
в определении
. Тем не менее,
2
считаем
выполненным
в
виду
δ ≤ δ
∞
Заметим, что

δ
2 Mn
≤ M + n =
µ

.
n
Ee g µ (=
x; e )
µ
(
(
)
Ee f ( x + µ e ) + δ ( x + µ=
e) e
)
= ∇ x Ee f ( x + µ e ) + δ ( x + µ e ) = ∇f µ ( x ) + ∇ x Eeδ ( x + µ e ) .
Все последующие результаты останутся неизменными
с точностью до мультипликативной константы в оценке
числа итераций, если мы заменим условие
{xk } , в
независимости и несмещенности
∇ x Eeδ ( x + µ e )
f ( x ) заменим ее сглаженной
Если
сложно проверить, что
δ ( x ) δ
константой
1
0 ≤ f ( x) − f ( x) ≤ M µ ≤ ε .
2
δ = Ο (ε )
µ
∞
δ
=
Ο (ε )

f

1

N
N
∑x
k =1
k
удовлетворяет условию Липшица с
Ο (1)
, то по-прежнему можно считать
(оценка на число итераций сохранится). В
η , как бы “замораживая” (считая не случайными) x
то есть забывая про то, что
вероятность берется как раз по
x
k
δ µ = Ο (ε )
µ = Ο (ε )

;η   − ... ”

. Тогда
) чтобы сохранилась та же
(поскольку
оценка на число итераций, требование на точность
означает, что под вероятностью мы считаем математическое
ожидание по
условием
.
общем случае мы будем иметь

 Eη

δ
) и случайный вектор e – независимы, и того,
g µ ( x; e )
µ
f=
( x ) Ee f ( x + µ e ) , µ = ε ( 4M ) . Не
“ Px1 ,..., x N
f ( x + µe)
=: Mn → 2 Mn :
константы M
равномерного распределения на сфере).
Основная идея – воспользоваться теоремой МЗС
генерирования
то

≥ 1 − σ удовлетворяла неравенству
1 N
f ( x) ≤ ε
∑ f ( x k ) − xmin
∈Sn (1)
N k =1
с как можно меньшим значением N .
Пусть e ( e ) – случайный вектор, равномерно
n
распределенный на единичной 1-сфере (1-шаре) в R
(не зависящий ни от чего, т.е. на каждом шаге k
вектор e будет независимой реализацией из
для
δ =0,
что Eδ ≡ 0 (ниже мы обобщим это условие). А
выполнение условия 3 требует некоторого пересчета
обращаясь к оракулу на одном шаге не более двух раз
за значением этой функции, так организовать
процедуру, чтобы сгенерированная на основе опроса
оракула последовательность
( f ( x + µe) − f ( x )) e .
предположения о том, что неточность оракула
но
не можем вычислять субградиент f ( x ) . Наша цель,
k
δ >0
Для
содержащим S n (1) . Будем считать, что мы можем
вычислять значения f ( x ) с точностью
градиента
Ee g µ ( x; e ) ≡ ∇f µ ( x ) ,
f ( x ) → min ,
f ( x ) – выпуклая функция в R , ∇f ( x )
µ
Также не сложно проверить [11], что если
выполнены условия 2, 3:
ln n + Ω ,
n
n
g µ ( x; =
e)
)
стохастического
f µ ( x ) следующий вектор
k
оракула должно усилиться:
,
тоже случайный вектор. А
Применим теорему о МЗС с
{ x } , с учетом того, что такая
k
зависимость есть (см. определение алгоритма МЗС).
17
δ = Ο (ε 2 )
.
N=
2 ( 2 Mn )
(ε 2 )
2
2
к функций f
1
N
(
ln n + 8ln (σ −1 )=
)
µ
( x ) . Тогда с вероятностью ≥ 1 − σ :
32 M 2 n 2
ε
2
Литература
( ln n + 8ln (σ ))
−1
1.
ε
∑ f µ ( x ) − min( ) f µ ( x ) ≤ 2
N
k
x∈Sn 1
k =1
2.
Осталось заметить, что с вероятностью ≥ 1 − σ :
1 N
1 N
ε
1 N 
f  ∑ x k  − min f ( x ) ≤ ∑ f ( x k ) − min f ( x ) ≤ ∑ f µ ( x k ) − min f µ ( x ) + ≤ ε .
x
∈
S
1
x
∈
S
1
x
∈
S
1
(
)
(
)
(
)
n
n
Nk1 =
Nk1
2
=
 N k 1=
 n
Таким
образом,
в
обозначениях
п.4:
1 N k
∑x ,
N k =1
=
t 1,..., N − 1 .
xε =
xi1 = 1 n ,
где
continuous monotone operators and smooth convexconcave saddle point problems // SIAM Journal on
Optimization. 2004. V. 15. P. 229–251.
3. Nesterov Y. Smooth minimization of non-smooth
function // Math. Program. Ser. A. 2005. V. 103. № 1.
P. 127–152.
4. Nesterov Y. Primal-dual subgradient methods for
convex problems // Math. Program. Ser. B. 2009. V.
120(1). P. 261–283.
5. Nesterov Y., Shikhman V. Convergent subgradient
methods for nonsmooth convex minimization // CORE
Discussion Paper 2014/5. 2014.
6. Ашманов С.А. Введение в математическую
экономику. М.: Наука, 1984.
7. Zhigljavsky A., Zilinskas A. Stochastic global
optimization. Springer, 2008.
8. Юдицкий А.Б., Назин А.В., Цыбаков А.Б., Ваятис Н.
Рекуррентное агрегирование оценок методом
зеркального спуска с усреднением // Проблемы
передачи информации. 2005. Т. 41:4. С. 78–96.
9. Juditsky A., Lan G., Nemirovski A., Shapiro A.
Stochastic approximation approach to stochastic
programming // SIAM Journal on Optimization. 2009.
V. 19. № 4. P. 1574–1609.
10. Гасников А.В., Нестеров Ю.Е., Спокойный В.Г. Об
эффективности одного метода рандомизации
зеркального спуска в задачах онлайн оптимизации //
Автоматика и телемеханика. 2014. (в печати)
11. Bubeck S., Cesa-Bianchi N. Regret analysis of
stochastic and nonstochastic multi-armed bandit
problems // Foundation and Trends in Machine
Learning. 2012. V. 5. № 1. P. 1–122.
12. Nesterov Yu. Random gradient-free minimization of
convex functions // CORE Discussion Paper 2011/1.
2011.
13. Dempe S. Foundations of bilevel programming.
i = 1,..., n ,
 1 t µ k k 
exp  −
∑ gi ( x ; e ) 
M t
 βt +1 k =1
 , i 1,...,
xit +1
n, βt
,
=
=
=
n
 1 t µ k k 
ln n
gl ( x ; e ) 
∑ exp  − β ∑
=l 1 =
 t +1 k 1

где
g µ ( x k ; e k ) вычисляются по формуле (*) с
помощью неточного оракула, выдающего значения
f ( x + µe) и f ( x ) .
Немного более аккуратные рассуждения позволяют
уменьшить константу 32 на один порядок в оценке
числа итераций. Детали мы вынуждены здесь опустить.
В
целом,
зависимость
N = Ο ( M 2 R 2n2 ε 2 ) ,
насколько нам известно, не улучшаема. Тем не менее,
если разрешить оракулу выдавать не значение
функции, а производную функции по указанному нами
направлению или же просто компоненту градиента,
которая нам нужна, то зависимость можно улучшить
N = Ο ( M 2 R2n ε 2 )
(с
аналогичной
Ващенко М.П., Гасников А.В., Молчанов Е.Г.,
Поспелова Л.Я., Шананин А.А. Вычислимые модели
и численные методы для анализа тарифной
политики железнодорожных грузоперевозок. М.: ВЦ
РАН, 2014.
Nemirovski A. Prox-method with rate of convergence
Ο (1 T ) for variational inequalities with Lipschitz
оценкой
вероятностей больших уклонений). Это оценка также
не улучшаема.
О других подходах к решению задач двухуровневой
оптимизации можно прочитать в монографии [12].
Dordrecht: Kluwer Academic Publishers, 2002.
Авторы выражают благодарность Ю.Е.Нестерову,
П.Е. Двуреченскому, Ю.Е. Нестерову, А.В. Орлову за
ряд ценных обсуждений.
Работа выполнена при поддержке грантов
РФФИ 13-07-13110-офи_м_РЖД, 14-01-00722-а;
Лаборатории структурных методов анализа данных в
предсказательном моделировании ФУПМ МФТИ,
грант правительства РФ дог. 11.G34.31.0073; гранта
Президента РФ № МК-5285.2013.9.
18
1/--страниц
Пожаловаться на содержимое документа