Введение к работе
Актуальность и степень разработанности темы исследования
В последние 30 - 40 лет в прикладной математике интенсивно исследуются различные проблемы, математические формулировки которых сводятся к задачам энтропийно-линейного программирования (ЭЛП). В качестве примера можно привести системы, равновесные конфигурации которых определяются на основе принципа максимума энтропии: социальные, экономические, транспортные. В частности, энтропийная модель расчета матрицы корреспонденций в транспортных задачах, закон частоты встречаемости слов в текстах, модель Парето распределения людей по доходам и многие другие.
Таким образом, теория численных методов решения задач ЭЛП достаточно глубоко разработана, им посвящено много работ.
Традиционный подход к решению задач ЭЛП заключается в том, что в явном виде выписывается двойственная задача и устанавливается функциональная связь между переменными прямой и двойственной задач. При этом размерность двойственной задачи всегда оказывается много меньшей размерности прямой задачи, а структура допустимого множества двойственной задачи представляет собой ортант для части ее переменных, в то время как остальные переменные неограничены. Тем самым, задача переводится из класса задач условной минимизации в класс задач безусловной минимизации или условной минимизации на ортанте. Такой подход упрощает решение задачи. В связи с этим, для решения задачи ЭЛП очень часто применяют прямо-двойственный метод, который решает задачу, двойственную к задаче ЭЛП, и параллельно (или потом) восстанавливает решение прямой задачи. Методы, исследуемые в диссертации, также используют эту схему.
Отметим некоторые особенности применения известных часто используемых методов решения задач расчета матрицы корреспонденций, которая является специальным случаем задач ЭЛП. К подобным методам относится, так называемый "метод балансировки", показывающий достаточно высокую эффективность по сравнению со многими другими методами. Однако, среди указанного класса задач существуют такие примеры, что эффективность метода балансировки при их решении резко падает, и задача расчета матрицы корреспонденций становится труднорешаемой. Под эффективностью метода здесь понимается его способность получить решение с требуемой точностью за приемлемое время при условии рационального использования имеющихся ресурсов ЭВМ (память, процессор и прочее).
Для решения задач, двойственных к задаче ЭЛП, используется быст-
рый градиентный метод (БГМ) решения выпуклых оптимизационных задач. В известных вариантах БГМ при неудачном выборе параметров метода необходима процедура его рестарта, которая заключается в изменении допустимого множества решений задачи, что, конечно, снижает эффективность метода.
Важным для построения эффективного метода решения экстремальных задач является также правило его остановки. Задачи, двойственные к задаче ЭЛП, могут быть плохо обусловленными, поэтому для их решения необходимо применять методы регуляризации.
Исходя из перечисленных особенностей, представляется актуальной разработка численных методов, лишенных указанных недостатков, и эффективно решающих задачу, двойственную к задаче ЭЛП, а также исследование скорости их сходимости.
Цели и задачи
Целью настоящей работы является разработка эффективных прямо-двойственных методов решения задачи ЭЛП. Задачами настоящей работы являются:
-
теоретическое и экспериментальное исследование свойств сходимости численных методов решения задачи, двойственной к задаче ЭЛП (ДЗЭЛП);
-
разработка новых прямо-двойственных методов как для решения задач ЭЛП, так и для более широкого класса экстремальных задач, в частности, модификаций БГМ, не требующих процедуры рестарта, методов более устойчивых по сравнению с методом балансировки при решении задач расчета матрицы корреспонденций, а также исследование эффективности методов решения регуляризованной задачи ЭЛП;
-
проведение численных экспериментов для сравнения эффективности известных и предлагаемых в диссертации методов.
Научная новизна
-
Предложена модификация БГМ, в схеме которого отсутствуют рестарты итерационного процесса (ИП) из начальной точки, и проведен подробный теоретический анализ сходимости этой модификации БГМ.
-
Предложена модификация БГМ c варьированием длины итерационного шага.
-
Предложена модификация градиентно-согласованных методов решения задач безусловной минимизации (БМ), проведен анализ ее сходимости.
-
Предложена модификация метода сопряженных градиентов, связанная со способом выбора направления шага, исследована его сходимость.
-
Предложена схема решения задач БМ, в которой вводится последовательность точек рестарта любого из известных методов после выполнения фиксированного числа итераций. Эта схема положена в основу построения релаксационных рестарт-методов.
Теоретическая и практическая значимость работы
Теоретическая значимость работы заключается в разработке новых численных методов решения задачи ДЗЭЛП и обосновании их сходимости.
Практическая значимость работы состоит в том, что предложенные численные методы существенно расширяют спектр методов для решения задач ЭЛП, причем эффективность этих методов подтверждена численными экспериментами.
Работа поддержана грантом РФФИ 14-01-00722 А «Оптимизация в пространствах сверхбольших размеров», 2014 — 2016.
Методология и методы исследования
В работе используется аппарат математического анализа, теории выпуклых функций, линейной алгебры и методов оптимизации.
Для выполнения численных экспериментов использовался интерпретируемый язык программирования Matlab, на котором были реализованы все методы, представленные в диссертации. Все предложенные методы были протестированы, в том числе, на эталонных задачах, решение которых легко проверяется или известно.
Положения, выносимые на защиту
1. Предложена модификация быстрого градиентного метода (БГМ) решения задачи выпуклого программирования с линейными ограничениями (равенствами и неравенствами), которая позволяет исключить рестарты метода, часто вынужденно применяемые при решении практических задач. Доказана сходимость этого метода, получены оценки скорости сходимости. Скорость сходимости метода является асимптотически сублинейной и TV-шагово линейной. Для БГМ предложен способ
выбора фиксированного шага итерационного процесса, позволяющий существенно повысить эффективность поиска решения задачи.
-
Предложена модификация градиентно-согласованных методов решения задачи БМ. Доказаны теоремы о их сходимости. Показано, что для сильно выпуклых функций скорость сходимости линейная.
-
Предложена модификация метода сопряженных градиентов, основанная на поиске минимума квадратичного приближении функции в текущей точке. Рассмотрено 6 вариантов этой модификации. Показано, что скорость сходимости для сильно выпуклой функции линейная.
-
Предложен способ модификации численных методов БМ, применимый, практически, к любому методу. Он заключается во введении последовательности точек рестарта метода после выполнения фиксированного числа итераций. Введено и используется понятие релаксационного рестарт-метода.
-
Исследована эффективность всех предложенных численных методов с помощью серии численных экспериментов. На основе анализа результатов этих экспериментов по тестированию предложенных методов показано, что спектр эффективных методов решения задачи ЭЛП существенно расширен.
Степень достоверности и апробация результатов
Достоверность полученных результатов обеспечивается корректным применением математического аппарата, в частности, строгими доказательствами сходимости всех предложенных методов и вычислительными экспериментами, подтверждающими их высокую эффективность.
Основные результаты диссертации опубликованы в 14 работах. Из них семь работ [1–7] изданы в журналах, рекомендованных ВАК, три работы [1, 5, 6] опубликованы в изданиях, входящих в Scopus и индексируемых Web of Science, [1, 6] имеют англоязычную версию.
Результаты диссертации были доложены, обсуждены и получили одобрение специалистов на следующих научных конференциях и семинарах:
международная конференция по математическому программированию ISMP-2015 (Pittsburgh, 2015);
VI международная конференция “Optimization and Applications” (OPTIMA-2015) (Черногория, Подгорица, 2015);
международная конференция "Quasilinear Equations, Inverse Problems and Their Applications"(Долгопрудный, 2015);
международная конференция "Discrete Optimization and Operations Research "(Владивосток, 2016);
XI международная научная конференция "Интеллектуальные системы и компьютерные науки"(Москва, 2016);
VIII Московская Международная конференция по исследованию операций (Москва 2016);
59-я научная конференция МФТИ (Долгопрудный, 2016);
40-я междисциплинарная конференция и школа ITAS-2016 (Санкт-Петербург, 2016).
Личный вклад соискателя в публикациях с соавторами
Все научные результаты, вынесенные на защиту и представленные в диссертации, получены лично автором. Лично соискателем написан весь программный код и проведены все расчеты.
Структура и объем диссертации