Параллельные вычислительные технологии решения конечномерных задач оптимизации большой размерности тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Аникин Антон Сергеевич

• Аникин Антон Сергеевич
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Аникин Антон Сергеевич

Введение

Глава 1. Основные трудности современных задач оптимизации

1.1. Размерность задачи

1.2. Вычислительная сложность

1.3. Сложная внутренняя структура

1.4. Общие подходы ускорения решения задач оптимизации

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

1.4.2. Распараллеливание вычислений, связанных с задачей

1.4.3. Распараллеливание метода оптимизации

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

2.1. Системы с общей памятью

2.2. Кластерные вычислительные системы

2.3. Ускорители расчётов

2.3.1. Графические ускорители

2.3.2. Ускорители архитектуры Intel MIC

2.3.3. Программируемая пользователем вентильная матрица

2.3.4. Интегральные схемы специального назначения

2.4. Гибридные вычислительные системы

2.5. Распределенные системы добровольных вычислений

Глава 3. Программная реализация

3.1. Средства реализации

3.2. Структуры данных

3.2.1. Плотные вектора и матрицы

3.2.2. Разреженные матрицы

3.2.3. Бинарные вычислительные деревья

3.3. Базовые модули

3.3.1. Базовые алгоритмы линейной алгебры (BLAS)

3.3.2. Разностные схемы вычисления градиентов

3.3.3. Быстрая генерация дискретной случайной величины

3.3.4. Схемы прямого обновления сумм

3.4. Методы одномерной минимизации

3.5. Градиентные методы локальной оптимизации

3.5.1. Метод сопряжённых градиентов

3.5.2. Метод Barzilai-Borwein

3.5.3. Метод Б.Т. Поляка

3.5.4. Методика создания унифицированных CPU/GPU реализаций

3.6. Покомпонентные методы локальной оптимизации

3.6.1. Прямой градиентный метод в 1-норме

3.6.2. Метод «диагонального поиска» hRPDS

3.6.3. Метод условного градиента (Франк-Вульфа)

3.6.4. Покомпонентная модификация метода покоординатного спуска

3.6.5. Метод покоординатного спуска в варианте Хука-Дживса hRCHJ

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

3.7. Методы глобальной оптимизации

3.7.1. Параллельная модификация метода MSBH

3.7.2. Метод Forest

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

Глава 4. Тестовые и прикладные задачи

4.1. Поиск равновесного распределения транспортных потоков для

модели Бэкмана

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

4.2. Задача восстановления матрицы корреспонденций компьютерных сетей

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

4.3. Задача ранжирования web-страниц (PageRank)

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

4.4. Оптимизация атомно-молекулярного потенциала Китинга .... 148 4.4.1. Вычислительные эксперименты

4.5. Оптимизация атомно-молекулярного потенциала Морса

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

4.6. Тестовые задач локальной оптимизации класса Huge-Scale (1011) . 158 4.6.1. Вычислительные эксперименты

Заключение

Литература

Список рисунков

Список таблиц

Введение

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

Актуальность

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

За свою достаточно долгую историю математическая теория оптимизации прошла путь от простейших методов решения задач, которые в наше время уже считаются тривиальными, до современных, достаточно сложных, комплексных подходов, позволяющих успешно работать с постановками, которые ранее воспринимались не иначе, как неразрешимые. С формальной позиции многие задачи оптимизации можно разбить на две основные группы: конечномерная (параметрическая) оптимизация и оптимизация в бесконечномерном пространстве. К последней группе в первую очередь стоит отнести задачи вариационного исчисления и задачи поиска оптимального управления. Диссертационная работа посвящена рассмотрению современных задач из первой группы — задач конечномерной оптимизации большой размерности. Такие задачи, в свою очередь, могут быть разделены на два традиционных клас-

са: задачи локальной оптимизации и задачи поиска глобального экстремума. Рассмотрим их более подробно.

Решение задач локальной оптимизации является, пожалуй, наиболее проработанной областью математического программирования. Первые фундаментальные результаты для этого класса были получены ещё несколько столетий назад, сохраняя при этом свою актуальность и в наши дни. В качестве яркого примера можно привести метод Ньютона, который до сих пор обладает вполне конкурентоспособными свойствами для класса дважды-дифференцируемых функций. Локальные задачи могут быть классифицированы по достаточно большому набору критериев: гладкости (дифференци-руемости), выпуклости, наличию или отсутствию ограничений и т.п. Существуют также задачи стохастической оптимизации, робастной оптимизации, оптимизации задач с неточным оракулом и множество других вариантов, обусловленных проблемами, поступающими из разных различных прикладных областей. Для каждого такого типа предложены свои подходы и методы, которые непрерывно совершенствуются. Разработаны различные схемы редукций, которые позволяют преобразовывать постановку решаемой задачи к другому, более удобному в конкретном случае, виду. Хорошим примером такого преобразования может быть метод внешних штрафных функций, переводящий задачу условной оптимизации (с ограничениями) в форму, позволяющую использовать методы безусловной оптимизации. Многие ведущие исследовательские группы ведут активную работу именно в классе локальных задач, существенно расширяя область применения теоретического аппарата для новых, всё более сложных постановок. Более того — в последние годы серьёзное продвижение было сделано для класса выпуклых задач, которые, казалось бы, уже были полностью изучены и исследованы «до дна». Здесь, безусловно, стоит выделить таких исследователей, как Ю.Е. Нестеров (см., например, [1]) и А.С. Немировский (см., например, [2]), чьи работы широко известны во всём мире и обладают огромным авторитетом в своей области. Обязательного изучения заслуживают и работы других ведущих специалистов: Б.Т. Поляка [3], Д. Бертсекаса [4; 5], С. Бойда [6]. Среди молодых исследователей можно также выделить работу С. Бубека [7], которую

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

Исследования в области оптимизации унимодальных функций, строго говоря, невыпуклых (см., например, [8]), пока, к сожалению, серьёзно отстают от темпа, заданного работами для класса выпуклых задач. Это связано с фактом большей сложности таких постановок и высокой трудоёмкостью получения, например, адекватных оценок скорости сходимости методов, решающих эти задачи. Возможно, большинство специалистов не «рискует» глубоко заниматься работами в данном направлении из-за низких ожиданий в получении достойных с точки зрения математической теории результатов. Такая ситуация, к сожалению, уже стала в каком-то смысле доминирующей. Рядом известных специалистов (см., например, [6]) даже выдвигается тезис о том, что текущее состояние развитие теории позволяет говорить о возможности надёжного решения только выпуклых постановок экстремальных задач, а решение унимодальных задач пока требует применения менее формализованных подходов и должно воспринимается как некоторое «искусство», требующее соответствующих навыков и не гарантирующее получение результата. Практический же опыт говорит, что унимодальные постановки вполне успешно могут быть решены с применением модификаций уже разработанных методов и подходов. Более того — на практике методы, имеющие не слишком хорошие оценки, зачастую показывают вполне достойные результаты, в ряде случаев превосходящие таковые для методов, имеющих более «хорошие» с точки зрения теории характеристики. Такой разрыв между теорией и практикой оптимизации не может не огорчать, но есть определённые надежды на то, что в ближайшие годы он будет устранён, поскольку количество прикладных задач, обладающих свойством выпуклости, серьёзно уступает числу унимодальных постановок.

Ситуация с теорией и методами решения задач глобальной оптимизации ещё более сложная (см., например, [9; 10]). Теоретические результаты, полученные к настоящему времени в этой области, к сожалению, гораздо скоромнее, чем для задач локальной оптимизации. Это связано с фактом несопоставимо большей реальной сложности глобальных постановок по сравнению с задачами поиска локального экстремума. Многие известные специалисты

сомневаются в достижение какого-либо серьёзного прогресса для таких задач, а некоторые исследователи полагают, что он вообще невозможен. На сегодняшний день для некоторых, пока весьма ограниченных, классов задач имеются теоретически обоснованные способы их решения, что вселяет осторожную надежду на то, что они в дальнейшем могут быть распространены на более широкий круг постановок. Один из таких подходов заключается в использовании методов интервального анализа [11; 12], что влечёт за собой целый ряд весьма серьёзных сложностей, которые, к сожалению, существенно ограничивают возможности его применения для решения многих прикладных задач. В качестве другого способа можно привести подходы, связанные с конструкциями неравномерных покрытий [13], предложенных в работах академика Ю.Г. Евтушенко. Особенностью подхода являются его высокая вычислительная сложность и требование наличия адекватной оценки константы Липшица для требуемой области поиска, что, к сожалению, далеко не всегда выполнимо на практике. Можно утверждать, что на сегодняшний день все надёжные, теоретически обоснованные методы при рассмотрении многомерных задач требуют либо огромных вычислительных ресурсов, либо выдвигают достаточно жёсткие требования к исходной задаче, что существенным образом ограничивает класс решаемых проблем.

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

фективность выполнения этой операции напрямую влияет на общую трудоёмкость глобального метода.

Наличие эффективных с математической точки зрения методов оптимизации может во многих случаях оказаться недостаточно для решения реальных прикладных задач. На современном этапе для этого применяются программные продукты, которые реализуют различные многометодные схемы, включающие комбинации разнородных численных алгоритмов. Важным моментом, о котором нельзя забывать, является факт того, что алгоритм метода и его конкретная программная реализация, вообще говоря, являются разными объектами. Это сказано как с различным языком описания и, соответственно, уровнем применяемых абстракций, так и с ограничениями, накладываемыми аппаратной архитектурой, которая используется для исполнения созданного программного кода. В силу целого ряда технических факторов прекрасный с математической точки зрения метод может оказаться малоэффективным в рамках используемого вычислительного устройства. Важность этой проблемы хорошо известна и изучена многими ведущими специалистами, работающими в области численных методов [14—17]. Обязательным моментом также является экспериментальное исследование свойств и поведения полученных реализаций, для чего, как правило, используются различные коллекции тестовых задач [8; 18—20]. Такие коллекции содержат модельные примеры, принадлежащие к различным классам, и имеющие некоторые характерные особенности, позволяющие выявить сильные и слабые стороны того или иного метода. Такой подход позволяет проверить не только корректность работы алгоритмов, но и облегчает выявление проблемных участков программного кода, что даёт возможность существенно повысить их надёжность и быстродействие.

В настоящее время создано большое число различных коммерческих и открытых программных продуктов и библиотек, реализующих популярные алгоритмы локальной и глобальной оптимизации: Matlab, Maple, Mathematica, NAG, AMPL, CVX, NLopt и множество других. Но новые вызовы, которые бросают современные постановки конечномерной оптимизации большой размерности, а также бурное развитие новых архитектур вычислительной техники, заставляют искать новые, более эффективные способы и подходы ре-

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

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

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

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

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

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

3. Разработка новых оптимизационных методов и их модификаций.

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

5. Разработка методик стандартизации программного кода градиентных алгоритмов оптимизации.

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

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

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

Научная новизна результатов работы, выносимых на защиту:

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

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

3. Разработана и верифицирована методика стандартизации программного кода для CPU- и GPU-реализаций градиентных алгоритмов.

4. На основе метода Б.Т. Поляка разработана новая вычислительная технология, позволившая за счёт учёта аппаратных характеристик современных вычислительных кластеров повысить размерность решаемых задач до 1011 переменных.

5. Разработан новый GPU-ориентированный алгоритм глобальной оптимизации («Forest»).

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

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

Основные результаты работы, выносимые на защиту:

1. Новые варианты покомпонетных методов локальной оптимизации и оценки скорости их сходимости.

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

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

4. Новый алгоритм глобальной оптимизации («Forest»), эффективно использующий мощности современных GPU.

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

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

• 4-я международная конференция «Квазилинейные уравнения, обратные задачи и их приложения» (QIPA-2019), МФТИ, Долгопрудный, 3-5 декабря 2019 г.;

• Всероссийская конференция «Математические методы распознавания образов», 2019, 2015 гг;

• 62-я Всероссийская научная конференция МФТИ, Долгопрудный, 18-23 ноября 2019 г.;

• International Conference «Optimization and applications» (OPTIMA), 2011-2016, 2018 гг.;

• Международная школа-семинар «Нелинейный анализ и экстремальные задачи», 2014-2018 гг.;

• XVII Байкальская международная школа-семинар «Методы оптимизации и их приложения», с. Максимиха, Республика Бурятия, 31 июля -6 августа 2017 г.;

• Международная конференция «Дискретная оптимизация и исследование операций», Владивосток, остров Русский, 19-23 сентября 2016 г. (соавтор доклада);

• Joint ORSC/EURO International Conference 2015 on Continuous Optimization, Шанхай, Китай, 10-12 мая 2015 г. (соавтор доклада);

• 27th European Conference on Operational Research, University of Strathclyde, Глазго, Великобритания, 12-15 июля 2015 г. (соавтор доклада);

• International conference ITAS-2015, Олимпийская деревня, Сочи, 7-11 сентября 2015 г. (соавтор доклада);

• Конференция «Выпуклая оптимизация и "стохастические" приложения», ИППИ РАН, Москва, 23 декабря 2015 г.;

• Отчётная транспортная конференция, МЦНМО, Москва, 26 декабря 2015 г.;

• XX Байкальская Всероссийская конференция и Школа-семинар научной молодёжи, Иркутск - Байкал, 29 июня - 7 июля 2015 г. (соавтор пленарного доклада);

• Десятая международная азиатская школа-семинар «Проблемы оптимизации сложных систем», Кыргызская республика, 25 июля - 5 августа 2014 г. (соавтор доклада);

• Systems Dynamics and Control Processes, International Conference dedicated to the 90th Anniversary of Academician N.N. Krasovskii, Екатеринбург, 15—20 сентября 2014 г. (соавтор доклада);

• Шестая традиционная всероссийская молодёжная летняя школа «Управление, информация и оптимизация» (ИПУ РАН), дер. Григор-чиково, Московская область, 22-29 июня 2014 г.;

• The 4th International Conference on Optimization, Simulation and Control, Улан-Батор, Монголия, 1-4 июля 2013 г.;

• XV Байкальская международная школа-семинар «Методы оптимизации и их приложения», п. Листвянка, Иркутск—Байкал, 23-29 июня 2011 г.;

• 4-я, 6-я Международная научная конференция «Параллельные вычислительные технологии (ПаВТ)», 2010, 2012 гг.;

• 11-я, 13-я Всероссийская конференция молодых учёных по математическому моделированию и информационным технологиям, 2010, 2012 гг.

Результаты работы также докладывались и обсуждались на научных семинарах академика Ю.Г. Евтушенко (ФИЦ ИУ, Москва), академика Б.Н. Четверушкина (ФИЦ ИПМ РАН, Москва), академика К.В. Рудакова

(ФИЦ ИУ, Москва), чл.-корр. А.В. Двуреченского (ИФП СО РАН, Новосибирск) , проф. А.П. Афанасьева (ИППИ РАН, Москва), проф. М.Г. Дмитриева (ИСА РАН, Москва), семинарах ИММ УРо РАН (Екатеринбург) и ИВТ СО РАН (Новосибирск).

Результаты, представленные в диссертационной работе, использовались для выполнения работ по проекту Министерства образования и науки РФ «Разработка архитектуры, принципов построения и программного обеспечения суперкомпьютерной информационно-аналитической платформы прикладного моделирования, прогнозирования и экспертиз транспортных процессов и систем в виде сетевой компьютерной лаборатории» (2015-2016 гг., руководитель: академик Б.Н. Четверушкин, ИПМ РАН), проектам РФФИ 2-07-31118 мол_а (2012-2013 гг, руководитель: А.С. Аникин), 18-31-20005 (2018-2020 гг, руководитель: Гасников А.В. МФТИ), 18-29-03071 (2018-2020 гг, Нурминский Е.А. ДВФУ), 18-07-00587 (2018-2019 гг, Горнов А.Ю., ИД-СТУ СО РАН), 17-07-00627 (2017-2019 гг, Зароднюк Т.С., ИДСТУ СО РАН), 16-07-00664 (2016 г, руководитель: А.Н. Андрианов, ИПМ РАН), 15-07-03827 (2015-2016 гг, руководитель: А.Ю. Горнов, ИДСТУ СО РАН), 13-01-00470 (2013-2015 гг, руководитель: А.Н. Андрианов, ИПМ РАН), 10-01-00595 (20102012 гг, руководитель: А.Н. Андрианов, ИПМ РАН), интеграционным проектам СО РАН №43 (2011 г, руководитель: чл.-корр. РАН А.В. Двуреченский, ИФП СО РАН) и №83 (2012 г, руководитель: чл.-корр. РАН А.В. Двуреченский, ИФП СО РАН), а также проекту «Traffic matrix estimation» (2015 г., договор между МФТИ и компанией Huawei Russia).

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

Публикации.

Основные результаты по теме диссертации изложены в 57 печатных изданиях, 13 из которых опубликованы в журналах из перечня Web of Science/Scopus/ВАК ([21—33]) , 40 - в тезисах докладов.

Объем и структура работы. Диссертация изложена на 180 страницах и состоит из введения, четырёх глав и заключения. Работа содержит 37 рисунков, 18 таблиц и 121 наименование списка литературы.

Глава 1

Основные трудности современных задач

оптимизации

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

1.1. Размерность задачи

Характерной особенностью многих современных задач оптимизации является большая размерность. Очевидно, что размерности решаемых задач всегда росли вслед за развитием теории оптимизации и увеличением мощности доступных вычислительных систем. При этом под «большой» размерностью уместно понимать совершенно разные величины — всё зависит от класса рассматриваемой задачи и её свойств. Если для многих задач глобальной оптимизации число переменных более 100 уже воспринимается как серьёзное испытание, то для подавляющего большинства задач локальной оптимизации это число является совершенно незначительным. Конечно, бывают и исключения — например, Ю.Е. Нестеровым предложено семейство тестовых унимодальных функций которые обладают настолько «неудобными» свойствами, что нахождение экстремума с требуемыми параметрами (требуется найти т.н. аргументное решение) уже при размерности порядка 10-20 переменных становится весьма нетривиальной задачей для большинства распространённых методов оптимизации. К счастью, на практике такая ситуация возникает достаточно редко, поэтому подобные постановки можно считать

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

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

Можно по-разному классифицировать задачи локальной оптимизации по их размерности, но в данной работе мы будем придерживаться варианта, предложенного Ю.Е. Нестеровым (см., например, [34]):

• Small-size — 100-102 оптимизируемых переменных;

• Medium-size — 103-104 оптимизируемых переменных;

• Large-scale — 105-107 оптимизируемых переменных;

• Huge-scale — 108-1012 оптимизируемых переменных.

Требуемый размер памяти для хранения вектора оптимизируемых переменных (при использовании чисел с плавающей точкой одинарной и двойной точности) представлен в таблице 1.1. Из неё следует, что задачи с размерностями до 108-109 переменных, в принципе, вполне можно решать без использования суперкомпьютерной техники, пусть и с потенциально большими временными затратами. Задачи же c более высокими размерностями уже в обязательном порядке требуют использования высокопроизводительных вычислительных систем хотя бы по причине необходимых объёмов оперативной памяти. Это обстоятельство накладывает свои ограничения на возможность

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

На первый взгляд могут возникнуть некоторые сомнения в существовании задач с размерностями класса Huge-scale, но современное состояние исследований во многих прикладных областях достаточно естественным образом даёт подобные постановки. К таким областям стоит отнести анализ современных сетей передачи данных, оптимизация больших атомно-молекулярных кластеров (кристаллов), современные транспортные задачи, задачи машинного обучения, задачи ранжирования интернет-страниц и т.п.

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

Список литературы диссертационного исследования кандидат наук Аникин Антон Сергеевич, 2020 год

Литература

1. Nesterov Y. Introductory Lectures on Convex Optimization. Vol. 87. — Boston, MA : Springer US, 2004. — (Applied Optimization).

2. Ben-Tal A., Nemirovski A. Lectures on Modern Convex Optimization. — 2013. — 590 p.

3. Поляк Б. Т. Введение в оптимизацию. — М. : Наука, 1983. — 384 с.

4. Bertsekas D. P. Convex Optimization Theory. — Athena Scientific, 2009. — 256 p.

5. Bertsekas D. P. Convex Optimization Algorithms. — Athena Scientific, 2015. — 576 p.

6. Boyd S. P., Vandenberghe L. Convex optimization. — Cambridge University Press, 2010. — 716 p.

7. Bubeck S. Convex Optimization: Algorithms and Complexity. — 2015. — arXiv: 1405.4980.

8. Sun W., Yuan Y.-X. Optimization Theory and Methods. Nonlinear Programming. — Springer Science & Business Media, 2006. — 688 p.

9. Жиглявский А. А., Жилинскас А. Г. Методы поиска глобального экстремума. — М. : Наука, 1991. — 248 с.

10. Zhigljavsky A., Zilinskas A. Stochastic global optimization. — Springer, 2008. — 262 p.

11. Шарый С. П. Конечномерный интервальный анализ. — 2015. — URL: http://www.nsc.ru/interval/Library/InteBooks/SharyBook.pdf.

13. Евтушенко Ю. Г., Посыпкин М. А. Применение метода неравномерных покрытий для глобальной оптимизации частично целочисленных нелинейных задач // Журнал вычислительной математики и математической физики. — 2011. — т. 51, № 8. — с. 1376—1389.

14. Форсайт Д., Малькольм М., Моулер К. Машинные методы математических вычислений. — М. : Мир, 1980. — 277 с.

15. Деннис Д. м., Шнабель Р. Б. Численные методы безусловной оптимизации и решения нелинейных уравнений. — М. : Мир, 1988. — 440 с.

16. Engeln-Mullges G., Uhlig F. Numerical algorithms with C. — Springer, 1996. — 596 p.

17. Numerical recipes. The art of scientific computing / W. H. Press [et al.]. — Third edit. — Cambridge University Press, 2007. — 1262 p.

18. Handbook of Test Problems in Local and Global Optimization. Vol. 33 / C. A. Floudas [et al.]. — Boston, MA : Springer US, 1999. — (Nonconvex Optimization and Its Applications).

19. Molga M., Smutnicki C. Test functions for optimization needs. — 2005. —URL: http://www.robertmarks.org/Classes/ENGR5358/ Papers/functions.pdf.

20. Andrei N. An unconstrained optimization test functions collection // Adv. Model. Optim. —2008. — Vol. 10, no. 1. — P. 147-161. — URL: http://nasport.pmf.ni.ac.rs/materijali/2271/v10a10.pdf.

21. Anikin A., Dorn Y., Nesterov Y. Computational Methods for the Stable Dynamic Model // Optimization and Applications. Vol. 1145 / ed. by M. Jacimovic [et al.]. — Cham : Springer International Publishing, 2020. — P. 280-294. — (Communications in Computer and Information Science).

22. Sorokovikov P., Gornov A., Anikin A. Computational Technology for the Study of Atomic-Molecular Morse Clusters of Extremely Large Dimensions // IOP Conference Series: Materials Science and Engineering. — 2020. — Jan. — Vol. 734, 012092.

23. Methane Hydrate Emergence from Lake Baikal: Direct Observations, Modelling, and Hydrate Footprints in Seasonal Ice Cover / N. G. Granin [et al.] // Scientific Reports. — 2019. — Dec. 18. — Vol. 9, 19361.

24. A universal modification of the linear coupling method / S. Guminov [et al.] // Optimization Methods and Software. — 2019. — Vol. 34, no. 3. — P. 560-577.

25. A global optimization algorithm for solving a four-person game / S. Bat-bileg [et al.] // Optimization Letters. — 2019. — Vol. 13, no. 3. — P. 587-596.

26. Local Algorithms for Minimizing the Force Field for 3D Representation of Macromolecules / P. A. Yakovlev [et al.] // Computational Mathematics and Mathematical Physics. — 2019. — Dec. 1. — Vol. 59, no. 12. — P. 1994-2008.

27. Kuz'menko V., Gornov A., Anikin A. Estimation of Mathematical Models Accuracy for Calculation of LDL-Cholesterol Concentration // (Vth International Workshop "Critical Infrastructures: Contingency Management, Intelligent, Agent-Based, Cloud Computing and Cyber Security" (IWCI 2018)). — Atlantis Press, 2018. — P. 111-116.

28. Dual Approaches to the Minimization of Strongly Convex Functionals with a Simple Structure under Affine Constraints / A. S. Anikin [et al.] // Computational Mathematics and Mathematical Physics. — 2017. — Aug. 1. — Vol. 57, no. 8. — P. 1262-1276.

29. Numerical solution of huge-scale quasiseparable optimization problems / A. N. Andrianov [et al.] // Lobachevskii Journal of Mathematics. — 2017. — Vol. 38, no. 5. — P. 870-873.

30. Global Optimization Reduction of Generalized Malfatti's Problem / R. Enkhbat [et al.] // Numerical Algebra, Control & Optimization. — 2017. — Vol. 7, no. 2. — P. 211.

32. Аникин А. С., Гасников А. В., Горнов А. Ю. О неускоренных эффективных методах решения разреженных задач квадратичной оптимизации // Труды МФТИ. — 2016. — т. 8, № 2. — с. 44—59.

33. Эффективные численные методы решения задачи PageRank для дважды разреженных матриц / А. С. Аникин [и др.] // Труды МФТИ. — 2015. — т. 7, № 4. — с. 74—94.

34. Nesterov Y. Subgradient methods for huge-scale optimization problems // Mathematical Programming. — 2014. — Vol. 146, no. 1/2. — P. 275-297.

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

36. Антонов А. С. Параллельное программирование с использованием технологии OpenMP. — М. : Изд-во МГУ, 2009. — 77 с.

37. T0P500 Supercomputer Sites. — URL: http://www.top500.org.

38. Антонов А. С. Параллельное программирование с использованием технологии MPI. — М. : Изд-во МГУ, 2004. — 72 с.

39. Wilt N. The CUDA Handbook: A Comprehensive Guide to GPU Programming. — Pearson Education, 2013. — 528 p.

40. The cuBLAS library: a GPU-accelerated version of the complete standard BLAS library. — URL: http://docs.nvidia.com/cuda/cublas.

41. The cuSPARSE library: a collection of a GPU-accelerated basic linear algebra subroutines used for sparse matrices. — URL: http : / / docs . nvidia.com/cuda/cusparse.

42. Sadrozinski H. F.-W., Wu J. Applications of Field-Programmable Gate Arrays in Scientific Research. — Taylor & Francis, 2010. — 167 p.

43. SAT@home. — URL: http://sat.isa.ru/pdsat.

44. BOINC: Open-source software for volunteer computing. — URL: https : //boinc.berkeley.edu.

46. CMake: an open-source, cross-platform family of tools designed to build, test and package software. — URL: https://cmake.org.

47. Eigen: C++ template library for linear algebra. — URL: http://eigen. tuxfamily.org.

48. C++ Format: Small, safe and fast formatting library for C++. — URL: http://fmtlib.net.

49. The Boost Graph Library (BGL). — URL: http://www.boost.org/doc/ libs/1_60_0/libs/graph/doc.

50. Nocedal J., Wright S. J. Numerical optimization. — 2nd ed. — New York : Springer, 2006. — 664 p. — (Springer series in operations research).

51. Писсанецки С. Технология разреженных матриц. — М. : Мир, 1988. — 410 с.

52. Канторович Л. В. О проведении численных и аналитических вычислений на машинах с программным управлением // Известия АН АрмССР, сер. физ.-мат. наук. — 1957. — т. X, № 2. — с. 3—16.

53. Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции : в 1,2. — М. : Мир, 1978.

54. Евтушенко Ю. Г. Оптимизация и быстрое автоматическое дифференцирование. — ВЦ Им. А. А. Дородницына РАН, 2013. — 144 с. — URL: http://www.ccas.rU/personal/evtush/p/198.pdf.

55. Иванов В. В. Методы вычислений на ЭВМ. — Киев : Наукова думка, 1986. — 584 с.

56. Antoniou A., Lu W.-S. One-dimensional optimization // Practical optimization: Algorithms and engineering applications. — Springer, 2007. — P. 81-117.

57. Кропотов Д. А. Методы одномерной оптимизации : Курс «Методы оптимизации в машинном обучении». — 2012. — URL: http://www. machinelearning.ru/wiki/images/a/a8/MOMO12_min1d.pdf.

58. Hestenes M. R., Stiefel E. Methods of Conjugate Gradients for Solving Linear Systems // Journal of Research of the National Bureau of Standards. — 1952. — Vol. 49, no. 6. — P. 409-436.

59. Fletcher R., Reeves C. M. Function minimization by conjugate gradients // The Computer Journal. — 1964. — Vol. 7, no. 2. — P. 149154.

60. Поляк Б. Т. Метод сопряжённых градиентов в задачах на экстремум // Ж. вычисл. матем. и матем. физ. — 1969. — т. 9, № 4. — с. 807—821.

61. Polak E., Ribiere G. Note sur la convergence de methodes de directions conjuguees // Francaise d'Informatique et de Recherche Operationnelle. — 1969. — No. 16. — P. 35-43.

62. Powell M. J. D. Restart procedures for the conjugate gradient method // Mathematical programming. — 1977. — Vol. 12, no. 1. — P. 241-254.

63. Neumaier A. On convergence and restart conditions for a nonlinear conjugate gradient method. — 1997. — Institut fur Mathematik, Universitat Wien, preprint.

64. Dai Y.-H., Liao L.-Z., Li D. On restart procedures for the conjugate gradient method // Numerical Algorithms. — 2004. — Vol. 35, no. 24. — P. 249-260.

65. Andrei N. Open Problems in Nonlinear Conjugate Gradient Algorithms for Unconstrained Optimization // Bulletin of the Malaysian Mathematical Sciences Society. — 2011. — Vol. 34, no. 2. — URL: http : //math.usm.my/bulletin/pdf/v34n2/v34n2p11.pdf.

66. Andrei N. 40 Conjugate gradient algorithms for unconstrianed optimization. A survey on their definition // ICI Technical Report. — 2008. — No. 13. — P. 1-13.

67. Andrei N. Another Conjugate Gradient Algorithm with Guaranteed Descent and Conjugacy Conditions for Large-scale Unconstrained Optimization // Journal of Optimization Theory and Applications. — 2013. — Vol. 159, no. 1. — P. 159-182.

68. Andrei N. A new three-term conjugate gradient algorithm for unconstrained optimization // Numerical Algorithms. — 2015. — Vol. 68, no. 2. — P. 305-321.

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

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

71. Nesterov Y. Gradient methods for minimizing composite functions // Mathematical Programming. — 2012. — Vol. 140, no. 1. — P. 125-161.

72. Nesterov Y. Smooth minimization of non-smooth functions // Mathematical Programming. — 2005. — Vol. 103, no. 1. — P. 127-152.

73. Гасников А. В., Нестеров Ю. Е. Универсальный метод для задач стохастической композитной оптимизации. — 2016. — arXiv: 1411.4218.

74. Barzilai J., Borwein J. M. Two-Point Step Size Gradient Methods // IMA Journal of Numerical Analysis. — 1988. — Vol. 8. — P. 141-148.

75. Dai Y.-H., Liao L.-Z. R-linear convergence of the Barzilai and Borwein gradient method // IMA Journal of Numerical Analysis. — 2002. — Vol. 22, no. 1. — P. 1-10.

76. Fletcher R. On the Barzilai-Borwein method // Optimization and Control with Applications. — Springer Science & Business Media, 2005. — P. 235-256.

77. Raydan M., Svaiter B. F. Relaxed steepest descent and Cauchy-Barzilai-Borwein method // Computational Optimization and Applications. — 2002. — Vol. 21, no. 2. — P. 155-167.

78. The cyclic Barzilai-Borwein method for unconstrained optimization / Y. H. Dai [et al.] // IMA Journal of Numerical Analysis. — 2006. — Vol. 26, no. 3. — P. 604-627.

79. Huang Y., Liu H., Zhou S. An efficient monotone projected Barzi-lai-Borwein method for nonnegative matrix factorization // Applied Mathematics Letters. — 2015. — Vol. 45. — P. 12-17.

80. Sopyla K., Drozda P. Stochastic Gradient Descent with Barzilai-Borwein update step for SVM // Information Sciences. — 2015. — Vol. 316. — P. 218-233.

81. Zhang H., Hager W. W. PACBB: A projected adaptive cyclic Barzilai-Borwein method for box constrained optimization // Multiscale Optimization Methods and Applications. — Springer Science & Business Media, 2006. — P. 387-392.

82. Xiao Y., Hu Q. Subspace Barzilai-Borwein Gradient Method for Large-Scale Bound Constrained Optimization // Applied Mathematics and Optimization. — 2008. — Vol. 58, no. 2. — P. 275-290.

83. Поляк Б. Т. Минимизация негладких функционалов // Журнал вычислительной математики и вычислительной физики. — 1969. — т. 9, № 3. — с. 509—521.

84. Brin S., Page L. The Anatomy of a Large-scale Hypertextual Web Search Engine // Comput. Netw. ISDN Syst. — 1998. — Vol. 30, no. 1-7. — P. 107-117.

85. Langville A. N., Meyer C. D. Google's PageRank and Beyond: The Science of Search Engine Rankings. — Princeton University Press, 2006.

86. Гасников А. В., Двуреченский П. Е., Нестеров Ю. Е. Стохастические градиентные методы с неточным оракулом // Труды МФТИ. — 2016. — т. 8, № 1. — arXiv: 1411.4218. — (в печати).

87. Introduction to algorithms / T. H. Cormen [et al.]. — 3rd ed. — MIT Press, 2009. — 1292 p.

88. Гасников А., Дмитриев Д. Об эффективных рандомизированных алгоритмах поиска вектора PageRank // Журнал вычислительной математики и математической физики. — 2015. — т. 55, № 3. — с. 355—371.

89. Frank M., Wolfe P. An algorithm for quadratic programming // Naval research logistics quarterly. — 1956. — Vol. 3, no. 1/2. — P. 95-110.

90. Jaggi M. Revisiting Frank-Wolfe: Projection-free sparse convex optimization // (30th International Conference on Machine Learning). — Atlanta, Georgia, USA, 2013. — URL: https : //sites . google . com/site/ frankwolfegreedytutorial.

91. Harchaoui Z., Juditsky A., Nemirovski A. Conditional gradient algorithms for norm- regularized smooth convex optimization // Math. Program. Ser. B. — 2015. — URL: http : //www2 . isye . gatech . edu/ ~nemirovs/ccg_revised_apr02.pdf.

92. Nesterov Y. Complexity bounds for primal-dual methods minimizing the model of objective function // CORE Discussion Papers. — 2015.

93. Nesterov Y. Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems // SIAM Journal on Optimization. — 2012. — Vol. 22. — P. 341-362.

94. Hooke R., Jeeves T. A. "Direct Search" Solution of Numerical and Statistical Problems // Journal of the ACM (JACM). — 1961. — Vol. 8, no. 2. — P. 212-229.

95. Lewis R. M., Torczon V., Trosset M. W. Direct search methods: then and now // Journal of computational and Applied Mathematics. — 2000. — Vol. 124, no. 1. — P. 191-207.

96. Гасников А. В., Двуреченский П., Усманова И. О нетривиальности быстрых (ускоренных) рандомизированных методов // Труды МФТИ. — 2016. — т. 8, № 2. — с. 67—100.

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

98. Lin H., Mairal J., Harchaoui Z. Catalyst Acceleration for First-Order Convex Optimization: From Theory to Practice // Journal of Machine Learning Research. — 2017. — Vol. 18.

99. Гасников А. В. Современные численные методы оптимизации. Метод универсального градиентного спуска: учебное пособие. — МФТИ, 2018. — 166 с.

100. Wales D. J., Doye J. P. K. Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms // The Journal of Physical Chemistry A. — 1997. — Vol. 101, no. 28. — P. 5111-5116.

101. Li Z., Scheraga H. A. Monte Carlo-minimization approach to the multiple-minima problem in protein folding // Proceedings of the National Academy of Sciences of the United States of America. — 1987. — Vol. 84, no. 19. — P. 6611-6615.

102. White R. P., Mayne H. R. An investigation of two approaches to basin hopping minimization for atomic and molecular clusters // Chemical Physics Letters. — 1998. — Vol. 289, no. 5/6. — P. 463-468.

103. Iwamatsu M., Okabe Y. Basin hopping with occasional jumping // Chemical Physics Letters. — 2004. — Vol. 399, no. 4-6. — P. 396-400.

104. Multicanonical basin hopping: a new global optimization method for complex systems / L. Zhan [et al.] // The Journal of Chemical Physics. — 2004. — Vol. 120, no. 12. — P. 5536-5542.

105. Sheffi Y. Urban transportation networks: Equilibrium analysis with mathematical programming methods. — Prentice Hall, 1985.

106. Patriksson M. The Traffic Assignment Problem: Models and Methods. — Dover Publications, 2015.

107. Transportation Network Test Problems. — URL: https://github.com/ bstabler/TransportationNetworks.

108. The NVIDIA Graph Analytics library (nvGRAPH). — URL: https : // developer.nvidia.com/nvgraph.

110. Modern efficient numerical approaches to regularized regression problems in application to traffic demands matrix calculation from link loads / A. Anikin [et al.] // Proceedings of International conference ITAS-2015. — Olympic Village, Sochi, Russia, 2015. — arXiv: 1508.00858.

111. Назин А. В., Поляк Б. Т. Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с применением к задаче PageRank // Автоматика и телемеханика. — 2011. — № 2. — с. 131—141.

112. Juditsky A., Polyak B. Robust eigenvector of a stochastic matrix with application to PageRank // Proceedings of the IEEE Conference on Decision and Control. — 2012. — P. 3171-3176.

113. Hastie T. J., Tibshirani R. J., Friedman J. H. The elements of statistical learning : data mining, inference, and prediction. — New York : Springer, 2009. — (Springer series in statistics).

114. Stanford Large Network Dataset Collection, Web graphs. — URL: http: //snap.stanford.edu/data/#web.

115. Связывание электронных состояний в многослойных напряжённых ге-тероструктурах Ge/Si с квантовыми точками 2-го типа / А. И. Якимов [и др.] // Письма в ЖЭТФ. — 2006. — т. 83, № 4. — с. 189—194.

116. Excitons in charged Ge/Si type-II quantum dots / A. I. Yakimov [et al.] // Semiconductor Science and Technology. — 2000. — Vol. 15, no. 12. — P. 1125-1130.

117. Keating P. N. Effect of invariance requirements on the elastic strain energy of crystals with application to the diamond structure // Physical Review. — 1966. — Vol. 145, no. 2. — P. 637-645.

118. Doye J. P. K., Wales D. J. Structural consequences of the range of the interatomic potential: A menagerie of clusters // Journal of the Chemical Society, Faraday Transactions. — 1997. — P. 4233-4243.

120. Feng Y., Cheng L., Liu H. Putative Global Minimum Structures of Morse Clusters as a Function of the Range of the Potential: 161 < N < 240 // The Journal of Physical Chemistry A. — 2009. — Vol. 113, no. 49. — P. 13651-13655.

121. Marques J. M. C, Pais A. A. C. C, Abreu P. E. On the use of bigbang method to generate low-energy structures of atomic clusters modeled with pair potentials of different ranges // Journal of Computational Chemistry. — 2012. — Vol. 33, no. 4. — P. 442-452.

Список рисунков

2.1. Устройство FPGA семейства Altera Arria 10.............46

3.1. CSR-формат хранения разреженной матрицы........................60

3.2. Бинарное вычислительное дерево длины п............................64

3.3. Бинарное вычислительное дерево длины 9............................64

3.4. Бинарное вычислительное дерево длины 9, хранящее пары «значение-индекс»....................................................65

3.5. Иллюстрация спуска методом сопряжённых градиентов в варианте Ю.Е. Нестерова........................................................80

3.6. Сходимость метода Barzilai-Borwein..................................81

3.7. Обмен данными между CPU и GPU, вариант 1......................86

3.8. Обмен данными между CPU и GPU, вариант 2......................86

3.9. Изменение зоны поиска метода MSBH................105

3.10. Поиск решения для многоэкстремальной функции методом MSBH 106

3.11. Асинхронная работа локальных спусков..............109

3.12. Синхронная работа локальных спусков...............109

3.13. Синхронная работа локальных спусков в методе Forest.......109

4.1. BPR-функция.............................113

4.2. Оптимизация транспортной модели Anaheim............117

4.3. Оптимизация транспортной модели Austin..............120

4.4. Оптимизация транспортной модели Barcelona............120

4.5. Оптимизация транспортной модели Berlin-Center..........121

4.6. Оптимизация транспортной модели Berlin-Friedrichshain......121

4.7. Оптимизация транспортной модели Berlin-Mitte-Center.......122

4.8. Оптимизация транспортной модели Berlin-Mitte-Prenzlauerberg-Friedrichshain-Center...........122

4.9. Оптимизация транспортной модели Berlin-Prenzlauerberg-Center . . 123

4.10. Оптимизация транспортной модели Berlin-Tiergarten........123

4.11. Оптимизация транспортной модели Birmingham-England......124

4.12. Оптимизация транспортной модели Chicago-Sketch.........124

4.13. Оптимизация транспортной модели GoldCoast...........125

4.14. Оптимизация транспортной модели Philadelphia..........125

4.15. Оптимизация транспортной модели SiouxFalls...........126

4.16. Оптимизация транспортной модели Sydney.............126

4.17. Оптимизация транспортной модели Winnipeg............127

4.18. Восстановление матрицы корреспонденций, сеть содержит 1000 узлов; (sumQLLA > 90%).......................133

4.19. Восстановление матрицы корреспонденций, сеть содержит 1000 узлов; (QLLA > 90%).........................133

4.20. Восстановление матрицы корреспонденций, сеть содержит 3000 узлов; (sumQLLA > 90%).......................134

4.21. Восстановление матрицы корреспонденций, сеть содержит 3000 узлов; (QLLA > 90%).........................134

4.22. Восстановление матрицы корреспонденций, сеть содержит 5000 узлов; (sumQLLA > 90%) ..............................................135

4.23. Восстановление матрицы корреспонденций, сеть содержит 5000 узлов; (QLLA > 90%) ..................................................135

4.24. Восстановление матрицы корреспонденций, сеть содержит 10000 узлов; (sumQLLA > 90%) ............................................136

4.25. Восстановление матрицы корреспонденций, сеть содержит 10000 узлов; (QLLA > 90%) ................................................136

4.26. Решение задачи PageRank, А — диагональная, п = 106, rid = 101 . 140

4.27. Решение задачи PageRank, А — случайная, п = 107, s = 51 .... 143

4.28. Решение задачи web-NotreDame...................144

4.29. Решение задачи web-BerkStan....................144

4.30. Задача Stanford, сходимость CPU-GPU методов..........145

4.31. Задача NotreDame, сходимость CPU-GPU методов.........146

4.32. Задача BerkStan, сходимость CPU-GPU методов..........146

4.33. Задача Google, сходимость CPU-GPU методов...........147

4.34. Вид квантовой точки Ge/Si.....................149

4.35. Потенциал Морса при разных значениях параметра р.......154

4.36. Вид кластеров (240 атомов) после оптимизации..........156

4.37. Время, затраченное на работу алгоритма в зависимости от размерности задачи. 1 - сепарабельная функция, 2 - несепарабельная функция...............................160

Список таблиц

1.1. Размер (ОЗУ) п-элементного вектора................................19

3.1. СРИ-СРИ функции БЬЛБ-модуля программного комплекса ЫОр1 . 69

3.2. СРИ-функции БЬЛБ-модуля программного комплекса ЫОр1 .... 70

4.1. Характеристики тестовых постановок транспортных сетей.....118

4.2. Время оптимизации тестовых постановок транспортных сетей ... 119

4.3. Восстановление матрицы корреспонденций для постановок различной размерности...........................132

4.4. Характеристики матрицы А, построенной по базам Стэнфордского университета ..........................................................138

4.5. Время (сек.) решения задачи Ра§еКапк, А — диагональная.....141

4.6. Время (сек.) решения задачи Ра§еЯапк, А — случайная.......142

4.7. Время (сек.) решения задачи Ра§еЯапк для шеЬ-графов.......143

4.8. Стоимость итерации для задач с шеЬ-графами............143

4.9. Задача Ра§еЯапк, время минимизации СРИ-СРИ методами, сек . . 145

4.10. Потенциал Китинга, п = 192000, метод сопряжённых градиентов . 150

4.11. п = 192000, модификации метода сопряженных градиентов .... 151

4.12. Метод сопряжённых градиентов (Флетчер-Ривс)..........152

4.13. Оптимизация потенциала Морса, 20-146 атомов..........155

4.14. Оптимизация потенциала Морса, 150-240 атомов..........155

4.15. Оптимизация потенциала Морса, 240 атомов............156

4.16. Оптимизация потенциала Морса, 241-250 атомов..........157

4.17. Время (сек.), затраченное на работу алгоритма в зависимости от размерности тестовой сепарабельной функции ......................159

4.18. Время (сек.), затраченное на работу алгоритма в зависимости от размерности тестовой несепарабельной функции ....................161