Главная / Основы оптимизационных методов / Метод последовательного перебора

Метод последовательного перебора

Суть метода состоит в том, что спускаясь из точки X0 с заданным шагом h в направлении уменьшения функции устанавливают интервал длиной h, на котором находится минимум и затем его уточняют.

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

Алгоритм варианта с уменьшением шага и изменением знака Задается x0, шаг h и погрешность e. Вычисляется y0=f(x0).

1. Из точки x0 делается шаг вправо x1=x0+h и вычисляется y1=f(x1).

2. Если на первом шаге функция убывает y1<y0, то направление спуска выбрано удачно, переходим на п.3. Иначе меняем направление спуска h=-h, возвращаемся в исходную точку х1=х0, у1=у0 и переходим к п.3. Если оба направления оказались неудачыми, то шаг делится на 4 и попытки делаются до тех пор, пока h не станет меньше e (в этом случае Xm=X0 и вычисление прекращается), или функция уменьшится в каком-то направлении.

3. x0=x1, y0=y1 — запоминается удачная точка.

4. Делаем k шагов в сторону убывания, пока f(x0+kh) не станет больше, чем f(x0+(k-1)h),т. е повторяем с п.3, пока y1<y0,иначе п.5.

5. h=-h/4. Шаг уменьшается в 4 раза, меняется его знак, мы перешагнули точку минимума и организуем спуск в обратном направлении.

6. Если ABSh > e/4, тогда повторить с п.3, иначе перейти к п.8.

7. Xm=X0, fm=fo, конец.

Задание: а) сОставить программу, найти минимальное значение функции; Б) уТочнить минимум функции, используя программу поиска

Условного минимума из лабораторной работы N 1.

Скорость сходимости данных методов существенно зависит от удачного выбора х0 и шага h. Шаг h следует выбирать как половину оценки расстояния от х0 до предполагаемого минимума Xm.

Для ускорения спуска к минимуму из точки Х0 применим следующий подход. Используется несколько значений функции в определенных точках для аппроксимации функции обычным полиномом в небольшой области значений. Затем положение минимума функции аппроксимируется положением минимума полинома, поскольку последний вычислить проще. Это метод аппроксимирующий функцию квадратичным полиномом, он хорошо работает с несложной унимодальной функцией одной

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