Прямые методы. Предварительные сведения

Численные методы решения задач одномерной оптимизации унимодальных функций

Прямые методы. Предварительные сведения

Для решения задачи минимизации функции f(x) на отрезке [а; b] на практике, как правило, применяют приближенные методы. Они по­зволяют найти решение этой задачи с необходимой точностью в ре­зультате определения конечного числа значений функции f(x) в ее производных в некоторых точках отрезка [а; b]. Методы, использую­щие только значения функции и не требующие вычисления ее произ­водных, называются прямыми методами минимизации. Большим достоинством прямых методов является то, что от целе­вой функции не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем ос­нованы алгоритмы прямых методов минимизации, это возможность оп­ределения значений f(x) в заданных точках.

Рассмотрим наиболее распространенные на практике прямые ме­тоды поиска точки минимума.

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

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

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

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

3. если

Применение некоторых методов одномерной минимизации возможно только в случае, если скорость изменения целевой функции на любом участке отрезка ограничена некоторым числом, одним и тем же для всех участков. В этом случае говорят, что данная функция удовлетворяет на этом участке условию Липшица. Целевые функции большинства практических задач оптимизации указанным свойством обладают.

Определение. Функция f(x)удовлетворяет на отрезке [а; b] условию Липшица, если существует такое число (константа Липшица), что

для всех , принадлежащих [а; b].