5.2.2. Метод парабол

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

Пусть дифференцируемая функция унимодальна на отрезке

.

Определение 2. Назовём тройку чисел выпуклой тройкой для функции , если

и

, . (1)

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

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

, по следующей формуле:

. (2)

Полученная точка принимается за приближенное значение минимума функции .

Удобно, когда в этом методе узлы –равноотстоящие, то есть , где . В этом случае из формулы (2) получаем

.

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

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

5.3. Методы нахождения начального отрезка локализации

Далее будем считать, что минимизируемая функция унимодальна на . Как видно из описания методов одномерной минимизации, для их применения необходимо знать начальный отрезок локализации либо выпуклую тройку точек. Напомним, что задачи одномерной минимизации, возникают, в частности, как задачи поиска полного шага в методах многомерной минимизации. Существуют три случая: полный шаг определяется на отрезке (например, в методе условного градиента), на полупрямой (например, в полношаговом градиентном методе), а также на всей число-вой оси (например, в методах покоординатного спуска).

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

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

Пусть дана точка . Задается . Вычисляется точка . Если , то . Если же , то полагаем и тогда .

Теперь мы можем описать метод простого перебора.