Лекция: Алгоритм с возвратом при неудачном шаге

1. Задать начальный шаг h0, число проб s £ n и точность e.

2. Сгенерировать или задать начальную точку X0и вычислить в ней функцию f; положить i=1 (i – счетчик проб).

3. Сгенерировать случайный вектор направления × .

4. На направлении определить точку Xk+1 = Xk + hk×Xk и вычислить в ней функцию f.

5. Проверить: а) если f(Xk+1)<f(Xk), положить k=k+1, i=1 и вернуться на 3; б) если f(Xk+1)³f(Xk) и i<s, положить i=i+1 и вернуться на 3; в) если f(Xk+1)³f(Xk), i=s и hk>e, положить hk=hk/2, i=1 и вернуться на 3. г) если f(Xk+1)³f(Xk), i=s и hk£e, поиск закончить, приняв Xk за точку минимума.▲

Таким образом, поиск останавливается, если в текущей точке s направлений, сгенерированных подряд, оказались неудачными при шаге, меньшем заданной точности. На рис. 8.38 показан характер движения при поиске по данному алгоритму (жирной линией выделены успешные шаги).