2.4.3. Дихотомический метод

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

Дихотомия - греческое dichotomia, от dicha - на две части и tome - разрез, сечение.

.

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

Теорема 2. (О сокращении интервала неопределенности строго квазивыпуклой функции одной переменной). Пусть  и строго квазивыпуклая на . Пусть  и Случай 1. Если то  для всех . Случай 2. Если  то  для всех  .

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

Начальный этап. Задаем интервал неопределенности ; выбираем константу различимости  и конечную длину интервала неопределенности ; полагаем счетчик итераций ; переходим к шагу 1.

Основной этап.

Шаг 1. Если , то остановиться, оптимальная точка  найдена, иначе ; переходим к шагу 2.

Шаг 2. Если  то полагаем , иначе ; заменим,  перейдем к шагу 1.