2. Теоретические аспекты методов одномерной оптимизации. Алгоритмы и примеры решения.

2.1 Поисковые методы

Основой всех одномерных поисковых методов является сокращение интервала неопределенности, а именно: построение последовательности отрезков [a_k ; b_k], стягивающихся в точке х^* - минимуму функции на исходном отрезке. Методы оптимизации отличаются друг от друга лишь различным выбором точек на начальном интервале неопределенности: в методе половинного деления – число Е>0 – наименьший сдвиг по х, при котором еще можно отличить f(x) и f(x+Е); в методе золотого сечения – величина ; в методе Фибоначчи используются числа Фибоначчи.

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

На этапе установления границ интервала на основе априорных данных или правил исключения строится относительно широкий интервал [a, b], содержащий точку оптимума x^*. Обычно поиск граничных точек такого интервала проводится с помощью эвристических методов поиска, хотя в ряде случаев можно также использовать методы экстраполяции. Так как минимум x^* на [a, b] неизвестен, то этот интервал называется интервалом неопределенности. Для унимодальной функции f(x) интервал неопределенности может быть сокращен с помощью вычисления значений функции в двух точках x, y  [a, b]. При этом возможны два случая. Если f(x) > f(y), то новым интервалом неопределенности является [x, b], поэтому переприсвоение границ интервала на итерациях для этого случая осуществляется по правилу a_k+1 = x_k, а b_k+1 = b_k. При выполнении условия f(x)  f(y), новым интервалом будет [a, y] и, соответственно, a_k+1 = a_k, b_k+1 = y_k.

2.1.1 Метод сканирования

Сканирование или равномерный поиск является примером одновременного поиска, когда точки, в которых вычисляется значение функции, выбираются заранее. Начальный интервал неопределенности [a₁, b₁] делится на отрезки величиной  сеткой из точек a₁ + k для k = 1, …, n. Тогда b₁ = a₁+ (n - 1). Затем функция f(x) вычисляется в каждой из n точек сетки и определяется , в которой она имеет наименьшее значение. Если f(x) унимодальна, то минимум принадлежит интервалу [ -  , + ].

После n вычислений функции интервал [a₁, b₁] сокращен до длины 2. Так как n = [(b₁ - a₁)/] - 1, то для достижения более высокой точности нахождения минимума необходимо большое число вычислений функции.

Алгоритм метода сканирования.

Начальный этап. Выбрать шаг разбиения > 0 и начальный интервал [a₁, b₁]. Задать k = 1 и перейти к основному этапу.

Основной этап. Шаг 1. Вычислить значение х=a₁ + k и f(x). Если k=n, то перейти к шагу 2, иначе положить k=k+1 и вернуться к шагу 1.

Шаг 2. Выбрать минимальное значение функции f(x) и соответствующее ему значение . Минимум функции находится в интервале [ - , + ].

Пример расчета экстремума функции методом сканирования.

Постановка задачи. Определить экстремум функции f(x)=(x-2)²+7.

Определение экстремума аналитически. Необходимым условием существования экстремума является равенство нулю первой производной. Решаем уравнение f'(x)=2(x-2)=0. Полученная точка х*=2 является точкой минимума, так как вторая производная в данной точке f''(x*) =2>0.

Реализация метода сканирования. Выбираем достаточно большой начальный интервал [-100, 100] и количество разбиений n=10. Результаты расчетов точек и значений функции представлены в таблице 2.1.

Таблица 2.1

Результаты расчетов методом сканирования.

№	х	f(x)
1	-100	10411
2	-80	6731
3	-60	3851
4	-40	1771
5	-20	491
6	0	11
7	20	331
8	40	1451
9	60	3371
10	80	6091
11	100	9611

Графический анализ функции Строим график функции на данном интервале (рис.2.1).

Рис.2.1

В результате реализации метода сканирования получена минимальная точка х*=0, значение функции в которой составляет f(x)=11. Границами интервала являются две точки по обе стороны от минимальной. Исходя из этого, делаем вывод, что экстремум находится в интервале [a₁ b₁]=[-20,20]. Этот интервал можно использовать в качестве начального при реализации других методов одномерной оптимизации либо двойного сканирования.