Этап установления границ интервала.

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

где х₀ – произвольно выбранная начальная точка, D – подбирае­мая некоторым способом величина шага. Знак D определяется путем сравнения значений f(х₀), f(х₀+ |D|) и f(х₀ - |D|). Если f(х₀ - |D|)³ f(х₀)³ f(х₀+ |D|), то, согласно предположению об унимодальности, точка минимума должна располагаться правее точки х₀ и величина D выбирается положительной. Если изменить знаки неравенств на противопо­ложные, то D следует выбирать отрицательной. Если же

f(х₀ - |D|) ³ f(х₀) £ f(х₀+ |D|)

то точка минимума лежит между х₀ - |D| и х₀+ |D| и поиск гранич­ных точек завершен. Случай, когда

f(х₀ - |D|) £ f(х₀) ³ f(х₀+ |D|)

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

Пример

Рассмотрим задачу минимизации функции f(x)=(100-х)² при заданной начальной точке х₀=30 и величине шага |D|=5.

Знак D определяется на основе сравнения значений

f(х₀) = f(30) = 4900

f(х₀+ |D|) = f(35) = 4225

f(х₀ - |D|) = f(25) = 5625

то величина D должна быть положительной, а координата точки минимума х* должна быть больше 30. Имеем х₁ =х₀ + D = 35. Далее х₂ = х₁ + 2D = 45, f(45) = 3025 < f(х₁)

откуда х*>35.

х₃ = х₂ + 2²D = 65, f(65) = 1225 < f(х₂),

откуда х*>45.

х₄ = х₃ + 2³D = 105 f(105) = 25 < f(х₃),

откуда х*>65.

х₅ = х₄ + 2⁴D = 185, f(185) = 7225 > f(х₄)

следовательно, х*<185. Таким образом, шесть шагов вычислений х* позволили выявить интервал 65£ х*£185, в котором располо­жена точка х*. Заметим, что эффективность поиска граничных точек непосредственно зависит от величины шага D. Если D велико, то получаем грубые оценки координат граничных точек, и построен­ный интервал оказывается весьма широким. С другой стороны, если D мало, для определения граничных точек может потребоваться достаточно большой объем вычислений.