Все формулы РФ

Математика / Численная оптимизация

Отражение в методе Нелдера—Мида

Отражение в методе Нелдера—Мида даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.

Опубликовано: Обновлено:

Оптимизация и исследование операцийСтраницы с задачами и решениямиЕсть историческая справкаДиагностика условий

Формула

$$x_r=\bar x+\alpha(\bar x-x_w),\quad\alpha=1$$
Схема Отражение худшей вершины
Отражение худшей вершиныОтражение худшей вершиныx_r=(−1;−1)центр (2;1,5)x_w=(5;4)Центр — середина отрезка [x_r,x_w] при α=1.

Худшая вершина отражается через центр остальных вершин. Схема показывает коллинеарность трёх точек.

Обозначения

$x$
аргумент, состояние или вектор данных конкретной задачи, единицы исходной модели
$n,k,i,j$
целые индексы узла, шага либо компоненты, безразмерные
$ε / err$
допуск или оценка вычислительной ошибки, если она используется, единицы результата

Условия применения

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

Ограничения

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

Подробное объяснение

Симплекс хранит n+1 точек, поэтому в плоскости это треугольник. Худшая вершина x_w сравнивается с центроидом остальных вершин, а отражение предлагает точку по другую сторону от центра.

При α=1 центроид оказывается серединой отрезка между x_w и x_r. Это геометрическое равенство позволяет быстро проверить знаки в формуле без вычисления целевой функции.

Отражение — только кандидат. Если оно лучше ожидаемого, алгоритм может растянуть симплекс; если нет, применяет сжатие или редукцию. Нельзя объявлять x_r новым минимумом, не сравнив значения цели.

Метод ценен, когда градиент недоступен или ненадёжен, но на плохо масштабированных переменных форма симплекса и сравнения могут вести себя неудачно. Масштабирование координат — часть подготовки.

Центроид двух не худших вершин вычисляется покоординатно: ((1+3)/2;(2+1)/2)=(2;1,5). Вектор от худшей вершины к центроиду равен (−3;−2,5); добавление его к центроиду даёт (−1;−1). Таким образом, отражение проверяется геометрически, а не только формулой.

Как пользоваться формулой

  1. Выпишите x_r=\bar x+\alpha(\bar x-x_w),\quad\alpha=1 и отметьте искомую величину; не заменяйте её одноимённым параметром из другой модели.
  2. Подготовьте данные в требуемой форме: проверьте индексы, знак, область аргумента, нормировку либо размерность.
  3. Выполните первое задание по действиям и сохраните промежуточные значения каждого коэффициента, отношения или суммы.
  4. Проверьте результат естественным способом: симметрией, точным частным случаем, невязкой или исходным ограничением.
  5. Разберите второе задание: изменённые данные показывают границу применимости и предупреждают типичную ошибку метода.

Историческая справка

Джон Нелдер и Роджер Мид опубликовали свой симплексный метод в 1965 году как практическую процедуру оптимизации без производных. Вместо одной точки метод поддерживает геометрическую фигуру из n+1 вершин и сравнивает значения цели. Отражение — первый способ проверить противоположную сторону от худшей вершины; затем могут понадобиться растяжение, сжатие или редукция. Метод получил широкое распространение в прикладных пакетах, хотя его сходимость требует более осторожного анализа, чем у гладких градиентных схем.

Nelder и Mead опубликовали «A simplex method for function minimization» в Computer Journal в 1965 году. Работа предложила набор простых геометрических операций для случаев, где аналитический градиент функции недоступен или слишком дорог.

Историческая линия формулы

Метод назван по авторам статьи 1965 года — Джону Нелдеру и Роджеру Миду. Приведённая формула отражения является одним шагом алгоритма; сама по себе она не гарантирует уменьшения целевой функции без правил выбора следующей операции. Источник в карточке указан для различения исторического имени, публикации и современной вычислительной формы; эти уровни не следует смешивать.

Пример

Пусть в двумерном симплексе лучшая и средняя точки (1;2), (3;1), худшая (5;4). Центроид без худшей: (2;1,5). При α=1 отражение x_r=2(2;1,5)−(5;4)=(−1;−1). Центроид двух не худших вершин вычисляется покоординатно: ((1+3)/2;(2+1)/2)=(2;1,5). Вектор от худшей вершины к центроиду равен (−3;−2,5); добавление его к центроиду даёт (−1;−1). Таким образом, отражение проверяется геометрически, а не только формулой. Симплекс хранит n+1 точек, поэтому в плоскости это треугольник. Худшая вершина x_w сравнивается с центроидом остальных вершин, а отражение предлагает точку по другую сторону от центра.

Частая ошибка

Нельзя включать худшую вершину в центроид отражения. Нельзя путать α отражения с коэффициентом растяжения. Не следует выбирать новую вершину только по её координатам — сравнивают значения цели. И алгоритм не гарантирует одинаковую надёжность на гладких и негладких функциях. В разборе «Отражение в методе Нелдера—Мида» проверяют именно обозначения и условия данной записи.

Практика

Задачи с решением

Отражение через центроид

Условие. Отразите худшую точку (6;2) относительно центроида (4;3).

Решение. x_r=(4;3)+((4;3)−(6;2))=(4;3)+(−2;1)=(2;4).

Ответ. x_r=(2;4).

Отражение с alpha=0,5

Условие. При α=0,5 найдите отражение точки (4;6) от центроида (2;2).

Решение. x_r=(2;2)+0,5((2;2)−(4;6))=(2;2)+(−1;−2)=(1;0).

Ответ. x_r=(1;0).

Дополнительные источники

  • https://doi.org/10.1093/comjnl/7.4.308
  • https://www.ime.unicamp.br/~sandra/MT853/handouts/Ref3%28NelderMead1965%29.pdf

Связанные формулы

Математика

Обновление BFGS для обратной матрицы Гессе

$H_{k+1}=(I-\rho sy^T)H_k(I-\rho ys^T)+\rho ss^T,\quad\rho=(y^Ts)^{-1}$

Обновление BFGS для обратной матрицы Гессе даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.

Математика

Условия Каруша—Куна—Таккера: комплементарная нежёсткость

$\lambda_i g_i(x)=0,\quad\lambda_i\ge0,\quad g_i(x)\le0$

Условия Каруша—Куна—Таккера: дополнительная нежёсткость даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.

Математика

Симплекс-метод: правило минимального отношения

$\theta^*=\min_{i:a_{ij}>0}\frac{b_i}{a_{ij}}$

Симплекс-метод: правило минимального отношения даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.