Детерминированные фильтрующие алгоритмы глобальной оптимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

1 Помехоустойчивость методов нелинейной оптимизации

1.1 Метод градиентного спуска.

1.2 Метод разностной аппроксимации градиента

1.3 Метод покоординатного спуска.

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

2 Фильтрующие алгоритмы локального поиска в глобальной оптимизации

2.1 7-регулярные задачи глобальной оптимизации.

2.2 Фильтрующие свойства метода разностной аппроксимации градиента.

2.3 Фильтрующие свойства метода покоординатного спуска

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

3 Численная реализация фильтрующих алгоритмов

3.1 Реализация алгоритмов в параллельной среде.

3.2 Пример 1.

3.3 Пример 2.

3.4 Пример 3.

3.5 Задача Леннарда-Джонса.

3.6 Задача в кубе.

Глобальная оптимизация имеет непосредственное отношение к широкому классу практических задач. В качестве примеров можно привести: решение проблемы оптимизации технологических процессов, направленной на максимальное увеличение выхода годных изделий и разработки продукции высоких технологий [69]; поиск устойчивой структуры многоатомных молекул и молекулярных кластеров при синтезе высокомолекулярных соединений [45], [60]; моделирование и анализ явлений в верхних слоях атмосферы [59] и другие.

Без ограничения общности рассматривается следующая математическая постановка задачи глобальной оптимизации:

V : F(x) -> min, v ' хех где Rк ~ к - мерное Евклидово пространство, а Т : R& —Ri многоэкстремальная функция цели, непрерывная на множестве X С R&.

В качестве приближенного решения требуется найти точку х G Xopt (е) для достаточно малого е. Здесь

Xopt{e) := {х е Rfcl^x) < fopt + е}, fopt := штТ(х).

Для данной задачи невозможно предложить универсального метода решения, эффективность которого не зависит от свойств Т и X.

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

X = Rk, (В.1)

Х = Ш1], (В.2) i=i

Класс задач с математической постановкой V, при условии (В.1) или (В.2) достаточно широк. Известно также, что при помощи метода штрафных функций к нему можно свести ряд задач условной оптимизации [1],

Н, [4].

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

Обычно, глобальный минимум J7^) предлагается найти, перебрав все без исключения локальные минимумы. Другой способ - показать, что упущенные из рассмотрения локальные минимумы не оказывают большого влияния на точность решения задачи. Ниже приведены несколько примеров современных методов решения задач глобальной оптимизации. Детальное описание существующих методов можно найти в [37], [39], [49], [65], [73].

Метод мультистарта (multistart method) [66] является не просто алгоритмом, а, скорее, обобщенным подходом. В случае многоэкстремальной функции цели для решения задачи предлагается применять известные алгоритмы локальной оптимизации, используя не одну, а множество точек начального приближения. Наиболее простым примером такого множества является N случайных точек области определения X (методы случайного поиска) или N, определенным (детерминированным) образом вычисленных, точек, представляющих собой разбиение в X. В результате дальнейшего применения локальных алгоритмов спуска определяется N точек локального минимума. В качестве приближенного решения исходной задачи выбирается наилучший из полученных результатов. Такой прием можно принять за одну итерацию метода и повторять его многократно для повышения точности решения задачи.

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

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

Параметрическая оптимизация [43], [51], в частности, метод продолжения [7], [12], предлагает строить так называемые квазиоптимальные траектории, соединяя все локальные минимумы не упуская ни одного из них. Данный метод основан на использовании глобальных свойств структуры множеств Куна-Таккера и заключается в последовательном решении ряда задач оптимизации размерности п : п = 1,2,— 1. Построение квазиоптимальных траекторий ведется по схеме предиктора-корректора с использованием локальных алгоритмов спуска.

Метод покрытий [5], [38] для каждого найденного локального минимума оценивает предельное изменение значения функции на ограниченном множестве, исходя из того, что градиент целевой функции удовлетворяет условию Липшица. В результате становится возможным "покрыть" область определения X ^-мерными шарами. В процессе создания покрытия каждому шару сопоставляется нижняя граница значений функции цели. Радиус составляющей покрытия выбирается из такого расчета, чтобы исключить область шара из рассмотрения, так как значение функции цели внутри него не может быть меньше текущего рекорда.

Другой метод, [44], для каждого найденного локального минимума выделяет область (domain of attraction), в которой траектории алгоритма локального поиска сходятся к данному минимуму. Область исключается из дальнейшего рассмотрения. Следующая точка начального приближения выбирается вне описанной области. Таким образом, шаг за шагом, определяются все локальные минимумы.

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

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

Методы прямого поиска [36], [71] в качестве локального алгоритма спуска включают в себя модифицированный симплексный метод [58].

На этапе локального поиска предлагается использовать методы решения задач с одно-экстремальной непрерывной функцией цели. Каждый такой метод гарантирует сходимость своих траекторий к окрестности локального минимума при выполнении J-{-) определенных условий.

Известно, если функция цели дважды дифференцируема и ее градиент удовлетворяет условиям Липшица, необходимым и достаточным условием существования локального минимума является равенство нулю градиента и положительная определенность ее гессиана. Построенные на этом принципе классические детерминированные методы, такие как методы градиентного спуска (1-го порядка) и методы ньютоновского типа (2-го порядка), сходятся к окрестности точки локального минимума. Существующие методы прямого поиска (0-го порядка) не требуют диффе-ренцируемости •?■"(■), но, как правило, при исследовании сходимости таких методов ссылаются на существование градиента функции цели и выполнение им условий Липшица [1].

Описание детерминированных методов локального поиска для решения задач глобальной оптимизации, в которых функция недиффе-ренцируема можно найти в работах [33], [34], [36], [57], [71]. Существенно расширяет применение детерминированных алгоритмов оптимизации инструмент обобщенных дифференциалов [32] и теория квазидифференци-руемых функций [3].

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

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

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

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

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

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

Р : Fix) min, v ' хек где Rfc обозначает fc-мерное Евклидово пространство, а функция F{x) непрерывно дифференцируема на R& и ее градиент XjF{-) удовлетворяет условию Липшица с некоторой константой L > 0:

S7F(-)eCLip(Rk,L). (В.З)

Определение 1 Будем называть функцию F(x) регулярной функцией с параметрами 77, б, //, L > 0 и М 6 {1,2,.}, обозначая,

F(-) (В.4) если выполнены следующие условия:

1) функция цели F{x) : R& —У Ri непрерывно дифференцируема на R^ и выполнено условие (В.З);

2) множество стационарных точек функции F{x) конечно

Xstat = Xstati0) = {%ltati •••> ®*fai}> \Xstat\ =

3) в некоторой ту-окрестности множества Xstat существует гессиан Н = F"{x) функции F(x) и он невырожден ця-1!! < 1 /V Ух е где

Ве(Х) := {х е Rjfcl Зх' Е X : \\х - ж'|| < е}\

4) ^-стационарное множество

Xstat(e) := G Rib 11| V F(x)\\ < e}, (B.5) ограничено для любого г > 0;

5) для некоторого е > 0 и для г) > 0 из п.З) выполнено

Х*ьи(е) С Bv{Xstat). (В.6)

Решение задачи Р находится путем сравнения результатов решения М задач локальной оптимизации в B£(xlstat), г = 1,., М.

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

Для задач Р в предположении, что F(-) - регулярная функция с параметрами г}, б, fi, L > 0 и М (Е {1,2,.} [17], вводится обозначение

P€P(r),e,/i,L,M). (В.7)

О взаимосвязи параметров регулярности rj, б, fi и соответствующих свойствах функции F(-) говорит следующая лемма.

Лемма 2 Пусть F(-) 6 Щг], е, ц, L, М), тогда справедливы утверждения

1) Для любого е, 0 < е < б, множества связны.

2) Для любого г — 1,., М V F(x)|| > (1 /у) ||® - х\ш\\ Мх G □

Возвращаясь к решению задачи V (В.1), к параметрам г/, б, /л, L,M предлагается добавить еще один, 7, в качестве характеристики незначительных экстремумов функции цели. Предполагается, что экстремумы глубиной 7 > 0 можно исключить из рассмотрения при решении задачи

Рисунок 1: Функция цели Т{х) 7-регулярной задачи V поиска глобального минимума функции Т. Исследования глобальной выпуклой структуры подобного рода проводились [50], [81].

Для обозначения многоэкстремальной функции цели задачи V, близкой к некоторой регулярной функции F(-) (см. Рисунок 1) вводится следующее определение.

Определение 3 Функция х), х G Rfc, называется функцией 7- регулярной структуры с параметрами 77, е, /i, L > 0 и М Е N, если существует такая регулярная, с теми же параметрами функция F(-) € Щг), е, д, L, М), для которой выполнено

F{x) - F(x)| < 7 Vx G Rfc. (В.8)

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

Соответствующая целевой функции F{x) регулярная скелетная функция F(x) явно не задана в условии задачи и является только характеристикой свойств функции Т(х). В то же время, существование F{x) позволяет расширить применение метода мультистарта для решения задачи V.

В рамках данного подхода остается оценить множество предельных точек фильтрующих алгоритмов оптимизации, определяя его положение относительно Xstat — uf£i Xltat ~ "главного" стационарного множества задачи V (см. Рисунок 1).

Построение и обоснование сходимости фильтрующих алгоритмов глобальной оптимизации основано на свойствах помехоустойчивости классических методов локального спуска. Первая часть работы посвящена изучению помехоустойчивости метода разностной аппроксимации градиента и метода покоординатного спуска. Вторая часть проводит исследование сходимости перечисленных алгоритмов при решении 7 - регулярной задачи V с параметрами 7, 77, e, L, М. Структура предложенных алгоритмов позволяет выполнить декомпозицию вычислительного процесса. Следовательно реализацию алгоритмов предложено провести в условиях параллельной среды.

Диссертация состоит из введения, трех глав, заключения и приложений.

Основные результаты работы.

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

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

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

Заключение

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

2. Гроссман К. Т, Каплан А.А. Нелинейное программирование на основе безусловной оптимизации. Новосибирск: Наука, Сибирское отд., 1981.

3. Демьянов В.Ф., Полякова JI.H. Условия минимума квазидиффе-ренцируемой функции на квазидифференцируемом множестве // Ж.вычисл.матем. и матем. физики, 1980, т. 20, N4, с.849-856.

4. Демьянов В. Ф. Точные штрафные функции в задачах негладкой оптимизации. Вестн. С-Петербург. ун-та, 1994, N4.

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

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

7. Завриев С. К. Конечные алгоритмы метода продолжения в задачах выпуклой параметрической оптимизации // Обратные задачи математического программирования, ВЦ РАН, Москва, 1992.

8. Завриев С. К. Помехоустойчивость методов нелинейной оптимизации: Диссертация на соискание ученой степени д.ф.м.н., ИПК РАН, Москва, 1993.

9. Завриев С. К., Перунов а Ю.Н. Об использовании конечных разностей в методе мультистарта для решения некоторого класса задач глобальной оптимизации // Вестн. Моск. ун-та, серия 15, N 3, 1997, с. 31-35.

10. Завриев С.К., Перунова Ю.Н. Помехоустойчивость алгоритма покоординатного спуска при распараллеливании // Электронный журнал: Исследовано в России, 2002. 50. С.540-554. http://zhurnal.ape.relarn.ru/articles/2002/050.pdf.

11. Завриев С.К., Орлянская И.В., Перунова Ю.Н. Об одном подходе к конструированию алгоритмов продолжения в глобальной оптимизации // Вестн. Моск. ун-та, № 2, 2000, с. 15-19.

12. Orlyanskaya I.V., Perunova Y.N., Zavriev S.K. An Implementation of the Parallel Continuation Algorithm for Global Optimization / Сборник трудов 2-ой Московской международной конференции по исследованию операций, 1998. С.59-60.

13. Карманов В.Г. Математическое программирование. 3-е издание. М.: Наука, 1986.

14. Михлевич В. С., Гупал А. М., Норкин М. И. Методы невыпуклой оптимизации. М.: Наука, 1987.

15. Орфали Р., Харки Д., Эдварде Дж. Основы CORBA. пер. с англ., Москва, "МАЛИП",1999.

16. Перунова Ю.Н. Помехоустойчивость методов разностной аппроксимации градиента при распараллеливании // электронный журнал Исследовано в России, 156, с.1782-1791, 2001, http://zhurnal.ape.relarn.ru/articles/2001/156.pdf.

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

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

19. Тихонов А.Н. , Арсенин В.Я. Методы решения некорректных задач. Москва, Наука, 1986.

20. Цимбал А.А. Технология CORBA для профессионалов. СПб: Питер 2001.

21. Сеа, Ж. Оптимизация. Теория и алгоритмы. М.: Мир, 1973.

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

23. Сухарев, А.Г. Глобальный экстремум и методы его отыскания. М.: Изд. МГУ, 1981.

24. Anderson E.J., Ferris, М.С. A direct search algorithm for optimization with noisy function evaluatons // SIAM J.Optimization, 11, 3, 837-857, 2001.

25. Bertsekas D.P., Tsitsiklis J.N. Parallel and Distributed Computation: Numerical methods. Prentice Hall, Englewood Cliffs, N.J. 1989.

26. Bertsekas D.P., Tsitsiklis J.N. Gradient convergence in gradient methods with errors // SIAM J.Optimization, 10, 3, 627-642, 2000.

27. Basaraa M. S., Shetty С. M. Nonlinear Programming. Theory and Algorithms. John Wiley & Sons, New York, 1979.

28. Boggs P. Т., Dennis J. E., Jr. A Stability Analysis for Perturbed Nonlinear Iterative Methods // Mathematics of Computation 30 (134), 199-215, 1976.

29. Boggs P. Т., Kearsley A. J., Tolle J.W. A Global Convergence Analysis of an Algorithm for Large-Scale Nonlinear Optimization Problems // SIAM J.Optimization, 9, 4, 833-862, 1999.

30. Byrd R., Eskow E., Schnabel R. A New Large-Scale Global Optimization Method and its Application to Lennard-Jones Problems. Technical Report CU-CS-630-92, Department of Computer Science,University of Colorado at Boulder.

31. Clarke F. H. Optimization and Nonsmooth Analysis. John Wiley & Sons, New York, 1983.

32. Conn A.R., Toint P.L. An algorithm using quadratic interpolation for unconstrained derivative free optimization. In: Nonlinear Optimization and Applications, G.D.Pillo and F.Gianessi (Eds.), Plenum Press, New York, pp. 27-47, 1996.

33. Conn A.R., Scheinberg K., Toint P.L. On the convergence of derivative-free methods for unconstrained optimization. In: Approximation Theory and Optimization, M.D.Buhmann and A.Iserles (Eds.), Cambridge University Press, Cambrige, pp. 83-108, 1997.

34. Csendes Т., Ratz D. Subdivision Direction Selection in Interval Methods for Global Optimization // SIAM J.Numerical Analysis, 34, 3, 922-938, 1997.

35. Dennis J.E.Jr, Torczon V. Direct search methods on parallel machines // SIAM J.Optimization, 1, 4, 448-474, 1991.

36. Dixon L.C.W., Szego G.P. (Eds.) Towards Global Optimization 2. North-Holland, Amsterdam, 1978.

37. Evtushenko Yu.G. Numerical methods for finding global extrema // USSR Computational Mathematics and Mathematical Physics 11, 13901403, 1971.

38. Floudas, C.A., Pardalos, P.M. (eds) Recent Advances in Global Optimization. Printon University Press. Prinston. USA, 1992.

39. Floudas, C.A., Pardalos, P.M. A Collection of Test Problems for Constrained Global Optimization Algorithms. Springer-Verlag, Berlin, 1998, 155.

40. Masao Fukushima Parallel variable transformation in unconstrained optimization // SIAM J.Optimization, 8, 4, 658-672, 1998.

41. Dong-Hui Li, Masao Fukushima On the Global Convergence of the BFGS Method for Nonconvex Unconstrained Optimization Problems // SIAM J.Optimization, 11, 4, 1054-1064, 2001.

42. Guddat J., Vasquez F., Jongen H.Th. Parametric Optimization: Singularities, Pathfollowing and Jumps. Willey, 1990.

43. Hassan A.M. Extention of Zubov's Method for the Determination of Domains of Attraction: Ph.D. Thesis, Loughborough University of Technology, 1982.

44. Neumaier A. Molecular Modeling of Proteins and Mathematical Prediction of Protein structure // SIAM Review, 39 3, 407-460, 1997.

45. Hirsch M. W. Differential Topology. Springer Verlag, New York, 1976.

46. Hoare M. Structure and Dynamics of Simple Microclusters. Advances in Chemical Physics 40, 49-135, 1979.

47. HookeR., Jeeves T.A. Direct search solution of numerical and statistical problems // J.ACM, 8, 212-229, 1961.

48. Horst R., Tuy H. Global Optimization; Deterministic Approaches. Springer-Verlag, Berlin, 1990.

49. Ни Т. С., Klee V., and Larman D. Optimization of Globally Convex Functions // SIAM J. Control and Optimization 27 (5), 1026-1047,1989.

50. Jongen, H.Th. Parametric Optimization:Critical Points and Local Minima // Lectures in Applied Mathematics, 26, 317-335, 1990.

51. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by Simulated Annealing // Science, 220, 4598, 671-680, 1983.

52. Levy A. V., Montalvo A. The tunneling algorithm for the global minimization of functions algorithm // SIAM J. Sci. Stat. Comput., 6, 1, 15-29, 1985.

53. Luenberger D.G. Linear and Nonlinear Programming. Addison-Wesle, London, 1984.

54. Mangasarian O.L. Parallel gradient distribution in unconstrained optimization // SIAM J. Control and Optimization, 33, 6, 1916-1925, 1995.

55. Maranas C.D., Floudas G.A. A deterministic global approach for molecular structure determination // Journal of Chemical Physics 100(2), 15 January 1994, 1247-1261.

56. Mayne D. Q., Polak E. Nondifferential Optimization via Adaptive Smoothing // JOTA 43 (4), 601-614, 1984.

57. Nelder J.A., Mead R. A simplex Method for Function Minimization // Comput.J. 7, 308-313, 1965.

58. Nicholson J.W., Jasapara J., Rudolph W., Omenetto F.G., Taylor A.J. Full-Field characterization of femtosecond pulses by spectrum and cross-correlation measurement // Optical Society of America, 1999.

59. Northby J.A. Structure and binding of Lennard-Jones clusters:13 < N < 147 // Journal of Chemical Physics 87(10), 15 November 1987, 6166-6177.

60. O'Leary D.P., Whitman P. Parallel QR Factorization by Householder ans modified Gram-Schmidt Algorithm // Parallel Сотр., 16, 99-112, 1990.

61. Powell M.J.D. Direct search algorithms for optimization calculations // Acta Numer., 7, 287-336, 1998.

62. Polak E. Computational Methods in Optimization: A Unified Approach. Academic Press, New York, 1971.

63. Press W.H., Teukolsky S.A., Vetterling W.T. and Flannery B.P. Numerical Recipes in C. 2nd ed. Cambridge U. Press, Cambridge, 1995.

64. Ratschek H., Rokne J. New Computer Methods for Global Optimization. Ellis Horwood, Chichester. 1988.

65. Rinnooy Kan, A.E.G., Timmer, G.T. Stocastic global optimization methods // Mathematical programming. 39, 27-78, 1987.

66. Rosenbrock H. H. An Automatic Method for Finding the Greatest or Least Value of a Function // Computer Journal,3, 175-184, 1960.

67. Sturua E.G., Zavriev S.K. A trajectory algorithm based on the gradient method 1. The search on quasioptimal trajectories // Journal of Global Optimization, 1, 375-388, 1991.

68. Shenghua Shi, Herschel Rabitz Optimal control of selectivity of uni-molecular reactions via an excited electronic state // J.Chem.Phys., 97 1, 276-287, 1992.

69. Shubert B.O. A sequential method seeking the global maximum of a function // SIAM J. Numer Anal., 9, 379-388, 1972.

70. Torczon V. On the convergence of the multidirectional search algorithm // SIAM J.Optimization, 1, 4, 123-145, 1991.

71. Torn A. Global Optimization as a combination of global and local search.: Ph.D Thesis, Abo Academi, HHAA A:13, 65.

72. Torn A., Zilinskas A. Global Optimization. Springer Verlag, Berlin, 1989.

73. Torn A., Viitanen S. Topographical Global Optimization. In: C.A.Floudas and P.M.Padalos (Eds.), Recent Advances in Global Optimization, Princeton University Press, 384-398, 1992.

74. Torn A., Viitanen S. Topographical global optimization using pre-sampled points // Journal of Global Optimization, 5, 267-276, 1994.

75. Wardi Y. Stochastic algorithms for Armijo stepsizes for minimization of functions // J.Optim. Theory Appl.,64, 399-417, 1990.

76. Xue G. Molecular Conformation on the CM-5 by Parallel Two-Level Simulated Annealing // Journal of Global Optimization, 4, 187-208,1994.

77. Yong Y. Dynamic Tunneling Algorithm for Global Optimization // IEEE Transactions on systems, man, and cybernatics, 19,5, 1222-1230, 1989.

78. Zangwill W.I. Minimizing a function without calculating derivatives // Computer Journal, 10, 293-296, 1960.

79. Zavriev S. K. Convergence Properties of the Gradient Method in Presence of Perturbations of a Variable Level // USSR Computational Mathematics and Mathematical Physics 30, 997-1007, 1990.

80. Zavriev S.K. On the global optimization properties of finite-difference local descent algorithms // Journal of Global Optimization, 3, 63-78, 1993.