Методы Оптимизации Систем Автоматизированного Проектирования

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

Постановка задачи.

Тебуется найти безусловный минимум функции f(x) одной переменной, т.е. такую точку , что .

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

Определение. Точка производит «золотое сечение» отрезка, если отношение длины всего отрезка к большей части равно отношению большей части к меньшей.

Рассмотрим для простоты отрезок [0,1] единичной длины.

Ясно, что на отрезке имеется две таких точки и , они симметричны относительно концов. Точка производит золотое сечение отрезка [A,C] , а точка производит золотое сечение отрезка [BD]. Положим |AB|= x. Тогда |BD|=1-x. В соответствии с определением точки «золотого сечения» имеем: . Решив эту пропорцию, получим .

Стратегия поиска.

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

Алгоритм.

Задать начальный интервал неопределенности и требуемую точность .

Вычислить точки ,.

вычислить значения : ,

Стр.: ..., 2, 3