Лекция: Необходимое и достаточное условие минимума функции одной переменной. Классический метод оптимизации. Виды целевых функций. Тестовые функции.

Из математического анализа известны следующие условия локального экстремумафункции f(x), дифференцируемой достаточное число раз.

Условие 1.Если функция f(x) дифференцируема в точке x~ (х с волнистой линией сверху) и достигает в этой точкелокального экстремума, то f‘(x~) = 0 (необходимое условие экстремума).

(Альтернативное определение необходимого условия экстремума)

Если функция y =f(x) в точке х0имеет экстремум, то производная fꞌ( x0) равна нулю.

· Точка, в которой производная равна нулю, называется стационарной.

· Стационарная точка необязательно является точкой экстремума функции.

· Точка, в которой производная функции равна 0 или не существует, называется критической точкой.

Условие 2.Пусть функция f(x) n раз дифференцируема в точке x~ и в этой точке всепроизводные f(x) до n – 1-го порядка включительно равны нулю, а f(n)(x~) ≠ 0. Тогда, если n – нечетно, то x~ не является точкой локального экстремума функции f(x). Если жеn – четное, то:

а) при f(n)(x~ )> 0 x~– точка локального минимума f(x);

б) при f(n)(x~ )> 0 x~ – точка локального максимума f(x) (достаточное условие экстремума).

(Альтернативное определение достаточного условия экстремума)

Пусть функция f(x) непрерывна на отрезке [a, b], а точка x0из этого отрезка является критической. Тогда:

1) если fꞌ(x) < 0 на (a;x0) и f`(x) > 0 на (x0;b), то точка x0–точка минимума функции f(x);

2) если fꞌ(x) > 0 на (a;x0) и f`(x) < 0 на (x0;b), то точка x0–точка максимума функции f(x).

f(x) → min, x ∈ [a, b] (2.1)

Перечисленные условия позволяют предложить следующий путь решения задачиминимизации (2.1):

1) c помощью Условия 1 находим все точки возможного экстремума функции f(x) наинтервале (a; b), т.е. корни уравнения

f‘( x ) = 0 (2.2)

(стационарные точки), принадлежащие интервалу (a; b);

2) найденные стационарные точки исследуем в соответствии с Условием 2, выделяя из них только точки локальных минимумов f(x);

3)значения f(x) в точках локальных минимумов и на концах отрезка [a; b]сравниваем между собой. Наименьшему из этих значений соответствует точкаглобального минимума f(x) на [a; b].

Замечание: Применение Условия 2 требует вычисления высших производныхфункций f(x), поэтому в большинстве случаев бывает проще сравнить значения f(x) вовсех стационарных точках, не интересуясь их характером. С учетом этого можнопредположить следующий алгоритм минимизации f(x) на отрезке [a; b] (классический

метод).

Шаг 1. Решить уравнение (2.2) на интервале x∈(a; b), т.е. найти все стационарные

точки x1, …, xк-1∈(a; b). Положить x0= a, xк = b.

Шаг 2. Вычислить значения f(xi) функции f(x) в точках xi, i = 1,k .

Шаг 3. Найти f* =MIN0≤i≤kf(xi) = f(xm). Положить x* = xm.

Пример. Классический метод минимизации функции.

Решить задачу f(x) = x3 – 3x +1 → min, x∈ [–2; 2].

Шаг 1. Находим корни уравнения f ’(x) = 3x2 – 3 = 0 из интервала (–2, 2):

x1 = –1, x2 = 1. Полагаем x0 = –2, x3 = 2.

Шаг 2. Вычисляем значения f(x) в точках xi, i = 0, …, 3:

f(x0) = –17, f(x1) = 3, f(x2) = –1, f(x3) = 1.

Шаг 3. Находим f* = min({–17, 3, –1, 1}) = –17 = f( x0). Поэтому принимаем

x* = x0= –2, значение функции f * = – 17.

При решении практических задач оптимизации классический метод имеетограниченное применение. Это объясняется тем, что, во-первых, во многих случаяхзначения целевой функции f(x) находятся из измерений или экспериментов, а измерениепроизводной f ‘(x) затруднительно или невозможно и, во-вторых, даже когдапроизводная f‘(x) задана аналитически или поддается измерению, решение уравнения(2.2) зачастую вызывает затруднения.

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

1. (Тест Розенброка): f(x) = 100(x2–x1)2 + (1–x1)2 →min, начальное приближение

x0 = (-1,2; 1), точка минимума x* = (1; 1), f* = 0.

2 .(Тест Пауэлла): f(x) = (x1+10 x2)2 +5(x3 – x4)2 +( x2 – 2x3)2 + 10(x1– x4)4→min

начальное приближение x0 = (–3; –1;0 ;–1), точка минимума x* = (0, 0, 0, 0), f * = 0.

3. (Тест Вуда): f(x) = 100(x2 – x12)2 + (1 – x1)2 + 90(x4 – x32)2 + (1 – x3)2 + 10,1(x2–1)2 +

(x4–1)2 +19,8(x2 – x1)(x4 – x1)→min начальное приближение x0 =(–3; –1; –3; –1), точка

минимума x* = (1, 1, 1, 1), f * = 0.