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

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

Поясним сначала идею метода геометрически, а затем выведем необхо­димые соотношения.

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

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

Теперь рассмотрим способ размещения внутренних точек на каждом отрезке . Пусть длина интервала неопределенности равна , а точка деления разбивает его на части . Золотое сече­ние интервала неопределенности выбирается так, чтобы отношение длины большего отрезка к длине всего интервала равнялось отношению длины меньшего отрезка к длине большего отрезка:

(1).

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

, , ,

,

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

.

Отсюда , . Поскольку заранее известно, в какой последовательности (и или и ) делить интервал неопределенности, то соответствующие двум этим способом деления.

На рис.точки деления и выбираются с учетом полученных значений для частей отрезка. В данном случае имеем

.

После первого шага оптимизации получается новый интервал неопределенности – отрезок (рис. ). Можно показать, что точка делит этот отрезок в требуемом отношении, при этом , . Для этого проведем очевидные преобразования:

,

,

.

Вторая точка деления выбирается на таком же расстоянии от левой границе отрезка, т.е. .

И снова интервал неопределенности уменьшается до размера

.

Используя полученные соотношения можно записать координаты точек деления и отрезка на -м шаге оптимизации :

.

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

.

Процесс оптимизации заканчивается при выполнении условия . При этом проектный параметр оптимизации составляет . Можно в качестве оптимального значения принять (или , или и т.п.).

Блок-схема метода золотого сечения:

.