Разработка программы метода деформируемого многогранника Нелдера-Мида

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

ВЫВОДЫ

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

Данный метод состоит из трех основных этапов: построение начального многогранника, отражение худшей вершины многогранника, переход к новому многограннику. Рассмотрим содержание этих этапов.

I. Построение начального многогранника.

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

, , .

Во всех вершинах многогранника вычисляются значения целевой функции:

, .

На этом первый этап метода заканчивается, и переходят ко второму этапу.

II. Отражение худшей вершины.

1. Определение лучшей и худшей вершин. Определяются индекс лучшей вершины с наименьшим значением функции (- low, низкий) и индекс худшей вершины с наибольшим значением функции (- high, высокий):

, .

Для лучшей и худшей вершин, а также для значений в них функции вводятся обозначения:

, , , .

Худшая вершина обозначена через (- worse, худший).

2. Проверка критерия останова. Определяется размер многогранника по разностям координат всех вершин и лучшей вершины:

.

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

3. Определение центра лучших вершин. Находится центр вершин многогранника за исключением худшей вершины

.

4. Отражение худшей вершины. Отражение худшей вершины выполняется по такой же формуле, как и в методе симплексного поиска:

, .

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

III. Переход к новому многограннику.

1. Растяжение многогранника. Точка отражения сравнивается с лучшей вершиной многогранника. Если , то аналогично отражению выполняется растяжение многогранника по формулам

, .

Точка растяжения , симметричная точке относительно точки отражения , сравнивается с точкой отражения . При этом возможны следующие случаи.

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

1.2. Неудачное растяжение. Если же , то худшая вершина заменяется точкой отражения . При этом полагают , .

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

2. Удачное отражение. Если точка отражения не лучше лучшей вершины многогранника , но за исключением худшей вершины существуют и другие вершины, худшие , то худшая вершина многогранника заменяется точкой отражения . Это означает, что

(, , ).

При этом полагают , и возвращаются ко второму этапу метода.

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

, , .

При этом возможно внешнее или внутреннее сжатие многогранника.

3.1. Внешнее сжатие. Если , то сжатие выполняется по формулам:

, .

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

3.2. Внутреннее сжатие. Если , то формулы сжатия

, .

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

3.3. Редукция многогранника. Если точка сжатия хуже худшей вершины многогранника или точки отражения, то выполняется редукция (уменьшение) многогранника по формулам:

, , , .

После этого возвращаются ко второму этапу метода.

На этом заканчивается третий этап метода Нелдера-Мида.

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

1.2 Алгоритм метода деформируемого многогранника Нелдера-Мида