автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Параллельные методы и алгоритмы для решения задач математического моделирования на основе вариационных неравенств

005533432

На правах рукописи

ЗАПОРОЖЕЦ Дмитрий Николаевич

ПАРАЛЛЕЛЬНЫЕ МЕТОДЫ И АЛГОРИТМЫ ДЛЯ РЕШЕНИЯ ЗАДАЧ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ НА ОСНОВЕ ВАРИАЦИОННЫХ НЕРАВЕНСТВ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

1 9 СЕН 2013

Челябинск-2013

005533432

Работа выполнена на кафедре прикладной математики и фундаментальной информатики ФГБОУ ВПО «Омский государственный технический университет»

Научный руководитель: доктор физико-математических наук, профессор

ЗЫКИНА Анна Владимировна.

Официальные оппоненты: доктор физико-математических наук, профессор

ПАНЮКОВ Анатолий Васильевич, заведующий кафедрой «Экономико-математические методы и статистика»

ФГБОУ ВПО «Южно-Уральский государственный университет» (НИУ);

доктор физико-математических наук, профессор, ЖАДАН Виталий Григорьевич, заведующий отделом прикладных проблем оптимизации Федерального государственного бюджетного учреждения науки Вычислительного центра им. А. А. Дородницына Российской академии наук.

Ведущая организация: ФГБОУ ВПО «Новосибирский национальный исследовательский государственный университет»

Защита состош-ся 1 октября 2013 г. в 15 часов на заседании диссертационного совета Д 212.298.14

при ФГБОУ ВПО «Южно-Уральский государственный университет» (НИУ) по адресу: 454080, Челябинск, пр. Ленина, 76.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Южно- т Уральский государственный университет» (НИУ).

Автореферат разослан « %0 » августа 2013 г.

Ученый секретарь диссертационного совета, доктор физ.-мат. наук, доцент

Келлер Алевтина Викторовна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Научный вклад в разработку математических моделей, методов и эффективных алгоритмов решения вариационных неравенств внесли известные ученые:

A. С. Антипин, В. А. Булавский, В. Г. Жадан, С. И. Зуховицкий, А. В. Зыкина,

B. В. Калашников, И. В. Коннов, Г. М. Корпелевич, А. В. Панюков, А. Б. Певный, Б. Т. Поляк, Л. Д. Попов, М. Е. Примак, Е. Н. Хоботов, К. Arrow, G. Debreu, P. Harker, J. Pang, R. Solow и другие.

Универсальными методами решения вариационных неравенств являются итерационные методы, наиболее распространенные из них - градиентные методы. Однако их применение требует выполнения достаточно жестких условий (к примеру, сильной монотонности оператора вариационного неравенства или компактности исходного множества). Ослабить эти условия, а значит, расширить применимость вариационных неравенств позволяют экстраградиентные методы.

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

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

3

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

Для достижения цели работы поставлены следующие задачи-.

1. Разработать метод математического моделирования в задачах оптимального резервирования.

2. Разработать технологию итерационных методов: итерационный метод с памятью, преобразующий последовательные итерационные методы в новый класс параллельных методов.

3. Построить и обосновать итерационные методы с памятью для градиентных и экстраградиентных методов решения вариационных неравенств.

4. Реализовать исследуемые последовательные итерационные методы и их параллельные модификации с памятью в виде программного комплекса.

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

Научная новизна диссертационной работы заключается в том, что разработанный метод моделирования задачи оптимального резервирования основан на использовании аппарата вариационных неравенств в моделировании двухуровневых задач. Разработана новая технология итерационных методов: итерационный метод с памятью. Доказана сходимость по норме итерационных методов с памятью к решению задач для градиентных и экстраградиентных методов, получены оценки скорости сходимости. Впервые разработана математическая модель оптимального резервирования возобновляемых ресурсов, для решения которой применимы разработанные в диссертации численные методы.

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

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

Практическая значимость работы. Программный комплекс ММЯоЬег позволяет решать сводящиеся к вариационным неравенствам актуальные задачи математического моделирования из различных областей знаний, в том числе, задачу оптимального резервирования возобновляемых ресурсов в сельскохозяйственной отрасли, экономическую задачу «Продавец — Покупатель», техническую задачу из теории смазки (задачу о смазке подшипника).

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

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

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

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

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

4. Разработана программа «Экстраградиентные методы» и программный комплекс ММБоЬег, реализующие исследуемые итерационные методы. В ходе вычислительных экспериментов, проведенных на программном комплексе, подтверждена эффективность разработанных алгоритмов, методов и подходов.

Степень достоверности и апробация результатов. Разработанные в диссертационной работе методы, алгоритмы и результаты вычислительных экспериментов докладывались на следующих международных и всероссийских конференциях: Российская конференция «Дискретная оптимизация и исследование операций» (Новосибирск, 2010); Всероссийская молодежная научно-техническая конференция «Россия молодая: передовые технологии - в промышленность» (Омск, 2010); Российская молодежная научно-практическая конференция «При-

5

кладная математика и фундаментальная информатика» (Омск, 2011, 2013); Всероссийская конференция «Математическое программирование и приложения» (Екатеринбург, 2011); Байкальская международная школа-семинар «Методы оптимизации и их приложения» (Иркутск, 2011); Всероссийская конференция «Статистика. Моделирование. Оптимизация» (Челябинск, 2011); Международная научно-техническая конференция «Динамика систем, механизмов и машин» (Омск, 2012); Международная научная конференция «Параллельные вычислительные технологии» (Челябинск, 2013); Международная конференция «Дискретная оптимизация и исследование операций» (Новосибирск, 2013).

Работа выполнялась при поддержке Министерства образования и науки Российской Федерации (соглашение № 14.В37.21.1123) и РФФИ (проекты № 1201-31360, № 12-07-00326).

Публикации. По теме диссертации опубликовано 17 научных работ, в их числе 4 статьи в ведущих российских рецензируемых научных журналах и изданиях, рекомендованных ВАК [1-4], и 2 свидетельства о государственной регистрации программ для ЭВМ. Список работ приведен в конце автореферата.

В совместных с научным руководителем работах [2, 3, 4, 9, 11, 13, 17] научному руководителю принадлежат постановки задач, Запорожцу Д. Н. - все основные полученные результаты.

Из остальных работ, выполненных в соавторстве, в диссертацию включены только те результаты, которые были получены лично Запорожцем Д. Н. и не затрагивают интересов других соавторов.

Структура и объем работы. Диссертационная работа состоит из введения, четырех разделов основного содержания, заключения, списка литературы из 106 наименований и приложений. Полный объем диссертации составляет 135 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

Первый раздел, «Математическое моделирование в двухуровневой оптимизации», состоит из шеста подразделов и содержит основные сведения из

6

теории вариационных неравенств, методов оптимизации и параллельных вычислений. На основе анализа разработанных моделей, методов и эффективных алгоритмов А. С. Антипина1, А. В. Зыкиной2, В. Г. Жадана3, И. В. Коннова4, А. В. Па-нюкова5 предлагается метод математического моделирования задач оптимального резервирования на основе вариационных неравенств в различных предметных областях.

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

Решить вариационное неравенство - значит найти такой вектор х* е А, удовлетворяющий условиям:

(Н(х*),х - х*> > О V* е а, (1)

где Н: Е" —> Ш^, А - выпуклое, замкнутое множество.

Приводятся постановки смешанных вариационных неравенств, вариационных неравенств со связанными ограничениями и вариационно-подобных неравенств.

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

Задача двухуровневой оптимизации выглядит следующим образом X* е АгдтптШх.у*) \х е Х,а1(х,у') < 0},

где у* — решение задачи (2)

у* е Агдтт{Р2(х\у)\у е У,д2(х\у) < 0}.

1 Антипин, А. С. О методе выпуклого программирования, использующем симметрическую модификацию функции Лаграгока // Экономика и математические методы. - 1976. - Т. 12. - № 6. - С. 1164-1173.

23ыкина, A.B. Обратная дополнительность в модели управления ресурсами // Журнал вычислительной математики и математической физики. - 2008.-Т. 48.11.-С. 1968-1978.

3Евтушенко,Ю.Г., Жадан, В.Г. Релаксационный метод решения задач нелинейного программирования // Журнал вычислительной математики и математической физики. - 1977. - Т. 17, №4. - С. 890-904.

'Konnov, I. V. Combined relaxation methods for variational inequalities. - Berlin etc.: Springer, 2001.-181 p.

5Панюков, А. В., Латипова, A.T. Численные методы определения положения равновесия в модели Неймана //Журнал вычислительной математики и математической физики. - 2008.-Т. 48, № И - С. 1999-2007.

Здесь функция F1: R+ х R+ ® — выпуклая, дифференцируемая по х для любого у, функция F2 Mi¡í х —» К — выпуклая, дифференцируемая по у для любого х, 9i (х> У) - выпуклая по х функция для любого у, д2 (х, у~) - выпуклая по у функция для любого х, X, Y — выпуклые компакты.

При указанных условиях задача (2) записана в терминах вариационных неравенств.

В п. 1.3 построена математическая модель задачи оптимального резервирования возобновляемых ресурсов в сельскохозяйственной отрасли. На верхнем уровне решается задача максимизации выручки от продажи зерна:

m л

х* 6 Агдтах ^Г ^ Р*(С1Х1 ~ У?) I * е Х(у) ,

(С=1 1=1 )

Х(у) = (хX** = ЯК'к - X** - <3,к'= 17п|.

Мс=1 ¡=1 ге/^ >

где х^— посевная площадь, занятая семенами /-го сорта к-й репродукции, га; р? — цена реализации семян /-го сорта к-й репродукции, руб/ц; ск - урожайность /-го сорта к-й репродукции, ц/га; у* — семенной фонд /-го сорта к-й репродукции, который необходимо заготовить, ц; Б — обшая посевная площадь, га; ¡к — подмножество номеров сортов, 1к € {¡к,..., }; (¿¡к -минимальная и максимальная допустимая посевная площадь под группу сортов 1к к-й репродукции, га, соответственно; О — норма высева, ц/га.

Задача второго уровня - минимизация затрат на покупку новых семян

ш л

у* 6 Агдтт{ ^ а?{0х? ~ У?) IУ е у(х)- к = 1,т} к=1¿=1

У(х) = ПГ а? (Ох? - у,*) < В ¡к, 1к б {/?...., /£}, к = Ш

Чей

где ак — цена семян /-го сорта к-й репродукции, руб/ц.

В п. 1.4 и 1.5 разработанный аппарат моделирования используется для моделирования экономической задачи «Продавец - Покупатель» и технической задачи из теории смазки (задачи о смазке подшипника).

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

Второй раздел, «Итерационные методы», состоит из пяти подразделов и содержит итерационные методы решения вариационных неравенств: градиентные методы с постоянным шагом, с убывающим шагом, одношаговый и двухшаговый экстраградиентные методы.

В п. 2.1 приводится описание градиентных методов для решения вариационного неравенства (1). Вычислительная схема методов имеет вид

хк+1 = Рп(хк- аН(хкУ), где а — длина шага метода, Н— оператор вариационного неравенства, Рп - оператор проецирования на множество П.

В п. 2.2 рассматриваются одношаговый и двухшаговый экстраградиентные методы. Одношаговый экстраградиентный метод для решения вариационного неравенства (1) задается следующими рекуррентными выражениями

хк = Рп(хк- аН (хк)) , хк+1 = Рп (хк-аН (хк)) . Основное отличие экстраградиентного метода от градиентного заключается в вычислении прогнозной точки хк.

Двухшаговый экстраградиентный метод для решения вариационного неравенства (1) задается рекуррентными выражениями

хк = Рп (хк - аН(хкУ),хк = Рп (хк - аН(хкУ), хк+1 = Рп (хк - аН(хк)). В отличие от одношагового экстраградиентного метода двухшаговый метод для вычисления очередной точки использует две прогнозные точки хк и хк.

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

Вычислительная схема итерационных методов с памятью строится следующим образом. Пусть задан итерационный процесс хк+1 = :к) ,где Г - некоторая процедура, последовательность действий, необходимая для получения следующей итерационной точки хк+1.

Вектором движения итерационного процесса на к-й итерации называется разность точек, полученных на к-н и (&-1)-й итерациях: гк = хк- хк_г

На к-й итерации строится вспомогательная точка хк = хк + ггк, Ле(ОД]. Выражение для вычислительной схемы итерационного метода с памятью на основе итерационного процесса Р задается следующим образом:

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

Предлагаемый подход заключается в том, что используя направление гк, вычисляем вспомогательную точку хк. Затем вычисляем Р(хк), а на другом процессоре - И если Хк удовлетворяет критерию одного направления, а именно, хк попадает в некоторую область у, то в качестве следующей точки хк+1 следует брать F(xk).

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

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

В п. 2.4 для итерационных методов с памятью доказаны следующие утверждения.

Теорема 1. Пусть последовательность заданная оператором

Р'-Кп Кп, монотонно сходится по норме к х* £ П с д" где П - замкнутое,

(3)

выпуклое множество. Тогда последовательность итерационного метода с памятью (3) на основе оператора ^(лг) с критерием одного направления в виде условия

11% - *к|| + ||*к - П%)11 = 11% - (4)

монотонно приближается по норме к х*.

Доказана монотонная сходимость в итерационных методах с памятью (3) с критерием одного направления в виде условия (4) для семейства градиентных методов (с постоянным шагом, с убывающим шагом) (Теорема 2), для одношагово-го и двухшагового экстраградиентных методов (Теорема 3). Построены вычислительные схемы алгоритмов с памятью.

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

Теорема 4. Пусть последовательность , заданная оператором

Р: -» Я", монотонно сходится по норме к х* £ П С Л", где Л - замкнутое, выпуклое множество. Пусть последовательность обладает сходимо-

стью степени (3 •

Зае(0Д]: ЭМеМ, Чк > N \\хк - х'\\ < аИ*^ - х'\\Р.

Тогда последовательность итерационного метода с памятью (3) на основе оператора с критерием одного направления (4) обладает сходимостью

степениД

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

Третий раздел, «Программный комплекс ММБоЬег», состоит из шести подразделов и содержит описание программного комплекса ММБоЬег и внутреннее строение его модулей, дается описание их интерфейсов, классов, реализованных методов. Каждый метод решения вариационного неравенства, каждая задача, сводящаяся к вариационному неравенству, реализованы в виде отдельных модулей, которые способны динамически загружаться в программный комплекс

11

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

В п. 3.1 рассматривается структура модуля MatrixCalc: программная реализация основных действий над векторами и матрицами. В п. 3.2 описывается структура модуля Task, в котором содержится описание интерфейса вариационного неравенства и содержательной задачи, сводимой к вариационному неравенству. В п. 3.3 содержится описание модуля Method. В этом модуле объявлен интерфейс итерационного метода решения вариационного неравенства. Таким образом, предоставляется возможным использовать в программном комплексе MMSolver собственные методы, причем к каждому методу автоматически добавится еще один метод «с памятью». В п. 3.4 исследуются особенности реализации итерационных методов с памятью на языке программирования С# 4.0 с использованием библиотеки TPL и на языке программирования С++ с использованием библиотеки OpenMP 2.0. В п. 3.5 дается описание интерфейса программного комплекса MMSolver.

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

Четвертый раздел, «Вычислительные эксперименты», состоит из трех подразделов и включает численные эксперименты, которые проводились для оценки эффективности итерационных методов с памятью по времени и по числу итераций. Проведены исследования на монотонность, овражность функций, выпуклость допустимого множества.

В п. 4.1 рассматриваются тестовые задачи: системы линейных алгебраических уравнений со специальной кососимметрической матрицей, задачи дополнительности, вариационные неравенства, оптимизационные задачи, в том числе, с функциями Розенброка и Химмельблау. Эмпирически подтверждено, что относительная эффективность применения итерационных методов с памятью по числу

12

итераций для градиентного метода и одношагового экстраградиентного метода составляет до 50%, для двухшагового экстраградиентного метода — до 80%.

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

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

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

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

ОСНОВНЫЕ НАУЧНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Разработан новый метод математического моделирования задачи оптимального резервирования возобновляемых ресурсов. Метод основан на использовании аппарата вариационных неравенств в моделировании двухуровневых задач. Метод применен для моделирования задач из различных предметных областей (задача резервирования семенного фонда в сельскохозяйственной отрасли, экономическая задача «Продавец - Покупатель», техническая задача о смазке подшипника).

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

3. Разработаны новые итерационные методы с памятью для градиентного метода с постоянным шагом, градиентного метода с убывающим шагом, одно-шагового экстраградиентного метода и двухшагового экстраградиентного метода, доказана сходимость методов по норме к решению задач, получены оценки скорости сходимости.

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

5. Разработана программа «Экстраградиентные методы» и программный комплекс MMSolver, реализующие исследуемые итерационные методы. В ходе вычислительных экспериментов, проведенных на программном комплексе, подтверждена эффективность разработанных алгоритмов, методов и подходов, получены новые закономерности, характеризующие построенную математическую модель оптимального резервирования возобновляемых ресурсов в сельскохозяйственной отрасли.

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи, опубликованные в ведущих российских рецензируемых научных журналах, рекомендованных ВАК

1. Запорожец, Д.Н. Обработка исходных данных при реализации экстраградиентных методов решения линейных оптимизационных задач / Д.Н. Запорожец // Омский научный вестник. Серия Приборы, машины и технологии. - № 3(93). -2010. — С.18 — 22.

2. Запорожец, Д.Н. Распараллеливание экстраградиентных методов / Д.Н. Запорожец, B.C. Зыкин, A.B. Зыкина, Д.И. Куянов // Омский научный вестник. Серия Приборы, машины и технологии. - № 3(103).- 2011.- С.22 - 25.

3. Запорожец, Д.Н. Двухшаговый экстраградиентный метод с памятью для решения вариационных неравенств со связанными ограничениями / Д.Н. Запорожец, A.B. Зыкина // Омский научный вестник. Серия Приборы, машины и технологии. —№ 3(113). - 2012. - С. 274 - 277.

4. Запорожец, Д.Н. Сравнительный анализ экстраградиентных методов решения вариационных неравенств для некоторых задач / Д.Н. Запорожец, A.B. Зыкина, Н.В. Меленьчук // Автоматика и телемеханика. - 2012. - № 4. - С. 32 - 46.

Свидетельства о регистрации программы

5. Запорожец, Д.Н. Экстраградиентные методы (программа) / Д.Н. Запорожец, Н.В. Меленьчук // М.: ОФЭРНиО ФГПУ ИНИПИ РАО, 2010. - № 50201050071. - Св-во о регистрации электронного ресурса № 16330 от 27 октября 2010 года.

6. Запорожец, Д.Н. Программный комплекс MMSolver (программный комплекс) / Д.Н. Запорожец // М.: ОФЭРНиО ФГПУ ИНИПИ РАО, 2012. - № 50201250473. - Св-во о регистрации электронного ресурса № 18137 от 17 апреля 2012 года.

Другие публикации

7. Запорожец, Д.Н. Вариационные неравенства со связанными ограничениями в модели планирования производства / Д.Н. Запорожец, Н.В. Меленьчук // Россия молодая: передовые технологии - в промышленность: материалы III Все-рос. молод, науч.-тех. конф. - Омск: Изд-во ОмГТУ, 2010. - Кн. 1. - С.276 - 278.

8. Запорожец, Д.Н. Программное обеспечение для решения линейных оптимизационных задач экстраградиентными методами / Д.Н. Запорожец // Омское время - взгляд в будущее: Тез.докл. регион, молод, науч.-техн. конф. - Омск: Изд-во ОмГТУ, 2010. - Книга 1. - С. 225-228.

9. Запорожец, Д.Н. Эффективность двухшагового экстраградиентного метода решения вариационных неравенств / Д.Н. Запорожец, A.B. Зыкина, Н.В. Меленьчук // Дискретная оптимизация и исследование операций: Материалы Рос. конф. - Новосибирск: ИМ СО РАН, 2010. - С.87.

10. Запорожец, Д.Н. Распараллеливание экстраградиентных методов решения оптимизационных задач с матричным оператором / Д.Н. Запорожец, B.C. Зыкин, Д.И. Куянов // Прикладная математика и фундаментальная информатика: Сб. науч. тр. - Омск: Изд-во ОмГТУ, 2011. - С. 73 - 79.

11. Запорожец, Д.Н. Экстраполяционные методы решения вариационных неравенств и смежных задач / Д.Н. Запорожец, A.B. Зыкина, Н.В. Меленьчук // Математическое программирование и приложения: Информац. бюллетень АМП № 12 / XIV Всерос. конф.: Тез.докл. - Екатеринбург: УрО РАН, 2011. - С. 41 - 42.

12. Запорожец, Д.Н. Экстраградиентные методы с памятью / Д.Н. Запорожец // XV Байкальская международная школа-семинар «Методы оптимизации и их приложения». Т. 2: Математическое программирование. — Иркутск: РИО ИДСТУ СО РАН, 2011. - С. 92 - 95.

13. Запорожец, Д.Н. Экстраградиентные методы с памятью для решения вариационных неравенств / Д.Н. Запорожец, A.B. Зыкина // Статистика. Моделирование. Оптимизация: сборник трудов Всерос. конф. - Челябинск: Изд. центр ЮУрГУ,2011.-С. 121- 124.

14. Запорожец, Д.Н. Программный комплекс MMSolver / Д.Н. Запорожец // Динамика систем, механизмов и машин: материалы VIII Междунар. науч.-техн. конф. - Омск: Изд-во ОмГТУ, 2012. - С. 258 - 261.

15. Запорожец, Д.Н. Распараллеливание итерационных методов решения вариационных неравенств / Д.Н. Запорожец // Параллельные вычислительные технологии: сб. тр. Междунар. конф. - Челябинск: Изд. центр ЮУрГУ, 2013. - С. 121-124.

16. Запорожец, Д.Н. Параллельные технологии в решении задачи оптимального резервирования возобновляемых ресурсов на примере сельскохозяйственной отрасли / Д.Н. Запорожец // Прикладная математика и фундаментальная информатика: сб. материалов III Рос. молод, науч.-практ. конф. - Омск: Изд-во ОмГТУ, 2013.-С. 48-51.

17. Запорожец, Д.Н. Разработка параллельных алгоритмов многошаговых экстраградиентных методов / Д.Н. Запорожец, A.B. Зыкина // Междунар. конф. «Дискретная оптимизация и исследование операций»: Материалы конф. Новосибирск : ИМ СО РАН, 2013. - С.49.

Печатается в авторской редакции Подписано в печать 15.08.13. Формат 60х 84 1/16. Отпечатано на дупликаторе. Бумага офсетная. Усл. печ.л. 1.Усл.-изд.л. 1.Тираж 100 экз.

Издательско-полиграфический центр ОмГМА 644050, г. Омск, пр. Мира, 30, тел. 60-59-08 16

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ОМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

На правах рукописи

04201362269

Запорожец Дмитрий Николаевич

ПАРАЛЛЕЛЬНЫЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ НА ОСНОВЕ ВАРИАЦИОННЫХ НЕРАВЕНСТВ

05.13.18 - Математическое моделирование, численные методы и

комплексы программ

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель: Зыкина Анна Владимировна, д.ф-м.н.. профессор

Омск - 2013

Оглавление

Введение ......................................................................4

1 Математическое моделирование в двухуровневой оптимизации ... 11

1.1 Вариационные неравенства в математическом моделировании 11

1.2 Двухуровневая математическая модель задачи оптимального резервирования на основе вариационных неравенств..........21

1.3 Двухуровневая математическая модель в сельском хозяйстве 24

1.4 Двухуровневая математическая модель

«Продавец-Покупатель»..........................................27

1.5 Двухуровневая математическая модель в задаче теории смазки 28

1.6 Итоги раздела 1....................................................29

2 Итерационные методы....................................................30

2.1 Градиентные методы..............................................31

2.2 Экстраградиентные методы......................................32

2.3 Итерационные методы с памятью................................36

2.4 Сходимость методов ..............................................38

2.5 Итоги раздела 2....................................................46

3 Программный комплекс MMSolver......................................47

3.1 Описание модуля MatrixCalc ....................................48

3.2 Описание модуля Task............................................49

3.3 Описание модуля Method..........................................51

3.4 Особенности реализации методов с памятью....................52

3.5 Интерфейс программного комплекса MMSolver................55

3.6 Итоги раздела 3....................................................58

4 Вычислительные эксперименты..........................................60

4.1 Тестовые задачи....................................................61

4.2 Двухуровневая задача оптимального резервирования в сельском хозяйстве ................................................86

4.3 Итоги раздела 4....................................................88

Заключение....................................................................92

Словарь терминов............................................................93

Список литературы ..........................................................97

Приложение А Вычислительные эксперименты решения СЛАУ .... 107 Приложение Б Вычислительные эксперименты решения линейной задачи дополнительности ..................................................110

Приложение В Вычислительные эксперименты решения нелинейного

вариационного неравенства.......................120

Приложение Г Вычислительные эксперименты решения задачи МП . . 120

Приложение Д Вычислительные эксперименты решения задачи ЛП . . 133

Введение

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

Научный вклад в разработку моделей, методов и эффективных алгоритмов решения вариационных неравенств внесли такие известные ученые как A.C. Антипин, В.А. Булавский, В.Ф. Демьянов,.В.Г. Жадан, С.И. Зуховицкий, A.B. Зыкина, В.В. Калашников, И.В. Коннов, Г.М. Корпелевич, A.B. Панюков, A.B. Певный, Б.Т. Поляк, Л.Д. Попов, М.Е. Примак, E.H. Хоботов, K.J. Arrow, G. Debreu, Р.Т. Harker, Т. Kose, J.S. Pang, R.M. Solow и другие.

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

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

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

Создавать параллельные программы при помощи специального набора директив и процедур позволяет технология ОрепМР, являющаяся наиболее эффективным средством программирования для систем с общей памятью. Данная технология использована при создании программного комплекса в диссертационном исследовании.

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

Диссертационная работа опирается на исследования A.C. Антипина, A.B. Зыкиной, И.В. Коннова, Н.В. Меленьчука и расширяет аппарат математических методов моделирования сложных оптимизационных систем и итерационных методов для их решения.

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

ционных неравенств.

Для достижения поставленной цели в диссертационном исследовании поставлены следующие задачи:

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

2. Разработать технологию итерационных методов: итерационный метод с памятью, преобразующий последовательные итерационные методы в новый класс параллельных методов.

3. Разработать и обосновать итерационные методы с памятью для градиентных и экстраградиентных методов решения вариационных неравенств.

4. Реализовать исследуемые последовательные итерационные методы и их параллельные модификации с памятью в виде программного комплекса.

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

Научная новизна диссертационной работы заключается в том, что разработанный метод моделирования задачи оптимального резервирования основан на использовании аппарата вариационных неравенств в моделировании двухуровневых задач. Разработана новая технология итерационных методов: итерационный метод с памятью. Доказана сходимость итерационных методов с памятью по норме к решению задач для градиентных и экстраградиентных методов, получены оценки скорости сходимости. Впервые разработана математическая модель оптимального резервирования возобновляемых ресурсов, для решения которой применим разработанный в диссертации численный метод.

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

Практическая значимость работы. Разработанное программное обес-

печение зарегистрировано в РО ОФЭРНиО. Программный комплекс ММЯокег позволяет решать сводящиеся к вариационным неравенствам актуальные задачи математического моделирования из различных областей знаний, в том числе, задачу оптимального резервирования возобновляемых ресурсов в сельскохозяйственной отрасли, экономическую задачу «Продавец - Покупатель», техническую задачу из теории смазки.

Программный комплекс ММвоЬег используется студентами и научными сотрудниками Омского государственного технического университета в рамках учебного процесса и при научных исследованиях.

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

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

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

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

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

4. Разработана программа «Экстраградиентные методы» и программный комплекс ММБоЬег, реализующие исследуемые итерационные методы. В ходе вычислительных экспериментов, проведенных на программном комплексе, подтверждена эффективность разработанных алгоритмов, методов и подходов.

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

1. Российская конференция «Дискретная оптимизация и исследование операций» (Новосибирск, 2010);

2. Всероссийская молодежная научно-техническая конференция «Россия

молодая: передовые технологии - в промышленность» (Омск, 2010);

3. Российская молодежная научно-практическая конференция «Прикладная математика и фундаментальная информатика» (Омск, 2011);

4. Всероссийская конференция «Математическое программирование и приложения» (Екатеринбург, 2011);

5. Байкальская международная школа-семинар «Методы оптимизации и их приложения» (Иркутск, 2011);

6. Всероссийская конференция «Статистика. Моделирование. Оптимизация» (Челябинск, 2011);

7. Международная научно-техническая конференция «Динамика систем, механизмов и машин» (Омск, 2012);

8. Международная научная конференция «Параллельные вычислительные технологии» (Челябинск, 2013);

9. Международная конференция «Дискретная оптимизация и исследование операций» (Новосибирск, 2013).

Публикации. По теме диссертации опубликовано 17 работ (12 статей, 2 тезисов докладов, 2 свидетельства о государственной регистрации программ для ЭВМ). Основные публикации приведены в конце автореферата. В их числе 4 статьи из ведущих российских рецензируемых научных журналов и изданий [26-29].

В совместных работах [27-29] Зыкиной А. В. принадлежат постановки задач, Запорожцу Д. Н. - все основные полученные результаты. Из остальных работ, выполненных в соавторстве, в диссертацию включены только те результаты, которые были получены лично Запорожцем Д. Н. и не затрагивают интересов других соавторов.

Структура и объем работы. Диссертационная работа состоит из введения, четырех разделов основного содержания, заключения, списка литературы из 106 наименований. Полный объем диссертации составляет 135 страниц.

Изложение материала диссертации построено следующим образом.

Раздел 1 состоит из пяти подразделов и содержит основные сведения из теории вариационных неравенств, методов оптимизации и параллельных вычислений. Рассматривается научный вклад в разработку моделей, методов и эффективных алгоритмов. На основе анализа разработанных моделей, методов и эффективных алгоритмов А. С. Антипина, В. Л. Береснева, Э. X. Гимади,

В.Т.Дементьева, А.В.Зыкиной, И. В. Коннова, Ю. А. Кочетова, Н.В.Мелень-чука, Е. А. Нурминского, Л.Д.Попова, Н.Б.Шамрай предлагается метод математического моделирования задач оптимального резервирования на основе вариационных неравенств в различных предметных областях. Даются постановки следующих задач: вариационные неравенства, смешанные вариационные неравенства, вариационные неравенства со связанными ограничениями и вариационно-подобные неравенства, лексикографические вариационные неравенства линейные и нелинейные задачи дополнительности, задачи линейного программирования, задачи выпуклого программирования, задачи о седловой точке. Отдельное внимание уделяется новому методу математического моделирования задач оптимального резервирования на основе вариационных неравенств.

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

У полученных методов с памятью есть два отличия от исходных методов. Во-первых, новые методы запоминают направление движения на каждом шаге и на очередном шаге используют информацию о направлении движения на предыдущем шаге. Во-вторых, вычислительная схема новых методов допускает распараллеливание, что позволяет сократить время вычислений. Для каждого метода получена оценка трудоемкости одной итерации через количество операций произведения и сложения.

Описывается применение нового метода к существующим градиентным и экстраградиентным методам и приводятся модификации градиентных методов с памятью, одношагового и двухшагового экстраградиентных методов с памятью. Строятся вычислительные схемы алгоритмов с памятью для семейства градиентных методов (с постоянным шагом, с убывающим шагом), для одно-шагового и двухшагового экстраградиентных методов.

Раздел 3 состоит из шести подразделов и содержит описание программного комплекса MMSolver и внутреннее строение его модулей: MatrixCalc, Task, Method, - дается описание их интерфейсов, классов, включая реализованные в них методы. Поэтапно излагается процесс написания собственного модуля для программного комплекса, реализующего либо метод решения вариационных неравенств, либо задачу, сводящуюся к вариационному неравенству. Отдельно исследован вопрос численной реализации итерационных методов с памятью и их эффективной параллельной реализации.

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