Модели и параллельные алгоритмы решения задач глобальной оптимизации с частично целочисленными переменными тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Лебедев Илья Генадьевич

• Лебедев Илья Генадьевич
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Лебедев Илья Генадьевич

ВВЕДЕНИЕ

1. ОБЩАЯ ХАРАКТЕРИСТИКА ПРОБЛЕМ ВЫБОРА ОПТИМАЛЬНЫХ РЕШЕНИЙ

1.1. Модель процесса выбора оптимального варианта

1.2. Постановка задачи глобальной оптимизации

1.3. Обзор методов решения задач оптимизации

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

1.5. Выводы

2. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ С НЕПРЕРЫВНЫМИ И ЧАСТИЧНО ЦЕЛОЧИСЛЕННЫМИ ПЕРЕМЕННЫМИ

2.1. Редукция к стандартной задаче

2.2. Базовый алгоритм глобального поиска

2.3. Индексный метода учета ограничений

2.4. Сведение многомерной задачи оптимизации к семейству одномерных задач

2.5. Решение задач с частично целочисленными переменными

2.6. Выводы

3. ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ

3.1. Параллельный алгоритм для вычислительных систем с общей памятью

3.2. Теоретические оценки ускорения параллельного алгоритма

3.3. Использование ускорителей вычислений

3.4. Параллельные алгоритмы для кластерных систем с распределенной памятью

3.5. Выводы

4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РАЗРАБОТАННЫХ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ

4.1. Общая характеристика исследовательской библиотеки

4.2. Высокоуровневая архитектура библиотеки

4.3. Особенности программной реализации разработанных алгоритмов

4.4. Использование исследовательской библиотеки

2

4.5. Выводы

5. ЭКСПЕРИМЕНТАЛЬНАЯ АПРОБАЦИЯ РАЗРАБОТАННОГО ПОДХОДА К ПОИСКУ ГЛОБАЛЬНО-ОПТИМАЛЬНЫХ РЕШЕНИЙ

5.1. Критерии оценки эффективности методов глобальной оптимизации82

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

5.3. Решение прикладных задач глобальной оптимизации

5.4. Выводы

ЗАКЛЮЧЕНИЕ

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

Приложение 1. Копии свидетельств о государственной регистрации программ для ЭВМ

Приложение 2. Копии документов о внедрении результатов диссертационной работы

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

ВВЕДЕНИЕ

Актуальность исследования. Проблема выбора наилучшего решения из множества возможных вариантов [86, 92] возникает во многих областях науки и техники, при исследовании различных объектов, процессов, явлений. Одна из основных моделей процесса выбора наилучшего решения - задача оптимизации (максимизации или минимизации) некоторой функции при ограничениях типа неравенств. При этом сложность исследуемых процессов выражается в том, что их характеристики не обладают свойством линейности или выпуклости, что соответствует многоэкстремальности целевой функции и ограничений и приводит к задачам глобальной оптимизации.

Типичным примером задач глобальной оптимизации являются задачи идентификации значений параметров математических моделей по экспериментальным данным в различных прикладных областях [49, 50, 51, 88, 91, 97, 144]. Ключевым свойством таких задач является сложность вычисления значений функций, т.к. вид функций обычно является неизвестным, а вычисление их значений связано с численным моделированием оптимизируемого объекта или процесса. В таком случае говорят о задачах с функциями вида «черный ящик».

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

В последнее время большую популярность получили эвристические алгоритмы, которые, так или иначе, основаны на идеях случайного поиска [15, 29, 83, 93, 95, 108, 123]. В силу своей вероятностной природы и простоты реализации алгоритмы подобного типа хорошо распараллеливаются, но при этом обеспечивают сходимость к глобально-оптимальному решению только при проведении достаточно большого числа итераций [17, 27, 43, 47].

Принципиально другим классом методов являются детерминированные алгоритмы. Для этих методов возможность достоверной оценки глобального оптимума основана на наличии априорных предположений о решаемой задаче, позволяющих связать значение функции в некоторой точке с ранее вычисленными известными значениями. Типичным предположением о свойствах решаемой задачи является липшицевость функций, входящих в ее постановку. В этом случае говорят о классе задач липшицевой оптимизации. Фундаментальные результаты в области разработки методов липшицевой оптимизации были получены в работах С.А. Пи-явского [125], Ю.Г. Евтушенко [20, 100, 101, 102], Р.Г. Стронгина [63, 135, 140], Я.Д. Сергеева [58, 132], В.П. Гергеля [33, 90], М.А. Посыпкина [18, 99, 128]. Д. Джонса (D. Jones) [44, 45], Я. Пинтера (J. Pinter) [55], А. Жилинскаса (A. Zilinskas) [66], Ю. Жилинскаса (J. Zilinskas) [53, 54].

Особый интерес представляют задачи, в которых часть переменных может принимать значения только из заранее заданного конечного множества. С формальной точки зрения такие задачи не являются задачами липшицевой оптимизации, и для них требуется разработка особых подходов к оценке оптимума. Различные способы решения задач со смешанными переменными описаны во многих публикациях (см., например, работы [6, 7, 21]). При этом широко известные методы решения задач данного класса ориентированы лишь на линейные [78] или выпуклые [40] задачи. Детерминированные алгоритмы решения невыпуклых задач с частично целочисленными переменными, основанные на идеях метода ветвей и границ, были предложены в работах Ю.Г. Евтушенко и М.А. Посыпкина [98, 99]. Одновременно с этим, во многих работах задачи указанного класса предлагается решать с помощью метаэвристических алгоритмов [14, 46, 52].

Данная диссертационная работа посвящена развитию параллельных алгоритмов решения задач глобальной оптимизации с частично целочисленными переменными в рамках информационно-статистического подхода, предложенного Р.Г. Стронгиным [63, 140] и обобщенного для широкого класса задач условной [62, 139] и многокритериальной [89, 120] оптимизации.

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

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

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

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

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

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

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

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

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

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

Соответствие паспорту специальности. Параллельные алгоритмы решения задач глобальной оптимизации с частично целочисленными переменными были разработаны на основе исследования системных связей между исходной задачей и эквивалентным ей множеством связанных задач непрерывной оптимизации, что соответствует п. 3-5 паспорта специальности 2.3.1 «Системный анализ, управление и обработка информации, статистика»: «Разработка критериев и моделей описания и оценки эффективности решения задач системного анализа, оптимизации, управления, принятия решений, обработки информации и искусственного интеллекта», «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений, обработки информации и искусственного интеллекта», «Разработка специального математического и алгоритмического обеспечения систем анализа, оптимизации, управления, принятия решений, обработки информации и искусственного интеллекта».

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

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

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

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

алгоритма в зависимости от свойств вычислительной системы и обеспечивает

7

возможность эффективного поиска оптимальных значений параметров в прикладных задачах (соответствует области исследований п. 5 паспорта специальности).

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

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

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

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

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

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

также решением вычислительно-трудоемких прикладных оптимизационных задач.

8

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

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

• в [2, 3, 30, 31, 37, 38, 48, 81, 116] - модель принятия оптимальных решений, метод хранения данных, последовательная и параллельная реализации алгоритма решения задач глобальной оптимизации с частично целочисленными переменными, анализ результатов вычислительных экспериментов, вывод следствий;

• в [32, 64, 118] - модель распараллеливания вычислений и реализованные на ее основе параллельные алгоритмы решения задач глобальной оптимизации;

• в [112, 113, 114, 115] - реализация параллельного алгоритма решения задач многомерной глобальной оптимизации.

Публикации по теме работы. По материалам диссертации опубликованы 16 работ, из них 8 статей индексируются в международных библиографических базах Web of Science и Scopus, 2 работы опубликованы в изданиях, рекомендованных ВАК РФ , 4 свидетельства на программы для ЭВМ.

Апробация и внедрение работы. Результаты диссертационной работы использовались при выполнении грантов Российского научного фонда (№ 16-1110150, 21-11-00204), Российского фонда фундаментальных исследований (19-079

00242), а также Министерства науки и высшего образования РФ (проект № 07292020-0055) и научно-образовательного математического центра «Математика технологий будущего» (проект № 075-02-2021-1394).

Результаты работы используются в учебном процессе Нижегородского государственного университета им. Н.И. Лобачевского. Разработанная в рамках диссертационного исследования библиотека Globalizer используется в Институте нефтехимии и катализа (что подтверждается актами внедрения). На разработанное программное обеспечение получены свидетельства о регистрации программ для ЭВМ.

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

• международная конференция «Parallel Computing Technologies», Н. Новгород, 2017.

• международная конференция «Математическое моделирование и суперкомпьютерные технологии», Н. Новгород, 2021.

• международная конференция «Суперкомпьютерные дни в России», Москва, 2017 - 2020, 2022.

• всероссийская научная конференция «Параллельные вычислительные технологии», Санкт-Петербург, 2023.

Структура и объем работы. Диссертационная работа состоит из введения, 5 глав, заключения и списка литературы из 147 наименований. Общий объём работы - 145 страниц.

1. ОБЩАЯ ХАРАКТЕРИСТИКА ПРОБЛЕМ ВЫБОРА ОПТИМАЛЬНЫХ РЕШЕНИЙ

К числу наиболее распространенных математических моделей процессов выбора оптимальных решений относятся задачи поиска глобального минимума (максимума) некоторой функций при дополнительных ограничениях. Эти задачи возникают в различных прикладных областях исследований. Примерами могут служить задачи оптимизации при молекулярном моделировании для разработки лекарств (докинге) [122, 130], при проектировании систем виброзащиты/виброизоляции зданий [76, 77, 75], и др. Одной из характерных областей возникновения задач глобальной оптимизации является подбор значений параметров математических моделей по экспериментальным данным [88, 97, 144]. Задачи поиска оптимума возникают и во многих других областях науки и техники (см., например, [56]).

Теорию и методы поиска наименьших значений функций нескольких переменных с учётом определённых ограничений на эти переменные изучают как отдельный раздел математики — математическое программирование. ([23, 24, 87, 107, 140]).

Пусть требуется найти глобальный минимум целевой функции ф(у), которая зависит от вектора переменных у = (у±,у2Ум). Значения целевой функции ф(у) соответствуют значениям критерия качества в конкретной прикладной задаче. Будем предполагать, что в задаче присутствуют ограничения, формулируемые в виде условий принадлежности вектора у к допустимой области Q с . Способ задания допустимой области заключается в указании возможного диапазона изменения переменных и дополнительных ограничений типа неравенств, т.е.

Q = {уеИ: д; (у) < 0, !<]< т], Э = {а1<у1<Ь1, 1<К Ы}.

В некоторых прикладных задачах ограничения записываются и в виде равенств. Не ограничивая общности, в рамках диссертационного исследования будут рассматриваться только ограничения-неравенства, т.к. любое равенство д(у) = 0 может быть формально выражено как система из двух неравенств д(у) < 0 и

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

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

у* = а^шт [<р(уУ у Е £} на основе конечного числа результатов испытаний = ф{у1\ 1 < I < к, в точках УiЕQ.

Процесс поиска наилучшего варианта подразумевает последовательное проведение поисковых испытаний в точках у1, 1 < / < к. При этом выбор точки для следующего испытания ук+1 осуществляется после обработки результатов, полученных на предыдущих итерациях. Отметим, что в некоторых задачах допустимая область Q может быть пустой, что является следствием слишком жестких ограничений на возможные значения вектора переменных. Установление данного факта (т.е. ситуации, когда первоначальная формулировка задачи должна быть изменена и процесс решения должен быть повторен), также можно рассматривать как решение задачи.

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

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

ф(у*, и*) = шт{у(у, и), у ей, и е и, д] (у) < 0, 1<] <т], (1.1)

И ={уЕЯм: а1<у1<Ъ1, 1 < I < Ы}. (1.2)

Методы решения подобных задач и будут рассматриваться в диссертационной работе.

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

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

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

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

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

• Разработка примеров проблемно-ориентированных программных модулей на основе реализованной библиотеки.

1.1. Модель процесса выбора оптимального варианта

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

у = (у, и) = (уг,... , yN; ult... , им) (1. 3)

и набором характеристик

w(^y) = (w±(у),... , wm+t(^у)>), (1.4)

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

Предполагается, что координаты вектора у = (yt,... ,yN) могут непрерывно изменяться в заданном гиперинтервале

D = [уе Rn : CLJ < yj < bj, 1<j< N], (1. 5)

определяемом векторами а и b

а = (at,... , aN), b = (bt,... , bN). (1. 6)

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

U = Ut X ... X UM

где Ui = [иц,... , uik}, 1<i<M.

Разрешенные сочетания и е U описываются путем задания отображения

и: t^U, 1<t<S, (1. 7)

сопоставляющего номеру т допустимый кортеж и(т) е U (т.е. все допустимые сочетания дискретных параметров перенумерованы числами т от 1 до S).

Каждая характеристика объекта Wi(y,и(т)), 1 < i < m, при фиксированном номере т, 1 < т < S, является липшицевой функцией с соответствующей константой Липшица KiT, которая заранее не известна.

Среди всех характеристик объекта выделяется одна (будем считать, что это

характеристика с номером m + 1), которую нужно улучшить - критерий

14

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

щ(у) , 1<Кт. (1.8)

Наборы у = {у, и(т)^), 1 < т < 5, удовлетворяющие условиям (1.8) называются допустимыми. Вводя обозначения

в1 (У, *) = п^у, и(т)) , 1<Кт, (1.9)

условия (1.8) можно записать в эквивалентной форме

д1 (у, т) < 0,1 < I < т. (1.10)

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

ш1п{дт+1 (у, т), у ей, те Б, д{ (у, т) < 0,1<1<т}, (1.11)

Э ={уЕЯм: а1<у1<Ъ1, 1 < I < Ы}, 1<т<5. (1.12)

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

ш[п{дт+1 (у), у ей, д{ (у) < 0,1<Кт}, (1.13)

И ={уЕЯм: а1<у1<Ъ1, 1 < I < Ы}. (1.14)

Известно множество методов решения задач в постановке (1.13) [58, 63, 94, 102, 105, 132, 137, 139, 140]. В соответствии со свойствами методов их можно разделить на локальные и глобальные. Локальные методы сходятся к одному из локальных минимумов целевой функции; в частном случае этот минимум будет являться также и глобальным. Методы глобальной оптимизации ориентированы на поиск глобального минимума в многоэкстремальных задачах.

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

английском языке слово «programming» обозначает планирование и составление планов. Термин «линейное программирование» был предложен Данцигом в 1949 году для изучения теоретических и алгоритмических проблем оптимизации линейных функций с линейными ограничениями.

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

Задачи выпуклого программирования включают определение минимума выпуклой функции (или максимума вогнутой) на выпуклом замкнутом множестве. Эти задачи являются наиболее изученными среди задач нелинейного программирования. Подкласс задач выпуклого программирования, где целевая функция является квадратичной, а ограничения — линейными, называется квадратичным программированием. В многоэкстремальных задачах возможность достоверной оценки глобального оптимума принципиально основана на наличии априорной информации о функции. Весьма часто такая информация о решаемой задаче представляется в виде предположения, что функции задачи удовлетворяют условию Липшица ([55, 132, 146]) с априори неизвестными константами Li, 1 < i < т. При этом целевая функция может быть задана реализованным программно алгоритмом вычисления ее значений в точках области поиска. Подобные задачи широко распространены в приложениях (задачи оптимального проектирования интегральных схем, задачи идентификации моделей по данным наблюдений в научных исследованиях, оптимизация процессов управления и т.п.).

Для решения задач нелинейного программирования известен ряд методов,

которые можно классифицировать по различным признакам (по числу критериев и

ограничений, размерности задачи, по типу информации, используемой в алгоритме

поиска экстремума, и т.п.). Однако ни один метод нелинейного программирования

16

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

1.2. Постановка задачи глобальной оптимизации

В данном разделе рассмотрим важный частный случай задачи (1.1) - задачу многомерной многоэкстремальной оптимизации с непрерывными переменными. Такую задачу можно записать в виде

<Р(У*) = min[^(y), у е D, gt (у) < 0,1 <i< т}, (1. ^

D = [aj < у; < bj, 1<j<N, yi е R]. (1.16)

Будем предполагать, что целевая функция ф(у) (обозначаемая в дальнейшем также дт+1 (у)) и ограничения gt (у), 1 < i < т., удовлетворяют условию Липшица \gi (У1) - 9i (У2 )\ < Ц\у1 - у2\\, 1<i<m + 1, (1.17)

с априори неизвестными константами Li, 1 < i < т. + 1, и могут быть многоэкстремальными. Предполагается также, что функции gt (у) определены и вычислимы только в точках у е D удовлетворяющих условиям

Список литературы диссертационного исследования кандидат наук Лебедев Илья Генадьевич, 2024 год

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

1. Arora, R.K. Optimization: Algorithms and Applications. [Text] / R.K. Arora. -CRC Press, 2015. - 466 p.

2. Barkalov, K.A. On Solving the Problem of Finding Kinetic Parameters of Catalytic Isomerization of the Pentane-Hexane Fraction Using a Parallel Global Search Algorithm [Text] / K.A. Barkalov, I.M. Gubaydullin, E.A. Kozinov, I.G. Lebedev, R.I. Faskhutdinova, A.G. Faskhutdinov, L.V. Enikeeva// Mathematics. - 2022. - № 19. - V. 10. - P. 3665.

3. Barkalov, K.A. Parallel Global Search Algorithm with Local Tuning for Solving Mixed-Integer Global Optimization Problems [Text] / K.A Barkalov, I.G. Lebedev, V.P. Gergely // Lobachevskii Journal of Mathematics. - 2021. - № 42. - V. 7. - P. 1492-1503.

4. Bastrakov, S. High Performance Computing in Biomedical Applications. [Text] / S. Bastrakov, I. Meyerov, V. Gergel, A. Gonoskov, A. Gorshkov, E. Efimenko, M. Ivanchenko, M. Kirillin, A. Malova, G. Osipov, V. Petrov, I. Surmin, A. Vildemanov // Procedia Computer Science. - 2013. - V. 18. - P. 10-19.

5. Bazaraa, M.S. Nonlinear Programming: Theory and Algorithms. [Text] / M.S. Bazaraa, H.D. Sherali, C.M. Shetty. - John Wiley and Sons, 2006. - 872 p.

6. Boukouvala, F. Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO [Text] / F. Bou-kouvala, R. Misener, C.A. Floudas // Eur. J. Oper. Res. - 2016. - V. 252. - P. 701-727.

7. Burer, S. Non-convex mixed-integer nonlinear programming: a survey [Text] / S. Burer, A.N. Letchford // Surv. Oper. Res. Manage. Sci. - 2012. - V. 17. - P. 97-106.

8. Cao, P. Multiscale Modeling of Isobutane Alkylation with Mixed C4 Olefins Using Sulfuric Acid as Catalyst [Text] / P. Cao, L. Zheng, W. Sun, L. Zhao, // Industrial & Engineering Chemistry Research. - 2019. - V.58 (16). - P. 6340 - 6349.

9. Censor, Y. Parallel optimization: Theory, algorithms, and applications. [Text] / Y. Censor, S.A Zenios. - Oxford University Press, 1998. - P. 576.

10. Chainikova, E.M. Interplay of Conformational and Chemical Transformations

of Ortho-Substituted Aromatic Nitroso Oxides: Experimental and Theoretical Study

123

[Text] / E.M. Chainikova, A.R. Yusupova, S.L. Khursan, A.N. Teregulova, A.N. Lobov, M.F. Abdullin, L.V. Enikeeva, I.M. Gubaydullin, R.L. Safiullin // The Journal of Organic Chemistry. - 2017. - V. 82 (15) - P. 7750-7763.

11. Chiandussi, G. Comparison of multi-objective optimization methodologies for engineering applications. [Text] / G. Chiandussi, M. Codegone, S.Ferrero, F.E. Varesio // Computers and Mathematics with Applications. - 2012. - V. 63(5). - P. 912-942.

12. Chih-Chung Chang. LIBSVM: a library for support vector machines [Text] / Chih-Chung Chang, Chih-Jen Lin // ACM Transactions on Intelligent Systems and Technology. - 2011. - V. 2. - No. 27. - P. 1-27.

13. Ciegis, R. Parallel Scientific Computing and Optimization: Advances and Applications. [Text] / R. Ciegis, D. Henty, B. Kagström, J. Zilinskas, (eds.). - New York: Springer. - 2009. - 274 p.

14. Deep, K. A real coded genetic algorithm for solving integer and mixed integer optimization problems [Text] / K. Deep, K. P. Singh, M.L. Kansal, C. Mohan //Appl. Math. Comput. - 2009. - V.212(2). - P. 505-518.

15. Eiben, A.E. Introduction to evolutionary computing [Text] / A.E. Eiben, J.E. Smith. - Berlin: Springer. - 2015. - 287 p.

16. Enikeeva, L. Parallel Gravitational Search Algorithm in Solving the Inverse Problem of Chemical Kinetics [Text] / L. Enikeeva, M. Marchenko, D. Smirnov, I. Gubaydullin // Communications in Computer and Information Science. - 2020. - V. 1331. - P. 98-109.

17. Erick Cantu-Paz. Goldberg Efficient parallel genetic algorithms: theory and practice [Text] / Erick Cantu-Paz, David E. // Computer Methods in Applied Mechanics and Engineering. - 2000. - V. 186 (2-4). - P. 221-238.

18. Evtushenko, Y. A deterministic approach to global box-constrained optimization [Text] / Y. Evtushenko, M. Posypkin // Optimization letters. - 2013. - V. 7(4). - P. 819-829.

19. Evtushenko, Yu.G. Method of non-uniform coverages to solve the multicriteria optimization problems with guaranteed accuracy. [Text] / Yu.G. Evtushenko, M.A. Posypkin // Automation and Remote Control. - 2014. - V. 75(6). - P. 1025-1040.

124

20. Evtushenko, Yu.G. Numerical methods for global optimization [Text] / Yu.G. Evtushenko, M.A. Potapov, V.V. Korotkikh // In: C.A. Floudas, P.M. Pardalos (Eds.) Recent advances in global optimization. - Princeton: Princeton University Press, 1992. -P. 274-297.

21. Fan, N. A mixed integer programming approach for optimal power grid intentional islanding / N. Fan, D. Izraelevitz, F. Pan, P. M. Pardalos, J. Wang // Energy Systems. - 2012. - V. 3 - p. 77-93.

22. Flach P.A., Precision-Recall-Gain Curves: PR Analysis Done Right / P.A. Flach, M. Kull. // - Advances in Neural Information Processing Systems 28 - Vol. 1. -2015. - P. 838-846. [Web page]. Available at: https://papers.nips.cc/paper/5867-preci-sion-recall-gain-curves-pr-analysis-done-right (accessed December 07, 2015)

23. Floudas, C.A State of the Art in Global Optimization [Text] / C.A. Floudas, P.M. Pardalos. Kluwer Academic Publishers, Dordrecht - 1996. 651 p.

24. Floudas, C.A. Encyclopedia of Optimization [Text] / C.A. Floudas, P.M. Pardalos. Kluwer Academic Publishers, Dordrecht - 2001. - 4646 p.

25. Floudas, C.A. Handbook of test problems in local and global optimization [Text]. / C.A. Floudas, P.M. Pardalos. - Springer. 1999. - 442 p.

26. Gablonsky, J.M. A Locally-Biased Form of the DIRECT Algorithm [Text] / J.M. Gablonsky, C.T. Kelley // Journal of Global Optimization. - 2001. - V. 21(1). - P. 27-37.

27. Gabriel, L. Parallel Genetic Algorithms: Theory and Real World Applications [Text] / L. Gabriel, A. Enrique. - Springer. 2011. - 184 p.

28. Gaviano, M. Software for generation of classes of test functions with known local and global minima for global optimization [Text] / M. Gaviano, D. Lera, D. E. Kvasov, Y. D. Sergeyev // ACM Transactions on Mathematical Software. - 2003 - V. 29. - P. 469-480.

29. Gendreau, M. Handbook of metaheuristics [Text] / M. Gendreau, J. Y. Potvin (Eds.). - New York: Springer. - 2010. - 648 p.

30. Gergel, V. A Flexible Generator of Constrained Global Optimization Test Problems [Text] / V. Gergel, K. Barkalov, I. Lebedev, M. Rachinskaya, A. Sysoyev // AIP Conference Proceedings. - 2019. - V. 2070. - art. no. 020009.

31. Gergel, V. A global optimization algorithm for non-convex mixed-integer problems [Text] / V. Gergel, K. Barkalov, I. Lebedev // Lecture Notes in Computer Science. - 2018 - V. 11353. - P. 78-81.

32. Gergel, V. Heterogeneous Parallel Computations for Solving Global Optimization Problems. [Text]/ V. Gergel, I. Lebedev // Procedia Computer Science. - 2015. - V. 66. - P. 53-62.

33. Gergel, V.P. A global optimization algorithm for multivariate functions with lipschitzian first derivatives [Text] / V.P. Gergel // Journal of Global Optimization. -1997. - V. 10(3). - P. 257-281.

34. Gergel, V.P. A novel supercomputer software system for solving time-consuming global optimization problems [Text] / V.P. Gergel, K.A. Barkalov, A.V. Sysoyev // Numerical Algebra, Control & Optimization. - 2018 - V. 8(1). - P. 47-62.

35. Gergel, V.P. Efficient multicriterial optimization based on intensive reuse of search information. [Text] / V.P. Gergel, E.A. Kozinov // Journal of Global Optimization. - 2018. - V. 71(1). - P. 73-90.

36. Grinkina, T. (2021). HakAtom, Analysis and forecasting of the state of power transformers of nuclear power plants. Kaggle. [Web page]. Available at: https://kaggle.com/competitions/transformer (accessed January 21, 2021)

37. Gubaydullin, I. Kinetic Modeling of Isobutane Alkylation with Mixed C4 Olefins and Sulfuric Acid as a Catalyst Using the Asynchronous Global Optimization Algorithm [Text] / I. Gubaydullin, L. Enikeeva, K. Barkalov, I. Lebedev, D. Silenko // Communications in Computer and Information Science. - 2022. - V. 1618. - P. 293-306.

38. Gubaydullin, I. Parallel Global Search Algorithm for Optimization of the Kinetic Parameters of Chemical Reactions [Text] / I. Gubaydullin, L. Enikeeva, K. Barkalov, I. Lebedev // Communications in Computer and Information Science. - 2022. - V. 1510 - P. 198-211.

39. Haykin, S. Neural Networks: A Comprehensive Foundation (2nd ed.) [Text] / S. Haykin. - Prentice Hall, 1998. - 842 p.

40. Hendrych, D. Convex mixed-integer optimization with Frank-Wolfe methods / D. Hendrych, H. Troppens, M. Besançon, S. Pokutta // - 2023. [Web page]. Available at: https://arxiv.org/abs/2208.11010 (accessed March 22, 2023)

41. Hooke, R. «Direct Search» Solution of Numerical and Statistical Problems [Text] / R. Hooke, T.A. Jeeves, // Journal of the ACM. - 1961. - V. 8 (2). - P. 212-229.

42. International Exascale Software Project [Web page]. Available at: http://www.exascale.org (accessed July 10, 2020)

43. Janaki Ram 1 D. Subramaniam Parallel Simulated Annealing Algorithms [Text] / D. Janaki Ram 1, T.H. Sreenivas, K. Ganapathy // Journal of Parallel and Distributed Computing. - 1996. - V. 37(2). - P. 207-212.

44. Jones, D.R. Lipschitzian optimization without the Lipschitz constant [Text] / D.R. Jones, C.D. Perttunen, B.E. Stuckman // Journal of Optimization Theory and Applications. - 1993. - V. 79, № 1 - P. 157-181.

45. Jones, D.R. The DIRECT global optimization algorithm [Text] / D.R. Jones // In: C. Floudas, P. Pardalos (Eds.). The encyclopedia of optimization. - Heidelberg: Springer, 2009. - P. 725-735.

46. Kalyanmoy Deb,. An efficient constraint handling method for genetic algorithms [Text] / D. Kalyanmoy // Computer Methods in Applied Mechanics and Engineering. - 2000. - Vol. 186(2-4). - P. 311-338.

47. Karacan, I. A Novel Parallel Simulated Annealing Methodology to Solve the No-Wait Flow Shop Scheduling Problem with Earliness and Tardiness Objectives [Text] / I. Karacan, S. Ozlem, B. Serol // Processes. - 2023. - vol. 11(2) - doi: 10.3390/pr11020454

48. Lebedev, I.G On using the decision trees to identify the local extrema in parallel global optimization algorithm [Text] / I.G. Lebedev, K.A. Barkalov, D.I. Silenko // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. -2023. - Т. 3. - №. 12. - С. 5-18.

49. Mardani, A. Multiple criteria decision-making techniques and their applications - a review of the literature from 2000 to 2014 [Text] / A. Mardani, A. Jusoh, K. Nor, Z. Khalifah, N. Zakwan, A. Valipour// Economic Research-Ekonomska Istrazivanja.

- 2015. - V. 28(1). - P. 516-571.

50. Marler, R. T. Survey of multi-objective optimization methods for engineering [Text] / R.T. Marler, J.S. Arora // Struct. Multidisciplinary Optimization. - 2004. - V. 26.

- P. 369-395.

51. Marler, T. Multi-Objective Optimization: Concepts and Methods for Engineering [Text] / T. Marler. - VDM Verlag, 2009. - P. 208.

52. Mixed Integer ga Optimization (Matlab) [Web page]. Available at: https://www.mathworks.com/help/gads/mixed-integer-optimization.html (accessed October 31, 2012)

53. Paulavicius, R. Globally-biased DISIMPL algorithm for expensive global optimization [Text] / R. Paulavicius, Y. Sergeyev, D. Kvasov, J. Zilinskas // Journal of global optimization. - 2014. - V. 59, № 2-3. - P. 545-567.

54. Paulavicius, R. Parallel branch and bound for global optimization with combination of Lipschitz bounds [Text] / R. Paulavicius, J. Zilinskas, A. Grothey // Optimization methods and software. - 2011. - V. 26, № 3. - P. 487-498.

55. Pinter, J.D. Global optimization in action: continuous and Lipschitz optimization: algorithms, implementations and applications [Text] / J.D. Pinter. - Dordrecht: Kluwer Academic Publishers, - 1996. - 480 p.

56. Pinter, J.D. Global Optimization: Scientific and Engineering Case Studies [Text] / J.D. Pinter, ed. - New York: Springer, - 2006. - 546 p.

57. Quinn, M. J. Parallel Programming in C with MPI and OpenMP [Text] / M. J. Quinn. -New York: McGraw-Hill, - 2004. - 516 p.

58. Sergeyev, Y.D. Introduction to global optimization exploiting space-filling curves [Text] / Y.D. Sergeyev, R.G. Strongin, D. Lera. - New York: Springer, 2013. -125 p.

59. Sergeyev, Y.D. Parallel Asynchronous Global Search and the Nested Optimization Scheme [Text] / Y.D. Sergeyev, V.A. Grishagin // J. Comput. Anal. Appl. - 2001

- vol. 3(2). - P. 123-145.

60. Sergeyev, Y.D. Univariate Global Optimization with Multiextremal Non-Dif-ferentiable Constraints Without Penalty Functions [Text] // Comput Optim Applic. -2006. - V. 34, - P. 229-248.

61. Sergeyev, Ya.D. Global search based on efficient diagonal partitions and a set of Lipschitz constants [Text] / Ya.D. Sergeyev, D.E. Kvasov // SIAM Journal on Optimization. - 2006. - vol. 16(3). - P. 910-937.

62. Strongin R.G. Numerical methods for multiextremal nonlinear programming problems with nonconvex constraints [Text] / / R.G. Strongin // Lecture Notes in Economics and Mathematical Systems. - 1985. - V. 255. - P. 278-282.

63. Strongin, R.G. Global Optimization with Non-convex Constraints. Sequential and Parallel Algorithms [Text] / R.G. Strongin, Ya.D. Sergeyev. - Kluwer Academic Publishers, 2000. - 704 p.

64. Sysoyev, A. Globalizer - A Parallel Software System for Solving Global Optimization Problems. [Text] / A. Sysoyev, K. Barkalov, V. Sovrasov, I. Lebedev, V. Gergel // Parallel Computing Technologies. PaCT 2017. Lecture Notes in Computer Science. -2017. - V. 10421. - P. 492-499.

65. Sysoyev, A.V. Globalizer Lite: A Software System for Solving Global Optimization Problems. [Text] / A.V. Sysoyev, A.S. Zhbanova, K.A. Barkalov, V.P. Gergel // Parallel Computational Technologies. PCT 2017. Communications in Computer and Information Science. - 2017. - V. 753. - P. 130-143.

66. Törn, A.A. Global Optimization [Text] / A.A. Törn, A. Zilinskas // Lecture Notes in Computer Science. - 1989. - V. 350.

67. Uskov, S.I. Fibrous alumina-based Ni-MOx (M = Mg, Cr, Ce) catalysts for propane pre-reforming [Text] / S.I. Uskov, D.I. Potemkin, N. Kamboj, P.V. Snytnikov, V.P. Pakharukova, L.V. Enikeeva, I.M. Gubaydullin, I. Hussainova // Materials Letters.

- 2019. - V. 257 - p. 126741

68. Uskov, S.I. Kinetics of low-temperature steam reforming of propane in a methane excess on a Ni-based catalyst [Text] / S.I. Uskov, L.V. Enikeeva, D. I. Potemkin, V. D. Belyaev, P.V. Snytnikov, I.M. Gubaidullin, V. A. Kirillov, V. A. Sobyanin // Catalysis in Industry. - 2017. - V. 9 - p. 104-109.

69. Uskov, S.I. Propane Pre-Reforming into Methane-Rich Gas over Ni Catalyst: Experiment and Kinetics Elucidation via Genetic Algorithm [Text] / S.I. Uskov, D.I. Potemkin, L.V. Enikeeva, P.V. Snytnikov, I.M. Gubaydullin, V.A. Sobyanin // Energies. -2020. - V. 13. - doi: 10.3390/en13133393.

70. Wolberg, W. Breast Cancer Wisconsin (Diagnostic) / W. Wolberg, O. Manga-sarian, N. Street, W. Street // Data Set. [Web page]. Available at: https://ar-chive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+(Diagnostic) (accessed October 31, 1995)

71. Антонов А. С. Параллельное программирование е использованием технологии ОрепМР: Учебное пособие. [Текст] / А. С. Антонов - М.: Изд-во МГУ, 2009. - 77 с.

72. Антонов, А. С. Параллельное программирование с использованием технологии MPI: Учебное пособие. [Текст] / А. С. Антонов - М.: Изд-во МГУ, 2004. -71 с.

73. Аргунова, Н.В. 3D проектирование установки получения высокооктанового компонента автомобильного бензина [Текст] / Н.В. Аргунова, Т.Н. Качалова // Вестник Казанского технологического университета. - 2013. - № 8. - С. 285-286.

74. Ахметов, С. А. Физико-химическая технология глубокой переработки нефти и газа [Текст] / С. А. Ахметов - Уфа: УГНТУ, 1997. - 279 с.

75. Баландин, Д.В. Двухкритериальные задачи оптимальной виброзащиты упругих конструкций [Текст] / Д.В. Баландин, Е.Н. Ежов, И.А. Федотов // Журнал Средневолжского математического общества. - 2018. - Т. 20. - № 2. - С. 215-224.

76. Баландин, Д.В. Оптимальное по Парето обобщенное Н2-управление и задачи виброзащиты [Текст] / Д.В. Баландин, М.М. Коган // Автоматика и телемеханика. - 2017. - №8. - C. 76-90.

77. Баландин, Д.В. Синтез систем активной виброзащиты высотных сооружений от динамических нагрузок методами интеллектуального анализа данных [Текст] / Д.В. Баландин, Л.Г. Теклина // Современные методы прикладной математики, теории управления и компьютерных технологий. Сборник трудов IX международной конференции ПМТУКТ-2016. - Воронеж: Изд-во «Научная книга». -2016. - С. 42-45.

78. Барболина, Т. Н. Полностью целочисленный метод отсечения для решения линейных условных задач оптимизации на размещениях [Текст] / Т. Н. Барболина, О. А. Емец // Ж. вычисл. матем. и матем. физ. - 2005. - Т. 45. - №2. 2. - С. 254261.

79. Баркалов, К.А. Интеграция программных комплексов Globalizer и Ansys для оптимизации процессов охлаждения капли в потоке газа. [Текст] / К.А. Баркалов, В.П. Гергель, Е.А. Козинов, С.Л. Калюлин, В.Я. Модорский, Ю.А. Лаптева // Научно-технический вестник Поволжья. - 2017. - №5. - C. 145-148.

80. Баркалов, К.А. Метод глобальной оптимизации с адаптивным порядком проверки ограничений [Текст] / К.А. Баркалов, Р.Г. Стронгин // Ж. вычисл. матем. и матем. физ. - 2002. - Т.42. - №9. - С. 1338-1350.

81. Баркалов, К.А. Реализация параллельного алгоритма поиска глобального экстремума функции на INTEL XEON PHI [Текст] / К.А. Баркалов, И.Г. Лебедев, В.В. Соврасов, А.В. Сысоев // Вычислительные методы и программирование:. -2016. - Т. 17. - № 1. - С. 101-110.

82. Барский А.Б. Параллельные процессы в вычислительных системах: планирование и организация [Текст] / А.Б. Барский. - М.: Радио и связь, - 1990. - 256 с.

83. Батищев, Д.И. Генетические алгоритмы решения экстремальных задач: Учеб. Пособие [Текст] / Под ред. Львовича Я.Е. Д.И. Батищев. - Воронеж: ВГТУ, 1995. - 64 с.

84. Бахвалов, Н.С. Численные методы [Текст] / Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. - М. Наука. - 1987. - 636 с.

85. Боресков, А.В. Параллельные вычисления на GPU. Архитектура и программная модель CUDA [Текст] / А.В. Боресков, А.А. Харламов, Н.Д. Марковский, Д.Н. Микушин. - М.: МГУ им. М.В. Ломоносова, 2015. - 336 с.

86. Васильев Ф.П. Численные методы решения экстремальных задач [Текст] / Ф.П. Васильев. - М.: Наука, 1988. - 552 с.

87. Васильев, Ф.П. Методы оптимизации [Текст] / Ф.П. Васильев. - М.: Факториал Пресс, 2002. - 824 с.

88. Гергель, В.П. Глобальная оптимизация в идентификации многосекторной модели экономики нижегородской области [Текст] / В.П. Гергель, Н.Н. Оленев, В.В. Рябов, К.А. Баркалов, С.В. Сидоров // Вестник Нижегородского государственного университета им. Н.И. Лобачевского. - 2013. - № 3(1). - С. 223-230.

89. Гергель, В.П. Методы многокритериальной оптимизации для решения задач виброзащиты [Текст] / В.П. Гергель, Е.А. Козинов, В.В. Соврасов // Проблемы прочности и пластичности. - 2018. - №80(2). - C. 281-292.

90. Гергель, В.П. Об одном способе учета значений производных при минимизации многоэкстремальных функций [Текст] / В.П. Гергель // Ж. вычисл. матем. и матем. физ. - 1996. - Т. 36, №6. - С. 51-67.

91. Гергель, В.П. Параллельные методы глобальной оптимизации в идентификации динамической балансовой нормативной модели региональной экономики [Текст] / В.П. Гергель, В.А. Горбачев, Н.Н. Оленев, В.В. Рябов, С.В. Сидоров // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. -2011. - № 25 (242). - С. 4-15.

92. Гермейер, Ю.Б. Введение в теорию исследования операций [Текст] / Ю. Б. Гермейер. - М.: Наука, 1971. - 384 с.

93. Гладков, Л.А. Генетические алгоритмы [Текст] / Л.А. Гладков, В.В. Ку-рейчик, В.М. Курейчик. - М.: ФИЗМАТЛИТ, 2006. - 320 с.

94. Городецкий, С.Ю. Нелинейное программирование и многоэкстремальная оптимизация [Текст] / С.Ю. Городецкий, В.А. Гришагин - Н. Новгород: Изд-во ННГУ, 2007. - 489 с.

95. Граничин, О.Н. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах [Текст] / О.Н. Граничин, Б.Т. Поляк - М.: Наука, 2003. - 291 с.

96. Гришагин, В.А. Операционные характеристики некоторых алгоритмов глобального поиска [Текст] / В.А. Гришагин // Проблемы случайного поиска. -Рига: Зинатне, 1978. - №. 7. - С. 198-206.

97. Губайдуллин, И.М. Применение индексного метода глобальной оптимизации при решении обратных задач химической кинетики [Текст] / И.М. Губайдуллин, В.В. Рябов, М.В. Тихонова // Вычислительные методы и программирование. -2011. - Т. 12. - №1. - С. 137-145.

98. Евтушенко, Ю. Г. Варианты метода неравномерных покрытий для глобальной оптимизации частично-целочисленных нелинейных задач [Текст] / Ю. Г. Евтушенко, М. А. Посыпкин // Доклады Академии Наук, - 2011. -Т. 437, -№ 2. - С. 168-172.

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

100. Евтушенко, Ю.Г. Метод половинных делений для глобальной оптимизации функции многих переменных [Текст] / Ю.Г. Евтушенко, В.А. Ратькин // Техническая кибернетика. - 1987. - № 1. - С. 119-127.

101. Евтушенко, Ю.Г. Параллельный поиск глобального экстремума функций многих переменных [Текст] / Ю.Г. Евтушенко, В.У. Малкова, А.А. Станевичюс // Ж. вычисл. матем. и матем. физ. - 2009. - Т. 49, №2. - С. 255-269.

102. Евтушенко, Ю.Г. Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке) [Текст] / Ю.Г. Евтушенко // Ж. вычисл. матем. и матем. физ. - 1971. - Т. 11, №6. - С. 1390-1403.

103. Ермаков, С.М. Метод Монте-Карло и смежные вопросы [Текст] / С.М. Ермаков. - М.: Наука, 1975. - 472 с.

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

105. Захарова, Е. Обзор методов многомерной оптимизации [Текст] / Е.М. Захарова, И.К. Минашина, // Информационные процессы. - 2014 - Т. 14. - № 3 - С. 256-274.

106. Измаилов, А.Ф. Численные методы оптимизации [Текст] / А.Ф. Измаилов, М.В. Солодов. - М.: ФИЗМАТЛИТ, 2008. - 320 с.

107. Карманов, В.Г. Математическое программирование [Текст] / В.Г. Карманов - М.: Физматлит, 2004. - 264 с.

108. Карпенко, А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: учебное пособие [Текст] / А.П. Карпенко. - М.: Издательство МГТУ им. Н. Э. Баумана, 2014. - 446 с.

109. Карр, Ч. Количественные методы принятия решений в управлении и экономике [Текст] / Ч. Карр, Ч. Хоув. - М.: Мир, 1964. - 464 с.

110. Климентова, Г.Ю., Маврин В.Ю. Топливные присадки для двухтактных двигателей [Текст] / Г.Ю. Климентова, В.Ю. Маврин // Вестник технологического университетаю. - 2010. - №10. - С. 323-326.

111. Корняков, К.В. Инструменты параллельного программирования в системах с общей памятью [Текст] / К.В. Корняков, И.Б. Мееров, А.А. Сиднев, А.В. Сысоев, А.В. Шишков. - Н. Новгород: Изд-во ННГУ . -2010.

112. Лебедев И.Г., Программный модуль Globalizer Adaptive для численного решения задач многомерной глобальной оптимизации на основе адаптивной схемы редукции размерности [Текст] / Баркалов К.А., Гергель В.П., Козинов Е.А., Лебедев И.Г. // Свидетельство о государственной регистрации программы для ЭВМ № 2020666472, внесена в Реестр программ для ЭВМ 10.12.2020.

113. Лебедев И.Г., Программный модуль Globalizer BMS для численного решения задач многомерной глобальной оптимизации на основе блочной многошаговой схемы [Текст] / Баркалов К.А., Лебедев И.Г., Сысоев А.В. // Свидетельство о государственной регистрации программы для ЭВМ № 2020614023, внесена в Реестр программ для ЭВМ 25.03.2020.

114. Лебедев И.Г., Программный модуль Globalizer GPU для численного решения задач многомерной глобальной оптимизации с использованием графических процессоров [Текст] / Баркалов К.А., Лебедев И.Г., Сысоев А.В. // Свидетельство о государственной регистрации программы для ЭВМ № 2020614022, внесена в Реестр программ для ЭВМ 25.03.2020.

115. Лебедев И.Г., Программный модуль Globalizer OneAPI для численного решения задач многомерной глобальной оптимизации с применением технологии Intel OneAPI [Текст] / Баркалов К.А., Козинов Е.А., Лебедев И.Г. // Свидетельство о государственной регистрации программы для ЭВМ № 2023610326, внесена в Реестр программ для ЭВМ 10.01.2023.

116. Лебедев, И.Г. Алгоритм глобальной оптимизации, использующий деревья решений для выявления локальных экстремумов [Текст] / И.Г. Лебедев, Д.И. Силенко // Проблемы информатики. - 2023. - № 2. - С. 21-33.

117. Лебедев, И.Г. Использование параллельной системы глобальной оптимизации Globalizer для решения задач конкурса GenOpt. [Текст] / И.Г. Лебедев, В.В. Соврасов // Суперкомпьютерные дни в России: Труды международной конференции (г. Москва). - М.: Изд-во МГУ. - 2016. - C. 874-886.

118. Лебедев, И.Г. Реализация параллельного алгоритма глобального поиска на GPU [Текст] / И.Г. Лебедев, К.А. Баркалов // Вестник ПНИПУ. Аэрокосмическая техника. - 2014. - № 39. - С. 64 - 82.

119. Лузин, Н. Н. Теория функций действительного переменного [Текст] / Н.Н. Лузин - Учпедгиз, -1948. - 60 c

120. Маркин, Д.Л. О равномерной оценке множества слабоэффективных точек в многоэкстремальных многокритериальных задачах оптимизации. [Текст] / Д.Л. Маркин, Р.Г. Стронгин // Ж. вычисл. матем. и матем. физ. - 1993. - №2(33). -C.195-205.

121. Мордухович Б. Ш. Методы аппроксимаций в задачах оптимизации и управления [Текст] / Б.Ш. Мордухович. - М.: Наука. - 1988. - 360 с.

122. Офёркин, И.В. Реализация поддержки параллельных вычислений в программах докинга SOLGRID и SOL [Текст] / И.В. Офёркин, А.В. Сулимов,

135

О.А. Кондакова, В.Б. Сулимов // Вычислительные методы и программирование. -2011. - Т. 12. - №1. - С. 9-23.

123. Пащенко, Ф.Ф. Введение в состоятельные методы моделирования систем [Текст] / Ф.Ф. Пащенко // Учеб. пособие: В 2-х ч. Ч. 1. Математические основы моделирования систем. Ч. 2. Идентификация нелинейных систем. -М.: Финансы и статистика. -2007.

124. Петров, Ю. П. История и философия науки [Текст] / Ю. П. Петров Математика, вычислительная техника, информатика. СПб.: БХВ-Петербург - 2005 -448 с.

125. Пиявский, С.А. Один алгоритм отыскания абсолютного экстремума функций [Текст] / С.А. Пиявский // Ж. вычисл. матем. и матем. физ. - 1972. - Т. 12. № 4. - С. 888-896.

126. Плотников, А.Д. Математическое программирование / А.Д. Плотников - Минск: Новое знание, 2006. - 171 с.

127. Поляк, Б.П. История математического программирования в СССР: анализ феномена [Текст] / Б.П. Поляк // Труды 14-й Байкальской школы-семинара «Методы оптимизации и их приложения» - 2008 -Т. 1. - С. 2-20.

128. Посыпкин, М.А. Решение задач глобальной оптимизации в среде распределенных вычислений [Текст] / М.А. Посыпкин // Программные продукты и системы. - 2010. - №1. - С. 23-29.

129. Растригин, Л.А. Адаптация сложных систем [Текст] / Л.А. Растригин. -Рига: Зинатне. - 1981. - 375 с.

130. Романов, А.Н. Компьютерный дизайн лекарственных средств: программа докинга SOL [Текст] / А.Н. Романов, Ф.В. Григорьев, А.В. Сулимов, С.В. Лущекина, Я.Б. Мартынов, В.Б. Сулимов // Вычислительные методы и программирование. - 2008. - Т. 9, № 3. - С. 213-233.

131. Сахаров, М.К. Новый адаптивный метод мультимеметической глобальной оптимизации для слабосвязанных вычислительных систем [Текст] / М.К. Сахаров // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. - 2019. - № 5. - С. 95-114.

132. Сергеев, Я.Д. Диагональные методы глобальной оптимизации [Текст] / Я.Д. Сергеев, Д.Е. Квасов - М.: Физматлит, 2008. - 352 с.

133. Смидович, Е. В. Технология переработки нефти и газа, ч. 2. [Текст] - М.: Химия, 1980. - 328 с.

134. Стронгин, Р.Г. Минимизация многоэкстремальных функций при невыпуклых ограничениях [Текст] / Р.Г. Стронгин, Д.Л. Маркин // Кибернетика. - 1986. - №4. - С. 63-69.

135. Стронгин, Р.Г. Многоэкстремальная минимизация [Текст] / Р.Г. Строн-гин // Автоматика и телемеханика. - 1970. - Т. 7. - С. 63-67.

136. Стронгин, Р.Г. О сходимости индексного алгоритма в задачах условной оптимизации с е-резервированными решениями [Текст] / Р.Г. Стронгин, К.А. Баркалов // Математические вопросы кибернетики. - 1999. - № 8. - С. 273-288.

137. Стронгин, Р.Г. Параллельные вычисления в задачах глобальной оптимизации. [Текст] / Р.Г. Стронгин, В.П. Гергель, В.А. Гришагин, К.А. Баркалов - М.: Изд-во МГУ. - 2013. - 280 с.

138. Стронгин, Р.Г. Параллельные методы решения задач глобальной оптимизации [Текст] / Р.Г. Стронгин, В.П. Гергель, К.А Баркалов // Известия высших учебных заведений. Приборостроение. - 2009 - Т. 52. № 10. - С. 25-33.

139. Стронгин, Р.Г. Поиск глобального оптимума [Текст] / Р.Г. Стронгин -М.: Знание, 1990. - 48 с.

140. Стронгин, Р.Г. Численные методы в многоэкстремальных задачах (информационно-статистические алгоритмы) [Текст] / Р.Г. Стронгин. - М.: Наука, 1978. - 240 с.

141. Схейвер, А. Теория линейного и целочисленного программирования [Текст] / А. Схейвер. - М.: Мир - 1991 - 360 с.

142. Сысоев, А.В. МР1-реализация блочной многошаговой схемы параллельного решения задач глобальной оптимизации [Текст] / А.В. Сысоев, К.А. Баркалов, В.П. Гергель, И.Г. Лебедев // Суперкомпьютерные дни в России: Труды международной конференции (г. Москва). - М.: Изд-во МГУ. - 2015 - С. 53-62.

143. Сысоев, А.В. Решение задач глобальной оптимизации на гетерогенных кластерных системах [Текст] / А.В. Сысоев, К.А. Баркалов, В.П. Гергель, И.Г. Лебедев // Суперкомпьютерные дни в России: Труды международной конференции (г. Москва). - М.: Изд-во МГУ. - 2015 - С. 411-419

144. Тихонова, М.В. Параллельная условная глобальная оптимизация при математическом моделировании кинетики химических реакций [Текст] / М.В. Тихонова, В.В. Рябов, С.И. Спивак, И.М. Губайдуллин // Вычислительные методы и программирование. - 2013. - Т. 14. № 2. - С. 262-268.

145. Химмельблау, Д. Прикладное нелинейное программирование [Текст] / Д. Химмельблау. - М.: Мир, 1975 - 536 с.

146. Черноусько, Ф. Л . Об оптимальном поиске экстремума унимодальных функций [Текст] / Ф. Л. Черноусько // Вычисл. матем. и матем. физ. -1970. -Т. 10.

- № 4. - С 922-933.

147. Шевченко, В. Н. Линейное и целочисленное линейное программирование [Текст] / В. Н. Шевченко, Н. Ю. Золотых. - Н. Новгород: Изд-во ННГУ, 2004.

- 154 с.

Приложение 1. Копии свидетельств о государственной регистрации программ для ЭВМ

1. Свидетельство о государственной регистрации программы для ЭВМ № 2020614022. Программный модуль Globalizer GPU для численного решения задач многомерной глобальной оптимизации с использованием графических процессоров / Баркалов К.А., Лебедев И.Г., Сысоев А.В. - Заявка № 2020613147 от 18.03.2020 г. Внесена в Реестр программ для ЭВМ 25.03.2020.

ШЙЖЖЖ ФВДЖРАЩШШ

СВИДЕТЕЛЬСТВО

о государственной регистрации программы для ЭВМ

№ 2020614022

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

Правообладатель: федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский Нижегородский государственный университет им. Н.И. Лобачевского» (.К11)

Авторы: Баркалов Константин Александрович (ЛС'), Лебедев Илья Генадьевич (Ш1), Сысоев Александр Владимирович (Я11)

Заявка № 2020613147

Дата поступления 18 марта 2020 Г.

Дата государственной регистрации в Реестре программ для ЭВМ 25 марта 2020 г.

Руководитель Федеральной службы по интеллектуальной собственности

Г.П- Ивяиев

2. Свидетельство о государственной регистрации программы для ЭВМ № 2020614023. Программный модуль GlobaHzer BMS для численного решения задач многомерной глобальной оптимизации на основе блочной многошаговой схемы / Баркалов К.А., Лебедев И.Г., Сысоев А.В. - Заявка № 2020613148 от 18.03.2020 г. Внесена в Реестр программ для ЭВМ 25.03.2020.

3. Свидетельство о государственной регистрации программы для ЭВМ № 2020666472. Программный модуль Globalizer Adaptive для численного решения задач многомерной глобальной оптимизации на основе адаптивной схемы редукции размерности / Баркалов К.А., Гергель В.П., Козинов Е.А., Лебедев И.Г. - Заявка № 2020665808 от 03.12.2020 г. Внесена в Реестр программ для ЭВМ 10.12.2020.

4. Свидетельство о государственной регистрации программы для ЭВМ № 2023610326. Программный модуль Globalizer OneAPI для численного решения задач многомерной глобальной оптимизации с применением технологии Intel OneAPI [Текст] / Баркалов К.А., Козинов Е.А., Лебедев И.Г. Заявка № 2022686137 от 26.12.2022 г. Внесена в Реестр программ для ЭВМ 10.01.2023.

Приложение 2. Копии документов о внедрении результатов диссертационной работы

И.С. Шепелевич

УТВЕРЖДАЮ К УФИЦ РАН

2024 г.

АКТ

о внедрении результатов диссертационного исследования Лебедева Ильи Геиадьевича «Модели и параллельные алгоритмы решения задач глобальной оптимизации с частично целочисленными переменными», представленной на соискание ученой степени кандидата технических наук

Настоящим актом Институт нефтехимии и катализа - обособленное структурное подразделение Федерального государственного бюджетного научного учреждения Уфимского федерального исследовательского центра Российской академии наук (ИНК УФИЦ РАН) подтверждает, что результаты исследований Лебедева Ильи Геиадьевича в области моделей и параллельных алгоритмов решения задач глобальной оптимизации с частично целочисленными переменными используется в Институте нефтехимии и катализа РАН для решения задач идентификации параметров химических реакций. В частности, с использованием разработанного И.Г, Лебедевым программного обеспечения проведена идентификация параметров реакций каталитического риформинга пропана и каталитического алкилирования изобутапа.

Заведующий лабораторией математической химии ИНК УФИ11 РАН, д.ф.-м.н., профессор

УТВЕРЖДАЮ

проректор по науке и инновациям

тп ■

Грязнов М.Ю. ,•§1 I 2024 г.

АКТ

внедрения результатов диссертационной работы Лебедева Ильи Генадьевича «Модели и параллельные алгоритмы решения задач глобальной оптимизации с частично

Настоящим актом федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский Нижегородский государственный университет им. Н.И. Лобачевского» подтверждает, что результаты диссертационного исследования Лебедева И.Г. «Модели и параллельные алгоритмы решения задач глобальной оптимизации с частично целочисленными переменными» были использованы при выполнении проекта Российского научного фонда № 21-11-00204 «Суперкомпьютерные вычисления для интеллектуального глобального поиска в задачах выбора наилучших решений большой вычислительной сложности». В частности, И.Г.Лебедевым разработано программное обеспечение, с помощью которого на суперкомпьютере «Лобачевский» был решен ряд задач глобальной оптимизации с частично целочисленными переменными, связанных с выбором оптимальных значений параметров сложных химических реакций.

целочисленными переменными»

Руководитель проекта, Д.Т.Н., доц.

Баркалов К.А.

УТВЕРЖДАЮ

АКТ

внедрения в учебный процесс Института информационных технологий, математики и механики Нижегородского государственного университета им. Н.И. Лобачевского результатов диссертации Лебедева И.Г. «Модели и параллельные алгоритмы решения задач глобальной оптимизации с частично

целочисленными переменными»

Мы, нижеподписавшиеся, комиссия в составе председателя - заместителя директора по учебной работе ИИТММ, Шестаковой Н.В., и членов: заведующего кафедрой Высокопроизводительных вычислений и системного программирования Института ИГММ ИНГУ, к.т.н., доцента Меерова И.Б. и доцента кафедры Высокопроизводительных вычислений и системного программирования Института ИТММ ННГУ, к.т.н. Сысоева A.B. составила настоящий акт в том, что результаты диссертационного исследования Лебедева И.Г. «Модели и параллельные алгоритмы решения задач глобальной оптимизации с частично целочисленными переменными» (научный руководитель - д.т.н., доцент Баркалов К.А.) были внедрены в учебный процесс института в 2021/2022 учебном году при преподавании курса по выбору «Модели выбора решений» (первый курс магистратуры Института ИТММ ИИГУ) и в 2022/2023 учебном году при преподавании курса «Системы поддержки принятия решений» (третий курс бакалавриата Института ИТММ ННГУ), а также были использованы при проведении научных школ по данной тематике (молодежная школа «Высокопроизводительные вычисления, оптимизация и приложения» в 2016 и 2017 гг.).

Председатель:

заместителя директора по учебно-методической работе ИИТММ

Члены комиссии:

зав. каф. ВВиСП ИИТММ, к.т.н., доцент

доцент каф. ВВиСП ИИТММ, к.т.н.