Например, Бобцов

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

Параллельные методы решения задач глобальной оптимизации

25
УДК 519.853.4

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

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

Ключевые слова: многоэкстремальная оптимизация, невыпуклые ограничения, кривые Пеано, параллельные алгоритмы.

Введение. В настоящей работе продолжено исследование в области нового подхода к

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

[1—6] и получившего название индексного метода глобальной оптимизации. Метод основан

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

функций. При этом решение многомерных задач сводится к решению эквивалентных им од-

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

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

нозначные отображения типа кривой Пеано, называемые также кривыми, заполняющими

пространство. Предложена новая схема построения множества кривых Пеано („вращаемые

развертки“), достоинством которой (в отличие от схемы „сдвиговых разверток“) является

простота в построении и использовании. Описан параллельный индексный алгоритм, осно-

ванный на одновременном использовании множества вращаемых разверток. Приведены ре-

зультаты экспериментов, подтверждающие достоинство новой схемы построения множест-

венных отображений.

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

ϕ( y* ) = min{ϕ( y) : y ∈ Ω, g j ( y) ≤ 0, 1 ≤ j ≤ m} ,

(1)

где область поиска Ω задана как единичный гиперкуб N-мерного евклидова пространства

Ω = {y ∈ RN : −2−1 ≤ yi ≤ 2−1, 1 ≤ i ≤ N} . Важный в прикладном отношении подкласс задач вида (1) характеризуется тем, что все

функции, входящие в определение задачи, заданы некоторыми (программно реализуемыми)

алгоритмами вычисления значений ϕ( y) , g j ( y) (1 ≤ j ≤ m ) в точках области поиска Ω . При

этом решение задачи (1) сводится к построению оценки y∗ ∈ Q , отвечающей некоторому по-

нятию близости к точке y * (например, чтобы y* − y∗ ≤ ε или ϕ( y* )−ϕ( y∗ ) ≤ ε , где ε > 0

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

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 10

26 Р. Г. Стронгин, В. П. Гергель, К. А. Баркалов

обозначаемая также gm+1 ) и левые части ограничений g j ( y) (1 ≤ j ≤ m ) удовлетворяют условию Липшица с соответствующими константами Lj (1 ≤ j ≤ m +1 ), а именно

g j ( y1) − g j ( y2 ) ≤ Lj y1 − y2 , 1 ≤ j ≤ m +1 , y1, y2 ∈ Ω .

(2)

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

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

минимизации в области Ω к одномерной задаче условной минимизации на отрезке [0,1]:

ϕ( y(x*)) = min{ϕ( y(x)) : x ∈[0,1], g j ( y(x)) ≤ 0, 1 ≤ j ≤ m} .

(3)

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

g j ( y(x′)) − g j ( y(x′′)) ≤ K j x′ − x′′1/N , x′, x′′ ∈[0,1], 1 ≤ j ≤ m +1 ,

где N есть размерность исходной многомерной задачи, а коэффициенты K j связаны с кон-

стантами Липшица Lj исходной задачи соотношением K j ≤ 4Lj N . Общая теория и вопро-

сы численного построения отображений типа кривой Пеано подробно рассмотрены в работах [1—6]. Отметим, что численно построенная кривая является приближением к теоретической

кривой Пеано с точностью не менее 2−κ по каждой координате (параметр κ называется плотностью развертки).
Для целей дальнейшего изложения введем классификацию точек y из области поиска

Ω с помощью индекса v = v( y(x)) , который определяется условиями

g j ( y(x)) ≤ 0 , 1 ≤ j ≤ v −1, gv ( y(x)) > 0 ,

(4)

при этом последнее неравенство несущественно, если v = m +1, и удовлетворяет неравенствам

1 ≤ v = v( y(x)) ≤ m +1.

Данная классификация порождает функцию

f ( y(x)) = gv ( y(x)) , v = v( y(x)) ,

(5)

определенную и вычисляемую всюду в Ω . Ее значение в точке y есть либо значение левой

части ограничения, нарушенного в этой точке (случай, когда v ≤ m ), либо значение минимизируемой функции ( v = m +1). Поэтому определение значения f ( y(x)) сводится к последова-

тельному вычислению величин gi ( y(x)) , 1 ≤ i ≤ v = v(x) , т.е. последующее значение

gi+1( y(x)) вычисляется лишь в том случае, когда gi ( y(x)) ≤ 0 . Процесс вычислений завершается либо в результате установления неравенства gi ( y(x)) > 0 , либо в результате достижения значения v(x) = m +1.

Описанная процедура, называемая испытанием в точке y , автоматически приводит к

определению индекса v этой точки. Пара значений

z = gv( y) , v = v(y) , порожденная испытанием в точке y ∈ Ω , называется результатом испытания.

(6)

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

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

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 10

Параллельные методы решения задач глобальной оптимизации

27

многомерном пространстве, так как точка x ∈[0,1] имеет лишь левых и правых соседей, а со-

ответствующая ей точка y(x) ∈ RN имеет соседей по 2N направлениям. Как результат, при

использовании отображений типа кривой Пеано близким в N-мерном пространстве образам

y′ , y′′ могут соответствовать достаточно далекие прообразы x′ , x′′ на отрезке [0,1].

Сохранить часть информации о близости точек позволяет использование множества отображений

YM (x) = {y1(x), ..., yM (x)}

(7)

вместо применения единственной кривой Пеано y(x) (см. работы [4, 6]). Каждая кривая

Пеано yi (x) из YM (x) может быть получена в результате некоторого сдвига вдоль главной
диагонали гиперинтервала Ω . Таким образом, сконструированное множество кривых Пеано позволяет получить для любых близких образов y′ , y′′, отличающихся только по одной

координате, близкие прообразы x′ , x′′ для некоторого отображения yi (x) .
Вращаемые развертки. К числу недостатков этой ставшей уже классической схемы построения множественных разверток (будем называть их сдвиговыми развертками, или С-развертками) можно отнести наличие дополнительного ограничения, порождающего сложную допустимую область на одномерных отрезках.
Преодолеть этот недостаток, сохранив информацию о близости точек в N-мерном пространстве, позволяет новая схема построения множественных отображений. Отличительная черта схемы — множество кривых Пеано строится не с помощью сдвига вдоль главной диагонали гиперкуба, а поворотом развертки вокруг начала координат. При этом найдется ото-
бражение yi (x) , точкам многомерного пространства y′ , y′′ (которым при исходном отобра-
жении соответствовали достаточно далекие прообразы на отрезке [0,1]) сопоставляющее более близкие прообразы x′ , x′′ .
Развертки, порождаемые в соответствии с новой схемой, будем называть вращаемыми развертками, или В-развертками.
Для иллюстрации на рис. 1 приведены две кривые, являющиеся приближением к развертке Пеано для случая N = 2 . Узлы сетки в N-мерном пространстве отмечены темными кружками, стрелкой указана одна из пар точек, прообразы которых далеки на одномерной оси при одном отображении и близки при другом.

Рис. 1
Максимальное число различных поворотов развертки, отображающей N-мерный гиперкуб на одномерный отрезок, составляет 2N. Использование их всех является избыточным, требуется выбрать лишь часть из всех возможных вариантов.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 10

28 Р. Г. Стронгин, В. П. Гергель, К. А. Баркалов

Предлагается осуществлять преобразование развертки в виде поворота на угол ±π / 2 в

каждой из координатных плоскостей. В качестве примера на рис. 2 приведены матрицы по-

⎡1 0 0 0 0⎤ ⎡1 0 0 0 0⎤ ворота в плоскости ( y2 , y4 ) при N = 5.

⎢⎢0 ⎢0 ⎢⎢0 ⎢⎣0

0 0 1 0

0 1 0 0

−1 0 0 0

0⎥⎥ 0⎥ 0⎥⎥ 1⎥⎦

⎢⎢0 ⎢0 ⎢⎢0 ⎢⎣0

0 0 −1 0

0 1 0 0

1 0 0 0

0⎥⎥ 0⎥ 0⎥⎥ 1⎦⎥

Число подобных пар поворотов определяется числом координатных плоскостей пространства: CN2 = N (N −1) 2 , а общее число преобразований будет равно N (N −1) . Учитывая исходное отображение,
приходим к заключению, что данный способ позво-

Рис.2

ляет строить до N (N −1) +1 разверток для отображе-

ния N-мерной области на соответствующие одномерные отрезки. При этом дополнительное

ограничение, которое возникало при построении сдвиговых разверток [4], отсутствует.

В случае необходимости данный способ построения множества отображений может

быть легко „отмасштабирован“ для получения большего (вплоть до 2N ) числа разверток.

Использование множества отображений YM (x) = {y1(x), ..., yM (x)} приводит к форми-

рованию соответствующего множества одномерных многоэкстремальных задач

min{ϕ( yl (x)) : x ∈[0,1], g j ( yl (x)) ≤ 0,1 ≤ j ≤ m}, 1 ≤ l ≤ M .

(8)

Каждая задача из данного набора может решаться независимо, при этом любое вычис-

ленное значение z = gv ( y′) , y′ = yi (x′) функции gv ( y) в i-й задаче может интерпретировать-

ся как вычисление значения z = gv ( y′) , y′ = ys (x′′) для любой другой s-й задачи без повтор-

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

решать исходную задачу (3) путем параллельного решения индексным методом М задач вида

(8) на наборе отрезков [0,1]. Каждая одномерная задача решается на отдельном процессоре.

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

процессоры помещают информацию о выполненных итерациях. Используемая схема не со-

держит какого-либо единого управляющего процессора, что повышает надежность выпол-

няемых вычислений.

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

ний позволяет решать исходную задачу (1) путем параллельного решения индексным мето-

дом М задач вида (8) на наборе отрезков [0,1]. Каждая одномерная задача решается на от-

дельном процессоре. Результаты испытания в точке xk , полученные конкретным процессо-

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

ных задачах (в соответствующих точках xk1, ..., xkM ). При таком подходе испытание в точке

xk ∈[0,1], осуществляемое в s-й задаче, состоит в последовательности действий.
1. Определить образ yk = ys (xk ) при соответствии ys (x) . 2. Проинформировать остальные процессоры о начале проведения испытания в точке yk (блокирование точки yk ).

3. Вычислить величины g1( yk ),..., gv ( yk ) , где значения индекса v ≤ m определяются условиями
gi ( yk ) ≤ 0 , 1 ≤ j < v , gv ( yk ) > 0 , v ≤ m .
Выявление первого нарушенного ограничения прерывает испытание в точке yk . В слу-

чае, когда точка yk допустима, испытание включает вычисление значений всех функционалов задачи, при этом значение индекса принимается равным v = m +1. Тройка

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 10

Параллельные методы решения задач глобальной оптимизации

29

ys (xk ) , v = v(xk ) , zk = gv ( ys (xk ))

(9)

является результатом испытания в точке xk .

4. Определить прообразы xkl ∈[0,1] (1 ≤ l ≤ M ) точки yk и интерпретировать испыта-

ние, проведенное в точке yk ∈ Ω , как проведение испытаний в М точках

xk1,..., xkM

(10)

с одинаковыми результатами

v(xk1) = ... = v(xkM ) = v(xk ) ,

gv ( y1(xk1)) = ... = gv ( yM (xkM )) = zk .

5. Проинформировать остальные процессоры о результатах испытания в точке yk .

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

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

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

ков. Начальная итерация осуществляется в произвольной точке x1 ∈ (0,1) (начальные точки

для всех процессоров задаются различными). Выбор точки xq+1 ( q ≥ 1 ) любого последующе-

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

для него результаты, включающие множество Yq = {yqi :1 ≤ i ≤ sq} точек итераций в области

D и вычисленные в них значения индекса и величин из (9). Определить множество

X q = {xqi :1 ≤ i ≤ sq} прообразов точек множества Yk при соответствии yl (x) .

Правило 2. Точки множества итераций

{x1}∪ X1 ∪... ∪ X q

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

0 = x0 < x1 < ... < xi < ... < xk < xk +1 = 1,

(11)

где k = 1+ s1 + ... + sq , и сопоставить им значения zi = gv (xi ) , v = v(xi ) (1 ≤ i ≤ k ), вычисленные
в этих точках. При этом индекс блокированной точки xi (т.е. точки, в которой начато проведение испытания другим процессором) полагается равным –1, т.е. v(xi ) = −1, значение zi является неопределенным. Точки x0 , xk+1 введены дополнительно для удобства последующего изложения, индекс данных точек полагается равным −2, т.е. v(x0 ) = v(xk+1) = −2 , а значения z0 , zk+1 являются неопределенными.
Правило 3. Провести классификацию номеров i (1 ≤ i ≤ k) точек из ряда (11) по числу ограничений задачи, выполняющихся в этих точках, путем построения множеств

I−2 = {0, k +1} , I−1 = {i :1 ≤ i ≤ k, v(xi ) = −1} , Iv = {i :1 ≤ i ≤ k, v(xi ) = v}, 1 ≤ v ≤ m + 1 ,

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 10

30 Р. Г. Стронгин, В. П. Гергель, К. А. Баркалов
содержащих номера всех точек xi (1 ≤ i ≤ k) с индексами, равными одному и тому же значению v . Определить максимальное значение индекса
νmax = max{v = v(xi ), 1 ≤ i ≤ k} .
Правило 3. Вычислить текущие нижние границы

µν

=

max

⎪⎧ ⎨ ⎪⎩

(

| zi xi −

− x

zj j )1

|
N

:

j

< i,

j





,

i





⎪⎫ ⎬

⎪⎭

(12)

для относительных разностей функций gv (1 ≤ v ≤ m +1 ). Если множество Iv содержит менее

двух элементов или если µv из (12) оказывается равным нулю, то принять µv = 1. Из (12) сле-

дует, что оценки µv являются неубывающими начиная с момента, когда (12) порождает пер-

вое положительное значение µv .

Правило 4. Для всех непустых множеств Iv (1 ≤ v ≤ m +1 ) вычислить оценки

zν∗ = ⎧⎩⎨m−iεnν{,gν (xi ):i∈Iν },

ν < νmax , ν = νmax ,

где вектор

εR = (ε1, ..., εm ) , имеющий положительные координаты, называется вектором резервов.

(13)

Правило 5. Для каждого интервала (xi−1, xi ) (1 ≤ i ≤ k +1) вычислить характеристику R(i)

R(i)

= ∆i

+

(zi − zi−1)2 rν2 µν2 ∆i

−2

( zi

+

zi−1 − 2zν∗ ), rν µν

ν = ν(xi−1) = ν(xi ) ,

R(i)

=

2∆i



4

(zi − zν∗ ), rν µν

ν(xi−1) < ν(xi ) = ν ,

R(i)

=

2∆i



4

(

zi−1 − zν∗ rν µν

)

,

ν = ν(xi−1) > ν(xi ) ,

∆i = (xi − xi−1)1/N .

Величины rv > 1 (1 ≤ v ≤ m +1 ) являются параметрами алгоритма.

Правило 6. Определить интервал (xt−1, xt ) , которому соответствует максимальная характеристика

R(t) = max{R(i) :1 ≤ i ≤ k +1} .

(14)

Правило 7. Провести очередное испытание в серединной точке интервала (xt−1, xt ) , если индексы его концевых точек не совпадают, т.е.

xq+1 = (xt + xt−1) / 2 , v(xt−1) ≠ v(xt ) .

В противном случае провести испытание в точке

xq+1

= (xt

+ xt−1)

2 − sign(zt



zt

−1

)

1 2rν

⎡ ⎢

|

zt



− zt−1 µν

|⎤N ⎥ ⎦

,

v = v(xt−1) = v(xt ) .

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

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 10

Параллельные методы решения задач глобальной оптимизации

31

Описанные правила можно дополнить условием остановки, прекращающим испытания, если ∆t ≤ ε , где t (см. выражение (14)), и ε > 0 — желаемая покоординатная точность в задаче.
Операционные характеристики и сравнение алгоритмов. Один из известных подходов к оценке эффективности методов безусловной глобальной оптимизации основан на численном решении этими методами всех задач из некоторой случайно генерируемой выборки большого объема (см., например, [7]).
Генераторы таких выборок можно рассматривать как некоторые классы функций f ( y)
( y ∈ Ω ) с определенной на них вероятностной мерой. Один из таких генераторов G , предло-
женный в работе [8], порождает многоэкстремальные функции в соответствии со схемой

∑ ∑ ∑ ∑ϕ(y1,

y2 )

=−

⎩⎪⎨⎪⎧⎝⎜⎛⎜

7 i=1

7
⎣⎡
j=1

Aij aij

( y1,

y2 )+ Bijbij

(

y1 ,

y2

)⎦⎤

⎞2 ⎟ ⎠⎟

⎛ +⎝⎜⎜

7 i=1

7
⎡⎣Cij aij
j=1

(

y1 ,

y2

)−

Dij bij

( y1,

⎞2 y2 )⎤⎦ ⎠⎟⎟

⎫1 ⎪ ⎬ ⎭⎪

2
,

где aij ( y1, y2 ) = sin(πiy1) sin(πjy2 ) , bij ( y1, y2 ) = cos(πiy1) cos(πjy2 ) определены в области
0 ≤ y1, y2 ≤1, а параметры −1 ≤ Aij , Bij , Cij , Dij ≤ 1 являются независимыми случайными вели-
чинами, равномерно распределенными в указанном выше интервале. Минимизация подобных функций возникает, например, в задаче оценки максимального напряжения (определяющего прочность) в тонкой пластине при поперечной нагрузке.
Примененная процедура оценки эффективности алгоритмов использует аппарат операционных характеристик из работы [8] и состоит в следующем. Пусть некоторая задача вида (1) из рассматриваемой выборки решается с помощью алгоритма S . При этом задаче сопоставляется порождаемая алгоритмом последовательность точек испытаний
{yk} . Указанная последовательность прерывается (т.е. процесс решения прекращается)
либо в связи с первым попаданием точки очередного испытания в заданную δ -окрест-
ность решения x* , либо в связи с тем, что в ходе выполнения заданного числа K испытаний такое попадание не имело места. В проведенных численных экспериментах использовалось значение K = 1000 .
Поскольку задание δ -окрестности предполагает координату x* известной, ее значение предварительно оценивалось (для каждой функции выборки) путем перебора всех узлов рав-
номерной (в области поиска Ω ) сетки с шагом 10−3 . Результат решения всех задач выборки с помощью алгоритма S представляется функ-
цией Ps (k) , характеризующей долю задач, для которых в ходе k шагов поиска имели место попадания точек испытаний в заданную δ -окрестность решения. Такую функцию будем называть операционной характеристикой алгоритма S .
Эксперименты проводились для описанных выше алгоритмов со сдвиговыми (С) и вращаемыми (В) развертками с плотностью κ = 12 , число разверток M = 2 . При этом использовались параметры rv = 2,1 , ε = 0, 01 и резервы εv = 0, 05 ( 0 ≤ v ≤ 1) из (13). Данные параметры являются минимальными для соответствующих методов, при которых достигается решение 100 % задач из выборки.
Операционные характеристики для обоих методов, полученные на выборках, рождаемых генератором G , представлены на рис. 3. При этом кривая 1 характеризует метод со сдвиговыми развертками, 2 — метод с единственной разверткой, 3 — метод с вращаемыми развертками. Указанное расположение кривых показывает, что алгоритм с В-развертками

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 10

32 Р. Г. Стронгин, В. П. Гергель, К. А. Баркалов обеспечивает в среднем более быстрое получение оценок, лежащих в заданной окрестности решения, чем алгоритм с С-развертками или алгоритм с единственной разверткой.
3
2
1
Рис. 3
С целью иллюстрации использования параллельного алгоритма с множеством В-разверток рассмотрим известную задачу минимизации функции Растригина
N
∑ϕ( y) = ( yi2 − cos(18yi2 )) , −1, 5 ≤ yi ≤ 1, 5 , 1 ≤ i ≤ N , N = 6 , i=1
где минимальное значение ϕ( y*) = −N достигается в точке y* = 0 . Для решения данной задачи использовались последовательный и параллельный методы
с вращаемой разверткой с плотностью κ = 10 , использовался параметр метода r = 2 , и ε = 0, 05 — в критерии остановки. Число разверток M = 30 соответствовало числу процессоров, задействованных при решении задачи. И последовательный, и параллельный алгоритмы нашли решение с требуемой точностью, при этом последовательный алгоритм выполнил 173 116 итераций, а параллельный — 8535 (максимальное число итераций на одном процессоре). Ускорение по числу итераций составило 20,3, а ускорение по времени — 7,5.
Работа выполнена при финансовой поддержке РФФИ (грант № 07-01-00467-а) и Совета по грантам Президента Российской Федерации по государственной поддержке ведущих научных школ Российской Федерации (грант № НШ-4694.2008.9).
СПИСОК ЛИТЕРАТУРЫ
1. Стронгин Р. Г. Численные методы в многоэкстремальных задачах. М.: Наука, 1978. 2. Стронгин Р. Г., Маркин Д. Л. Минимизация многоэкстремальных функций при невыпуклых ограничениях //
Кибернетика. 1986. № 4. С. 63—69. 3. Стронгин Р. Г. Поиск глобального оптимума. М.: Знание, 1990. 4. Стронгин Р. Г. Параллельная многоэкстремальная оптимизация с использованием множества разверток //
Журн. вычислительной математики и математической физики. 1991. Т. 31, № 8. С. 1173—1185. 5. Стронгин Р. Г., Баркалов К. А. О сходимости индексного алгоритма в задачах условной оптимизации с ε-резер-
вированными решениями // Математические вопросы кибернетики. М.: Наука, 1999. С. 273—288. 6. Strongin R. G., Sergeyev Ya. D. Global optimization with non-convex constraints. Sequential and parallel
algorithms. Dordrecht: Kluwer Academic Publishers, 2000. 7. Гергель В. П., Стронгин Р. Г. Абсолют. Программная система для исследований и изучения методов гло-
бальной оптимизации. Н. Новгород: Изд-во Нижегородского ун-та, 1998. 8. Гришагин В. А. Операционные характеристики некоторых алгоритмов глобального поиска // Проблемы
случайного поиска. Рига: Зинатне, 1978. № 7. С. 198—206.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 10

Блочно-рекурсивное параллельное перемножение матриц

33

Роман Григорьевич Стронгин Виктор Павлович Гергель Константин Александрович Баркалов

Сведения об авторах — д-р физ.-мат. наук, профессор; Нижегородский государственный
университет им. Н. И. Лобачевского; кафедра математического обеспечения ЭВМ; президент; E-mail: strongin@unn.ac.ru — д-р техн. наук, профессор; Нижегородский государственный университет им. Н. И. Лобачевского; кафедра математического обеспечения ЭВМ; декан; E-mail: gergel@unn.ru — канд. физ.-мат. наук; Нижегородский государственный университет им. Н. И. Лобачевского; кафедра математического обеспечения ЭВМ; ст. препод.; E-mail: barkalov@fup.unn.ru

Рекомендована институтом

Поступила в редакцию 10.03.09 г.

ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 10