Численные методы решения задач безусловной одномерной оптимизации

Пусть требуется найти экстремум (максимум или минимум) функции одной независимой переменной

y = f(x) при a x b.

Интервал изменения параметра х принято называть интервалом проектирования или интервалом неопределенности.

В дальнейшем условимся:

· рассматривать только поиск минимума целевой функции, поскольку в силу симметричности функции y = f(x)и y = –f(x) относительно оси Ох, минимум функции y = f(x) является максимумом для функции y = –f(x);

· предполагать, что на интервале неопределённости целевая функция унимодальна, т.е. имеет только один экстремум.

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

Классический метод для функции одной переменной приводит к решению уравнения . Найти его корни можно:

· для простых уравнений непосредственно: путем выделения переменной x для уравнений вида ax + b = 0; через дискриминант для уравнений квадратных: ax + bx + c = 0 и приводящихся к ним и т.д.;

· для сложных – применением специальных методов, например последовательных приближений, половинного деления (см. выше п. 3.2).

Если же функция y = f(x) или ее производная сложны или имеют разрывы в некоторых точках интервалах [a, b], то применение классического приема затруднительно или невозможно. Численные методы в этих случаях действуют безотказно. Суть этих методов заключается в сужении границ интервала неопределенности (внутри которого заключена искомая точка экстремума) до таких размеров, в пределах которых любая точка x может быть взята в качестве приближенного решения c некоторой, заранее оговорённой точностью. Точность решения, естественно, задается разработчиком либо по длине интервала неопределенности DL, либо по изменению целевой функции DF (см. рис. 2.13), исходя из смыслового содержания решаемой задачи.

Определение погрешности:

а) по длине интервала неопределённости DL;

б) по значениям целевой функции DF.

Условимся задавать точность по длине интервала неопределенности DL.

Наиболее простым для понимания является метод половинного деления. Этот метод сужает интервал на каждом этапе ровно вдвое и требует на каждом шаге вычисления значения функции в двух точках.

Алгоритм метода половинного деления:

1.Определяется первоначальный интервал неопределенности [a,b](анализом графика или таблицы значений функции F(x)).

2.Определяется численное значение производной в точке c=(a+b)/2,то есть в середине интервала. Для этого можно использовать приближенное выражение второго порядка точности (25); в качестве шага hберется значение e/2.

3.Если производная положительна, за новый интервал неопределенности принимается [a, c], в противном случае [c, b]. Если производная окажется равной нулю, искомая точка минимума – это точка с.

4.Шаги 2, 3 повторяются до тех пор, пока новый интервал неопределенности не окажется короче, чем допустимая величина погрешности e.Тогда за искомую точку принимается середина последнего найденного интервала.

(Замечание: из выражения (25) видно, что можно не определять производную, а просто поставить условие:

Если оно выполнено, производная положительна, в противном случае – отрицательна).