Многомерный поиск, использующий производные

Многомерный поиск без использования производных.

МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ

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

Рассмотрим методы решения минимизации функции нескольких переменных f, которые опираются только на вычисление значений функции f(x), не используют вычисление производных, т.е. прямые методы минимизации. Важно отметить, что для применения этих методов не требуется не только дифференцируемости целевой функции, но даже аналитического задания. Нужно лишь иметь возможность вычислять или измерять значения f в произвольных точках. Такие ситуации часто встречаются в практически важных задачах оптимизации. В основном все описанные методы заключаются в следующем. При заданном векторе х определяется допустимое направление d. Затем, отправляясь из точки х, функция f минимизируется вдоль направления d одним из методов одномерной минимизации. Задача линейного поиска заключается в минимизации f(x+lym*d) при условии, что lym принадлежит L, где L обычно задается в форме L=E1, L={lym: lym >= 0} или L={l: a<=lym<=b}. Будем предполагать, что точка минимума lym* существует. Однако в реальных задачах это предположение может не выполняться. Оптимальное значение целевой функции в задаче линейного поиска может быть не ограниченным или оптимальное значение функции конечно, но не достигается ни при каком lym.

Пусть функция f(x) дифференцируема в Еn. В этом разделе рассматривается итерационная процедура минимизации вида:

x[k] = x[k-1] + lim[k]*dk, k=1,...,

где направление убывания dk определяется тем или иным способом с учетом информации о частных производных функции f(x), а величина шага lim[k] >0 такова, что

f(xk) < f(xk-1), k=1,2,....

Так как функция предполагается дифференцируемой, то в качестве критерия останова в случае бесконечной итерационной последовательности { xk }, как правило, выбирают условие ||grad(f(xk))||<eps, хотя, разумеется, могут быть использованы и другие критерии.

Дата добавления: 2014-01-07