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

Первую группу образуют критерии, основанные на сравнении различий в значениях ЦФ (критерия  оптимальности) в последовательности {z^k}. Они учитывают особенность, состоящую в том, что в окрестности точки оптимума различия в значениях членов таких последовательности уменьшаются (т.е. при k® ¥  | z^k+1 - z^k | ® 0 ).

Вторую  группу образуют критерии, учитывающие различия в значениях длины вектора–шага D(X^k). Они учитывают то обстоятельство, что в окрестности точки оптимума длина такого вектора стремится к нулю (т.е. при k® ¥   | D(X^k) | ® 0 ).

Такие критерии могут трактоваться также и как критерии, учитывающие уменьшение различий между точками последовательности {Х^k} при k® ¥ .   

Третью  группу образуют критерии, оценивающие различия в значениях длины шага  h^k . В большинстве методов такая длина автоматически уменьшается в процессе поиска  (т.е. при  k® ¥   h^k ® 0 ).

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

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

dz_k = | (z(X^k+1)– z(X^k) | / | z(X^k) |  £  d_зад  ,                                          (4.13)

где  d_зад - некоторое заданное значение точности решения задачи оптимизации. Такую точность можно трактовать как порог неразличимости относительных приращений  ЦФ. (При этом в качестве точки экстремума принимается точка X^k+1 ).

По аналогии с (4.13) может быть построен критерий, оценивающий абсолютные приращения  значений ЦФ  D_k= .| (z(X^k+1)– z(X^k) | .

Пример критерия второй группы:

| D(X^k) |  £ D_зад ,                                                                  (4.14)

где D_зад – некоторое заданное значение длины вектора-шага. Такой критерий задает порог  неразличимости точек X^k  в последовательности {Х^k}.

Пример критерия третьей группы:

h^k  £ h_зад ,                                                                     (4.15)

где h_зад – заданное значение шага.

3) Проблема “оврагов”

Часто встречающейся особенностью ЦФ, описывающих реальные технические системы и встречающихся в задачах проектирования, является наличие в них так называемых “оврагов” (или “хребтов”) [21]. (Соответствующие ЦФ называются “овражными”).

З а м е ч а н и е  4.12. Овраг может быть определен как подобласть ОДП, в которой наблюдается резкое различие в скорости изменения  ЦФ в различных направлениях n-мерного пространства.  

У большинства шаговых методов процесс поиска экстремума в “оврагах” либо замедляется,  либо  вообще останавливается.

В отношении эффективности “прохождения оврагов” шаговые методы делятся на три группы: 1) обычные методы, 2) улучшенные методы, 3) специализированные методы.

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

4.2.3.4  Классификация численных методов безусловной оптимизации

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

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

З а м е ч а н и е 4.13. Считается, что производная нулевого порядка есть сама исходная функция.