Методы одномерной оптимизации

К методам одномерной оптимизации относятся методы дихотомического деления, золотого сечения, чисел Фибоначчи, полиномиальной аппроксимации и ряд их модификаций.

Пусть задан отрезок , на котором имеется один минимум (в общем случае нечетное число минимумов). Согласно методу дихотомического деления (рис. 1,а) отрезок делят пополам и в точках, отстоящих от центра отрезка на величину допустимой погрешности , рассчитывают значения целевой функции и . Если окажется, что , то минимум находится на отрезке , если , то минимум — на , если — на . Таким образом, на следующем шаге вместо отрезка нужно исследовать суженный отрезок , или . Шаги повторяются, пока длина отрезка не уменьшится до величины погрешности . Таким образом, требуется не более шагов, где — ближайшее к целое значение, но на каждом шаге целевую функцию следует вычислять дважды.

Рис. 1. Одномерная минимизация: а — дихотомическое деление; б — золотое сечение

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

Условие получения такого значения а формулируется следующим образом , откуда с учетом того, что , имеем . Это значение и называют золотым сечением.

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

Согласно методу чисел Фибоначчи, используют числа Фибоначчи , последовательность которых образуется по правилу при , т.е. ряд чисел Фибоначчи имеет вид 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... Метод аналогичен методу золотого сечения с тем отличием, что коэффициент а равен отношению , начальное значение определяется из условия, что должно быть наименьшим числом Фибоначчи, превышающим величину , где — заданная допустимая погрешность определения экстремума. Так, если , то начальное значение , поскольку , и , на следующем шаге будет и т.д.

В соответствии с методом полиномиальной аппроксимации при аппроксимации квадратичным полиномом

(1)

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