Метод золотого сечения алгоритм. Метод золотого сечения. Алгоритм метода золотого сечения для минимизации функции

Длину конечного интервала неопределенности, обеспечивающего заданную величину e , можно вычислить по формуле

Положив D n = e, можно определить соответствующее количество итераций:

Схема алгоритма метода дихотомии приведена на рис. 1.6.1-4.

Рис.1.6.1-4. Схема алгоритма поиска минимума методом дихотомии

Пример 1.6.2-1. Найти минимум функции f(x)=x 3 -x+e -х на отрезке c точностью e и вычислить количество итераций, требуемое для обеспечения точности.

Выберем d =0.001 и положим a = 0; b = 1;

При e = 0.1 x*=0.7183 f(x*)=0.1399, а при e = 0.01 x*=0.7066 f(x*)=0.13951
.

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

В основу метода положено разбиение отрезка неопределенности в соотношении золотого сечения, такого, что отношение длины его большей части ко всей длине отрезка равно отношению длины его меньшей части к длине его большей части:

l

Положим l =1 , тогда l 2 2 = 1 - l 2 , а l 2 2 + l 2 -1= 0, откуда

где k 1 , k 2 - коэффициенты золотого сечения.

В методе золотого сечения каждая точка (х 1 и х 2 )осуществляет золотое сечение отрезка (рис. 1.6.3-1).

или

Нетрудно проверить, что точка х 1 , но и отрезка . Точно так же точка х 2 осуществляет золотое сечение не только отрезка , но и отрезка [х 1 ;b]. Это приводит к тому, что значение целевой функции на каждой итерации (кроме первой) вычисляется один раз.

После каждой итерации длина отрезка неопределенности сокращается в 1.618 раза. Длина конечного отрезка неопределенности D n = 0.618 n D 0 , где D 0 = (b-a) – начальная длина отрезка.

Условие окончания процесса итераций D n e. Отсюда можно найти количество итераций, необходимое для достижения точки минимума:

отсюда логарифмируя, получим

Схема алгоритма метода золотого сечения приведена на рис. 1.6.3-2.

Пример 1.6.3-1. Пусть минимум функции f(x) = x 3 – x + e - x отделен на отрезке . Определить количества итераций и конечные длины отрезков неопределенности, необходимые для достижения заданных точностей e=0.1 и e=0.01.

При e = 0.1 x*=0.718847, f(x*)=0.139925.

При e = 0.01 x*=0.704139, f(x*)=0.139516.

1.6.3-2. Схема алгоритма поиска минимума методом золотого сечения

Сравнение методов

Накаждойитерации при использовании метода дихотомии отрезок неопределенности сокращается практически в два раза, а при использовании метода золотого сечения в 1.618 раз.

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

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

1.6.6. Тестовые задания по теме
«Одномерная оптимизация»

1. Оптимальное значение функции –это

1) наилучшее

2) наименьшее

3) наибольшее

4)

2. Локальный минимум – это

1)

2)

3)

4) в списке нет правильного ответа

3. Глобальный минимум – это

1) один из минимумов функции в области допустимых значений

2) наименьшее значение функции в некоторой окрестности

3) наименьший из минимумов в области допустимых значений

4) в списке нет правильного ответа

Метод основан на делении текущего отрезка [а, b ], где содержится искомый экстремум, на две неравные части, подчиняющиеся правилу золотого сечения, для определения следующего отрезка, содержащего минимум (максимум).

Золотое сечение определяется по правилу: отношение всего отрезка к большей его части равно отношению большей части отрезка к меньшей. Ему удовлетворяют две точки c и d , расположенные симметрично относительно середины отрезка.

Путем сравнения R (c ) и R (d ) определяют следующий отрезок, где содержится максимум. Если R (d ) > R (c ), то в качестве следующего отрезка выбирается отрезок [с, b ], в противном случае – отрезок [a , d ].

Новый отрезок снова делится на неравные части по правилу золотого сечения. Следует отметить, что точка d является и точкой золотого сечения отрезка [с, b ], т.е.

Поэтому на каждой следующей итерации (кроме "запуска" метода на исходном отрезке) нужно вычислять только одно значение критерия оптимальности.

Существуют аналитические формулы для расчета новой точки на отрезке, где находится максимальное значение R (x ), которую нетрудно получить:

Условие окончания поиска – величина отрезка, содержащего максимум, меньше заданной погрешности.

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

На рис. 3 приведены два этапа поиска максимума функции методом золотого сече­ния.

Рис. 3. Иллюстрация метода золотого сечения: 1 – интервал, включающий в себя искомый максимум функции после первого этапа (первого золотого сечения в точках c и d ); 2 – то же, после второго этапа (новая точка е и старая точка d )

Алгоритм метода золотого сечения для минимизации функции.

Начальный этап. Выбрать допустимую конечную длину интервала неопределённости l > 0. Пусть [а , b ] – начальный интервал неопределённости. Положить
и
. Вычислить R (c ) и R (d ), положить k = 1 и перейти к основному этапу.

Основной этап.

Шаг 1. Если b ­ k – a k < l , то остановиться; точка минимума принадлежит интервалу [а k , b k ]. В противном случае если R (c k ) > R (d k ), то перейти к шагу 2, а если R (c k ) ≤ R (d k ), то к шагу 3.

Шаг 2. Положить a k +1 = c k и b k +1 = b k ,
. Вычислить R (d k +1) и перейти к шагу 4.

Шаг 3. Положить a k +1 = a k и b k +1 = d k ,
. Вычислить R (c k +1) и перейти к шагу 4.

Шаг 4. Заменить k на k + 1 и перейти к шагу 1.

Пример.

Дана функция R (x ) = D sin(Ах B + С), где коэффициенты имеют следующие значения: А = 1,0, В = 1,0, С = 1,0, D = 1,0. Найти максимум на интервале: [-1, 2]. Ошибка задается по х: ε =0,05.

Результаты расчетов. Для "запуска" метода найдем две симметричные точки золотого сечения для отрезка [-1, 2]:

x 1 =0,145898, х 2 =0,85410197.

Значения критериев в этих точках соответственно R(x 1) = 0,911080, R (x 2) = 0,960136. Следовательно, новым отрезком является , внутри которого находится максимальное из найденных значений R . Точка золотого сечения для нового отрезка будет x 3 =0,58359214, a R (x 3) =0,99991813. Далее приведены только координаты лучших точек при очередном шаге, номер шага и значения критерия в этих точках.

х 3 = 0,58359214; R 3 = 0,99991813;

х 4 =0,58359214; R 4 = 0,99991813

х 5 = 0,58359214; R 5 = 0,99991813;

х 6 = 0,58359214; R 6 = 0,99991813

х 7 = 0,58359214; R 7 = 0,99991813;

х 8 = 0,55920028; R 8 = 0,99993277;

х 9 = 0,55920028; R 9 = 0,99993277.

Всего было проведено 10 вычислений критерия оптимальности.

В этой блок-схеме y, z - точки деления отрезка ,причем y < z .

y = 0.618a + 0.382b

z = 0.382a + 0.618b

Fy = f(y) : Fz = f(z)

b - a < e b - a < e

z = y: Fz = Fy y = z: Fy = Fz

y = 0.618a + 0.382b z = 0.382a + 0.618b

Fy = f(y) Fz = f(z)

Вывод x, f(x)

Пример. Для оценки сопротивления дороги движению автомобиля при скорости v км/ч можно использовать эмпирическую формулу f(v) = 24 - 2/3*v + 1/30*v 2 (для шоссе). Определить скорость, при которой сопротивление будет минимальным.

Решение.

1) Данную задачу легко решить с помощью вычисления производной:

, v = 10 км/ч.

2) Решение с помощью метода "золотого сечения". Начальные границы интервала неопределенности примем равными a = 5, b = 20.

Решение для первого этапа:

y = 0.618*5 + 0.382*20 » 10.7: z = 0.382*5 + 0.618*20 » 14.3

Fy = 24 - 2*10.7/3 + 10.7 2 /30 » 20.7: Fz = 24 - 2*14.3/3 + 14.3 2 /30 » 21.3

Результаты вычислений обычно представляют в виде таблицы. Расчеты проводятся в соответствии с блок-схемой с погрешностью e = 1 км/ч.

После пяти шагов оптимизации искомое значение скорости равно v = (8.6+10.7)/2 = 9.65 км/ч. После еще одного шага этот результат получается с меньшей погрешностью v = (9.4+10.7)/2 = 10.05 км/ч.

Оптимизация функции многих переменных Минимум функции нескольких переменных

Минимум дифференцируемой функции многих переменных u = f(x 1 , x 2 , … , x n) можно найти, исследуя ее значение в критических точках, которые определяются из решения системы дифференциальных уравнений

Отметить, что в данном случае критические точки могут соответствовать либо экстремальным, либо "седловым" точкам (точкам "минимакса"). Под этими точками понимаются такие точки, в которых по некоторым направлениям функция имеет минимум, а по остальным направлениям - максимум.

Пример постановки задачи. Пусть требуется спроектировать контейнер в форме прямоугольного параллелипипида объемом V=1 м 3 , причем на его изготовление необходимо израсходовать как можно меньше материала.

При постоянной толщине стенок это условие означает, что площадь полной поверхности контейнера S должна быть минимальной. Если обозначить через x 1 , x 2 и x 3 длины ребер контейнера, то задача сведется к минимизации функции:

S = 2 (x 1 x 2 + x 1 x 3 + x 2 x 3) .

Эта функция в данном случае является целевой, а условие V = 1 м 3 - ограничением-равенством, которое позволяет исключить один параметр:

.

Задача свелась к минимизации функции двух переменных. В результате ее решения будут найдены значения параметров оптимизации x 1 и x 2 , а затем и x 3 . В приведенном примере фактически получилась задача безусловной оптимизации, так как ограничение-равенство было использовано для исключения параметра x 3 .

Решение. После дифференцирования получим

Отсюда находят x 1 = x 2 =1 м, x 3 = 1/(x 1 x 2) = 1 м. Таким образом, оптимальной формой контейнера в данном случае является куб, длина ребра которого равна 1 м.

При таком подходе могут возникнуть серьезные трудности при решении системы нелинейных уравнений.

Вместе с тем, можно эту задачу усложнить. Например, потребуем, чтобы данный контейнер имел длину не менее 2 м. Это условие запишется в виде ограничения-неравенства на один из параметров, например, x 1 ³ 2 .

Таким образом, получили следующую условную задачу оптимизации: минимизировать функцию

учитывая ограничение-неравенство x 1 ³ 2 и найти оптимальные значения факторов x 2 , x 3 (x 2 ³0, x 3 ³0).

Графическое представление функции двух переменных: рассмотреть функцию

f(x 1 , x 2) = x 1 2 + x 2 2 .

Показать линии равного уровня для этой функции.

Дать общий вид трех возможных вариантов линий равного уровня, показать "овражные" функции.

В общем случае для поиска минимального значения целевой функции можно ввести дискретное множество точек (узлов) путем разбиения интервалов изменения параметров x 1 и x 2 на части с шагами h 1 и h 2 . В полученных узлах можно вычислить значения целевой функции и среди них найти наименьшее. Однако в многомерных задачах оптимизации такой подход требует слишком большого объема вычислений.

Опять рассмотрим задачу из примера 2.6, в которой требуется минимизировать f(х)=(100-х ) 2 в интервале 60£х £150. Для того чтобы перейти к интервалу единичной длины, проведем замену переменной, положив w=(х - 60)/90. Таким образом, задача принимает следующий вид: минимизировать f(w) = (40 – 90w ) 2 при ограничении 0£w£1.

Итерация 1. I 1 = (0, 1); L 1 = l. Проведем два первых вы­числения значений функции:

w 1 = t = 0,618, f(w 1) = 244,0

w 2 = 1-t = t 2 = 0,382, f(w 2) = 31,6

Так как f(w 2) < f(w 1) и w 2 < w 1 , интервал w ³ w 1 исключается.

Итерация 2. I 2 =(0. 0,618); L 2 = 0,618 = t . Следующее вы­числение значения функции проводится в точке

w 3 = t-t 2 = t(1-t) = t 3 = 0,236, f(w 3) = 352.

Так как f(w 3) > f (w 2) и w 3 < w 2 , интервал w £ w 3 , исключается.

Итерация 3. I 3 =(0,236, 0,618); L 3 = 0,382 = t 2 . Следующее вычисление значения функции проводится в точке, расположенной на расстоянии t ´ (длина полученного интервала) от левой гра­ничной точки интервала, или на расстоянии (1-t ) ´ (длина ин­тервала) от правой граничной точки. Таким образом,

w 4 =0,618 – (1-t)L 3 = 0.618 - t 2 L 3 0.618 - t 2 (t 2) = 0.618 - t 4 = 0,472, f(w 4) = 6,15.

Так как f(w 4) < f (w 2) и w 4 > w 2 , интервал w £ w 2 исключается.

В результате получен следующий интервал неопределенности: 0,382 £ w £ 0,618 для переменной w, или 94,4£х £115,6 для перемен­ной х .

Если в процессе поиска проведено шесть вычислений значений функции, то длина результирующего интервала для переменной w равна

t N -1 = t 5 = 0,09,

что соответствует интервалу длины 8,1 для переменной х . Для срав­нения напомним, что в аналогичной ситуации метод деления интер­вала пополам привел к получению интервала длины 11,25.

В общем случае если правая и левая граничные точки интервала неопределенности (обозначим их через XR и XL ) известны, то ко­ординаты всех последующих пробных точек, получаемых в соответ­ствии с методом золотого сечения, можно вычислить по формулам

w = XR - t n или w = XL + t n , в зависимости от того, какой подынтервал был исключен на преды­дущей итерации – левый или правый. В приведенных выше форму­лах через t n обозначена n -я степень t , где п – количество вычисле­ний значений функции.

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

Сравнение методов исключения интервалов. Ниже проводится сравнение относительных эффективностей рас­смотренных методов исключения интервалов. Обозначим длину неходкого интервала неопределенности через L 1 , а длину интервала, получаемого в результате N вычислений значений функции, - через L N . В качестве показателя эффективности того или иного метода исключения интервалов введем в рассмотрение характеристику относительного уменьшения исходного интервала FR(N)=L N /L 1

Напомним, что при использовании метода деления интервала пополам и метода золотого сечения длина получаемого интервала составляет L 1 (0,5) N /2 и L 1 (0.618) N -1 соответственно. Следовательно, относительное уменьшение интервала после N вычислений значений функции равно

FR(N) = (0,5) N /2 для метода деления интервала пополам;

FR(N) = (0,618) N -1 для метода золотого сечения.

Для сравнения рассмотрим также метод равномерного поиска, в соответствии с которым оценивание функции проводится в N равноотстоящих друг от друга точках (при этом интервал L 1 де­лится на (N+1) равных интервалов длины L 1 /(N+l)). Пусть х* – точка, в которой наблюдается минимум функции f(х). Тогда точка истинного минимума f(x) оказывается заключенной в интервале

откуда L N = 2L 1 /(N+l). Следовательно, для метода равномерного поиска FR(N)=2/(N+1).

В табл. 6.2 представлены значения FR(N), соответствующие выбранным N, для трех методов поиска. Из таблицы следует, что поиск величины относительного уменьшения интервала с помощью метода золотого сечения

Таблица 6.2

обеспечивает наибольшее от­носительное уменьшение исходного интервала при одном и том же количестве вычислений значений функции. С другой стороны, можно также сравнить количества вычислений значения функции, требуе­мые для достижения заданной величины относительного уменьшения интервала или заданной степени точности. Если величина FR(N) = E задана, то значение N вычисляется по следующим формулам:

для метода деления интервала пополам

N=2 ln(E)/ln(0,5),

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

N=1+,

для метода равномерного поиска

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

Используйте метод золотого сечения для того, чтобы отыскать с точностью \varepsilon локальный максимум функции на отрезке .

Входные данные

a, b — концы отрезка, на котором требуется найти максимум, и точность \varepsilon.

Выходные данные

Точка локального максимума и локальный максимум в формате (x_{max}, y_{max}).

Тесты

Алгоритм

Для начала проанализируем данную нам функцию. Найдем ее область определения.

D(f) = x^2 + 1 + \cos x > 0

D(f) = x^2 + 1 + \cos x = x^2 + \frac{1}{2} \cos^2 \frac{x}{2} > 0 \forall x \in \mathbb{R}

Таким образом, функция определена на всей числовой оси и мы имеем право рассматривать функцию для любого значения аргумента (также это видно по графику).
Однако следует помнить о том, что используемый нами метод золотого сечения принадлежит к группе симметричных методов и накладывает некоторые ограничения на исследуемую функцию. Применимость данного метода гарантируется только для непрерывных , унимодальных функций.
Унимодальная функция — это функция, которая монотонна на обе стороны от точки максимума x_{max}.

x_1 \le x_2 \le x_{max} \Rightarrow f(x_1) \le f(x_2) \lef(x_{max})

X_1 \ge x_2 \ge x_{max} \Rightarrow f(x_1) \le f(x_2) \lef(x_{max})

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

Проведя анализ функции, обратимся к самому методу золотого сечения.

Для того чтобы найти определенное значение функции на заданном отрезке, отвечающее заданному критерию поиска (в нашем случае максимум), рассматриваемый отрезок требуется поделить в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки x_1 и x_2 такие, что

\frac{b — a}{b — x_1} = \frac{b — a}{x_2 — a} = \varphi = \frac{1 + \sqrt{5}}{2}

То есть точка x_1 делит отрезок в отношении золотого сечения. Аналогично x_2 делит отрезок в той же пропорции. Для нахождения максимума выполняем следующую последовательность действий:

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

Код программы: