Рассмотрим следующую многомерную задачу условной локальной оптимизации: найти минимум критерия оптимальности , определенного во множестве евклидова пространства ,

где множество допустимых значений

Метод скользящего допуска существенно использует множество

(3)

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

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

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

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

Одна итерация метода скользящего допуска состоит из одного или двух этапов:

1) С помощью базового метода, исходя из сточки , выполняем итерацию по решению задачи локальной безусловной оптимизации

(4)

- находим точку . Если (точка является допустимой точкой или почти допустимой точкой), то полагаем и заканчиваем данную итерацию.

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

(5)

с условием окончания итераций

(6)

и заканчиваем данную итерацию.

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

Одна из сложностей применения метода скользящего допуска — возможные осцилляция решения относительно границы области (см. ниже).

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

(7)

Здесь — вектор координат центра тяжести многогранника , так что величина

есть среднее расстояние вершин многогранника от его центра тяжести.

Из (7) следует, что критерий скользящего допуска является положительно определенной функцией координат вершин многогранника . С другой стороны, поскольку размер многогранника при приближении к точке минимума уменьшается (в пределе до нуля), то справедливо предельное соотношение

Для задачи (1), (2) в качестве функционала обычно используют функционал

(8)

где

Из (8) следует, что функционал обладает следующим свойством

Из (8) вытекает также, что если значение функционала мало, то точка находится недалеко от границы области .

Симплекс с вершинами обозначим .

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

x = 0 : 0.15 : 5;
y = x;
[X, Y] = meshgrid(x);
Z = -X - Y;
V = [-1, -2, -3, -4, -5, -6, -7, -8, -9, -10];
[C, h] = contour(X, Y, Z, V);
clabel(C, h);

x = 0 : 0.01 : 5;
y = x;
[X, Y] = meshgrid(x);
Z = X.^2 + Y.^2 - 9.;
V =[1, 2, 4, 8, 16, 32, 64, 128];
[C, h] = contour(X, Y, Z, V);
clabel(C, h);

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

Эффект, рассмотренный в прим. 1, и называется осцилляцией решения относительно границы области .

Для ослабления влияния осцилляций в простейшем случае можно вместо точки использовать точку — середину отрезка .

Чаще с этой целью используют квадратичную интерполяцию функции на отрезке по трем точкам , где — также середина отрезка — см. рис. 3. Обозначим эту интерполирующую функцию (см. параграф 4.7). Вместо точки в этом случае можно использовать один из нулей функции либо его приближенное значение, найденное, например, методом касательных.