Нелинейное программирование. Методы безусловной оптимизации в нелинейном программировании, страница 16

З а м е ч а н и е  4.20. В результате вычисления вектора S^k  формуле (4.19) определяются координаты его конца, причем его начало считается находящимся в начале координат. Однако поскольку этот вектор является свободным, то при графических построениях он может быть перенесен параллельно самому себе в любую точку пространства.

При выполнении процедуры поиска возможна ситуация, когда в полученной в результате выполнения рабочего шага, значение ЦФ не уменьшилось по сравнению со значением ЦФ  предыдущей такой точке. В этом случае найденная точка объявляется временной базовой точкой  (ВБТ) и вокруг нее производится исследующий поиск.  Если такой поиск не дал меньшего значения ЦФ, то осуществляется возврат  в предыдущую последнюю базовую точку и из нее выполняется исследующий поиск с уменьшенной длиной шага.  

Критерий окончания итераций в рассматриваемом методе проверяется после каждого удачного поиска по образцу, определяющего новую точку последовательности {X^k}.  В случае  уменьшения длины шага проверку значения критерия окончания итераций необходимо дополнительно производить после выполнения каждого удачного исследующего (предварительного)  поиска.

З а м е ч а н и е  4.21. В рассматриваемом методе последовательность обхода переменных и направления шагов предварительного поиска принимается неизменной.  

Алгоритм метода Хука-Дживса приведен в [20,34].

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

Идея метода состоит в повороте осей координат в процессе поиска для создания удобного взаимного расположения оврага и системы координат. Для поворота осей используется информация, получаемая на предыдущих шагах поиска. (Рассмотренная идея хорошо проиллюстрирована на примере ЦФ двух переменных в работе [21]).

Следует отметить, что метод Розенброка имеет несколько существенно отличающихся модификаций, приводимых в [49,18,54].

Перейдем к рассмотрению группы случайных  методов.

Метод случайного поиска

К методам, использующим лишь значения функции и не требующим вычисления производных, относятся методы случайного поиска, у которых перемещение к точке экстремума осуществляется случайным образом. Известно много разновидностей таких методов [26,54,33,15,17,21].

Один из простейших методов случайного поиска состоит в следующем. Выбирают величину шага l и из начальной точки X⁰ совершают в случайном направлении  перемещение на расстояние l. Если значение z(X) в новой точке не уменьшилось, то возвращаются в точку X⁰ и осуществляют в случайном направлении новый шаг на расстояние l. В случае неудачи опять возвращаются в точку X⁰ и процесс повторяется до тех пор, пока очередное перемещение не приведет к уменьшению целевой функции. После этого в направлении последнего перемещения делают шаги величиной l до тех пор, пока приращение функции z(X) не изменит знак. Затем процесс повторяют. При этом если из очередной точки X^k определенное число случайных перемещений на расстояние l не привело к уменьшению функции, то точку X^k считают точкой минимума.

Главное преимущество методов случайного поиска заключается в их простоте; эти методы не налагают никаких ограничений на функцию z(x). Основной их недостаток – медленная сходимость. Для ее ускорения включают процедуры, которые анализируют результаты выполненных операций и выделяют направления с большей вероятностью убывания минимизируемой функции. Методы такого типа называются методами случайного поиска с обучением.

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