Определение 1.1.7. Достаточные условия оптимальности

(по второй производной)

Используя сформулированные необходимые и достаточные условия, поиск оптимального решения задачи (1.1.1) для случая дифференцируемой на множестве X функции f(x) можно осуществить, выполнив, например, следующие действия:

1. Определить множество стационарных точек функции f(x), принадлежащих множеству X.

2. Проверить в каждой стационарной точке выполнение достаточного условия минимума функции f(x) и вычислить ее значение в тех точках,
в которых это условие выполнено.

3. Из всех точек, в которых вычислялось значение функции[2], выбрать точку с наименьшим значением.

В заключение отметим характерные особенности рассмотренного метода решения задачи (1.1.1):

– он может быть практически реализован, если число стационарных точек функции f(x) на множестве X, определяемых в п. 1, и число граничных точек в случае замкнутого множества X, анализируемых в п. 3, конечно. В этом случае метод позволяет определить глобальный минимум функции f(x) на множестве X;

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

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

В практическом отношении рассмотренный метод не имеет большой ценности, тем не менее многие известные методы решения задачи (1.1.1) используют необходимые условия экстремума в том смысле, что они ориентированы на поиск решения уравнения f^¢(x) = 0, т. е. на поиск стационарных точек минимизируемой функции. Если это уравнение не может быть решено аналитически, то для его решения применяются численные методы. Для решения задачи (1.1.1) используются численные методы, которые могут быть классифицированы по различным характерным признакам.
В частности, если в качестве такого признака используется необходимость вычисления производных минимизируемой функции, все рассматриваемые в данном пособии методы можно разделить на две группы:

– методы нулевого порядка – их реализация не требует вычисления производных минимизируемой функции;

– методы второго порядка – их реализация требует вычисления производных второго порядка минимизируемой функции.

Рассматриваемые методы одномерной оптимизации являются итерационными. С их помощью, начиная с некоторого начального приближения х⁽⁰⁾, строят – бесконечную последовательность точек х⁽⁰⁾, х⁽¹⁾, х⁽²⁾, …, х^(k), …, где х^(k) – k-е приближение к искомой точке х^* локального минимума функции f(x).

Для итерационных методов важным является понятие сходимости метода.

Определение 1.1.8

Пусть итерационный метод сходится, если генерируемая в процессе его работы последовательность сходится к х* – искомому решению, т. е. выполнено условие lim х(k) = х*. (1.1.2) k ® ¥ В противном случае метод расходится.

Помимо понятия сходимости итерационного метода не менее важным является понятие скорости его сходимости. Различают линейную, сверхлинейную и квадратическую скорости сходимости итерационного метода.

Определение 1.1.9

Пусть х* – искомое решение и сходящийся итерационный метод генерирует в процессе своей работы последовательность . Тогда будут справедливы следующие утверждения: 1. Метод сходится с линейной скоростью (или со cкоростью гео-метрической прогрессии, если для всех k, начиная с некоторого k* ³ 0 и 0 £ q < 1, выполнено условие çх(k + 1) – х*ê £ qçх(k) – х*ê. (1.1.3) 2. Метод сходится со сверхлинейной скоростью, если для всех k, начиная с некоторого k* ³ 0, выполнено условие çх(k + 1) – х*ê £ qkçх(k) – х*ê, (1.1.4) где последовательность сходится к нулю. 3. Метод сходится с квадратической скоростью, если для всех k, начиная с некоторого k* ³ 0 и q ³ 0, выполнено условие çх(k + 1) – х*ê £ qçх(k) – х*ê2. (1.1.5)

Методы нулевого порядка, рассматриваемые в § 1.2 и 1.3, имеют следующие особенности.

1. Они ориентированы на исследование функции, унимодальной
на некотором начальном интервале , содержащем искомую точку локального минимума.

Начальный интервал D₀ будем называть исходным интервалом неопределенности, длину этого интервала обозначим L₀. Определение интервала D₀ осуществляется на первом (подготовительном) этапе, который называется этапом отделения (локализации) положения локального минимума. В зависимости от предполагаемых свойств минимизируемой функции для выполнения этого этапа используются различные способы, в том числе графические.

2. На втором этапе – этапе уточнения положения локального минимума – осуществляется последовательное уменьшение длины исходного интервала неопределенности, чтобы обеспечить требуемую точность вычисления оптимального решения х^*.

Действительно, если известно, что х^* Î , то точка х₀ = /2 (середина интервала) определяет значение х^* с погрешностью, не превышающей L₀ / 2 – половины длины интервала неопределенности. Пусть теперь число e > 0 задает требуемую точность определения х^*. Тогда если в процессе работы метода одномерной оптимизации длина текущего интервала L_k, содержащего х^*, равна 2e, то требуемая точность определения будет достигнута, если в качестве х^* выбрать точку – среднюю точку текущего интервала неопределенности D_k.

Таким образом, в процессе работы рассматриваемых методов итерационно строится некоторая последовательность вложенных интервалов неопределенности D_i, i = 0, 2, 3, …, k, … :

É D₁ = É … É D_k = É …

При этом если исходный интервал D₀ содержит искомую точку х^*,
то ее содержат и все остальные интервалы строящейся последовательности.

Работа метода завершается, когда длина очередного k-го интервала неопределенности окажется достаточно малой. Тогда искомую точку минимума определяют как середину последнего интервала неопределен-ности D_k.

Построение последовательности вложенных интервалов базируется на свойстве унимодальности функции на начальном интервале неопределенности. Рассмотрим основное правило, позволяющее последовательно уменьшать длину этого интервала. Пусть . Внутри этого интервала выберем каким-либо образом две точки – х₁, х₂, такие, что х₁ < х₂. Тогда возможны три случая (в силу унимодальности функции f(x)):

– если f(х₁) > f(х₂), точка минимума может быть только на интервале ;

– если f(х₁) < f(х₂), точка минимума может быть только на интервале ;

– если f(х₁) = f(х₂), точка минимума может быть только на интервале (х₁, х₂).

Во всех случаях исходный интервал неопределенности уменьшился на некоторую величину, в результате чего был получен новый интервал D₁, содержащий точку минимума. Этот интервал также может быть уменьшен аналогичным образом. Методы, которые будут рассмотрены ниже, отличаются друг от друга способом выбора на каждом шаге пробных значений х₁ < х₂ внутри текущего интервала неопределенности.