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

• Сысоев, Александр Владимирович
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Сысоев, Александр Владимирович

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. ПАРАЛЛЕЛЬНЫЕ ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА ГЛОБАЛЬНО-ОПТИМАЛЬНЫХ РЕШЕНИЙ

1.1. Математическая модель объекта глобально-оптимального выбора

1.1.1. Модель объекта

1.1.2. Функциональные ограничения

1.1.3. Частичная вычислимость функционалов задачи

1.1.4. Векторный критерий эффективности

1.1.5. Понятие оптимального решения

1.1.6. Область применимости

1.1.7. Необходимость параллельных вычислений при решении задач рационального выбора

1.2. Пример задачи. Оптимизация профиля колеса для рельсовых видов транспорта

1.2.1. Содержательная постановка задачи

1.2.2. Математическая модель

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

1.3.1. Сведение многокритериальной задачи к семейству однокритериальных задач

1.3.2. Сведение многомерной задачи к семейству одномерных задач -многошаговая схема

1.3.3. Сведение многомерной задачи к семейству одномерных задач -редукция размерности на основе кривых Пеано

1.3.4. Параллелизм на основе множественной развертки

1.3.5. Модифицированная множественная развертка

1.3.6. Характеристическая представимость методов

1.4. Информационно-статистические алгоритмы глобального поиска и параллельные вычисления

2. ИНФОРМАЦИОННО-АЛГОРИТМИЧЕСКАЯ МОДЕЛЬ ПРОЦЕССА ПАРАЛЛЕЛЬНОГО ГЛОБАЛЬНОГО ПОИСКА

2.1. Моделирование процесса параллельного глобального поиска

2.1.1. Модель объекта исследований

2.1.2. Поисковая информация и оптимизационные данные

2.1.3. Общая схема процесса глобального поиска

2.1.4. Параллельные вычисления в процессе глобального поиска

2.2. Моделирование информационного обеспечения методов параллельного

глобального поиска

2.2.1. скаляризация векторного критерия

2.2.2. Учет ограничений

2.2.3. Редукция размерности

2.2.4. Параллельные вычисления в методах глобального поиска

2.3. Моделирование информационного обеспечения процесса параллельного

глобального поиска

2.3.1. Информационная модель состояния поиска

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

2.4. Методы снижения вычислительной трудоемкости процесса глобального поиска

2.4.1. Блочное представление матрицы состояния поиска

2.4.2. Информационная поддержка решающих правил алгоритмов глобального поиска

2.4.3. Система страничной организации памяти

2.4.4. Выбор структуры хранения поисковых данных

2.4.5. Параллельные вычисления при информационном обеспечении процесса глобального поиска

2.5. Общая схема процесса параллельного глобального поиска

3. РАЗРАБОТКА ПРОГРАММНОГО КОМПЛЕКСА ПАРАЛЛЕЛЬНЫХ

ВЫЧИСЛЕНИЙ В ЗАДАЧАХ ГЛОБАЛЬНО-ОПТИМАЛЬНОГО ВЫБОРА

3.1. Принципы организации программного комплекса

3.1.1. Назначение и основные задачи

3.1.2. Высокоуровневая архитектура программного комплекса

3.1.3. Программные компоненты системного уровня

3.1.4. Программные компоненты прикладного уровня

3.1.5. Последовательный и параллельный режимы работы

3.1.6. Способы постановки задачи оптимизации

3.1.7. Использование чисел расширенной точности

3.1.8. Эффективность программного комплекса

3.1.9. Требования к аппаратному и программному окружению

3.2. Реализация программного комплекса

3.2.1. Общие принципы реализации программного комплекса

3.2.2. Системный уровень - библиотека классов

3.2.3. Принципы реализации параллельного индексного метода

3.2.4. Прикладной уровень - консольный решатель

3.2.5. Прикладной уровень - решатель в виде динамически подключаемой библиотеки

3.2.6. Прикладной уровень - решатель в виде оконного приложения

4. ОЦЕНКА ЭФФЕКТИВНОСТИ ПРОГРАММНОГО КОМПЛЕКСА

4.1. Методика применения программного комплекса

4.1.1. Создание постановки задачи в виде динамически подключаемой

библиотеки

4.1.2. Запуск консольного решателя

4.1.3. Постановка задачи в системе управления кластером Microsoft НРС Server 2008

4.1.4. Постановка задачи в GUI-решателе

4.1.5. Эффективность использования чисел расширенной точности

4.1.6. Схемы оценки ускорения при решении задач оптимизации

4.2. Решение тестовых задач

4.2.1. Примеры решения задач безусловной оптимизации

4.2.2. Пример решения задачи условной оптимизации

4.3. Решение прикладных задач

4.3.1. Задача идентификации параметров в модели экономики

4.3.2. Оптимизация профиля колеса для рельсовых видов транспорта

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

ПРИЛОЖЕНИЕ 1. АКТ ВНЕДРЕНИЯ

ПРИЛОЖЕНИЕ 2. ФРАГМЕНТЫ ИСХОДНЫХ ТЕКСТОВ ПРОГРАММНОГО

КОМПЛЕКСА

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

ВВЕДЕНИЕ

Оптимизация, понимаемая как улучшение, представлена практически во всех сферах человеческой деятельности. Производители автомобильной или авиационной техники стремятся одновременно минимизировать расход топлива, улучшить аэродинамику, повысить безопасность и комфорт, выполнить требования по нормам вредных выбросов и т.д. Разработчики процессоров в рамках достигнутых технологических норм пытаются добиться максимальной производительности при минимальном тепловыделении, а, улучшая архитектуру, сохранить совместимость с существующим системным и прикладным программным обеспечением. Компании, создающие программное обеспечение, в процессе разработки ищут баланс в «треугольнике компромиссов» (ресурсы-время-возможности) [48].

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

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

5

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

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

Достижение указанной цели предполагает решение следующих задач:

• построение математической модели объекта глобально-оптимального выбора с учетом использования параллельных вычислений для ее дальнейшего численного анализа;

• разработку информационно-алгоритмической модели процесса параллельного поиска глобально-оптимальных решений;

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

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

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

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

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

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

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

Практическая ценность работы. Исследования по теме диссертации выполнялись при поддержке Российского Фонда Фундаментальных Исследований (грант № 04-01-89002-НЕЮ_а), Совета по грантам Президента Российской Федерации (грант № МК-1536.2009.9) и Федерального агентства по науке и инновациям (ФЦП «Научные и научно-педагогические кадры инновационной России», госконтракт № 02.740.11.5018). Результаты работы использовались при реализации совместного исследовательского проекта РФФИ и Нидерландской организации по научным исследованиям (the Netherlands Organization for Scientific Research - NWO); номер проекта NWO: 047.016.014. Практическая ценность работы определяется созданием программного комплекса параллельных вычислений для решения сложных существенно многоэсктремальных многомерных задач глобально-оптимального выбора.

Разработанный программный комплекс GlobEx реализован на языке С++ в среде Microsoft Visual Studio 2005, внедрен в опытную эксплуатацию.

Научные результаты и положения диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: Международный научно-практический семинар «Высокопроизводительные вычисления на кластерных системах» (Нижний Новгород, 2005, 2007, 2011, Санкт-Петербург, 2006, Владимир, 2009), Всероссийская конференция «Научный сервис в сети Интернет» (Новороссийск, 2006), Всероссийская научно-техническая конференция «Аэрокосмическая техника, высокие технологии и инновации» (Пермь, 2008), научно-техническая конференция «Технологии Майкрософт в теории и практике программирования» (Москва, 2005, Нижний Новгород, 2006-2008), на научных конференциях и семинарах Нижегородского государственного университета.

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

Диссертационная работа состоит из введения, 4 глав, заключения, списка использованной литературы из 118 наименований и приложений. Основная часть работы изложена на 131 странице текста, содержит 34 рисунка и 6 таблиц.

1. ПАРАЛЛЕЛЬНЫЕ ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА ГЛОБАЛЬНО-ОПТИМАЛЬНЫХ РЕШЕНИЙ

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

1.1. Математическая модель объекта глобально-оптимального выбора

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

9

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

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

1.1.1. Модель объекта

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

Пусть объект исследования характеризуется набором параметров

определенных таким образом, что уменьшение значений характеристик соответствует лучшему выбору. Предполагается, что: 1. Координаты вектора у= [ух, ... могут непрерывно изменяться в

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

(1.1)

и вектор-функцией характеристик

(1.2)

а = {ах,...,аы), Ъ = (ЬХ,...,ЬМ), (1-3)

которые задают гиперинтервал

£> = [у^-.а^у^ Ъ{ , 1< /< ТУ}. (1.4)

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

и = ихх...хим, (1-5)

где Ц= {ип, ...,и1к), 1 <1<М.

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

и:т->и, 1 <т<Б, (1.6)

сопоставляющего номеру т допустимый кортеж и(т)&17 (т.е. все

допустимые сочетания дискретных параметров перенумерованы числами т от 1 до 5).

3. Каждая характеристика wi(y,u(тf), 1<1<п, 1 <г<£ является

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

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

1.1.2. Функциональные ограничения

В отношении части координатных функций wj из (1.2), номера которых определяются множеством

G = {j\,...,jm}<^{\,...,n], (1.7)

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

W/,0Jt*G. О-8)

Наборы у = {у,и(т^), 1 <t<S, удовлетворяющие условиям (1.8),

называются допустимыми. Обозначения

gi{y,t) = wji(y,u(r))-qi, 1 <i<m (1.9)

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

gi(y,r)< О, 1 <i<m. (1.10)

1.1.3. Частичная вычислимость функционалов задачи

Поскольку при нарушении некоторых неравенств (1.8) (или эквивалентных им неравенств (1.10), характеризующих нормальное функционирование объекта или нормальное протекание процесса, часть координат вектора характеристик (1.2) могут быть не определены, рассматриваемая модель задачи оптимизации допускает частичную вычислимость координат вектора характеристик. Принимается, что каждая функция g¡(y,T), \<i<m, \<t<S определена и вычислима лишь в

соответствующем множестве Q¡ (г), где

Q=A Qm(t) = {yeQi(t):gi(y,t)<о}. (1.11)

1.1.4. Векторный критерий эффективности

Часть координатных функций w{ из (1.2), номера которых определяются множеством

F = {/15...,4}c{1, ...,и}, (1.12) рассматривается как векторный критерий эффективности

f{y,T) = (j](y,T),...,fk{y,T)), (1.13)

где

/АУ,Т) = Ч;(У,и{Т))> (1Л4)

Принимается, что функции fj{y,z), 1< j < к определены и вычислимы лишь в соответствующих областях Qj(t) из (1.11).

Допускается, что на некоторую характеристику w, накладывается условие вида (1.8), т.е. требование непревышения заданного допуска qh и одновременно ставится задача рассмотрения возможности дополнительного уменьшения значения этой характеристики (т.е. она включается в векторный критерий как одна из координат). При этом множества G и F будут иметь непустое пересечение. Указанное допущение не противоречит свойству частичной вычислимости, поскольку, согласно (1.11),

1.1.5. Понятие оптимального решения

В многокритериальных задачах выбор оптимального решения представляет дополнительную сложность в связи с обычной противоречивостью критериев. Типичным подходом в этом случае является поиск эффективных (неулучшаемых, оптимальных по Парето [23]) или слабо эффективных (оптимальных по Слейтеру) решений. Точка у* е Q называется

эффективной (слабо эффективной), если не существует yeQ с /{у*)Ф f{y),

что /;0)</у(/) (//00 <//(/))■ Одним из подходов к построению

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

Елм

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

гшп(тахЯ^/Ду)),

зависящих от вектора весов Я е А, где А есть симлекс, т.е.

м

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

В работе используется другая схема оптимального выбора в рассматриваемом классе задач, основанная на предполагаемой лексикографической упорядоченности частных критериев составляющих векторный критерий (1.13), по важности: главным критерием является /}, менее важен/2, затем следуют/3,/4, ... ,/к. Оптимальный выбор определяется следующей процедурой [45, 74].

Минимизируется первый по важности критерий /} и определяется его

минимальное значение

/; = шп(тт{ф,т)-. уедт+х(т)}). (1.16)

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

определяется величина

я = & (у,т), У е : л {у,г) < £ +гг,}).

Затем назначается величина уступки е2 по второму критерию, которая вместе с первой уступкой используется для отыскания условного минимума третьего критерия и т.д. Наконец, минимизируется последний по важности критерий при условии, что значение каждого из предшествующих критериев /¡, 1<1< к не превышает соответствующей величины /* + 81. Получаемое в итого решение считается оптимальным.

Указанный оптимальный выбор для заданного набора уступок 1<г< к описывается парой (У, г*), которая является решением рекурсивной задачи:

(У,г) = аЦ5 тш ^тт }{Л(^г): ф, г) </> , \<]<к-\), (1.17)

1 <1<к.

При к= 1 векторный критерий (1.12) превращается в скалярный и оптимальный выбор сводится к решению задачи нелинейного программирования (1.16), которая, таким образом, является частным случаем рассматриваемой постановки. Необходимо отметить, что при соответствующем выборе уступок можно получить любое требуемое Парето-оптимальное решение.

1.1.6. Область применимости

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

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

Кроме того модель поддерживает смену постановок для одного и того же объекта оптимизации. Так, в процессе решения часть параметров из (1.1) может быть зафиксирована (что лишь расширяет кортеж и, не меняя модель в целом); может быть сужена область поиска (1.4); функционалы из векторного критерия эффективности могут переводиться в ограничения и наоборот, что ведет лишь к изменению пересечения множеств G и F из (1.7) и (1.12).

1.1.7. Необходимость параллельных вычислений при решении задач рационального выбора

В научных и промышленных задачах поиск глобального оптимума часто является лишь одним из этапов в работе с объектом исследований. Модель объекта может быть построена в прикладном программном комплексе (MATLAB, ANSYS, ...), обрабатываться специализированными расчетными модулями, а задачей оптимизационного компонента является встраивание в общую цепочку расчетов. При этом вычисление функционалов, описывающих объект исследования, даже в одной точке может занимать значительное время. Так, в задаче квантово-химических расчетов малых систем для одного состояния методом связанных кластеров (Coupled Cluster Singles and Doubles, CCSD) для системы из 57 атомов требуется 41 час на одном процессоре частотой 2 ГГц [54].

Численное решение поставленной в § 1.1 задачи подразумевает проведение серии испытаний в некоторых точках области поиска из (1.4) -(1.6). Каждое испытание состоит в выборе по определенному правилу следующей точки в пространстве поиска, вычислении в ней ограничений из (1.8) и критериев из (1.13), обновлении при необходимости оценки глобального оптимума и сохранении насчитанной информации для использования на следующих итерациях. Способ выбора очередной точки и

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

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

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

1.2. Пример задачи. Оптимизация профиля колеса для рельсовых видов транспорта

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

1.2.1. Содержательная постановка задачи

Рассматривается задача оптимизации профиля рельсового колеса [76, 111, 112]. Работа выполнена в рамках совместного проекта «Быстрые вычисления в глобальной оптимизации: последовательные и параллельные среды» между ННГУ и Технологическим университетом г. Делфта, Нидерланды в рамках российско-голландского сотрудничества при поддержке РФФИ и NWO (грант Netherlands Organization for Scientific Research (NWO) № 047.016.014).

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

Рис. 1.1. Траектория движения колесной пары Радиус вращения колеса в контактной точке может различаться для правого и левого колес, поскольку колесная пара смещается по рельсу (радиусы Т\ и г2 соответственно на рис. 1.2).

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

Дг(х)=г,(х)-г2(х).

1.2.2. Математическая модель

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

В качестве компонент вектора у параметров задачи оптимизации выбраны ординаты г, подвижных точек сплайна, т.е. у = [г1,...,гп], при этом

абсциссы данных точек фиксированы. В описываемой задаче число подвижных точек, а, следовательно, и число переменных N=11, границы изменения параметров [-1, 1]; минимизируется разность радиусов вращения Аг(х), а ограничения вводятся из соображений устойчивости (например, одно из ограничений наложено на максимальный угол наклона колесной пары). Таким образом, возникает задача оптимизации с числом параметров N=11, числом ограничений m = 6; целевая функция и функции ограничений -многоэкстремальные. Для иллюстрации на рис. 1.4 приведено одномерное сечение целевой функции.

Указанная задача является вычислительно-трудоемкой: проверка ограничений задачи и вычисление значения целевой функции в одной точке занимает более десяти секунд (Intel Xeon 3 ГГц) [111,112]. Результаты решения описанной задачи с использованием представляемого в работе программного комплекса изложены в § 4.3.2.

Рис. 1.4. Одномерное сечение критерия

1.3. Параллельные вычисления в методах решения

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

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

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

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

Т-* U о

поиска соответственно. В задачах дискретнои оптимизации, выпуклой минимизации может быть использован метод ветвей и границ [106]. Значительное количество методов разработано для ситуаций, когда возможно использование дополнительной информации о поведении оптимизируемых функций, так, например, в работах [15, 16, 108, 109] представлены методы, в которых предполагается, что функционалы задач дифференцируемы, а их производные удовлетворяют условию Липщица. Также активно используются эвристические алгоритмы глобальной оптимизации, такие как, например, генетические алгоритмы [95].

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

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

21

группу таких методов составляют центральные методы [34, 88, 99, 103], в которых область D разбивается на гиперинтервалы с вычислением целевой функции в их центральных точках. Также активно применяются диагональные методы [43,90,99,106], где вычисления функционалов проводятся в вершинах, соответствующих главной диагонали гиперинтервала. Известны и более сложные стратегии разбиения, например, основанные на симплексах [24, 88, 96, 99].

1.3.1. Сведение многокритериальной задачи к семейству однокритериальных задач

Семейство задач (1.18), последовательное решение которых дает оценку (1.17) оптимального варианта, может быть представлено в виде семейства скалярных задач с ограничениями, зависящих от целочисленных индексов ;ит

f* = mmminj fj(y,z), у <eD: g,(y, r)<0, \<i<m +j-\},\< j <k, (1.19) где/)из (1.4) и

gi (У> = fi-m (У у T)-fL-Zi-m>m<Í<m + J- (1 -2°)

Запись (1.20) обеспечивает представимость условия непревышения заданной уступки по частному критерию с номером /- т, как стандартного ограничения в форме (1.10). В случае т - 0 все ограничения задачи (1.19) описывают требования непревышения уступок по частным критериям.

В соответствие с лексикографической схемой последовательное решение задач при j = 1, ..., к позволяет получить оценки f*,... соответствующие оптимальному выбору (у ,е*) из (1.17). При этом уступка по у'-му частному критерию может назначаться после вычисления соответствующей оценки /*.

1.3.2. Сведение многомерной задачи к семейству одномерных задач - многошаговая схема

Решение многомерных задач оптимизации существенно затрудняется экспоненциальным ростом числа испытаний с ростом размерности, характерным не только для метода полного перебора, но и для оптимальных алгоритмов многоэкстремальной оптимизации [38, 39, 77], являющихся более экономными, чем перебор. К тому же, для этих алгоритмов характерны трудоемкие решающие правила, требующие построения оптимальных покрытий сложных многомерных областей. Как следствие, целесообразным является применение подходов, если и не уменьшающих экспоненциальный рост числа испытаний, то, по крайней мере, упрощающих решающие правила. Один из типовых подходов - редукция размерности, обсуждаемая в §§ 1.3.2-1.3.3.

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

тт<р(у)= min min <p(y„...,yN). (1.21)

yeD У1Ф1М Уы^М v '

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

<р=тт(р(у)= min у <>,), (1.22)

yeD уЛаиЬх] v j

где

min <pi+\yv...,yi,yM),l<i<N, (1.23)

<PN{yv->yN) = (р(.Ух,-,Уы), (1.24)

причем каждое вычисление значения одномерной функции (р\ух) для заданного уi предполагает минимизацию по у2 функции (р2(ух,у2) и т.д.

Выражения (1.22) - (1.24) положены в основу ряда многомерных методов оптимизации [29, 48, 49, 55].

Важно отметить, что многошаговая схема в значительной степени содействует построению параллельных алгоритмов. Так, учитывая «однородный характер» вычислений в многошаговой схеме, задаваемый формулой (1.21), она может быть естественным образом распараллелена на любом из N-1 «уровней» минимизации. Например, для отыскания минимума по параметру уи требуется выполнить определенное число испытаний, в каждом из которых вычисление функции <р\ух) есть решение задачи минимизации по у2. Все такие задачи минимизации могут решаться одновременно, каждая на своем процессоре. Как результат, при наличии р процессоров за один «такт» может быть обеспечено получение р новых точек по параметру у].

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

1.3.3. Сведение многомерной задачи к семейству одномерных задач - редукция размерности на основе кривых Пеано

Отображения, называемые кривыми {развертками) Пеано, сопоставляют любой липшицевой в гиперкубе Р функции (р{у) одномерную функцию (р{у{х)), удовлетворяющую на отрезке [0, 1] равномерному условию Гельдера с показателем 1 /М.

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

числом М {номер разбиения), которое определяет допустимую максимальную погрешность оценки каждой координаты кривой у(х) для любого заданного значения аргумента х, равную 2_(м+1). Оценки точек кривой сопоставляют равномерной с шагом Тш сетке на отрезке [0, 1] равномерную с шагом Тм

сетку в гиперкубе Р.

Кратко опишем схему редукции применительно к постановке задачи,

представленной в § 1.1.

Установим отображение области В из (1.4) с единичным гиперкубом

Р = [уеЛ": -2-'< 2"1 , 1<г<ЛА}. (1.25)

Поскольку в общем случае

тах{Ь,.-а,., 1< /< #}*тт{^-щ, 1< /< А^},

то линейное взаимно однозначное отображение гиперкуба Р на гиперинтервал £> ведет к тому, что равномерной сетке в области Р будет соответствовать неравномерная сетка в области £>. Избежать этого можно введением вспомогательного гиперкуба

Ц = [уеЛ": а,+с! , 1</<7У}. (1.26)

где

¿ = тах{бг.-аг., 1< /< Ы} (1.27)

и линейное преобразование

к(у) = с{у+ф + а)/2 (1.28)

отображает гиперкуб Р на гиперкуб Д>. При этом равномерная сетка в Р порождает равномерную сетку в Дь и, следовательно, - в £>.

Чтобы исключить из рассмотрения точки у е Д \ £) введем

дополнительное ограничение

ео(у) = шах{у-Ь„ 1< i<N}<0,y<ED0 (1.29)

и соответствующие ему области

о-30)

дополняющие (1.11), (1.15). Теперь семейство задач (1.19), (1.20) можно считать определенным в гиперкубе Р:

f* = пни min | fj (h(v), т), v е Р: gi(h(v),r)< 0, 0<i<m + j-l},l<j<k.(13l)

Непрерывное однозначное отображение ^(х) отрезка [0, 1] вещественной оси х на vV-мерный гиперкуб из (1.25) позволяет рассматривать семейство задач (1.31) в области [0, 1]

/* - minmin{/ (h(y(x)),t), х е[0,1]:

. (1.32)

g(.(/z(Xx)),r)<0, 0<i<m +j -1},\< j <к

1.3.4. Параллелизм на основе множественной развертки

Редукция многомерных задач к одномерным с помощью разверток сохраняет непрерывность и равномерную ограниченность разностей при ограниченной вариации аргумента, однако теряет часть информации о близости точек в многомерном пространстве, поскольку точка х на отрезке [0, 1] имеет два соседа, тогда как соответствующая ей точка у{х) е Р имеет

соседей по 2м направлениям. Возможный способ учета этой информации состоит в следующем [70]. Вводится гиперкуб

Р0 = \ueRN: -2Ч< ц < 3-2"1 , 1< /< ЛГ} (1.33)

с длиной ребра, равной 2, и семейство гиперкубов

Р, = {ueRN : -2"'< ц + < 3-2~] , 1< /< TV}, \<1<L, (1.34)

где гиперкуб Р!+{ получается путем сдвига гиперкуба Pt вдоль главной диагонали на шаг -2~1 по каждой координате, и для каждого гиперкуба Ph 0<1<L вводится своя развертка yi(x) типа кривой Пеано, отображающая отрезок [0, 1] на этот гиперкуб. Приближенное построение развертки у foe) для точности, соответствующей разбиению с номером М+ 1 порождает в

гиперкубе Р\ равномерную сетку с шагом 2~м по каждой координате. При этом на величину Ь накладывается ограничение Ь<М.

Поскольку гиперкуб Р из (1.25) является общей частью всех гиперкубов семейства (1.33), (1.34), т.е.

Р глР0глРхс\... глРь =Р, (1.35)

то имеют место включения

Рс{^(х):хб[0,1]},0</<Х. (1.36)

Наконец, вводя ограничение

р(и) = шах||ц|-2-1, 1< /< 7У}<0, (1.37)

можно задать гиперкуб Р как множество вида

Р = {у,(х), хе[0,1]:р{У1{х))<0}, 0</<Ь. (1.38)

В результате получаем, что каждая задача семейства (1.32) эквивалентна задачам семейства

I] = тттт{/7 (к(у>,(х)),т), х е [0,1]: р(у1(х)) <0, 0, 0</<т + у-1},0</<1

Замена одной у-й задачи семейства (1.32) набором (1.39), содержащим 1 + 1 задач, позволяет более полно отражать информацию о близости точек в многомерном пространстве. Если точки и1 =уг(х/')еР, и2 =^(х,2)еР близки в

гиперкубе Р, но соответствующие им прообразы х], х? не являются близкими на отрезке [0, 1], то найдется такое соответствие у^х), 0<t<L, что прообразы х), х,2, где у1 -у({х)\ у2 =у((х2), будут близкими на отрезке [0, 1] (см. [18]). Рассмотренная схема приведения исходной многомерной задачи к семейству одномерных называется множественной разверткой.

Задачи из набора (1.39) можно решать параллельно, используя следующую схему [70].

Итерация в точке Х[, соответствующая /-й задаче начинается с вычисления точки

и = у1 (х,)

(1.40)

и проверки условия р(и) < 0. Если условие не выполняется, то, согласно (1.38), о £ Р. При выполнении условия определяется точка

и проверяется условие g0(y)<0, нарушение которого означает, что . В случае, когда уеИ, осуществляется последовательное вычисление левых частей ограничений задачи g¡(y,т), 1 < / < т + у -1, завершающееся либо обнаружением нарушенного ограничения, либо вычислением значения частного критерия /У (у,т) .

Поскольку прообразу х( точки V из (1.40) при отображении у{(х), 0<1<Ь, т.е.

соответствуют те же самые результаты вычислений, что и для точки х/, то результат итерации в точке х/ можно интерпретировать как результат итерации в точке х(. Таким образом, итерация в точке V из (1.40) может рассматриваться как Ь+1 итерация одновременно во всех точках хп 0<1<Ь отрезка [0, 1] из (1.42). Отсюда следует, что все Ь+1 одномерных задач из (1.39) могут решаться одновременно (параллельно), используя в максимуме для каждой из них отдельный процессор, - необходимо лишь организовать взаимообмен результатов выполняемых на разных процессорах вычислений

1.3.5. Модифицированная множественная развертка

Параллелизм на основе рассмотренной в предыдущем параграфе множественной развертки ограничен условием, которое накладывает приближенное построение каждой отдельной развертки, -1+1 <= М. Это означает, что при точности построения развертки М = 10, возможно

у = /2(и)е Д

(1.41)

х^-'^МО, 1]

(1.42)

[22].

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

Рассмотрим первоначально двумерный случай. На рис. 1.5 представлены гиперкубы Ро~Р3 исходной множественной развертки для Ь = 3.

Рис. 1.5. Гиперкубы исходной множественной развертки (N=2,1 = 3) При этом левый нижний угол гиперкуба Р0 совпадает с левым нижним углом гиперкуба Р. Построим еще три множественных развертки, в каждой из которых положение базового гиперкуба Р0 выбирается так, чтобы у него с гиперкубом Р совпадал один из трех оставшихся углов. На рис. 1.6 представлена множественная развертка, в которой у базового гиперкуба Р0 и гиперкуба Р совпадают правые нижние углы. Нетрудно показать, что все четыре множественных развертки будут обладать одной и только одной общей разверткой, задаваемой в каждой из них гиперкубом

(1.43)

Рис. 1.6. Гиперкубы модифицированной множественной развертки

Таким образом, общее число разверток построенного семейства будет равно 4-4-1 = 15 для рассмотренного примера.

Дадим общее описание правила построения каждой множественной развертки для произвольного N.

Введем двоичную нумерацию множественных разверток, состоящую из разрядов:

а =(а0,...,ад,_,), а, =0,1. (1.44)

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

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

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

Р0 = [иеЯ": ~2'х-щ< ц< Ъ-2~х-щ, 1< /< ТУ} (1.45)

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

30

соответствующим переменным границы ~3-2'\.2'\ а по разрядам равным нулю границы по переменным будут -2~1..3-2~1.

Смещение же остальных гиперкубов Р\, ..., Рь в множественной развертке с номером а будет описываться вектором

/3 =(-2-/-(-1)й%...,-2-/-(-1)а-) . (1.46)

То есть по переменным, которым в двоичном номере множественной развертки соответствует единица, сдвиг будет выполняться на 2"\ а по остальным на -2'1.

Введенная в работе модифицированная множественная развертка значительно повышает потенциал использования параллелизма в процессе поиска глобально оптимума. Так уже для трехмерных задач при точности построения приближения развертки М= 10, общее число доступных разверток в семействе множественных разверток составит М - 2 - 1 = 79. В общем же случае число разверток может быть получено согласно следующему правилу.

Утверждение. Для задач размерности N при точности приближенного построения кривых Пеано М максимальное число разверток в семействе множественных разверток равно М • 2м - 1.

1.3.6. Характеристическая представимость методов

Широкий класс численных методов поиска глобального оптимума функции одной переменной может быть описан в терминах характеристической представимости, впервые введенной В.А. Гришагиным [27] и позднее обобщенной и распространенной на другие классы задач и типы алгоритмов [25,106,116]. Дадим краткое описание схемы характеристической представимости с той точки зрения, что наличие такой общей схемы формулировки методов позволяет рассматривать множество численных методов глобальной оптимизации с единых позиций, а, значит, дает возможность унифицировать их программную реализацию и

31

использовать единые подходы по распараллеливанию ко всем методам данного класса.

Согласно [26] алгоритм решения одномерной задачи глобальной оптимизации, заданной на отрезке [а, Ь], является характеристическим, если, начиная с некоторого шага к0 > 1, выбор координаты хк очередного испытания (к>к0) заключается в выполнении следующих действий:

1. Задать набор Л* = {х0,х]5... ,х7} конечного числа г/(к) + 1 точек отрезка

[а, Ь], полагая, что а^Ак,ЬеАк, все координаты предшествующих

испытаний х' еЛд.,1 <i<k, и множество Ак упорядоченно (нижним

индексом) по возрастанию координаты, т.е.

а = х0 <х, <...<xJf_l <хл =Ь. (1-47)

2. Каждому интервалу (хм,хг), 1<г<77 поставить в соответствие число

R(i), называемое характеристикой этого интервала.

3. Определить интервал (хм,х,), которому соответствует максимальная

характеристика R(t), т.е.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Сысоев, Александр Владимирович

Основные результаты диссертации состоят в следующем:

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

ЛИТЕРАТУРА

1. Алексеев В.М., Тихомиров В.М., Фомин С.В, Оптимальное управление. М.: Наука, 1979.

2. Баркалов К.А. Учет зависимости времени вычисления функционалов от точки итерации в задачах условной глобальной оптимизации // Математика и кибернетика 2003. Сборник научных статей юбилейной научно-технической конференции факультета ВМК ННГУ и НИИ ПМК. Нижний Новгород, издательство Нижегородского госуниверситета, 2003. С. 31-33.

3. Баркалов К.А. Разработка и исследование методов ускорения сходимости алгоритмов глобальной условной оптимизации // Дисс. на соискание ученой степени канд. физ.-мат. наук. 2006.

4. Баркалов К.А., Рябов В.В., Сидоров C.B., Сысоев A.B. Об опыте решения задач многоэкстремальной оптимизации на высокопроизводительных кластерных системах // Материалы XI всероссийской научно-технической конференции «Аэрокосмическая техника, высокие технологии и инновации», Пермь, 2008. С. 36-39.

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

6. Баркалов К.А., Стронгин Р.Г. Учет времени вычисления функционалов в задачах условной глобальной оптимизации // Вестник ННГУ. Математическое моделирование и оптимальное управление, Нижний Новгород: изд-во Нижегородского гос. ун-та, 2003. С. 145-161.

7. Батищев Д.И. Методы оптимального проектирования. М: Радио и связь, 1984.

8. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М. Наука, 1987.

9. Булавский В.А., Звягина P.A. Яковлева М.А. Численные методы линейного программирования. М.: Наука, 1977.

Ю.Булатов В.П. Методы погружения в задачах оптимизации. Новосибирск: Наука, 1977.

11.Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. Второе издание. - Бином, 1998.

12.Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980.

И.Виноградов Р.В., Гергель В.П., Сысоев A.B. Визуализация вычислений в процессе решения задач глобально-оптимального выбора // Материалы конференции «Технологии Microsoft в теории и практике программирования». - Нижний Новгород: Изд-во Нижегородского гос. ун-та, 2006. С. 42-45.

14.Габасов Н.С., Кириллова Ф.М. Методы оптимизации. Минск: Изд-во Белорусского ун-та, 1975.

15.Гергель В.П. Алгоритм глобального поиска с использованием производных // Динамика систем: Мезвуз. тематич. сб. науч. тр. / Под ред. Ю.И. Неймарка. - Горький: ГГУ, 1992. - С. 161-178.

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

17.Гергель В.П. Организация памяти при численном решении многомерных многоэкстремальных задач. // Оптимизация и математическое обеспечение САПР.-Горький: ГГУ, 1980,-С. 164-169.

18.Гергель В.П. Решение одного класса многомерных многоэкстремальных многокритериальных задач со сложными ограничениями // Дисс. на соискание ученой степени канд. техн. наук. 1984.

19.Гергель В.П., Стронгин Л.Г., Стронгин Р.Г. Метод окрестностей в задачах распознавания // Изд. АН СССР. Техническая кибернетика. 1987. №4. С. 14-22.

20.Гергель В.П., Стронгин Р.Г. Абсолют. Программная система для исследований и изучения методов глобальной оптимизации. Н.Новгород: Изд. Нижегород. ун-та, 1998.

21.Гергель В.П., Субботина Е.В., Сысоев A.B. Способы организации поисковой информации в программной системе параллельного решения задач глобально-оптимального выбора // Материалы конференции «Технологии Microsoft в теории и практике программирования». -Нижний Новгород: Изд-во Нижегородского гос. ун-та, 2006. С. 284-288.

22.Гергель В.П., Сысоев A.B. О реализации параллельной версии индексного метода поиска глобально-оптимальных решений в многомерных задачах оптимизации в программном комплексе «Абсолют Эксперт» // Труды всероссийской конференции «Научный сервис в сети Интернет: технологии параллельного программирования». - М.: Изд-во МГУ, 2006. С. 115-118.

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

24.Городецкий С.Ю. Многоэкстремальная оптимизация на основе триангуляции области // Вестник ННГУ. Математическое моделирование и оптимальное управление, Нижний Новгород: изд-во Нижегородского гос. ун-та, 1999, вып. 2, С. 249-269.

25.Городецкий С.Ю. Сходимость и асимптотические оценки поведения для одного класса методов поиска // Динамика систем. Динамика и управление. - Горький: ГГУ, 1984.

26.Городецкий С.Ю., Гришагин В.А. Нелинейное программирование и многоэкстремальная оптимизация: учебное пособие. Н.Новгород: Изд. Нижегород. ун-та, 2007.

27.Гришагин В.А. Об условиях сходимости для одного класса алгоритмов глобального поиска. В. сб.: Тезисы докл. III Всес. Семинара «Численные методы нелинейного программирования». - Харьков: ХГУ, 1979. С. 82-84.

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

29.Гришагин В.А. Программная реализация многошаговых алгоритмов глобального обеспечения САПР. - Горький: ГГУ, 1981. С. 150-163.

30. Демьянов В.Ф., Рубинов A.M. Приближенные методы решения экстремальных задач. JL: Изд-во Ленингр. ун-та, 1968.

31 .Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982.

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

33.Евтушенко Ю.Г., Жадан И.Г. Барьерно-проективные методы решения задач нелинейного программирования // Ж. вычисл. матем. и матем. физ., 1994, Т. 34. №5. С. 669-684.

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

35.Еремин И.И., Астафьев H.H. Введение в теорию линейного и выпуклого программирования. М. Наука, 1976.

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

37.Жилинскас А. Глобальная оптимизация. Аксиоматика статистических моделей, алгоритмы, применение. Вильнюс: Мокслас, 1988.

38. Зализняк Н.Ф., Личун A.A. Об оптимальных стратегиях поиска глобального максимума функции. - Ж. вычисл. матем. и матем. физики. 1978. №2. С. 314-321.

39. Иванов В.В. Об оптимальных алгоритмах минимизации функций некоторых классов. - Кибернетика. 1972. №4. С. 81-94.

40.Казаков А.О., Сысоев A.B. Структуры хранения данных в программной системе параллельного поиска глобально-оптимальных решений Global Expert // Материалы Девятой международной научно-практической конференции-семинара «Высокопроизводительные параллельные вычисления на кластерных системах». - Владимир, 2009. С. 196-201.

41.Канторович JI.B. Горстко А.Б. Оптимальные решения в экономике. М: Наука, 1972.

42.Карпов В.Е., Коньков К.А. Основы операционных систем. Курс лекций. Учебное пособие. М.: Интернет-университет информационных технологий. 2005.

43.Квасов Д.Е., Сергеев Я. Д. Многомерный алгоритм глобальной оптимизации на основе адаптивных диагональных кривых // Ж. вычисл. матем. и матем. физ. - 2003. - Т. 43, № 1. - С. 42-49.

44.Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. -М.: МЦНМО, 2001.

45.Маркин Д.Л., Стронгин Р.Г. Метод решения многоэкстремальных задач с невыпуклыми ограничениями, использующий априорную информацию об оценках оптимума // Ж. вычисл. матем. и матем. физ. 1987. Т.27. №1. С. 52-62.

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

47.Маюрова И.В., Стронгин Р.Г. Минимизация многоэкстремальных функций, имеющих разрывы // Ж. вычисл. матем. и матем. физ. 1984. Т.24. №12. С. 1789-1798.

48.Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. - Кибернетика. 1965. №1. С. 45-55.

49.Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. — Кибернетика. 1965. №2. С. 85-89.

50.Модель процессов MSF. Белая книга, 2003, перевод eLine Software.

51.Моисеев H.H., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.:Наука, 1978.

52.Моцкус И. Б. Многоэкстремальные задачи в проектировании. М.: Наука, 1967.

53.0ленев H.H. Параллельные вычисления для идентификации параметров в моделях экономики // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы четвертого Международного научно-практического семинара и Всероссийской молодежной школы. / Под ред. чл.-корр. РАН В.А.Сойфера, Самара, 2004. С. 204-209.

54.Отчет ННГУ по опытно-конструкторской работе по теме: «Разработка высокопроизводительного программного комплекса для квантово-механических расчетов и моделирования наноразмерных атомно-молекулярных систем и комплексов» в рамках федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2012 годы».

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

56.Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. М.: Советское радио, 1975.

57.Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. - М.: Наука, 1982.

58.Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М.: Наука, 1980.

59.Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М.:Наука, 1975.

60.Романовский И.В. Алгоритмы решения экстремальных задач. М: Наука, 1977.

61.Русинович М., Соломон Д. Внутреннее устройство Microsoft Windows: Windows Server 2003, Windows XP и Windows 2000. Мастер-класс. / Пер. с англ. - 4-е изд. - М.: Изд-во «Русская редакция»; СПб.: Питер, 2006.

62.Сидоров C.B., Сысоев A.B. Использование чисел расширенной точности в реализации индексного метода поиска глобально-оптимальных решений // Материалы пятого Международного научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерных системах». 2005. С. 208-212.

63.Соболь И.М. Численные методы Монте-Карло. - М.: Наука, 1973.

64.Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. -М.: Наука, 1981.

65.Стронгин Р.Г. Информационный метод многоэкстремальной минимизации при измерениях с помехами // Изв. АН СССР. Техническая кибернетика. - 1969. - Т. 6. - С. 118-126.

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

67.Стронгин Р.Г. О сходимости одного алгоритма поиска глобального экстремума // Изв. АН СССР. Техническая кибернетика. - 1973. - Т. 4. -С. 10-16.

68.Стронгин Р.Г. Численные методы в многоэкстремальных задачах. М.: Наука, 1978.

69.Стронгин Р.Г. Поиск глобального оптимума. М.: Знание, 1990.

70.Стронгин Р.Г. Параллельная многоэкстремальная оптимизация с использованием множества разверток // Ж. вычисл. матем. и матем. физ. 1991. Т.31. №8. С. 1173-1185.

71.Стронгин Р.Г., Баркалов К.А. Индексный метод условной глобальной оптимизации с адаптивными резервами // Проблемы теоретической кибернетики: тез. докл. XII международн. конф., М., изд-во механико-математического факультета МГУ, 1999. С. 220.

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

73.Стронгин Р.Г., Баркалов К.А. Метод глобальной оптимизации с адаптивным порядком проверки ограничений // Компьютерные науки и информационные технологии: тез. докл. международн. конф., посвященной памяти проф. A.M. Богомолова, Саратов, изд-во Саратовского ун-та, 2002. С. 68.

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

75.Стронгин Р.Г., Маркина М.В. Многоэкстремальные лексикографические задачи выбора // Всесоюзная школа-семинар. Системное моделирование процессов интенсификации общественного производства. Май 1987, Горький. Тезисы докладов. Секции 1, 2, 3. Горький: Изд-во ГГУ, 1987. С. 169-170.

76.Суперкомпьютерные технологии в науке, образовании и промышленности / под редакцией: академика В.А. Садовничего, академика Г.И. Савина, чл.-корр. РАН Вл.В. Воеводина. - М.: Изд-во Московского университета, 2009. - 232 с.

77.Сухарев А.Г. Оптимальный поиск экстремума. - М.: Изд. МГУ. 1975.

78.Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. -М.: Наука, 1986.

79.Сысоев А.В. Об одной информационно-алгоритмической модели процесса параллельного глобального поиска // Вестник ННГУ. Математическое моделирование и оптимальное управление. - Нижний Новгород: Изд-во Нижегородского гос. ун-та, 2011. Вып. 3(2). С. 304-311.

80.Сысоев А.В. О построении семейства множественных разверток на основе кривых Пеано для параллельного решения задач глобально-оптимального поиска // Известия вузов. Приборостроение. Изд-во СПбГУ ИТМО, 2011. Вып. 10. С. 100-102.

81.Таненбаум Э. Современные операционные системы. - СПб.: Питер, 2002.

82.Федоров В.В. Численные методы максимина. М., Наука, 1979.

83.Хилл Дж. Д., Гибсон Дж. И. Способ автоматической оптимизации многоэкстремальных оптимизаций // Теория самонастраивающихся систем управления. М.: Наука, 1969.

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

85.Уайлд Д.Дж. Методы поиска экстремума. М.: Наука, 1967.

86.Barkalov К.А. A global optimization technique with an adaptive order of checking for constraints: application to multidimensional problems // VI International congress on mathematical modeling: Nizhny Novgorod, University of Nizhny Novgorod, 2004. P. 68.

87.Bomze I.M., Csendes Т., Horst R., Pardalos P.M. Developments in Global Optimization // Kluwer Academic Publishers, Dordrecht, 1997.

88.Clausen J., Zilinskas A. Subdivision, sampling, and initialization strategies for simplical branch and bound in global optimization // Comput. Math. Appl. -2002. - Vol. 44, № 7. - P. 943-955.

89.Gablonsky J.M., Kelley C.T. A locally-biased form of the DIRECT algorithm // J. Global Optim. - 2001. - Vol. 21, № 1. - P. 27-37.

140

90.Gergel V.P. A global optimization algorithm for multivariate function with Lipschitzian first derivatives // J. Global Optim. - 1997. - Vol. 10, № 3. - P. 257-281.

91.Gergel V.P., Sergeev Y. D., Strongin R.G. A parallel global optimization method and its implementation on a transputer system // Optimization. - 1992. -Vol. 26.-P. 261-275.

92.Handbook of Global Optimization / Ed. by R. Horst, P.M. Pardalos. -Dordrecht: Kluwer Academic Publishers, 1995. - Vol. 1.

93.Handbook of Global Optimization / Ed. by P.M. Pardalos, H.E. Romeijn. -Dordrecht: Kluwer Academic Publishers, 2002. - Vol. 2.

94.Hill J.D. A search technique for multimodal surfaces // IEEE Trans. Systems Sci. and Cybernetics. 1969. V.5. №1. P. 2-8.

95.Holland J.H. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, 1975.

96.Horst R. On generalized bisection of N-simplices // Math. Comp. - 1997. -Vol. 66, №218,-P. 691-698.

97.Horst R., Pardalos P.M. Handbook of Global Optimization // Kluwer Academic Publishers, Dordrecht, 1995.

98.Horst R., Pardalos P.M., Thoai N.V. Introduction to Global optimization. Kluwer Academic Publishers, Dordrecht, 1995.

99.Horst R., Tuy H. Global optimization - deterministic approaches. Berlin: Springer-Verlag, 1996.

100. Jones D.R. The DIRECT global optimization algorithm // Encyclopedia of Optimization / Ed. by C.A. Floudas, P.M. Pardalos. - Dordrecht: Kluwer Academic Publishers, 2001. - Vol. 1. - P. 431-440.

101.MAPM, A Portable Arbitrary Precision Math Library in C -[http://www.tc.umn.edu/~ringx004/mapm-main.html].

102. Markine V.L., Barkalov K.A., Gergel V.P. An Optimum Design Procedure Based On Multipoint Approximations And A Global Optimisation Method //

141

6th World Congresses of Structural and Multidisciplinary Optimization, Rio de Janeiro, Brazil, 2005.

103. Meewella C.C., Mayne D.Q. Efficient domain partitioning algorithm of Lipschitz optimization of rational and Lipschitz continuous functions // J. Optim. Theory Appl. - 1989. - Vol 61, № 2. - P. 247-270.

104. Mockus J. Bayesian approach to global optimization. Kluwer Academic Publishers, Dordrecht, 1988.

105. The MPFR Library - [http://www.mpfr.org/].

106. Pinter J. Global optimization in Action. - Dordrecht: Kluwer Academic Publishers. The Netherlands, 1996.

107. Sergeyev Ya.D. An information global optimization algorithm with local tuning // SIAM J. of Optimization, 1995. V.5. №4. P. 858-870.

108. Sergeyev Y.D. Global optimization algorithms using smooth auxiliary functions: Tech. Rep. 1. - Institute of Systems and Informatics, Rende(CS)/ 1994.

109. Sergeyev Y.D. Global one-dimensional optimization using smooth auxiliary functions // Math. Program. - 1998. - Vol. 81, № 1. - P. 127-146.

110. Shekel J. Test functions for multimodal search technique // Proc. 5-th Princeton Conf. Inform. Sci. Systems. Princeton Univ. Press. 1971. P. 354-359.

111. Shevtsov I.Y., Markine V.L., Esveld C. An inverse shape design method for railway wheel profiles. Structural and Multidisciplinary Optimization. Volume 33, № 3, Springer Berlin/Heidelberg, 2007. P.243 - 253.

112. Shevtsov I.Y., Markine V.L., Esveld C. Optimal design of wheel profile for railway vehicles // Proceedings 6th International Conference on Contact Mechanics and Wear of Rail/Wheel Systems, Gothenburg, Sweden, June 10 -13, 2003. P. 231 -236.

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

142

114. Strongin R.G. Algorithms for multi-extremal mathematical programming problems employing the set of joint space-filling curves // J. of Global Ootimization, 1992. №2. P. 357-378.

X

115. Strongin R.G., Sergeyev Ya.D. Global optimization with non-convex constraints. Sequential and parallel algorithms. Kluwer Academic Publishers, Dordrecht, 2000.

116. Strongin R.G., Sergeyev Ya.D., Grishagin V.A. Parallel Characteristical Algorithms for Solving Problems of Global Optimization // Journal of Global Optimization, 1997. 10. P. 185-206.

117. Torn A.A., Zilinskas A. Global optimization. Lecture notes in computer science 350. Springer-Verlag, Berlin, 1989.

118. Tuy H. Convex Analysis and Global Optimization. Kluwer Academic Publishers, Dordrecht, 1998.

ПРИЛОЖЕНИЕ 1. АКТ ВНЕДРЕНИЯ

УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК

ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР РАН им. А.А.Дородницына РАН

119333, Москва, ул. Вавилова, 40 Тел.: [phone].

Факс: [phone]

Для телеграмм: Москва.. 119296, ВЦ РАН Электронная почта: [e-mail]

Интернет: http://www.ccasjfu

r/SM i-f, № / Ректору Нижегородского

Государственного университета

На №_им. Н.И. Лобачевского

д,ф.-м.н., профессору Чупрунову Е. В.

Учреждение Российской академии наук Вычислительный центр им. A.A. Дородницына РАН (ВЦ РАН) подтверждает, что результаты исследований ассистента ИНГУ Сысоева Александра Владимировича в области параллельных методов глобальной оптимизации используются в отделе «Математическое моделирование экономических систем» (ММЭС) ВЦ РАН для решения задач идентификации математических моделей российской экономики. В частности, с помощью его программных средств на кластере ННГУ по статистическим данным Нижегородской области 2000-2010гг. были определены параметры нормативной балансовой модели региональной экономики, построенной в отделе ММЭС.