2 Схема решения задач оптимизации

Процесс выбора наибольшего или наименьшего значений целевой функции в области проектирования можно провести по схеме:

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

2. Вычислить значения целевой функции на границе области проектирования.

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

4. За значения проектных параметров x₁, x₂, …, x_n принять значения, удовлетворяющие выбранному значению целевой функции.

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

, (i = 1, 2, …, n) (53)

подлежит решению. Решение таких систем даже для определения одной точки, подозрительной на экстремум, весьма трудоёмкое мероприятие. А ведь целевая функция может иметь внутри области проектирования несколько экстремумов.

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

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

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

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 некоторой, заранее оговорённой точностью. Точность решения, естественно, задается разработчиком либо по длине интервала неопределенности L, либо по изменению целевой функции F (см. рис. 2.13), исходя из смыслового содержания решаемой задачи.

Рисунок 2.13

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

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

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

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

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

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

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

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

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

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

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

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