17. Одномерная задача оптимизации. Аналитическое решение и решение методом золотого сечения.

Задачи на экстремум.Одномерная задача оптимизации в общем случае формулируется следующим образом. Найти наименьшее (или наибольшее) значение целевой функции y=f(x), заданной на множестве , и определить значение проектного параметра x, при котором целевая функция принимает экстремальное значение.

Будем рассматривать методы оптимизации для разных классов целевых функций. Простейшим из них является случай дифференцируемой функции f(x) на отрезке [a,b], причем функция задана в виде аналитической зависимости y=f(x), и может быть найдено явное выражение для ее производной f(x). Нахождение экстремумов таких функций можно проводить известными из курса высшей математики методами дифференциального исчисления.

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

Метод золотого сечения

Одним из наиболее эффективных методов, в которых при ограниченном количестве вычислений f(x) достигается наилучшая точность, является метод золотого сечения. Он состоит в построении последовательности отрезков [a₀,b₀], [a₁,b₁], ... , стягивающихся к точке минимума функции f(x). На каждом шаге, за исключением первого, вычисление значения функции f(x) проводится лишь один раз. Эта точка, называемая золотым сечением, выбирается специальным образом.

Рис. 2.

На первом шаге процесса оптимизации внутри отрезка [a₀,b₀] (рис. 2, а) выбираем две внутренние точки x₁ и x₂ и вычисляем значения целевой функции f(x₁) и f(x₂). Поскольку в данном случае f(x₁)<f(x₂), очевидно, что минимум расположен на одном из прилегающих к x₁ отрезков [a₀,x₁] или [x₁,x₂]. Поэтому отрезок [x₂,b₀] можно отбросить, сузив тем самым первоначальный интервал неопределенности.

Второй шаг проводим на отрезке [a₁,b₁] (рис. 2, б), где a₁=a₀, b₁=x₂. Нужно снова выбрать две внутренние точки, но одна из них (x₁) осталась из предыдущего шага, поэтому достаточно выбрать лишь одну точку x₃, вычислить значение f(x₃) и провести сравнение. Поскольку здесь f(x₃)>f(x₁), ясно, что минимум находится на отрезке [x₃,b₁]. Обозначим этот отрезок [a₂,b₂], снова выберем одну внутреннюю точку и повторим процедуру сужения интервала неопределенности. Процесс оптимизации повторяется до тех пор, пока длина очередного отрезка [a_n,b_n] не станет меньше заданной величины .

Теперь рассмотрим способ размещения внутренних точек на каждом отрезке [a_k,b_k]. Пусть длина интервала неопределенности равна l, а точка деления делит его на части l₁, l₂: l₁>l₂, l= l₁+ l₂. Золотое сечение интервала неопределенности выбирается так, чтобы отношение длины большего отрезка к длине всего интервала равнялось отношению длины меньшего отрезка к длине большего отрезка:

. (7)

Из этого соотношения можно найти точку деления, определив отношение l₂/l₁. Преобразуем выражение (7) и найдем это значение:

Поскольку нас интересует только положительное решение, то

Отсюда l₁ 0.618l, l₂ 0.382l.

Поскольку заранее неизвестно, в какой последовательности (l₁ и l₂ или l₂ и l₁) делить интервал неопределенности, то рассматривают внутренние точки, соответствующие двум этим способам деления. На рис. 2, а точки деления x₁ и x₂ выбираются с учетом полученных значений для частей отрезка. В данном случае имеем

.

После первого шага оптимизации получается новый интервал неопределенности - отрезок [a₁,b₁] (см. рис. 2, б). Можно показать, что точка x₁ делит этот отрезок в требуемом соотношении, при этом

.

Используя полученные соотношения, можем записать координаты точек деления y и z отрезка [a_k,b_k] на k+1-м шаге оптимизации (y<z):

. (8)

При этом длина интервала неопределенности равна

. (9)

Процесс оптимизации заканчивается при выполнении условия d_k<. При этом проектный параметр оптимизации составляет a_k<x<b_k. Можно в качестве оптимального значения принять x = a_k (или x = b_k, или x = (a_k + b_k)/2 и т.п.).