Симплексный метод поиска

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

Зная значения функции в вершинах симплекса, легко определить направление, в котором функция может улучшиться. В этом направлении строится новый симплекс: определяется самая худшая вершина (по значению функции) и она отражается через центр противолежащей грани (см рис.). В построенном симплексе значение функции неизвестно только в вершине 4. Таким образом, после построения нового симплекса функция вычисляется всего один раз при любой размерности пространства. Лишь в начальном симплексе необходимо вычислять функцию во всех вершинах. Последовательное отражение наихудших вершин перемещает симплекс в направлении уменьшения значения функции, что в конечном итоге приводит к отысканию минимума с заданной точностью. Отражение вершин показано пунктирными линиями. Сначала отражается вершина 1, затем в полученном симплексе отражается вершина 3, симплекс 2,4,5 заменяется на 4,5,6 и так далее. В процессе движения, особенно вблизи экстремума, новая вершина может оказаться не лучше отраженной. Для предотвращения зацикливания либо отражается другая вершина, либо уменьш-ся размер нового симплекса.

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

где i – номер вершины, j – координата вершины (индекс переменной), n – число переменных (размерность пространства), а приращения d ₁ и d ₂ зависят от n и выбранного масштабного множителя m:

При m =1 все ребра имеют единичную длину. Вычисление координат новой вершины, получающейся в результате отражения одной из вершин последнего симплекса: Пусть отражается вершина k. Тогда сначала определяется центр противолежащей грани C: а затем координаты новой вершины s:

x ^{( s )} = x ^{( k )} + l ×(x ^C – x ^{( k )}) или x ^{( s )} = x ^С + q ×(x ^C – x ^{( k )}), где l >0 и q – параметры отражения.

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

 

Значения коэффициентов отражения были подобраны экспериментально: a = 1; b = 0,5; g = 2. Предложены и другие наборы значений, однако они дают лучшие результаты только в частных случаях. В алгоритме Нелдера-Мида используются три вершины: А – с наибольшим значением целевой функции (худшая), В – со следующим значением и L – с наименьшим значением (лучшая). Всегда отражается вершина А. Сначала производится нормальное отражение. Получаемая в результате точка D считается временной. Далее идут проверки:

· если f^L<f^D<f^B, нормальное отражение приемлемо и временная точка фиксируется;

· если f^B £ f^D < f^A, то выполняется сжатие с q =b и фиксируется точка D_b;

· если f^D ³ f^А, симплекс сжимается с q =–b и фиксируется точка D_–b;

· если f^D < f^L, то производится растяжение (q =g), дающее точку D _g, которая фиксируется, если она не хуже временной; иначе она не учитывается и фиксируется временная точка.

В условии останова поиска может использоваться показатель размера симплекса, например, максимальная длина ребра, и/или разность значений целевой функции f^А – f^L.

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

Интересен вариант метода, в котором на всех итерациях симплекс остается регулярным. В нем используется коэффициент уменьшения длины ребра b ³ 0,85. Симплекс сжимается, стягиваясь к лучшей вершине, как показано на рис, и после этого происходит отражение. Такое значение b обусловлено тем, что на вершины уменьшенного симплекса переносятся значения функции соответствующих вершин до сжатия. Тем самым исключаются дополнительные вычисления функции. Возможно также увеличение симплекса за счет удлинения всех ребер с коэффициентом 1/ b при сохранении положения наихудшей вершины.