Общая характеристика методов нулевого порядка

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

Метод прямого поиска (метод Хука-Дживса)

Суть этого метода состоит в следующем. Задаются некоторой начальной точкой х [0]. Изменяя компоненты вектора х [0], обследуют окрестность данной точки, в результате чего находят направление, в котором происходит уменьшение минимизируемой функции f(x). В выбранном направлении осуществляют спуск до тех пор, пока значение функции уменьшается. После того как в данном направлении не удается найти точку с меньшим значением функции, уменьшают величину шага спуска. Если последовательные дробления шага не приводят к уменьшению функции, от выбранного направления спуска отказываются и осуществляют новое обследование окрестности и т. д.

Алгоритм метода прямого поиска состоит в следующем.

1. Задаются значениями координат х _i[0], i = 1,..., п, начальной точки х [0], вектором изменения координат  х в процессе обследования окрестности, наименьшим допустимым значением е компонентов  х.

2. Полагают, что х [0] является базисной точкой х ^б, и вычисляют значение f(x^б).

3. Циклически изменяют каждую координату х ^б_i, i = 1,..., п, базисной точки х ^б на величину? х _i, i = 1,..., п, т. е. х_i [ k ] = х^б +  х; х _i[ k ] = х ^б_i -? х _i. При этом вычисляют значения f(x [ k ] ) и сравнивают их со значением f(x^б). Если f(x [ k ] ) < f(x^б), то соответствующая координата х _i, i = 1,..., п, приобретает новое значение, вычисленное по одному из приведенных выражений. В противном случае значение этой координаты остается неизменным. Если после изменения последней п- й координаты f(x [ k ] ) < f(x ^б ), то переходят к п, 4. В противном случае - к п. 7.

4. Полагают, что х [ k ] является новой базисной точкой х ^б, и вычисляют значение f(x^б).

5. Осуществляют спуск из точки х [ k ] > х _i[ k+ 1] = 2х_i[ k ] - x ^б, i = 1,..., n, где x ^б - координаты предыдущей базисной точки. Вычисляют значение f(x [ k +1] ).

6. Как и в п. 3, циклически изменяют каждую координату точки х [ k +1], осуществляя сравнение соответствующих значений функции f (х) со значением f (х [ k +1]), полученным в п. 5. После изменения последней координаты сравнивают соответствующее значение функции f(x [ k ] ) со значением f(x ^б ), полученным в п. 4. Если f(x [ k ] ) < f(x ^б ), то переходят к п. 4, в противном случае - к п. 3. При этом в качестве базисной используют последнюю из полученных базисных точек.

7. Сравнивают значения  х и е. Если  х < е, то вычисления прекращаются. В противном случае уменьшают значения  х и переходят к п. 3.

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

Недостаток метода прямого поиска состоит в том, что в случае сильно вытянутых, изогнутых или обладающих острыми углами линий уровня целевой функции он может оказаться неспособным обеспечить продвижение к точке минимума. Действительно, в случаях, изображенных на Рис. 2.4, а и б, каким бы малым ни брать шаг в направлении х ₁ или x ₂ из точки х ’ нельзя получить уменьшения значения целевой функции.

Рис. 2.4. Прямой поиск: невозможность продвижения к минимуму: а – С₁ > C₂ > C₃; б - С₁ > C₂

Напомним, что поверхностью уровня (на плоскости - линией уровня) является поверхность, получаемая приравниванием выражения функции f(х) некоторой постоянной величине С, т. е. f(х) = С. Во всех точках этой поверхности функция имеет одно и то же значение С. Давая величине С различные значения С₁,..., С_n, получают ряд поверхностей, геометрически иллюстрирующих характер функции.

ВОПРОС 23 (2)