Этап установления границ интервала.
На этом этапе сначала выбирается исходная точка, а затем на основе правила исключения строится относительно широкий интервал, содержащий точку оптимума. Обычно поиск граничных точек такого интервала проводится с помощью эвристические методов поиска, хотя в ряде случаев можно также использовать методы экстраполяции. В соответствии с одним из эвристических методов, который был предложен Свенном (k+1)-я пробная точка определяется по рекуррентной формуле
где х0 – произвольно выбранная начальная точка, D – подбираемая некоторым способом величина шага. Знак D определяется путем сравнения значений f(х0), f(х0+ |D|) и f(х0 - |D|). Если f(х0 - |D|)³ f(х0)³ f(х0+ |D|), то, согласно предположению об унимодальности, точка минимума должна располагаться правее точки х0 и величина D выбирается положительной. Если изменить знаки неравенств на противоположные, то D следует выбирать отрицательной. Если же
f(х0 - |D|) ³ f(х0) £ f(х0+ |D|)
то точка минимума лежит между х0 - |D| и х0+ |D| и поиск граничных точек завершен. Случай, когда
f(х0 - |D|) £ f(х0) ³ f(х0+ |D|)
противоречит предположению об унимодальности. Выполнение этого условия свидетельствует о том, что функция не является унимодальной.
Пример
Рассмотрим задачу минимизации функции f(x)=(100-х)2 при заданной начальной точке х0=30 и величине шага |D|=5.
Знак D определяется на основе сравнения значений
f(х0) = f(30) = 4900
f(х0+ |D|) = f(35) = 4225
f(х0 - |D|) = f(25) = 5625
то величина D должна быть положительной, а координата точки минимума х* должна быть больше 30. Имеем х1 =х0 + D = 35. Далее х2 = х1 + 2D = 45, f(45) = 3025 < f(х1)
откуда х*>35.
х3 = х2 + 22D = 65, f(65) = 1225 < f(х2),
откуда х*>45.
х4 = х3 + 23D = 105 f(105) = 25 < f(х3),
откуда х*>65.
х5 = х4 + 24D = 185, f(185) = 7225 > f(х4)
следовательно, х*<185. Таким образом, шесть шагов вычислений х* позволили выявить интервал 65£ х*£185, в котором расположена точка х*. Заметим, что эффективность поиска граничных точек непосредственно зависит от величины шага D. Если D велико, то получаем грубые оценки координат граничных точек, и построенный интервал оказывается весьма широким. С другой стороны, если D мало, для определения граничных точек может потребоваться достаточно большой объем вычислений.
Дата добавления: 2022-05-27; просмотров: 90;