Классификация методов одномерной безусловной оптимизации

Все численные методы одномерной безусловной оптимизации условно можно сгруппировать следующим образом: 1 Методы исключения интервалов (линейный поиск)(м половинного деления; м «золотого сечения»; м Фибоначчи) 2 м полиномиальной аппроксимации (м Пауэлла) 3 м с использованием производных (м секущих; м касательных).

Первые две группы методов используют только значения функции и не требуют вычисления ее производных и называются методами минимизации нулевого порядка.

М исключения интервалов накладывают единственное требование на исследуемую функцию: она должна быть унимодальной. =>указанные методы можно использовать для анализа непрерывных и разрывных функций, и когда переменные принимают значения из дискретного множества. Логическая структура поиска с помощью методов исключения интервалов основана на простом сравнении значений функции в двух пробных точках. Кроме того, при таком сравнении в расчет принимается только отношение порядка на множестве значений функции и не учитывается величина разности между значениями функции. Большим достоинством этих методов является то, что от целевой функции не требуется дифференцируемости и она м/б не задана в аналитическом виде. Единственное, на чем основаны алгоритмы методов нулевого порядка, это возможность определения значений f(x) в заданных точках, а также, что исследуемая целевая функция в допустимой облас-ти, по крайней мере, обладает свойством унимодальности.

РАССМОТРЕНИЕ МЕТОДОВ:

Метод половинного деления: м относится к последовательным стратегиям и позволяет исключить из дальнейшего рассм-ия на каждой итерации ровно половину текущего интервала неопределенности. Задается начальный интервал неопределенности и требуемая точность. Алгоритм основан на анализе значений функции в 3-х точках, равномерно распределенных на текущем интервале (делящих его на четыре равные части). Поиск заканчивается, когда длина текущего интервала неопределенности оказывается < установленной величины.

Метод золотого сечения: м относится к последовательным стратегиям. Задается начальный интервал неопределенности и требуемая точность. Алгоритм основан на анализе величин функции в 2-х точках. В качестве точек вычисления функции выбираются точки золотого сечения. Тогда учетом свойств золотого сечения на каждой итерации, кроме первой, требуется только одно новое вычисление функции. Поиск заканчивается, когда длина текущего интервала неопределенности оказывается < установленной величины.

Метод Фибоначчи: м относится к последовательным стратегиям. Задается начальный интервал неопределенности и количество N вычислений функции. Алгоритм основан на анализе величин функции в 2-х точках. Точки вычисления функции находятся с использованием последовательности из N+1 чисел Фибоначчи. На 1-ой итерации требуется 2 вычисления функции, а на каждой последующей итерации, требуется 1 новое вычисление функции. Поиск заканчивается, когда длина текущего интервала неопределенности оказывается < установленной величины.

Метод Пауэлла: относится к последовательным стратегиям. Задается начальная точка и с помощью пробного шага находится 3 точки так, чтобы они были как можно ближе к искомой точке минимума. В полученных точках вычисляются значения функции. Затем строится интерполяционный полином 2-ой степени, проходящий через эти точки. В качестве приближения точки минимума берется точка минимума полинома. Поиск заканчивается, когда полученная точка отличается от лучшей из трех опорных точек не более чем на заданную величину.

Метод секущих: ориентирован на нахождение корня уравнения f(x)=0 в интервале [a,b], в котором имеются две точки, в которых f(a), f(b) < 0. Между этими точками проводится секущая к кривой y=f(x). В качестве следующего приближения выбирается точка пересечения этой секущей с осью абсцисс. Процесс построения секущих и нахождения точек пересечения с осью продолжается до тех пор, пока разность между двумя последовательными приближения не станет меньше ε.

Метод Ньютона (метод касательных): в окрестности имеющегося приближения x_n задача f(x)=0 заменяется некоторой вспомогательной линейной задачей. Эта задача выбирается так, чтобы погрешность замены имела более высокий порядок малости, чем первый (порядок малости) в окрестности имеющегося приближения. За следующее приближение принимается решение этой вспомогательной задачи. Метод состоит в замене кривой y= f(x) на касательную к ней в процессе каждой итерации.