Тестирование методов многомерной безусловной оптимизации

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

Методы прямого поиска основаны только на вычислении значений целевой функции. К ним относятся методы Хука-Дживса, поиска по симплексам, сопряженных направлений, случайного поиска, покоординатного спуска и др.Общая схема методов: поиск начинается в начальной точке, далее выбирается направление поиска по критерию уменьшения значения целевой функции при решении задачи минимизации, делается шаг в этом направлении. Выбор направления поиска и длины шага зависит от стратегии поиска [4,7].

В методе Хука – Дживса выделяют два действия: исследующий поиск и поиск по образцу. По результатам исследующего поиска происходит выбор направления из начальной точки. Далееиз нееделается шаг, получается пробная точка. Если значение целевой функции в пробной точке уменьшилось, то исследующий поиск удачен и осуществляется поиск по образцу. Если значение целевой функции в пробной точке больше значения функции в начальной точке, то выбирается новая пробная точка (из начальной точки делается шаг в противоположном направлении) и так происходит до тех пор, пока исследующий поиск не будет удачным. Если такого не происходит, то следует уменьшить шаг. Поиск по образцу: в случае удачного исследующего поиска, получаем пробную точку, из которой делается единственный шаг в новом направлении. Поиск продолжается до тех пор, пока величина шага не станет меньше заданной точности вычисления [4,7].

В методе поиска по симплексам, оперируют вершинами регулярного симплекса. Регулярный симплекс в N – мерном пространстве представляет собой многогранник, образованный N+1 равностоящими друг от друга точками – вершинами. Поиск начинается с построения регулярного симплекса в пространстве независимых переменных. Из вершин симплекса выбирается та, в которой целевая функция принимает наибольшее значение, происходит её проецирование через центр тяжести оставшихся вершин симплекса, получаем новую точку, а проецируемая точка исключается из рассмотрения. При плавном убывании функции, поиск продолжается до тех пор, пока не будет, найдена точка минимума, или не начнется циклическое движение по двум или более точкам симплекса. Условиями окончания поиска являются: уменьшение размеров симплекса, разность значений целевой функции в вершинах симплекса становится меньше заданной точности.

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

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

В градиентных методах требуется, чтобы исследуемая функция была дифференцируемой, в ряде случаев – дважды дифференцируемой. Общая схема методов: выбирается начальная точка, выбирается направление поиска, делается шаг. Текущее приближение к оптимальной точке вычисляется по формуле (1) [7].

^1 =x* +Q,M^)>          (1)

где x_k – текущее приближение к точке минимума, a^k – параметр, характеризующий длину шага, s ( x_k ) – направление поиска.

Способ выбора a^k и s ( x_k ) зависит от данного метода. Для определения происходит решение задачи одномерной оптимизации. Основные виды градиентных методов представлены в таблице 1.

Таблица 1. Обзор градиентных методов

В таблице 1 использованы следующие обозначения:

-Vf(xO — градиент функции в точке x_k ,

H – матрица Гессе,

I – единичная матрица,

Ak – метрика.

Таблица 2. Сравнение методов прямого поиска и градиентных

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

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