Прямо-двойственные методы решения задач энтропийно-линейного программирования тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Чернов Алексей Владимирович

• Чернов Алексей Владимирович
• кандидат наук
• 2017

Оглавление диссертации кандидат наук Чернов Алексей Владимирович

Цели и задачи

Научная новизна

Теоретическая и практическая значимость работы

Методология и методы исследования

Положения, выносимые на защиту

Степень достоверности и апробация результатов

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

Содержание работы

Глава 1. Постановка задачи и её свойства

1.1. Примеры прикладных задач, сводящихся к задаче ЭЛП

1.2. Задача, двойственная к задаче ЭЛП

1.3. Об эффективности численных методов

1.3.1. Определение эффективности численных методов

1.3.2. Предложения по повышению эффективности численных методов решения задачи ДЗЭЛП

1.4. О вычислительной сложности элементов задачи ЭЛП

1.5. Выводы

Глава 2. Численные методы решения задачи ЭЛП

2.1. Быстрый Градиентный метод

2.1.1. Градиентный метод для выпуклой задачи БМ

2.1.2. БГМ для решения задачи безусловной минимизации

2.1.3. Приложение к задаче условной минимизации с аффинными ограничениями

2.1.4. Приложение к задаче условной минимизации с линейными ограничениями равенствами и неравенствами

2.1.5. Варьирование длины шага в БГМ

2.1.6. БГМ для решения регуляризованный задачи ЭЛП с аффинными ограничениями на симплексе

2.2. Метод балансировки

2.3. Градиентно-согласованные методы

2.3.1. Модификации метода сопряженных градиентов

2.3.2. Релаксационный рестарт-метод

2.4. Выводы

Глава 3. Численные эксперименты

3.1. Предварительные эксперименты по расчету элементов задачи ЭЛП

3.2. Исследование БГМ для выпуклой задачи с линейными ограничениями

3.3. Исследование эффективности БГМ при изменении длины шага

3.4. Сравнение методов при расчете матрицы корреспонденций

3.5. Численное изучение модификаций МСГ

3.6. Релаксационный рестарт-метод

3.7. Выводы

Заключение

Список условных обозначений

Список сокращений

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

Введение диссертации (часть автореферата) на тему «Прямо-двойственные методы решения задач энтропийно-линейного программирования»

Введение

В последние 30 — 40 лет в прикладной математике интенсивно исследуются различные проблемы, математические формулировки которых сводятся к задачам энтропийно-линейного программирования (ЭЛП). Укажем некоторые из них. Принцип максимума энтропии, по-видимому, впервые в достаточно большой общности был сформулирован Е.Т. Джейнсом в 50-е годы ХХ века [1]. Этот принцип в то время был в основном известен только в связи с поиском равновесий физических макросистем (Больцман, Гиббс). В 60^70-е годы в работах А.Дж. Вильсона [2] и В. Вайдлиха [3] этот принцип был перенесен на социальные и экономические модели. В СССР в этом направлении работал Ю.С. Попков. Его монография [4] посвящена исследованию систем, содержащих большое количество элементов со стохастическим типом поведения. Такие системы названы макросистемами. Во всех отмеченных работах постулировались равновероятные распределения на микросостояних макросистемы. Оказывается, что в таком случае при весьма общих условиях для большого класса макросистем вероятность найти макросистему в малой окрестности наиболее вероятного макросостояния стремится к 1 с ростом размерности макросистемы. При этом поиск наиболее вероятного макросостояния сводился к решению задачи максимизации энтропии при аффинных ограничениях. В работе [5] была предложена эволюционная интерпретация понятия равновесия макросистемы, а также получены необходимые и достаточные условия, при которых поиск равновесия сводится к задаче ЭЛП [6]. Таким же образом можно обосновать энтропийную модель расчета матрицы корреспонденций [7], закон Ципфа-Мандельброта частоты встречаемости слов в текстах, модель Парето распределения людей по доходу и многое другое.

Другая причина возникновения задач ЭЛП связана с решением некорректных задач (энтропийная регуляризация). В качестве примера такого приложения можно указать Minimal Mutual Information модель [8].

Энтропия также появляется в качестве регуляризатора в транспортных задачах ЛП. Недавний цикл работ М. Кутюри с соавторами [9] показал эффективность такого подхода.

Имеются и другие приложения, приводящие к необходимости решения задачи ЭЛП [10].

Приведем постановку задачи ЭЛП.

Рассмотрим на п-мерном вероятностном симплексе

Sn(1)= i x G R+ : ^ Xi = 1

i=1

задачу ЭЛП:

n

f(x) = E gi(xi) ^ min;

i=1 xGG

i xi ln ^, если xi > 0; (1)

gi(Xi) = Л г ;

I 0, иначе;

G = {x G Sn(1) : Cix - bi < 0; C2x - 62 = 0} .

Здесь ^ > 0, i = 1, ..,n — параметры задачи, определяющие целевую функцию, Ci G RmiXn, b1 G Rmi, C2 G Rm2Xn, b2 G Rm2 — параметры (матрицы и векторы соответственно), определяющие допустимое множество задачи.

Введем дополнительные обозначения (2) для упрощения дальнейших выкладок.

C = [Ci; C2] G R(mi+m2)xn b = [bi; 62] G Rmi(2)

Пусть D = D(x) — диагональная матрица размерности n x n, на диагонали

которой расположены компоненты вектора x, т.е. di;i(x) = xi и dij (x) = 0 при i = j.

Градиент функции Vf(x), функция Лагранжа L(x,y) на симплексе Sn(1), где y G Rm1 x Rm2, её градиент VL(x,y) и гессиан принимают вид:

Vf (x)i = ln I + 1, i =1~П; L(x,y) = f (x) + (y,Cx — b), x G Sn(1),y G Rm1 x Rm2; VL(x, y) = ln I + 1 + [CT y]i, i = T~n; L(x,y) = f//(xx) = D—i(x), x G R++.

Несложно показать, что верна следующая лемма (см. например критерии выпуклости первого и второго порядков [11])

Лемма 1. Целевая функция задачи ЭЛП (1) строго выпукла на К+ и сильно выпукла на любом выпуклом ограниченном подмножестве из К+].

В силу того, что множество О — выпуклый компакт и функция ](х) непрерывна и строго выпукла, задача (1) имеет единственное решение [12]. Пусть Д(х) = 11(Схж — Ъ1)+\\ + ||С2х — Ъ2\\ — невязка точки х для множества О. В рамках изучения различных методов решения задачи ЭЛП в работе подразумевается поиск точки в пространстве Яп, которая достаточно точно соответствует решению. Критерий поиска такой точки задается следующим определением:

Определение 1. Под (£f ,ед)-решением задачи ЭЛП (1) будем понимать такую точку х £ Яп, что \/(х) — /*\ < £/ и Д(х) < ед, где /* - точное решение задачи.

Определение 1 совместно с определением задачи минимизации ЭЛП (1) дают постановку изучаемой задачи как поиск её (£f ,ед)-решения.

Актуальность и степень разработанности темы исследования

Теория численных методов решения задач ЭЛП достаточно глубоко разработана, им посвящено много работ [2-4, 8-10, 13].

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

Отметим некоторые особенности применения известных часто используемых методов решения задач расчета матрицы корреспонденций, которая является специальным случаем задач ЭЛП. К подобным методам относится, так называемый "метод балансировки", показывающий достаточно высокую эффективность по сравнению со многими другими методами. Однако, среди указанного класса задач существуют такие примеры, что эффективность метода балансировки при их решении резко падает, и задача расчета матрицы корреспонденций становится труднорешаемой. Под эффективностью метода здесь понимается его способность получить решение с требуемой точностью за приемлемое время при условии рационального использования имеющихся ресурсов ЭВМ (память, процессор и прочее).

Для решения задач, двойственных к задаче ЭЛП, используется быстрый градиентный метод (БГМ) решения выпуклых оптимизационных задач. В известных вариантах БГМ при неудачном выборе параметров метода необходима процедура его рестарта, которая заключается в изменении допустимого множества решений задачи, что, конечно, снижает эффективность метода.

Важным для построения эффективного метода решения экстремальных задач является также правило его остановки. Задачи, двойственные к задаче ЭЛП, могут быть плохо обусловленными, поэтому для их решения необходимо применять методы регуляризации.

Исходя из перечисленных особенностей, представляется актуальной разработка численных методов, лишенных указанных недостатков, и эффективно решающих задачу, двойственную к задаче ЭЛП, а также исследование скорости их сходимости.

Цели и задачи

Целью настоящей работы является разработка эффективных прямо-двойственных методов решения задачи ЭЛП.

Задачами настоящей работы являются:

1. теоретическое и экспериментальное исследование свойств сходимости численных методов решения задачи, двойственной к задаче ЭЛП (ДЗЭЛП);

2. разработка новых прямо-двойственных методов как для решения задач ЭЛП, так и для более широкого класса экстремальных задач, в частно-

сти, модификаций БГМ, не требующих процедуры рестарта, методов более устойчивых по сравнению с методом балансировки при решении задач расчета матрицы корреспонденций, а также исследование эффективности методов решения регуляризованной задачи ЭЛП;

3. проведение численных экспериментов для сравнения эффективности известных и предлагаемых в диссертации методов.

Научная новизна

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

2. Предложена модификация БГМ с варьированием длины итерационного шага.

3. Предложена модификация градиентно-согласованных методов решения задач безусловной минимизации (БМ), проведен анализ ее сходимости.

4. Предложена модификация метода сопряженных градиентов, связанная со способом выбора направления шага, исследована его сходимость.

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

Теоретическая и практическая значимость работы

Теоретическая значимость работы заключается в разработке новых численных методов решения задачи ДЗЭЛП и обосновании их сходимости.

Практическая значимость работы состоит в том, что предложенные численные методы существенно расширяют спектр методов для решения задач ЭЛП, причем эффективность этих методов подтверждена численными экспериментами.

Работа поддержана грантом РФФИ 14-01-00722 А «Оптимизация в пространствах сверхбольших размеров», 2014 — 2016.

Методология и методы исследования

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

Для выполнения численных экспериментов использовался интерпретируемый язык программирования МаШЬ, на котором были реализованы все методы, представленные в диссертации. Все предложенные методы были протестированы, в том числе, на эталонных задачах, решение которых легко проверяется или известно.

Положения, выносимые на защиту

1. Предложена модификация быстрого градиентного метода (БГМ) решения задачи выпуклого программирования с линейными ограничениями (равенствами и неравенствами), которая позволяет исключить рестарты метода, часто вынужденно применяемые при решении практических задач. Доказана сходимость этого метода, получены оценки скорости сходимости. Скорость сходимости метода является асимптотически сублинейной и N шагово линейной. Для БГМ предложен способ выбора фиксированного шага итерационного процесса, позволяющий существенно повысить эффективность поиска решения задачи.

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

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

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

5. Исследована эффективность всех предложенных численных методов с помощью серии численных экспериментов. На основе анализа результатов

этих экспериментов по тестированию предложенных методов показано, что спектр эффективных методов решения задачи ЭЛП существенно расширен.

Степень достоверности и апробация результатов

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

Основные результаты диссертации опубликованы в 14 работах. Из них семь работ [15-21] изданы в журналах, рекомендованных ВАК, три работы [15, 19, 20] опубликованы в изданиях, входящих в Scopus и индексируемых Web of Science, [15, 20] имеют англоязычную версию.

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

• международная конференция по математическому программированию ISMP-2015 (Pittsburgh, 2015);

• VI международная конференция "Optimization and Applications" (OPTIMA-2015) (Черногория, Подгорица, 2015);

• международная конференция "Quasilinear Equations, Inverse Problems and Their Applications"(Долгопрудный, 2015);

• международная конференция "Discrete Optimization and Operations Re-search"(Владивосток, 2016);

• XI международная научная конференция "Интеллектуальные системы и компьютерные науки"(Москва, 2016);

• VIII Московская Международная конференция по исследованию операций (Москва 2016);

• 59-я научная конференция МФТИ (Долгопрудный, 2016);

• 40-я междисциплинарная конференция и школа ITAS-2016 (Санкт-Петербург, 2016).

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

Все научные результаты, вынесенные на защиту и представленные в диссертации, получены лично автором. Лично соискателем написан весь программный код и проведены все расчеты.

Основное содержание работы

Глава 1 диссертационной работы является вводной. В разделе 1.1. приведены примеры прикладных задач, сводящихся к задаче ЭЛП. В разделе 1.2. данной главы определяются:

• задача, двойственная к задаче ЭЛП;

• градиент двойственной функции и матрица вторых производных;

• константа Липшица Ь градиента двойственной функции, определяемая через норму матрицы ограничений прямой задачи;

• свойства выпуклости двойственной функции: множество сильной выпуклости и множество строгой выпуклости.

В разделе 1.3. дано описание понятия эффективности численных методов (ЧМ), которое используется в данной работе:

• в разделе 1.3.1. дано определение эффективности ЧМ и указана значимость его корректного использования.

• раздел 1.3.2. содержит предложения по повышению эффективности ЧМ для задачи ДЗЭЛП, которые в дальнейшем изучаются в диссертации.

В следующем разделе 1.4.:

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

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

значении матрицы (явная формула), т.е. показано как можно ускорить работу методов, используя имеющиеся аналитические выражения для параметров задачи.

В главе 2 исследуются прямо-двойственные методы, применяемые для решения задачи ЭЛП. В частности доказываются леммы и теоремы о сходимости методов, дающие верхние оценки скорости сходимости. В разделе 2.1. данной главы приводится исследование модификаций быстрого градиентного метода (БГМ), доказываются теоремы о их сходимости для задач безусловной и условной минимизации (в случае простого множества вида ортант), а также описывается его применение на основе полученных данных к прямой задаче с аффинными ограничениями через построение двойственной задачи. Основным результатом здесь является отсутствие необходимости применения техники рестартов метода, требуемое в его исходной версии. Это связано с тем, что метод сходится к решению задачи монотонно (отмеченно в отдельной теореме) и определена скорость сходимости метода. Далее в работе исследован подход с регуляризацией двойственного функционала по Тихонову и применением БГМ для него, получена оценка скорости сходимости и количества рестартов.

В разделе 2.2. данной главы описан метод балансировки, применяемый для решения задачи ЭЛП в частном случае с разделяемыми переменными — расчете матрицы корреспонденций. Данный метод часто применяется при решении таких задач так как на практике является более эффективным по сравнению с другими методами.

В разделе 2.3. главы 2 вводится понятие градиентно-согласованного метода (ГСМ) решения задачи БМ и доказывается линейная скорость его сходимости при определенных условиях, накладываемых на целевой функционал. Показано, что градиентный метод и метод сопряженных градиентов являются ГСМ для двойственной задачи ЭЛП. Для метода сопряженных градиентов предложена его модификация, основанная на квадратичном приближении целевой функции на аффинном множестве L2 размерности 2 в текущей точке. Данная модификация представляет интерес тем, что в случае неточного одномерного поиска позволяет найти минимум квадратичного приближения функции на L2.

В этом же разделе вводится понятие релаксационных рестарт-методов (РРМ), т.е. методов, в основе которых лежит понятие рестарта: после m шагов основного метода (например, метод градиентного спуска или метод сопря-

женных градиентов) выполняется рестарт — шаг в направлении определяемом специально выбранными двумя точками. Величина рестарт-шага определяется по правилу одномерной минимизации. Именно такое поведение данных методов определяет их название — релаксационные рестарт-методы. Идея такого подхода к итерационному процессу восходит к известному ещё в середине прошлого столетия партан-методу или методу параллельных касательных, в которых шаги с определенной периодичностью проводились по касательным (тангенциальным) направлениям и ортогональным к ним направлениям. Показано, что методы из семейства РРМ являются градиентно-согласованными и обладают линейной скоростью сходимости

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

В других разделах данной главы описано применение релаксационных рестарт-методов причем как к выпуклой задаче ЭЛП так и невыпуклой тестовой функции. Здесь удалось продемонстрировать многократное увеличение скорости сходимости метода наискорейшего спуска. Применение рестарт-методов к методу сопряженных градиентов ведет к незначительному уменьшению эффективности метода в довольно редких случаях. Гораздо чаще наблюдались результаты, когда скорость сходимости либо существенно возрастала либо была не сильно хуже исходной скорости метода. Проведенные эксперименты показали существенное увеличение скорости сходимости градиентного метода, особенно при частых рестартах, а для различных модификаций метода сопряженных градиентов такой подход также демонстрировал улучшение результатов сходи-

мости, но при редких рестартах.

Отдельный раздел посвящен изучению метода сопряженных градиентов и его модификаций для выпуклых задач (ЭЛП) и невыпуклых задач. Показана численная эффективность модификации метода сопряженных градиентов, предложенной в главе 2 как для выпуклых так и невыпуклых задач.

В заключении приведены основные результаты, полученные в диссертационной работе.

Глава 1

Постановка задачи и её свойства

В диссертации изучаются численные методы решения задач ЭЛП. Для решения специальной задачи ЭЛП с транспортными ограничениями на практике используется метод балансировки, также называемый методом Брэгмана (Брэг-мана-Шелейховского) или методом Синхорна [9]. Для задач ЭЛП на данный момент имеется большое число разнообразных методов, описание которых можно найти в монографиях Фанга-Раджасекеры-Занга [29], Ю.С. Попкова [4], а также в работе [5]. В работах [4, 5] исследуются специальные методы , имеющие специальную структуру. Эти методы названы мультипликативными. Однако, в указанных работах приведены только доказательства сходимости предложенных методов и результаты численных экспериментов. Оценки скорости сходимости в этих работах приведены в редких случаях. В совместной работе автора [15] был предложен новый метод решения задач ЭЛП с помощью решения специальным образом регуляризованной задачи ДЗЭЛП быстрым градиентным методом (Ю.Е. Нестерова). Для этого метода (в отличие от предыдущих) были получены оценки скорости сходимости. В диссертации приведено описание этого метода, а также приведены другие подходы (также базирующиеся на решении двойственной задачи), которые уже не требуют регуляризации. Проведены численные эксперименты. Проведен сопоставительный анализ эффективности исследуемых методов.

Помимо описанных методов в работе исследуются и классические численные методы для решения задачи ДЗЭЛП, такие как метод сопряженных градиентов

и метод градиентного спуска.

1.1. Примеры прикладных задач, сводящихся к задаче ЭЛП

Приведем пример возникновения задачи ЭЛП специального вида, а именно расчет матрицы корреспонденций в рамках моделирования транспортных потоков.

В качестве основы модели рассмотрим замкнутую систему: город с населением, состоящий из S > 0 районов. Будем полагать, что в городе живет N жителей, причем число жителей много больше чем число районов: б*2 ^ N. Жители распределены по районам: число жителей в районе г равно Ь2 > 0. Полагаем, что население города занято в тех или иных районах (работа, школа, учеба, прочее): число занятых в районе ] равно Wj■ > 0.

В указанных обозначениях свойство замкнутости системы выражается в виде ограничений

п п

Е ^ = Е ^ = N.

2 = 1 j = 1

Элементы Ь2, Wj■ являются входными параметрами модели и обычно рассчитываются посредством дополнительного моделирования [13].

Рассмотрим динамику такой системы, в которой жители могут меняться квартирами или местами работы, полагая время дискретным. При этом число жилых помещений и рабочих мест в районах остается неизменным и полностью заполненным. В рамках этой динамики пусть (£) > 0 — число жителей, живущих в районе г и работающих в районе ] в момент времени £ > 0. Формализуя сказанное находим, что

Е^(£) = Ьг, Е^(£) = Wj, г,] =!Д > 0. j=1 2=1

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

жеством исходов) для элементов ^:

( Б Б

А = ^ > 0 : ^ ^ = ¿¿, ^ ^¿^ = ^, г,; =

I ¿=1 ¿=1

Полагая, что побуждением к обмену является длина дороги (или время в пути) от дома до работы (что в общем-то выглядит вполне разумным), введем линейную функцию затрат на дорогу

Я(Т) = вТ/2,

где Т — время пути от дома до работы, в — параметр модели. Далее — затраты, необходимые для того, чтобы добраться из района г в район ;.

Пусть теперь в момент времени £ > 0 житель г живет в районе к и работает в районе т, а житель в живет в районе р, а работет в районе д. Тогда вероятность обмена местами жительства (£) можно определить согласно (1.1), где коэффициент А > 0 является параметром и характеризует интенстивность обменов модели. Аналогично определяется вероятность обмена работы [7]:

= = 1 ехр (Л(Т^ТО) + Я(ТМ) — ) + Я(Трш))). (1.1)

Тогда в силу эргодической теоремы для марковских цепей [7] предельное распределение, которое вычисляется по формуле (1.2), будет совпадать со стационарным.

Иш Р (*) = ^; г,; = 1,5) = Я—1 П ехр(—2Я(Тг^!)—1

¿Л=1 (1.2)

= Р(М.? >Б!^=1).

В указанной формуле (1.2) ^ € А, константа Я определяется нормировкой вероятностной меры. На полученное распределение можно посмотреть с другой стороны, а именно как на последовательность из N независимых испытаний с исходами, где — вероятность исхода (г,;), г,; = 1,5. Тогда вероятность

итоговой конфигурации ^^ определяется по формуле:

р (^ = II . (^3)

П^=1 "у' • ¿^=1

Сказанное позволяет применить теорему Санова [30] и утверждать, что полученное распределение =1) при N ^ 1 будет экспоненциально сконцентрировано на множестве исходов А в окрестности наиболее вероятного значения, которое можно определить, решив задачу:

1Пр({ду }5=1) ~ — Е 1П — ^ ^ П1аХ . (1.4)

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

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

й ^ й — а + в.

Множество переходов или реакций системы обозначим J. Каждый переход в системе может произойти с вероятностью Аа,в(й), которая зависит только от текущего состояния системы:

1 — У] а; т—г

Аа,вМ = М ; К| П (* • ... • (Й' — а' + 1)).

а;>0 18

В указанной формуле > 0 называется константой реакции и полагается пг = М, а величину Аа,в (в) называют также интенсивностью реакции.

¿

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

Отметим, что под условием унитарности (или условием Штюкельбер-га-Батищевой-Пирогова [31, 32]) понимаются следующие утверждения для констант реакции:

> 0: Ув £ К П С = £ К П3.

Список литературы диссертационного исследования кандидат наук Чернов Алексей Владимирович, 2017 год

Литература

1. Jaynes E.T. Information theory and statistical mechanics // Physical Review. Series II. — 1957 — V. 106, N 4. — P.620-630.

2. Вильсон А.Дж. Энтропийные методы моделирования сложных систем. — М.: Наука, 1978. — 248 с.

3. Вайдлих В. Социодинамика: системный подход к математическому моделированию в социальных науках. — М.: УРСС, 2010. — 480 с.

4. Попков Ю.С. Теория макросистем: Равновесные модели. — М.: УРСС, 2013. — 320 c.

5. Гасникова Е.В. Моделирование динамики макросистем на основе концепции равновесия: дисс. к.ф.-м.н. — М.: МФТИ, 2012. — 90 с.

6. Гасников А.В., Гасникова Е.В. Об энтропийно-подобных функционалах, возникающих в стохастической химической кинетике при концентрации инвариантной меры и в качестве функций Ляпунова динамики квазисредних // Математические заметки. — 2013 — Т. 94, вып. 6. — C.819-827.

7. Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Н.Б. Введение в математическое моделирование транспортных потоков. Под ред. А.В. Гасникова, 2-е изд. — М.: МЦНМО, 2013. — 427 с.

8. Zhang Y., Roughan M., Duffield N., Greenberg A. Fast accurate computation of large-scale ip traffic matrices from link loads // Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems. San Diego, CA. — 2003. — P.206—217.

9. Cuturi M. Sinkhorn distances: Lightspeed computation of optimal transport

// Advances in Neural Information Processing Systems 26. — 2013. — P.2292—2300.

10. Kapur J.N. Maximum - entropy models in science and engineering. — John Wiley & Sons, 1989. — 635 p.

11. Жадан В.Г. Методы оптимизации. Ч.1. Введение в выпуклый анализ и теорию оптимизации : учебное пособие. — М.: МФТИ, 2014. — 271 с.

12. Бирюков А.Г. О разностно-аппроксимационном подходе к решению систем нелинейных уравнений // ДАН. — 1983. — Т.270 — C.777-781.

13. Швецов В.И. Математическое моделирование транспортных потоков // Автоматика и телемеханика. — 2003. — Т.11. — С.3-46.

14. Kim D., Fessler J.A.. Optimized first-order methods for smooth convex minimization // Mathematical Programming, Ser. A. — 2016 — V.159(1-2). — P.81 —107.

15. Гасников А.В., Гасникова Е.В., Нестеров Е.С., Чернов А.В. Об эффективных численных методах решения задач энтропийно-линейного программирования // Журнал вычислительной математики и математической физики. — 2016. — Т.56, № 4. — С.523-534.

16. Гасников А.В., Двуреченский П.Е., Камзолов Д.И., Нестеров Ю.Е., Спокойный В.Г., Стецюк П.И., Суворикова А.Л., Чернов А.В. Поиск равновесий в многостадийных транспортных моделях // Труды МФТИ. — 2015. — Т.7, № 4. — С.143-155.

17. Чернов А.В. Прямо-двойственный метод решения задачи энтропийно-линейного программирования // Интеллектуальные системы. Теория и приложения. — М., 2016. — Т.20, вып.1 — C.39-57.

18. Бирюков А.Г., Чернов А.В. Релаксационные рестарт-методы решения задач безусловной минимизации // Интеллектуальные системы. Теория и приложения. — М., 2016. — Т.20, вып.4 — C.16-20.

19. Chernov A., Dvurechencky P., Gasnikov A. Fast primal-dual gradient method for strongly convex minimization problems with linear constraints // In: Kochetov,

Yu. et all (eds.) DOOR-2016. LNCS. — Springer, Heidelberg, 2016. - V.9869. - P.391-403.

20. Аникин А.С., Гасников А.В., Двуреченский П.Е., Тюрин А.И., Чернов А.В. Двойственные подходы к задачам минимизации сильно выпуклых функционалов простой структуры при аффинных ограничениях // Журнал вычислительной математики и математической физики. — 2017. — Т.57, № 8.

- С.1270-1284.

21. Чернов А.В. Об одной модификации быстрого градиентного метода решения задачи энтропийно-линейного программирования // Интеллектуальные системы. Теория и приложения. — М., 2017. — Т.21, вып.2 — C.24-44.

22. Бирюков А.Г., Чернов А.В. О модификациях метода сопряженных градиентов // сб. трудов МФТИ: Модели и методы обработки информации. — М.: МФТИ, 2016. — C.106-112.

23. Гасников А.В., Двуреченский П.Е., Суворикова А.Л., Чернов А.В. Об энтропийной регуляризации транспортной задачи линейного программирования // Труды VIII Московской международной конференции по исследованию операций (ORM2016). — М.: Издательство ФИЦ ИУ РАН, 2016. — Т. 2. — С.241-242.

24. Тюрин А.И., Чернов А.В. Двойственный быстрый градиентный метод решения задач энтропийно-линейного программирования // Труды VIII Московской международной конференции по исследованию операций (ORM2016).

— М.: Издательство ФИЦ ИУ РАН, 2016. — Т. 2. — С.254-257.

25. Chernov A., Dvurechensky P. A primal-dual first-order method for minimization problems with linear constraints // The 40th Interdisciplinary Conference and School. 2016. [PDF] (http://itas2016.iitp.ru/pdf/1570282003.pdf), 5 p.

26. Бирюков А.Г., Чернов А.В. Градиентно-согласованные методы решения задач безусловной минимизации // сб. трудов МФТИ: Информационное обеспечение математических моделей. — М.: МФТИ, 2017 — С.113-125.

27. Chernov A., Gasnikov A., Dvurechensky P. , Stetsyuk P., Suvorikova A. Equilibriums in multistage transport problems // VI International

Conference on Optimization Methods and Applications. Optimization and Applications (OPTIMA-2015). Proceedings — М.: 2015 — P.73-74, [PDF] (http://www.cima.uevora.pt/optima2015/Optima2015.pdf).

28. Чернов А.В. Исследование быстрого градиентного метода при изменении длины шага // 59-я Всероссийская научная конференция МФТИ с международным участием. 2016. [PDF] (http://conf59.mipt.ru/static/reports_pdf/2909.pdf), 2 с.

29. Fang S.-C., Rajasekera J.R., Tsao H.-S.J. Entropy optimization and mathematical programming. — Kluwer's International Series, 1997. — 323 p.

30. Санов И.Н. О вероятности больших отклонений случайных величин // Ма-тем. сб. — 1957. — Т.42, вып. 84. — C.11-44.

31. Батищева Я.Г., Веденяпин В.В. I-й закон термодинамики для химической кинетики // Мат. мод. — 2005. — Т.17, № 8. — C.106-110.

32. Malyshev V.A., Pirogov S.A., Rybko S.A. Random walks and chemical networks // Mosc. Math. J. — 2004. — V.4, N 2. — P.441-453.

33. Tomlin J.A. A new paradigm for ranking pages on the world wide web // Proceedings of the 12th International World Wide Web Conference. — 2003. — P.350-355.

34. Поляк Б.Т. Введение в оптимизацию. Изд. 2-е, испр. и доп. — М.: ЛЕ-НАНД, 2014. — 384 c.

35. Nesterov Y. Smooth minimization of non-smooth function // Math. Program. Ser. A. — 2005. — V.103, N. 1. — P.127-152.

36. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации.— М.: ФИЗМАТЛИТ, 2005. — 368 c.

37. Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. — М.: Наука. Главная редакция физико-математической литературы, 1979. — 384 c.

38. Нестеров Ю.Е. Эффективные методы нелинейного программирования. — М.: Радио и Связь, 1989. — 304 c.

39. Нестеров Ю.Е. Введение в выпуклую оптимизацию. — М.: МЦНМО, 2010. — 280 c.

40. Нестеров Ю.Е. Метод минимизации выпуклых функций со скоростью сходимости o(1/k2)// Докл. АН СССР. — 1983. — Т.269, вып.3. — C.543-547.

41. Pele O., Werman M. Fast and robust earth mover's distances // 2009 IEEE 12th International Conference on Computer Vision (ICCV'09). — 2009. — P.460-467.

42. Benamou J.-D., Carlier G., Cuturi M., Nenna L., Peyre G.. Iterative bregman projections for regularized transportation problems // SIAM Journal on Scientific Computing. — 2015. — V.37, N 2. — P.A1111-A1138.

43. Franklin J., Lorenz J. On the scaling of multidimensional matrices // Linear Algebra and its applications. — 1989. — V.114. — P.717-735.

44. Жадан В.Г. Методы оптимизации. Ч.2. Численные алгоритмы : учебное пособие. — М. МФТИ, 2015. — 319 c.

45. Ортега Дж., Рейнболт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. — М.: Мир, 1975. — 560 c.

46. Полак Э. Численные методы оптимизации. Единый подход. — М.: Мир,

1974. — 376 c.

47. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. — М.: Мир,

1985. — 510 c.

48. Ларичев О.И., Горвиц Г.Г. Методы поиска локального экстремума овражных функций. — М.: ВНИИСИ, 1983. — 93 c.

49. Карманов В.Г. Математическое программирование. — М.: Физматлит,

1986. — 288 c.

50. Бирюков А.Г., Гриневич А.И. Коррекции алгоритмов разностно-аппроксимационных методов решения задач безусловной оптимизации минимизации // сб. трудов МФТИ: «Модели и методы обработки информации». — М.: МФТИ, 2009.

51. Химмельблау Д. Прикладное нелинейное программирование. — М.: Мир,

1975. — 534 c.