5. Необходимые условия экстремума первого и второго порядков

Необходимое условие существования экстремума функции: если   х = х₀   - точка экстремума, то f ^/(x₀) =0 или f ^/(x₀) не существует. Точки, в которых f ^/(x₀) обращается в нуль или не существует, называется критическими.

6. Достаточные условия экстремума (гладкие функции одной

переменной). 

Достаточное условие существования экстремума функции: если функция y=f(x) непрерывна в точке х = х₀ и ее окрестности, дифференцируема в этой окрестности, кроме, быть может, самой точки, и производная y’=f’(x) при переходе через точку х = х₀ меняет свой знак, то функция имеет экстремум при х = х_{0 .}

При этом х = х₀ - точка максимума, если знак меняется с « + » на « - », и х = х₀ - точка минимума, если знак меняется с « - » на « + » .

7. Необходимые условия экстремума первого порядка (гладкие функции многих переменных).

8. Одномерная безусловная оптимизация. Унимодальная функция. Лемма о свойстве унимодальных функций.

Задача одномерного поиска формулируется следующим образом: требуется найти максимум (минимум) функции одной переменной f(x), заданной на единичном отрезке. x*=argmin (max) f(x), x принадлежит X. X–множество допустимых точек, среди которых ищется x*. X=[a, b] – отрезок неопределенности. А относительно f(x), предполагают, что она унимодальна. 

Функция f (x) называется унимодальной на отрезке [a, b] , если она непрерывна на [a, b] и существуют числа α и β , a ≤α ≤ β ≤b , такие, что:

1)если a <α , то на отрезке [a, α] функция f (x) монотонно убывает;

2)если β < b , то на отрезке [β, b] функция f (x) монотонно возрастает;

3) при x [α, β] выполняется f (x) = f = min f (x) на отрезке [a,b]

Свойства унимодальных функций: 

1) Любая из точек локального минимума унимодальной функции является и точкой ее глобального минимум на отрезке [a,b]. 

2) Функция, унимодальная на отрезке [a,b], унимодальна и на любом меньшем отрезке [c,d]⊂[a,b]. 

3) Пусть f(x) унимодальна на [a,b]  и a≤x1<x2≤b. Тогда:

если f(x1)≤f(x2), то x*∈[a,x2], 

если f(x1)>f(x2), то x*∈[x1,b]

9.Пассивные методы поиска экстремума.

10.Метод перебора.

Метод перебора или равномерного поиска является простейшим методом минимизации и заключается в следующем. Разобьем отрезок [a, b] на N+1 равных частей точками деления xi = a + i*((b-a)/(N+1)), где i=1,2,3..N. Вычислим значения f(x) в точках 𝑥𝑖 . Найдем точку xl , для которой значение целевой функции минимально

Точность найденного решения 𝑥̃определяется по формуле: x*-xгарант , где гарант =((b-a)/(N+1))

Если необходимо найти приближенное решение с заданной точностью ε, то минимальное число экспериментов N для достижения этой точности определяется из условия гарант =((b-a)/(N+1))

N = Nрасч = minNZ{N:Nb-a-1}

11. Алгоритм оптимального пассивного поиска.

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

Алгоритм:

Отрезок [a,b] исходный отрезок неопределенности. Пусть N - число точек, в которых необходимо провести вычисления целевой функции f(x), т.е. N экспериментов. Точки, в которых необходимо провести эксперименты, определяются следующим образом:

Если N = 2k-1  -  нечетное, то xi = a + i*((b-a)/(N+1)), где i=1,2,3..N

Если N = 2k  -  четное, то x2i = a + i*((b-a)/(k+1)), x2i-1 =x2i - , где i=1,2,3..k

Среди вычисленных значений {f(xi)} (i=1,N), ищется точка xj, в которой достигается минимум: f(xj)= min f(xi) (min от 1 до N)

Найденная точка принимается за приближенное решение задачи x = xj. Исходный отрезок неопределенности [a,b] после экспериментов в N точках сужается до [xj-1,xj+1], длина которого равна:

Точность найденного решения x равна половине отрезка неопределенности, т.е. x*-x. , где = 1/2*LNи x* - точное решение.