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

Метод одномерной минимизации

В таких методах нужно найти наименьшее значение целевых функций y=f(x), заданной на некотором ми-ве R, и определить значение параметра R, при котором целевая функция принимает это экстремальное значение. Это вытекает из теоремы Вейерштрассе: всякая функция f(y) непрерывна на отрезке [a,b] принимает на этом отрезке наименьшее и наибольшее значение.

1) Метод равномерного поиска

Найти тип функции f(x) на отрезке [a,b]. При этом полагают, что функция f(x) на [a,b] унимодальной, т.е. у неё существует финальный минимум на рассматриваемом отрезке. Процесс решения этим методом состоит в последующем сужении интервала применения проектного параметра. Наиболее простым способом сужения является его деление на некоторое число равных частей с последующим вычислением значений целевой функции в каждой точке разбиения.

2) Метод половинного деления

Используется для решения алг. уравнений состоит в делении пополам отрезка [a,b] затем анализируется изменение знака функции на половинных отрезках и одна из границ отрезка [a,b] переносится в его середину. Переносится та граница, со стороны которой функция на половине отрезка знака не имеет.
Процесс повторется.

Работа заканчивается, когда длинна текущего отрезка оказывается не более требуемой точности.

3) Метод золотого сечения

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

22.

1) Метод средней точки.
Искать тип функции f(x), непрерывно дифференцируемой и строго унимодальной на отрезке [a1,b1]. В этом случае единственной точкой х(принадлежащей)[a1,b1] стационарная точка, в которой f"(х)=0. Но функция может иметь более одной стационарной точки. Он основан на алгоритме исключения интервалов, на каждой интерации которого рассматривается одна пробная точка R. Возьмём например отрезок [a1,b1] , где х1 – это середина исходного отрезка. Если f*(х)>0, то отрезок [a1,b1] отбрасывают, т.к. в нём унимодальная функция только возрастает, а если f*(х)<0, то отбрасываю отрезок [a1,х1], т.к. на нём унимодальная функция убывает. Процесс повторяется.

2) Метод секущих
Задан отрезок [a,b]. Задаётся начальное приближение из концов отрезка [a,b], где значение функции и её второй производной имеют одинаковые знаки. В этой точке строится касательная к кривой и ищется её пересечение с осью х. Точка пересечения принимается за новую интерацию. Продолжается пока f(х)<е, где е – заданная точности.

3) Метод кубической интерполяции

Поиск искомой точки х(принадлежащей)(х1,х2) при условии f1*f2*<0 на отрезке [х1,х2]. Можно построить единственный многочлен третьей степени располагающий значениями f1,f2, f1*,f2*
Многочлен называющийся кубическим, называется многочленом Эрмита.

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

1) Метод покоординатного поиска(спуска)

Направление поиска выбирается поочерёдно вдоль всех координатных осей, шаг рассчитывается на основе одномерной оптимизации.
Проводится минимизация целевой функции по переменным х1, … ,хn. С её помощью мФ строим последовательность точек М0, М1, М2… , которой соответствует последовательность значений функции f(M0)>= f(M1) )>= f(M2)

Пусть нужно найти наименьшее значение функции и f(M)= f(хх1,х2,.., хn), Где М-точка n-мерного пространства.

Выберем начальную точку М0(х10, х20, … , хn)), будем двигаться от начала точки в сторону убывания функции пока не дойдём до её минимума х1*, после которого она начинает возрастать. Обозначим её Мi далее аналогично обрывая её на некотором поле R можно приблизительно принять значение функции f(Mn) за её наименьшее значение.

2) Метод Розенброка

Метод поиска минимума в много-мерном пространстве. Он использует только значение функции(поэтому нулевого порядка) . В нём реализуется покоординатный спуск, а потом предлагается искать ортогональную систему координат, в которой направление первой оси совпадает с направлением между исходной и конечной точкой начального приближения. Остальные орты ищутся методом Грама-Шмидта.

3) Метод ФСК(тот же метод только без ортогонализации направления)

4) Метод Пауэлла

Первые n-операций совпадают с операциями покоординатного спуска, затем необходимо рассчитать направление нашего прохода за n-операций. Все остальные увеличивают свой номер на 1, другие отбрасываются.

5) Симплексный метод (метод Нелдера — Мида )

Основан на многократно повторяемых операциях построения многогранника с(n+1) вершинами, где n – размерность пр-ва управляемых параметров и перемещение наихудшей вершины (с наихудшем значением целевой функции в направлении центра тяжести многогранника)

6) Метод Ньютона

Основан на использовании необходимых условий, в условиях экстремума целевой функции.