Детерминированные фильтрующие алгоритмы глобальной оптимизации

• Автор: Перунова, Юлия Николаевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Москва
• Количество страниц: 86 с.

Оглавление
Введение

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

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

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

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

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

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

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

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

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

2.4 Сравнение последовательных и параллельных версий модифицированных алгоритмов градиентного и покоординатного спуска
3 Численная реализация фильтрующих алгоритмов
3.1 Реализация алгоритмов в параллельной среде
3.2 Пример
3.3 Пример
3.4 Пример
3.5 Задача Леннарда-Джонса

3.6 Задача в кубе
Заключение
Приложение
Литература

Введение
Глобальная оптимизация имеет непосредственное отношение к широкому классу практических задач. В качестве примеров можно привести: решение проблемы оптимизации технологических процессов, направленной на максимальное увеличение выхода годных изделий и разработки продукции высоких технологий [69];
поиск устойчивой структуры многоатомных молекул и молекулярных кластеров при синтезе высокомолекулярных соединений [45], [60];
моделирование и анализ явлений в верхних слоях атмосферы [59] и другие.
Без ограничения общности рассматривается следующая математическая постановка задачи глобальной оптимизации:
V : Т(х) —> min,
V ’ хех’
где Rк ~ к - мерное Евклидово пространство, а Т : Ra —¥ Ri многоэкстремальная функция цели, непрерывная на множестве X С Ra-.
В качестве приближенного решения требуется найти точку х £ Xopt (г) для достаточно малого е. Здесь
Xopt{s) ■= {ж € Rfcl^(x) < fopt + е}, fopt := ттТ(х).

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

Обозначим m - число координат, рассматриваемых на каждом рабочем процессоре. В общем случае р < к, учитывая возмущение Їїо(х) Є Ri функции цели F(-) в точке а: Є Rь
||«о(®)|| < £о,
алгоритм покоординатного спуска будет иметь следующий вид. Алгоритм (р). Параметры: в,0 < в < 1,а > 2уєо/L,£stop > О,
peN,p Входные данные: х° Є Rfc.
Результат: Nstop Є N, xNstop Є R*,
Обозначим:
И - инициализация: п := 0; хп := ж0.
П - подготовка к работе: п п + 1; xf ж”-1 af := а.
Выбрать ортонормированную систему е’" из m векторов
m.n г т.п т.П'ї
е1 ~~ 1егд el,m S такую, что еп = Uf=1ep",

еп = {е",..., е|} Є Rk -
ортонормированный базис пространства Rk-Р - выполнение на I-ом рабочем процессоре, I — 1,... ,р, одной итерации метода покоординатного спуска (ПС) в рамках подпространства

Итерация метода ПС.
Шаг 1. Пусть
af := а/в
ai := 0,» = 1 ,...,к]
з? ■= 0;
Шаг 2. Если YlfLi аПі,і > 0> т0 перейти к Шагу 5.

Щ ^ &stop:
то перейти к Шагу 5, иначе: і := 0 аі — О/