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

РГБ ОД

..-л '.'"Г'* На правах рукописи

СЕРГЕЕВ Ярослав Дмитриевич

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

Специальность 01.01.09 — Математическая кибернетика

Авт ореферат

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

Москва, 1996

Работа выполнена в Нижегородском государственном университете им. Н. И. Лобачевского.

доктор технических наук, профессор Батищев Д. И., доктор физико-математических наук Жадаи В. Г., доктор физико-математических наук Завриев С. К.

Ведущая организация — Санкт-Петербургский государственный университет.

Защита состоится « ' "У » и_1Э96 г. в. // час.

на заседании диссертационного совета Д 053.05.38 при МГУ по адресу: 119899, ГСП, г. Москва, Ленинские горы, МГУ, факультет вычислительной математики и кибернетики, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

Официальные оппоненты:

Автореферат разослан «

1996 г.

Ученый секретарь диссертационного совета, профессор

Трифонов Н. П.

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

Актуальность проблемы. Многие задачи принятия оптимальных решении (а том числе восстановление зависимостей по результатам экспериментальных наблюдений, задачи выбора оптимальных параметров проектируемых объектов и процессов и др. ) могут быть сведены и решению сложных задач глобальной многоэкстремальной оптимизации. Вопросам численного решения таких задач посвящена обширная литература (работы Д. И. Батищева, В. П. Булатова, Ф. П. Васильева, D. Ф. Демьянова, Ю. Г. Евтушенко, С. М. Ермакова, Ю. М. Ермольева, В. Г. Жадана, А. А. Жиглявского, А. Г. Жилинснаса, С. К. Завриева, В. В. Иванова, В. Г. Карманова, В. С. Михалевича, Н. Н. Моисеева, И. Б. Моцнуса, Ю. И. Неймарна; П. М. Пардалоса, Я. Пинтера, С. А. Пиягзского, Э. Полана, Б. Н. Пшеничного, Л. А. Растригина, A.C. Стреналовско-го, Р. Г. Стронгина, А. Г. Сухарева, А. Н. Тихонова, X. Туя, Д. Дж. УаИпда, В. В. Федорова, Д. Химмельблау, П. Хансена, Р. Хорста, В. К. Чичинадэе, Д. Б. Юдина и др. ). Однако, возрастающая -сложность практических задач приводит и увеличению времени, затрачиваемого на вычисление каждого значения оптимизируемой функции, и росту числа таких вычислений в целом, что накладывает ограничения на круг решаемых проблем и постоянно выдвигает на передний план задачу повышения эффективности методов глобальной оптимизации.

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

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

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

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

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

Вопросы построения решающих правил для параллельного выбора точек итераций) ноторым посвящена настоящая работа, гораздо менее изучены. В настоящее время начинают появляться первые работы в этом направлении (В. Н. Белецкий, П. Ж. М. ван Лаарховен, Ф. А. Лутсма, Т. А. Стратер, П. М. Пардалос, М. ФеИлмейер, Р. Флетчер, Т. Л. Фриман, Р. Шнабел и др. ), однако, большей частью они относятся к проблемам, связанным с поиском локально -от имальных решении, мало затрагивая вопросы отыскания глобального оптимума. В связи с этим представляются актуальными исследования по разработке эффективных

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

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

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

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

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

Научная новизна :

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

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

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

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

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

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

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

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

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

Практическая ценность работы. Исследования по теме диссертации выполнялись в рампах основного научного направления Нижегородского университета "Методы принятия решении и оптимизация", задания 06. 21А научно-технической программы ГННТ СССР 0.80.03, а также темы "Адаптивное управление, принятие решении и оптимизация" № гос. регистрации 0186. 0136674 Координационного плана НИР АН СССР на 1986-1990 гг.

Практическая значимость работы определяется возможностью использования разработанных численных методов в системах принятия решения для САПР и АСНИ на однопроцессорных и многопроцессорных вычислительных комплексах. Результаты работы использовались при проведении исследований в рамках научно-технической темы "Раыработна теоретических основ и программная реализация систем полпержни выбора решении для

научных исследований и проектирования" (К- Гос. регистрации 01. О. 30007173).

Апробация работы. Основные результаты работы докладывались на совещаниях-семинарах "Использование вычислительных средств в экологии, экономике и медицине" (Горький, 1986, Саратов, 1988), Международной конференции "Передовые вычислительные методы, параллельные вычисления и оптимизация " (ФРГ, Карлсруэ, 1987), VI Международной конференции "Основы теории вычислений" (Казань, 1987), IV Всесоюзной конференции "Автоматизация поискового конструирования и подготовка инженерных кадров" (Волгоград, 1987), VIII Всесоюзной конференции "Проблемы теоретической кибернетики" (Горький, 1988), II Всесоюзном совещании "Конвейерные вычислительные системы" (Киев, 1988), VI научной конференции "Методы математического программирования и программное обеспечение" (Свердловск, 1989), Всесоюзном научно-техническом совещании "Перспективы развития локальных информационно-вычислительных сетей на базе персональных ЭВМ" (Москва, 1989), конференции "Диалог "Человек - ЭВМ" (Свердловсн, 1989), VII Всесоюзном семинаре "Распараллеливание обработки информации" (Львов, 1909), IV Всесоюзном межвузовском научном семинаре "Диалоговые средства распределенной обработки данных в комплексах и сетях ЭВМ" (Москва, 1990), Первой Советско - Итальянской конференции по методам и приложениям математического программирования (Италия, Четраро, 1992), Международном совещании "Распределенные и параллельные вычисления в системах логического программирования" (США, Вашингтон, 1992), Межгосударственной научной конференции "Экстремальные задачи и их приложения" (Н.Новгород, 1992), 5-И Международной конференции по параллельным вычислениям PARLE (ФРГ, Мюнхен, 1993), 18-м Международном симпозиуме "Исследование Операции" (ФРГ, Кельн, 1993), XII-H Международной конференции "Математическое Программирование" (Венгрия, Матрафюред, 1994), Международном совещании "Передовые математичесние методы в электрических и электронных измерениях" (Италия, Комо, 1994), Международной конференции EURO XIII / OR 36 "Исследование Операций для разработки практических решений" (Шотландия,

Глазго, 1994), Международной конференции "Глобальная оптимизация : численные методы и приложения" (США, Принстон, 1995), II 1-м Международном совещании по глобальной оптимизаций (Венгрия, Сегед, 1995), а также на научных семинара:? Московского, Санкт-Петербургского, Нижегородского университе тов, ВЦ РАН, в итальянских университетах городов Рим, Неаполь, Бергамо, Салерно, Коэенца, в университетах городов Поган (Ста; США), Баулдер (Колорадо, США), институтах Итальянского Наци онального Совета по Науне в городах Рим, Милан, Козенца и др.

Публикации. По теме диссертации опубликовано 53 работы. Основное содержание диссертации изложено в работах [1-30].

Структура и обьеи работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 358 наименований и приложения. Основной печатный текст занимает 253 страницы, кроме того, в работе содержится 32 рисунка и 16 таблиц.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

В $ 1. 1 дается постановка задачи параллельной глобальной минимизации отыснания точен х* и значения fix*) абсолютного (глобального) минимума действительной функции f (х), заданной на области И, т.е.

х* - argmin ( f(x) : х с М с R* ). (1)

Кратно рассматриваются•известные алгоритмы поиска глобально- и локально-оптимальных решений. ^Вводится базовая идея, исполь-

эуемая в работе для распараллеливания последовательных

методов : на каждой итерации параллельным алгоритмом

одновременно (на р параллельных процессорах) проводятся

вычисления значений целевой функции в р > 1 точках (в

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

х испытанием). Вводятся следующие критерии эффективности

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

Пусть Т (1) есть время решения задачи (1) последовательным

алгоритмом (ПОС), а Т(р) - время решения той же задачи на

многопроцессорной системе с р процессорами параллельным

методом (ПАР). Тогда величину

S (р) = Т(1) / т(р)

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

использовании параллельного алгоритма (в сравнении с его

последовательным прообразом).

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

целевой функции даже в одной точке велико, другой важной

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

ускорение в итерациях

8 (р) - П(1)р / П(р) ,

где п(1) есть число испытаний, выполненных ПОС для решения

проблемы (1), п(р) - число испытаний, выполненных ПАР с р

процессорами для решения той же задачи.

Естественным, при использовании р параллельных

процессоров, является желание получить ускорение в (р) = р. К

сожалению, это возможно далеко не всегда. Схема

распараллеливания последовательных алгоритмов, принятая в

настоящей работе, не является тривиальной с информационной

точки зрения (как бывает, например, при распараллеливании

цинпа присваивания в программировании).

Действительно, ПОС при выборе точки х1"1 на шаге k+l

обладает полной информацией, полученной к этому -моменту на

предыдущих к итерациях в точнах х1,...,ПАР на основе той

же информации выбирает не одну, а р точен хкП, хк*г, . . . , хк*р.

Это значит, что выбор точки xll,J осуществляется при отсутствии

k+l k-»l-l

информации о результатах испытаний в точках х , ..., х , 2sjsp. Следовательно, тольно первая точка xk<1 определяется на

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

T(m,n) » Т'(га/П)/(ш - п), где m > п, а величина Т" (m,n) есть число избыточных испытаний, выполненных ПАР с (n-t-l) -го по т-е испытание.

Построение параллельных методов начинается (§ 1.2) с рассмотрения наглядного примера - распараллеливания последовательного информационно-статистического, алгоритма (ПОСИ), предложенного Р. Г. Стронгиным для решения одномерной задачи глобальной оптимизации

min { f (х) ! X « .<аД>)'.}, (2)

где функция £ (х) является многоэнстремальной и на 'интервала [а,Ь] удовлетворяет условию Липшица с константой 0< К <», т.е. IflxJ - f(xa)| a K|xt - ха|, V Xj, х2 с [а,Ь]. (3) ПОСИ кан база .для распараллеливания интересен для нас по нескольким причинам :

имеющиеся оценки скорости сходимости поназывают его существенное превосходство над переборными схемами поиска;

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

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

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

Идея распараллеливания ПОСИ, приводящая и построению параллельного информационно-статистического алгоритма (ПИА), заключается в следующем. . ПОСИ . построен на основе стохастической модели, согласно которой' каждому интервалу 'xi -1 ,xt'' гда xi> есть; точки испытаний, сопоставляется

характеристика R(i), оценивающая вероятность нахождения в

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

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

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

Теорема 1.1. Пусть х есть предельная точка последовательности {хк}, порождаемой ПИЛ при минимизации пипшицевой с нонстантой К функции tlx), х • (а,Ь), причем, число используемых параллельных процессоров не превосходит Q, 1<Q<». Тогда :

1) сходимость к внутренней точна х е (а,Ь) является двусторонней;

2) точка х локально оптимальна, если функция f (х) имеет конечное число локальных экстремумов;

3) если наряду с х существует другая предельная точка х, то следует f (х) « £(х) ;

4) при любом к » 1 следует гк - С(хк) t f (it) ;

5) если на некотором шаге для адаптивной оценки константы Липшица M выполняется условие

rM е 2К,

где г есть параметр метода, то множество предельных точек последовательности (х } совпадает . с множеством точек глобального минимума функции f(х).

Большое внимание в работе уделено получению теоретических условий, позволяющих организовать безыэбыточный поиск и, следовательно, получить значения ускорения s(р), близкие к числу р используемых параллельных процессоров. Так, теорема 1.2 устанавливает условия безызбыточности (т.е. T(m,n) « 0) при использовании ПИА с двумя параллельными процессорами на каждой итерации, т.е. при р(к) - 2, к*1.

Поскольку оптимизируемая функция f (х) предполагается

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

Теорема 1.3. Пусть х* есть точка глобального, ах' -локального минимума функции f(x) и верно неравенство

f (х') - f (х*) sa, где г > О. Тогда, если существует точка yn е {хк} такая, что х' s у" s х* или х* * у" s х' , для ПИА справедливо :

1) при Q ■ 2, г > l+v/~2 следует Т(ш,п) » 0, пока длина интервала, где проводится испытание, больше е ,•

2) при Q » 4, г > 2+fs следует T(m,n) < 0.17, пока длина интервала, где проводится испытание, больше е, где величины е,

с определяются следующим образом

4«г * - 4аг е = ---, е - -;-.

М(г -2г-1) М(г -4г-1)

Дополнительная информация о целевой функции . позволяет

уточнить границы эффективного распараллеливания.

Теорема 1.4. Пусть х* s (а,Ь) есть единственная точка

абсолютного минимума функции f(х) и существует некоторая

окрестность W этой точки, для которой справедливо, что

£ (х) - К|х - х*|, х « W, 0< К <м. (4)

Тогда при Q-2, г > 2 и M » К, где К из (3)

последовательность испытаний, порождаемая ПИА, будет иметь

только нонечное число точек испытаний вне W, а в W будет

Т(га,п) » 0.

Приведенная теорема интересна в связи с тем, что функция £(х) может быть адаптирно приведена к виду (4) в процессе оптимизации. Теорема 1. 5 и следствия к ней рассматривают более общие случаи, н которым может привести адаптация функции £(х) в процессе оптимизации и дают рекомендации по выбору параметров ПИА для беэыэбыточного распараллеливания. В частности, для случая, когда функция £(х) имеет Р точек глобального минимума х* с (а,Ь) и существуют окрестности W( , liisp, этих точек, для которых справедливо

-J0-

£(х)

К (х* - х), X * X*, X в 1*, Ка , Iх - Х|) , X > X*, X в ,

где 0< К1 1 <®, 0< К2 1 <», 1*1яР, причем известна лишь константа

К - тах { ^ К : 1*1зР }, получены условия, позволяющие получить ускорение а(2Р) * 1.66Р при использовании 2Р параллельных процессоров.

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

В § 1.3 принципы построения параллельных методов, апробированные при работе с ПИА в § 1. 2, обобщаются и вводится класс параллельных синхронных характеристических алгоритмов (ПСХА). Эти методы привлекают наше внимание еще и потому, что в совокупности с многошаговой схемой или со схемой редукции размерности при помощи разверток типа кривой Пеано, могут быть использованы для решения задач многомерной глобальной оптимизации. С единых позиций исследуются условия сходимости и эффективного распараллеливания алгоритмов введенного класса, в том числе, при работе в метрике Гельдера, которая используется при решении редуцированных с помощью разверток Пеано задач многомерной глобальной оптимизации.

Получены следующие общие условия сходимости для последовательностей испытаний, порождаемых ПСХА методами :

- условия двусторонней сходимости к любой внутренней точке х* € (а,Ь), являющейся предельной точкой последовательности испытаний (теорема 1. 6);

- условия всюду плотной сходимости (любая точка интервала [а,Ь] является предельной точкой последовательности испытаний) (теорема 1.7);

- условия локальной оптимальности предельных точек (теорема 1.8);

-М-

достаточные условия сходимости к глобальному минимуму (теорема 1. 9).

Схема распараллеливания ПСХА является обобщением схемы ПИА, вот почему при работе с ПСХА встают те же вопросы об эффективности их применения, что были исследованы для ПИА, а именно : каное ускорение процесса решения задачи по сравнению с последовательным прототипом дает применение параллелизма; какое количество избыточных испытаний может быть выполнено при параллельных вычислениях. Эти вопросы исследуются с единых позиций и теоремы 1. 10, 1. 11 распространяют результаты, полученные для ПИА в теоремах 1.2, 1.3, на весь класс ПСХА методов, устанавливая границы их беэыэбыточн'ого распараллеливания.

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

В § 1.4 строятся асинхронные параллельные методы глобальной оптимизации с целью ликвидации прос+оев процессоров при проведении параллельных итераций. Асинхронные методы

особенно важны при решении многомерных задач глобальной

\

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

Для решения безусловных задач в качестве базового

-и-

синхронного метода при построении асинхронного параллельного алгоритма (АПА) берется ПИЛ. Для АПА проводится теоретичесное исследование условии сходимости и беэызбыточного распараллеливания. Предлагаемая методика построения асинхронных методов может быть естественно распространена с ПИА на весь класс ПСХЛ алгоритмов.

Для исследования сходимости и условий беэызбыточного распараллеливания асинхронных параллельных алгоритмов последовательности испытаний {х*}, порождаемой АПА, сопоставляются последовательности {Т^}, l3jsp, где Т^ есть момент завершения j-м процессором выполнения 1-го испытания, проводимого на этом процессоре.

Теорема 1.12. Пусть х есть предельная точка последовательности (хк}, порождаемой АПА при минимизации липшицевой с константой К функции f(x), х а (а,Ь), причем, для числа р используемых процессоров имеет место l<p<Q<», а для моментов завершения испытаний верно

т' - т' < Т < «о, Н j 1 р, 1>1. Тогда выполняются все утверждения теоремы 1. 1.

Теоремы 1. 13, 1. 14 устанавливают условия беэызбыточного распараллеливания АПА.

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

min { дяИ(х): хе [а, Ы , lssjsm }, (5)

где g^ (х), lsjsm+1, - многоэкстремальные функции, удовлетворяющие условию Липшица с константами К^ > 0, т.е.

|gj(x'> "3j(x") х' |, х' [а, b] , lsjsm+l. (6)

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

-J3-

ограничений.

На основе АПА и инденсной схемы строится асинхронны!' параллельный индексный алгоритм для решения задачи (5), (6). Условия его сходимости описываются теоремой 1. 15.

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

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

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

В § 2. 1 показывается, что дополнительная априорная информация о классе, к которому принадлежит оптимизируемая Функция, позволяет существенно улучшить теоретические оценки на получаемое уснорение и увеличить число используемых параллельных процессоров, не приводя при этом к росту избыточности.

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

-У*-

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

В & 2.2 строятся параллельные ПСХА алгоритмы, использующие не только значения целевой Фуннции для поиска глобального решения, но и ее первые производные. Для класса Функций, имеющих первые производные, удовлетворяющие условию Липшица

| £' (х,)-«' (ха) | 1 Ь|х1-ха|, V х1, ха е 1а,Ь], (7) где 0 < Ь < м, строится параллельный алгоритм с производными (ПАП), адаптивно оценивающий Ь в процессе поиска и обобщающий на случай параллельных вычислений чисто последовательный метод, предложенный В. П. Гергепем.. Условия сходимости ПАП устанавливаются теоремами 2. 3 - 2.5, последняя из которых определяет достаточные условия сходимости к точкам глобального минимума. Теорема 2.6 и следствия н ней описывают условия эффективного распараллеливания ПАП.

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

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

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

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

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

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

- алгоритмы с локальной настройкой могут быть распараллелены по ПСХА схеме.

В § 2.3 рассматривается применение нового подхода для построения последовательных методов решения базовых задач (2), (3), (5), (б). Описывается алгоритм с локальной настройкой на поведение целевой функции (АЛН) для решения безусловных задач (2), (3). Теоремы 2.7 - 2.9 и следствия к ним описывают свойства сходимости АЛН. Теорема 2. 10 оценивает его скорость сходимости и устанавливает условия, при выполнении которых она превосходит скорости методов Пиявского, Стронгина и некоторого пассивного алгоритма.

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

Теорема 2.11. Пусть {х") и {ук} есть последовательности точек испытаний, порождаемые, АЛН в ходе минимизации непрерывных функций Их), х е [а, Ь] и в (у) - £(у) + «Л (у) , у « [а,Ь] ,

где Л (у) - ограниченная функция. Обозначим аа {Ьк} и {х1*} последовательности номеров интервалов, содержащих новые точки хк*' и у1"1 из {хк} и {у"), соответственно. Тогда, для любого ксуществует номер > 0 такой, что для функций О (у) с | 5 | 5 8к следует

Ь (V) х (1^) , О з I» а к,

если Мй) - единственный номер, удовлетворяющий следующим условиям на итерациях V, 1 а V а к,

» агдт1п { М (х) : 1 а 1 а V } , М(МУ) ) < М(1) , 1 * Ы1>) .

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

В § 2.4. предлагаются методы с лонапьной настройкой для решения задач, где возможно вычисление первых производных, причем, для них выполняется условие (7). Вместо оценивания глобальной константы Липшица Ь из (7), предлагается оценивать локальные константы Липшица для пёрвых производных. Вводится алгоритм с производными, использующий новые негладкие вспомогательные функции и локальную настройку (НОЛИ). Теоремы 2. 13 - 2. 1В описывают его свойства сходимости, в частности, теорема 2. 16 и ее следствия показывают, что для глобальной сходимости необязательно точно оценивать глобальную константу Липшица (которая может быть недооценена), а достаточно иметь точные данные лишь . о локальной константе Липшица для подынтервала, содержащего точку''** на к-ой итерации.

В этом же параграфе строятся новые, гладниа на всем интервале [а,Ь), вспомогательные функции, лучше приближающие г (х), чем негладкие огибающие, рассмотренные ранее при работе с ПАП и НОЛИ. На их базе предлагается некоторая общая схема построения алгоритмов для решения задачи (2), (7), допускающая распараллеливание, используя ПСХА подход. Рассматриваются три ноннретных метода, работающих с : априорно заданной константой

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

Глава третья - "Параллельные методы и схемы решения многомерных задач глобальной оптимизации". Основное внимание здесь уделено решению следующей задачи глобальной оптимизации Ф* ' Ф(у*) - mjg ф(у), (в)

D - { у « R": а * yt a blf 1 s i а N } , (9)

где у - (у,,.. ..у^).

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

В § 3.1 рассматривается первый подход к параллельному решению оадачи (8), (9), основанный на известной многошаговой схеме минимизации вложенных одномерных подзадач

min ф(у) » min ... min ф(у , ...у^), (10)

у в D a dy sib . * Äy Sb

1 'l t к *к к

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

при помощи ПСХА метода. При ótom вводится вектор уровней распараллеливания

Ч - («ij. Чг.....q„h (Ш

-Jé-

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

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

у «Т1п,ы .....Уп-г'У^'

где 'У^ • • • < ^ " фиксированы. Использование параллельного алгоритма с вектором (11) по схеме (10) позволяет привленать

для решения задачи (8) , (9) до 0 параллельно работающих

-1

процессоров, которые решают до Оц"' одномерных подзадач

минимизации, где и

О « П а.

1 «1

На примере параллельного многошагового информационно-статистического алгоритма устанавливаются условия (см. теорему 3. 1), при которых возможно беэызбыточиое использование до 2м параллельно проводящих испытания процессоров, где N - размерность задачи (8), (9), при использовании ПСХА методов в совокупности со схемой (10).

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

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

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

§ 3.2. посвящен построению параллельных алгоритмов с редукцией размерности при помощи разверток типа кривой Пеано. При этом решение многомерной задачи (В), (9) сводится и минимизации одномерной функции ф(у(х)) в метрике Гельдера min Ф1у) « min 4(у(х)), (12)

у€ D ««10,11

причем, если многомерная функция Ф (у) удовлетворяет условию Липшица с константой L, то ф(у(х)) удовлетворяет на отрезке [0,1] условию

|«(у(х')) - #(у<х")')| * К|х' - х"}1". (13)

где константа' Гельдера К соответствует раэвертне У(х), вычислительная схема которой обоснована Р. Г. Стронгиным.

Представлена схема использования ПСХА методов для решения задачи (12), (13). На примере обобщенного ПИЛ рассматриваются условия сходимости (теорема 3.4) и безубыточного распараллеливания (теорема 3.5) ПСХА метопов.

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

min { ^(х) : х с D, gt(x) * 0, islam}, где D из (9), . а левые части ограничений g( (х), isism, и Функция ФЫ) удовлетворяют условиям Липшица с соответствующими константами К, lsism+l,' строится обобщенный асинхронный параллельный индексный алгоритм, достаточные условия сходимости которого описывает теорема 3. 6.

Для ускорения процесса поиска решения задачи (12), (13) применяется техника локальной настройки, .введенная в § 2.3 и строится обобщенный информационно-статистический алгоритм с локальной настройкой. Теоремы 3.7, 3.8 описывают свойства сходимости метода и устанавливают взаимосвязь между сходимостью к глобальному минимуму х* одномерной редуцированной задачи (12), (13) в метрике Гельдера и сходимостью к решению у* исходной многомерной проблемы (8), (9).

В §3,3 вводятся новые многомерные схемы деления гиперинтервалов - разбиения,с глобальными связями, позволяющие :

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

- проводить адаптивное оценивание глобальной или локальных констант Липшица (чего не позволяют схемы Пиявского, Бреймана-Катлер и Жумар-Херманн-Ребо) ;

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

обеспечить экономное хранение данных при многомерном поиске.

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

Четвертая глава - "Численные примеры и решение практических задач". В первом Параграфа главы мы приводим результаты численных экспериментов, выполненных на параллельном 4-х процессорном мини-суперкомпьютере ALLIANT.FX/80. На ряде тестовых задач, взятых ! из литературы, иллюстрируются теоретические утверждения, полученные, для рассмотренных параллельных алгоритмов в предыдущих главах.

§ 4.2 содержит • описание задачи определения моментов переключении в электротехнических и электронных устройствах, которая часто возникает на практике. Известно (см. работы X, Вейса, П. Даромте, Ж. Фумо), что эта задача эквивалентна задаче нахождения ¡первого слева корня (ПСК) уравнения $(t)«О, где Функция времени

«<t>, t « ta,bj, *(а) > О, многоэкстремальна и имеет производные удовлетворяющие условию Липшица. Функция ф (t) представляет собой некий сигнал или," в

-JJ-

более широком смысле, характеристику работоспособности некоторой математической модели или устройства. Устройство является работоспособным, пока <р (t) >0.

В этом параграфе строится новый алгоритм нахождения первого слева корня (АПК), базирующийся на идеях ПСХА методов глобальной оптимизации. В качестве базы для АПК используются такие ПСХА методы как ПАП (см. § 2.2) и НОЛИ (см. § 2. 4). Рассматриваются два конкретных практических примера применения АПК : нейронный АЦ конвертер, в состав которого входит переключаемая сеть и некоторая преобразовывающая система.

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

t* = min { t* s IsisN }, (14)

где t* есть ПСК для каждого из N устройств.

Предлагается новый метод решения задачи (14),-основанный на идее одновременного анализа тестируемых с помощью АПК сигналов путем сравнения их текущих решений в процессе поиска. Численные результаты показывают преимущество новой техники по сравнению с методами, использовавшимися ранее.

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

В основе РНС лежат две простыв идеи:

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

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

-¿г-

(т. е. более достоверную) информацию и с болев низкой - на процессор с устаревшей информацией о его состоянии.

Эффективность РНС была протестирована на ПАЛМ (ПАраллельной Логической Машине), являющейся параллельным интерпретатором логических программ, где число активизируемых пронес-сов (задач) может быть очень велико (от 1000 до 100000). РНС был написан на языке OCCAM в среде ПАЖ и апробирован на системе из 32-х транспьютеров Т800/25 МГц.

Приложение содержит таблицы критичесних значений параметров МАЛИ, при которых происходит смена структур минимизирующих последовательностей для класса линейных Фуу^ций, акт о внедрении результатов диссертации в учебный процесс в Нижегородском университете, a Vara® описок сокращенных названий алгоритмов:'

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

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

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

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

4. Построены асинхронные параллельные алгоритмы решения

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

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

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

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

8. Разработанные алгоритмы глобальной оптимизации реализованы и прошли опытную эксплуатацию на 4-х процессорном мини-суперкомпьютере ALLIANT FX/80. Методы были использованы для решения проблем надежности моделей и обработки сигналов в задачах электротехники. Построена инструментальная система поддержки диалога "пользователь - ЭВМ" для задач принятия решений.

По теме диссертации опубликованы 53 работы. Основное содержание диссертации отражено в публикациях, перечисленных ниже.

1. Стронгин Р. Г. , Сергеев Я. Д. Имитация вычислений в многопроцессорной среде (на примере решения многоэкстремальных задач). -Горький: Горьн. ун. -т, 1988.

2. Сергеев Я. Д. О распараллеливании алгоритма глобальной оптимизации // Оптимизация и моделирование: Межвуз. сб. тр. / Под ред. А. В. Сергиевского. Горький: Горьк. ун. -т, 1988. С. 4S -52.

3. Сергеев Я. Д., Стронгин Р. Г. Алгоритм глобальной минимизации

о параллельными итерациями // Журн. выЧисл. матем. и матем. фиэ. 1989. Т. 29, М; 3. С. 332-345.

4. Сергеев Я. Д. Одномерный детерминированный алгоритм глобальной минимизации /1 Журн. вычисл. матем. И матем. фиэ. 1995, Т. 35, №5. С. 705-717.

5. Strongin R.G., Sergeyev Ya.D. Effective algorithm for go-bal optimization with parallel computations // Lecture No-уев in Economics and Math. Systems, Vol.304. Springer-Her-lag.'Berlin Heidelberg. 1988 . P.158-162.

6. Gergel V.P., Sergeyev Ya.D., Strongin E.G. A parallel method for global optimization and its implementation on a transputer system Ц Report no.90-04. Lyngby. Technical University of Denmark.1990. 23 p.

7. Sergeyev Ya.D., Grishagin V.A. 1991 A parallel method for finding the global minimum // Report no.114. Rende (CS) . University of Calabria, Dip. Syst.1991. 28 p.

8. Grishagin V.A., Sergeyev Ya.D,, Strongin RiG. An approach to the creation of parallel characteristical algorithms for global optimization // Report no.107. Rende (CS). University of Calabria, Dip. Syst.1991. 10 p.

9. Cannataro M., Sergeyev Ya.D., Spezzano G., Talia D. Probabilistic load balancing strategy with the neighbourhood synchronization // Technical Report no.92-03. CRAI. 1992. 28 p.

10.Sergeyev Ya.D. A one-dimeneional global minimization algorithm using local estimation of Lipschitz constant // Report no.28, Rende (CS). University of Calabria, DEIS. 1992. 19p.

11. Sergeyev Ya.D. An information global optimization algorithm with local tuning // Report no.29, Rende (CS). University of Calabria, DEIS. 1392. 19p.

12.Strongin R.G., Sergeyev Ya.D. Global multidimensional optimization on parallel computer // Parallel Computing. 1992. No.18. P.1259-1273.

13.Gergel V.P., Sergeyev Ya.D., Strongin R.G. A parallel global optimization method and its implementation on a transputer system // Optimization. 1992. No.26. P. 261-275.

-J6~

14 .Cannataro M., Sergeyev Ya.D., Spezzano G., Talia D. A dynamic load balancing strategy for massively parallel computers // Proc. of the 5-th PARLE Conference, Springer-Verlag, Berlin Heidelberg. 1993. P.664-667.

15.Sergeyev Ya.D., Grishagin V.A. A parallel algorithm for finding the global minimum of univariate functions // Journal of Optimization Theory and Applications. 1994. Vol.80. No.3. P.513-536.

16.Sergeyev Ya.D., Grishagin V.A., Sequential and parallel global optimization algorithms // Optimization Methods and Software. 1994. Vol.3 .. P. 111-124 .

17.Cannataro M., Sergeyev Ya.D., Spezzano G., Talia D. PNS : A dynamic mapping strategy for massively parallel computers // Computers & Artificial Intelligence. 1994. Vol.13. No.5. P.477-494.

18.Sergeyev Ya.D. "Divide the best" algorithms for global optimization // Report no.2/94, Rende (CS). University of Calabria, Dip. of Math. 1994. 14p.

lS.Markin D.I,., Sergeyev Ya.D. An information algorithm with local tuning for solving global optimization problems with nonlinear constraints // Report no.t/94, Rende (CS), University of Calabria, Dip. of Math. 1994. 14p.

20.Gergel V.P., Sergeyev Ya.D. Sequential and parallel global optimization algorithms using derivatives // Report no.7/94, Rende (CS), University of Calabria, Dip. of Math. 1994. 14p.

21.Sergeyev Ya.D. A global optimization algorithm using derivatives and local tuning // Report no.l, ISI CNR, Rende (CS). 1994. 24p.

22.Sergeyev Ya.D. Global optimization algorithms using smooth auxiliary functions // Report no.5, ISI CNR, Rende (CS) . 1994. 33p.

23.Sergeyev Ya.D. A multidimensional global optimization algorithm using derivatives and local tuning // Report no.6^, ISI CNR, Rende (CS) . 1994. 23p.

24.Sergeyev Ya.D. On symmetric' exponential sums // Report no.7, ISI CNR, Rende (CS) . 1994. lip. .

25.Sergeyev Ya.D. An algorithm for finding the global minimum of multiextremal Lipschitz functions // Operations Research' 93, eds. A. Bachem, U. Deriga, M. Junger, R. Schräder, Phyaica-Verlag, Heidelberg. 1994. P.4S3-465.

26.Daponte P., Grimaldi D., Molinaro A., Sergeyev Ya.D. An algorithm for a reliable search of switching times // In Proc. of the International workshop on advanced math, methods in electrical and electronic measurements, Progetto Leonardo, Bologna. 1995. P.229-240.

27.Molinaro A., Sergeyev Ya.D. Finding zero crossing pointB in electrotechnical problems // Report no.9, ISI CNR, Rende (CS). 1995. 16p.

28.Sergeyev Ya.D, An information global optimization algorithm with local tuning // SIAM Journal on Optimization. 1995. Vol.5. No.4. P.1-17.

2 9.Daponte P., Grimaldi D., Molinaro A., Sergeyev Ya.D. An

algorithm for finding zero crossing of time signals with Lipschitzean derivatives // Measurement. 1995. Vol.16. No.1. P.37-49.

3 0.Sergeyev Ya.D., Markin D.L., An algorithm for solving glo-

bal optimization problems with nonlinear constraints // Journal of Global Optimization. 1995. Vol.4. No.4. P.407-419.