§ 10.6. Метода минимизации без вычисления производных

1. Методы прямого поиска. Метод деформируемого многогранника.

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

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

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

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

Затем вычисляют "центр тяжести" оставшихся точек по формуле и строят пробную точку отразив симметрично вершину относительно точки

Геометрическая иллюстрация этой операции в случае приведена на рис. 10.9, а. Заметим, что в плоском случае роль многогранника играет треугольник.

Рис. 10.9 Далее возможны три случая.

Случай 1: т. е. пробная точка не привела к уменьшению значения целевой функции, но и не стала "худшей" в наборе . В этом случае точку признают удовлетворительной и заменяют на х.

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

Случай 3: В этом случае считают, что многогранник следует сжать. Если вершину заменяют точкой Если же то заменяют на Здесь коэффициент сжатия (обычно На рис. 10.9, в показано "сжатие" с коэффициентом

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

Известно большое число различных модификаций этого метода. Подробно они описаны в книгах [24], [91]. Там же указаны различные критерии окончания.

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

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

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

Подобная модификация алгоритмов не является тривиальной и требует достаточной осторожности в реализации. Это связано с высокой чувствительностью формул численного дифференцирования к ошибкам в вычислении функции (см. § 12.3). Более подробное обсуждение методов минимизации, использующих конечно-разностное аппроксимации производных, можно найти в [24] и [32]. В заключение все же отметим, что конечно-разностные аппроксимации производных используются в алгоритмах минимизации тогда, когда аналитическое вычисление производных невозможно. Бели же производные можно вычислить аналитически, то усилия, потраченные на такое вычисление, как правило, окупаются.