Общий вид алгоритма поиска минимума функции

Алгоритм поиска минимума некоторой функции f(x) в общем виде представляет собой итерационную процедуру вида:

x(k+1)=x(k)+α(k)S(k), где

х(k) - предыдущая точка в пространстве переменных;

x(k+1) - следующая точка;

S(k) - вектор направления перемещения;

α(k) - скалярный множитель, определяющий величину шага в направлении S(k)

k - номер итерации.

Операции алгоритма состоят в следующем:

1)задать kj = 0 и начальную точку х(0);

2)вычислить значение функции f(x(k));

3)вычислить направление S(k) из условия уменьшения функции f(x);

4)вычислить очередную точку x(k+1) = х(k) + а(k)S(k);

5)вычислить значение f(x(k+1))

6)вычислить и проверить выполнение условия останова. Если условие выполнено, идти к 9.

7)k=k+1

8)идти к 3;

9)вывод результатов. SТОР.

Методы поиска минимума отличаются друг от друга способом вычисления направления и множителя а(k), а также условиями останова.

Наиболее общим условием останова является сравнение нормы разности ∆x(k)=x(k+1)-x(k) с заданным числом ε _х.

Останов алгоритма в общем случае еще не означает, что найдена точка минимума. Чтобы это утверждать, нужно проверить классическое условие минимума ∆f(x(k+1))=f(x)-f(x(k+1))>0 для всех х из sph(x(k+1)), ε, то есть из ε-окрестности точки x(k+1).

Одним из распространенных способов вычисления множителя α(k) является следующий: α(k) = агg minf(x(k) + S(k)), где минимум берется по переменной .

Это означает, что точка х(k+1) определяется как минимум функции f(x) в направлении S(k). При этом используется один из способов поиска минимума функции одной переменной, а конкретное значение а(k) в алгоритме не используется. Указанный поиск называется одномерным поиском в заданном направлении.

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