Реферат: Сходимость

Сходимость алгоритма является наиболее важным вопросом оптимизации. Большинство методов решения задач оптимизации имеют итерационную природу: xi+1 = A(xi), т.е. исходя из некоторой начальной точки x0, они порождают последовательность {x0, x1, …, xi, …} на основе алгоритма A, сходящуюся к точке экстремума x*.

Для оценки эффективности выбранных методов можно рекомендовать три характеристики: время, затраченное на получение решения (Т, c); точность решения; чувствительность к изменению параметра сходимости.

Для одномерных методов оптимизации время и чувствительность можно исследовать на типовых тестовых функциях, например, f(x) = sink(x), путем варьирования значений показателя степени k на множестве нечетных чисел от 1 до 79. Отметим, что для всех kminf(x) достигается в точке x* = 4,71239, при этом f(x*) = –1,0. Однако с увеличением k степень гладкости функции, которая обладает узкими впадинами в окрестности x*, уменьшается. Проверку методов на чувствительность можно осуществить путем варьирования значений параметра сходимости k и параметров алгоритма.

Точность решения можно измерить как относительную (в процентах) ошибку оценивания координаты истинного минимума.

Критерии останова алгоритма

Приведем несколько наиболее распространенных критериев останова оптимизационных методов:

ε – заданная точность:

где k – четное число (данный критерий используется в методах штрафных

и барьерных функций).

При выполнении неравенств полагают: x* ≈ xk и f* ≈ f(xk).