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

Унимодальной называется функция, имеющая один экстремум.

Задача поиска экстремума сводится к нахождению значения х_о, соответствующего максимуму или минимуму f(x).

Алгоритм численного метода или метода случайного поиска экстремума может быть рассчитан на нахождение максимума или минимума. Для нахождения противоположного вида экстремума, например, максимума по алгоритму на минимум, необходимо значения оптимизируемой функции f(x) умножить на (-1).

Для аналитического метода, в случае дифференцируемости функции f(x) находим

f'(x) = 0. Решение полученного уравнения дает оптимальное значение х_о. Затем вычисляем f''(х_о). Если f''(х_о) > 0, то имеем минимум; и если f''(х_о) < 0, то максимум (рисунок 3.1).

f(x)

х_о x

f '(x)

x

f ''(x)

x

Рисунок 3.1 – Графическая интепретация поиска эстремума дифференцируемой функции

Из приведенной графической интерпретации метода следует, что функция (1) имеет максимум и функция (2) – минимум.

Среди численных находят применение следующие методы: дихотомии, золотого сечения, Фибоначчи, шаговые и аппроксимации кривыми.

Метод дихотомии (половинного деления) является одним из методов одномерной безусловной оптимизации унимодальной целевой функции. Алгоритм метода основывается на выборе исходного отрезка поиска решения [a, b] и его последующем делении пополам:

1) x_c=(b+a)/2;

2) x₁ = x_c - e/2; x₂ = x_c + e/2;

3) Если при минимизации f(x₁) < f(x₂), то b = x_с, иначе a = x_с.

4) При b - a <= e, x_опт = (b + a)/2, где e – точность поиска экстремума. Иначе на п. 1.

Ниже приведена графическая интерпретация (рисунок 3.2) и один из алгоритмов метода дихотомии (рисунок 3.3).

f(x)

f(x₂)

f(x₁)

e

a x₁ x_с x₂ b х

Рисунок 3.2 – Графическая интепретация метода дихотомии

1

Пуск

Ввод a, b, e a и b – текущие значения нижней и верхней

границ интервала поиска экстремума

e – точность поиска

3 4

x_с= (a+b)/2 b-a≤e Да 11 Z_п – значение

Z_п= f(x_с) целевой

функции

5 Нет 12 для решения

i = 1, 2 Вывод x_c, Z_п,e

6 13

x₁ = x_с +(2i-3) e/2 Останов

Z₁= f(x₁)

Поиск по сайту: