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

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

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

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

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

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