Метод случайного поиска.

Метод случайного поиска относится к группе итерационных методов минимизации.

Итерационные методы минимизации функции F(x) состоят в построении последовательности

векторов, то есть точек x0, x1, ..., xk, таких, что F(x0) > F(x1) >...>F(xk)>... Любой такой метод называется методом спуска. Естественно, должна быть обеспечена сходимость. Иными словами, рассматриваются методы, позволяющие получить точку минимума за конечное число шагов, или приблизиться к ней достаточно близко при соответствующем числе шагов. Дето в том, что теоретически все сходящиеся методы этим свойством обладают, но практически близость к минимуму в задачах большой размерности ограничивается ошибками вычислений. В этой связи необходимо вести вычисления с самой большой возможной точностью. Для построения итерационной последовательности необходимо выбрать начальное приближение x0. В задачах с ограничениями это должна быть допустимая точка, а в задачах без ограничений теоретически любая точка. Однако целесообразно использовать всю имеющуюся информацию о поведении целевой функции F(x), чтобы выбрать x0 поближе к точке минимума.

После того, как начальное приближение получено, прежде чем перейти к следующей точке нужно принять два решения:

1). Выбрать направление, по которому пойдем из x0 в точку с меньшим значением целевой функции (направление спуска).

2). Определить величину шага по направлению спуска.

Для задач безусловной минимизации любое напрвление является возможным (никакие ограничения не мешают), но далеко не все направления приемлемы. Нас могут интересовать только те направления, которые обеспечивают убывание целевой функции, хотя бы при достаточно малом шаге. Предполагая непрерывность первых частных производных целевой функции и используя её разложение в ряд Тэйлора в произвольной точке х, получим F(x+λp) ~ F(x) + X(g,p). Здесь g - градиент функции, вычисленный в точке х. Отсюда следует, что приращение функции F(x+Xp) – F(x) < 0 при отрицательном скалярном произведении (g,p). Итак, направление спуска должно составлять острый угол с антиградиентом. Этот вывод справедлив и для задач с ограничениями, но там ещё дополнительно требуется, чтобы при достаточно малом шаге не нарушалось ни одно из ограничений.