Ф.П. Васильев - Методы оптимизации (2002), страница 5

Метод золотого сечения. Симметричные методы Перейдем к описанию метода минимизации унимодальной функции иа отрезке, столь же простого, как метод деления отрезка пополам, но позволяющего решить задачу с требуемой точностью при меньшем количестве вычислений значений функции. Речь пойдет о методе золотого сечения. Е Как известно, золотым сечением отрезка называется деление отрезка на две неравные части так, чтобы отношение длины всего отрезка к длине большей части равнялось отношению длины большей части к длине меньшей части отрезка. Нетрудно проверить, что золотое сечение отрезка [а, Ь] производится двумя точками х, = а + (3 — ~/5)(6 — а)/2 = а + (6 — а) 0,381966011... и х = а+ (Л вЂ” 1)(Ь вЂ” а)/2 = а+ (6 — а) 0,618033989..., расположенными симметрично относительно середины отрезка, причем а < х, < х < Ь, (Ь вЂ” а)/(Ь вЂ” х,) =(Ь вЂ” х,)/(х — а) =(Ь вЂ” а)/(х — а) =(х — а)/(Ь вЂ” х ) = (45+ + 1)/2 = 1,618033989...

Замечательно здесь то, что точка х, в свою очередь производит золотое сечение отрезка [а, х,], так как х, — х, < х, — а = 6 — хз и (х, — а)/(х, — а) = =(х — а)/(х — х,). Аналогично точка х, производит золотое сечение отрезка [х„б].

Опираясь на это свойство золотого сечения, можно предложить следующий метод минимизации унимодальной функции /(х) на отрезке [а, Ь], Положим а, = а, Ь, = Ь. На отрезке [а„Ь,] возьмем точки хп х„производящие золотое сечение, и вычислим зйачения /(х,),/(хз). Далее, если /(х,) < /(х,), то примем а = а, Ь = х, х, = х,; если же /(х() > /(хз), то примем а, = х,, 6, = 6,, х, = х~. Г(оскольку функция /(х) унимодальна на [а, 6], то отрезок [а„Ь,] ймеет хотя бы одну общую точку с множеством Х„точек минимума /(х) на [а, д].

Кроме того, 6, — а, =(ч/5 — 1)(6 — а)/2 и весьма важно то, что внутри [а„Ь,] содержится точка х, с вычисленным значением /(х ) = ш!и(/(х();/(хз)), которая производит золотое сечение отрезка [аз, Ь,]. Пусть уже определены точки х„ ...,х ,, вычислены значения /(х,),... ..., /(х„ ,), найден отрезок [а „ 6„ ,] такой, что [а„ „ Ь„ ,] и Х, ф И, Ь , — а , = ((ч/5 — 1)/2)а-з(6 — а), и известна точка х (, производящая золотое сечение отрезка [а „ Ь ,] и такая, что /(х ,) = ппп /(х.) (о > 2). Тогда в качестве следующей точки возьмем точку х„= а„, + Ь„ — х„,, также производящую золотое сечение отрезка [а„„Ь„,], вычислим значение /(х„). 18 Гл.

Е МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ $4. МЕТОД ЗОЛОТОГО СЕЧЕНИЯ. СИММЕТРИЧНЫЕ МЕТОДЫ 19 Пусть для определенности а„, < х„< х„, < Ь, (случай х„, < х. рассматривается аналогично), Если /(х„) < /(х„,), то полагаем а„= а„ 6„= х„п х„= х„; если же /(х„)>/(х„,), то полагаем а„= х„, Ь„= Ь„ х„= х,. Йовый отрезок [а„, 6„] таков, что [а„, 6„] ОХ„ф Й, 6„— а„= =((Л вЂ” 1)/2)" '(Ь вЂ” а), точка х„производит золотое сечение [а„Ь„] и /(х„) = ш[п(/(х„);/(х„,)) = ппп /(х,.). ! из е ч Если число вычислений значений /(х) заранее не ограничено, то описанный процесс можно продолжать, например, до тех пор, пока не выполнится неравенство Ь вЂ” пч < з, где з — заданная точность. Если же число вычислений значений фуйкции /(х) заранее жестко задано и равно и, то процесс на этом заканчивается и в качестве решения задачи второго типа (см. $1) можно принять пару /(х„), х„, где /(х„) является приближением для /„= !и[ /(х), а точка х„служит приближением для множества Х, с е(,ь[ погрешностью р(х„, Х,) < тахТ܄— х„; х„— а ) = -(ъ/5 — 1)(܄— а„) = [ — у:/' (Ь вЂ” а) = Агс ! /т/5-[ъ" Вспомним, что с помощью метода деления отрезка пополам за и = 2/с вычислений значений функции /(х) в аналогичном случае мы получили точку хо с погрешностью р(х, Х„) < 2 "/э(6 — а — Б) < 2 "/'(6 — а) =В„.

Отсюда имеем А„/В„= (2ъ'2/(Л+ 1)) ю (О, 87...) — видно, что уже при небольших п преимущество метода золотого сечения перед методом деления отрезка пополам становится ощутимым. 2. Обсудим возможности численной реализации метода золотого сечения на ЭВМ. Заметим, что число Л на ЭВМ неизбежно будет задаваться приближенно, поэтому первая точка х, = и+ (3 — Л)(6 — а)/2 будет найдена с некоторой погрешностью. Посмотрим, как повлияет эта погрешность на результаты последующих шагов метода золотого сечения. Обозначим Ьо хх Ь вЂ” а„=((Л вЂ” 1)/2)" '(Ь вЂ” а) (и =1, 2,...).

Нетрудно проверить, что ".'ь„является решением конечно-разностного уравнения /ь, э = Ь„, + сь„, или хь„=ха„,— Л„ы я=3,4,..., (1) с начальными условиями /[ь, = Ь вЂ” п, сзэ = Ь вЂ” хы Как известно, линейно независимые частные решения этого уравнения имеют вид т," и т," (п = 1, 2,:..), где г, = (Л вЂ” 1)/2, т, = †(Л+ 1)/2— корни характеристического уравнения т'+ т- 1 =О, а любое решение уравнения (1) представимо в виде Ь„= Ат," + Вт,", и = 1, 2,..., (2) где постоянные А и В однозначно определяются начальными условиями из линейной системы А т, + Вт, = ьь„А т,' + Вт,' = с)ьэ.

(3) При ьь, = Ь вЂ” а, сь = Ь вЂ” х, из (3) имеем А = 2(Ь вЂ” а)/(Л вЂ” 1), В =О, и понятно что формула (2) в этом случае дает уже известное нам решение Ь„= тч '(Ь вЂ” а). Однако точка х, задана с погрешностью, поэтому А„/2 < П„„1 < 2Ао/3, т~ =1,..., Аг, (4) в системе (3) вместо точного значения ььэ придется взять приближенное аьз = ььз+ Б. Тогда постоянные А, В из (3) определятся с соответствующими погрешностями: А = А + Бы В = В+ Бэ, н вместо (2) с точными А, В будем иметь /т„=Аз;"+ Вт," (и =1,2,...). Поскольку 0< т, =О,б... <1, [т,[= 1, б...

> 1, то погРешность [/ь„— ть„[ = [Б,т,"+ Бэта" [ с возРастанием и будет расти очень быстро. Это значит, что уже прй не очень больших и отрезок [а„, 6„] и точки х„, х„т, = а„+ 6„— х будут сильно отличаться от тех, которые получились бы при работе с точными данными. Численные эксперименты на ЭВМ также подтверждают, что метод золотого сечения в описанном выше виде практически неприменим уже при небольших и. Как же быть? К счастью, имеется достаточно простая модификация метода золотого сечения, позволяющая избежать слишком быстрого возрастания погрешностей при определении точек х (и > 2).

А именно на каждом отрезке [о„Ь„], содержащем точку х с предыдущего шага, при выборе следующей точки х„т, нужно остерегаться пользоваться формулой х„„, = а, + ܄— х„, и вместо этого лучше непосредственно произвести золотое сечение отрезка [а„, 6„] и в качестве х„,, взять ту из точек а„ + (3 — ъ'5)(6„ — а )/2, ао + (ъ/5 в 1)(6„ — а„)/2, которая наиболее удалена от х (здесь под ъ'5 подразумевается какое-либо подходящее приближение этого числа). Конечно, после такой модификации метод золотого сечения, вообще говоря, теряет свойство симметричности и, быть может, уже не так красив, но зато вполне годится для приложений.

Нетрудно видеть, что этот метод может применяться и без априорного знания о том, что минимизируемая функция унимодальна, но в этом случае полученное решение может оказаться далеким от глобального минимума. 3. Метод золотого сечения относится к классу так называемых симметричных мешодоз. Дадим краткое описание произвольного симметричного метода минимизации функции /(х) на отрезке [а, 6), Первый шаг: на [а, 6] задается точка ж1 (а< х, < Ь), полагается а1 — — а, 6, = 6, х, = х, и вычисляется /(х1).

Пусть уже сделано и — 1 шагов (и > 2) и найдены отрезок [а„ы Ь ~] н точка хч 1 (ач 1 < х„~ < Ь 1) с вычисленным значением /(х„1), причем х ф (а„~ + 6„1)/2. Тогда на следующем и-м шаге берется точка х„= а„~ + 6„1' — х расположенная внутри [а„ ы 6„ ~], симметрична точке х„ ~ относительно середины этого отрезка — отсюда происходит название методов.

Затем вычйсляется значение /(х„) н сравнивается с /(х„ ~). Пусть для определенности ж, 1 < хч (случай х < хь ~ рассматривается аналогично), Тогда при /(я ~) < /(х„) полагается а„ = а„ и 6„ = хч, х„ = ж„ П если же /(х„ ~) > /(хе) то ао = х„ 1 6„ = 6 н хо = х„. если х г'-(а„ + 6„)/2 то процесс может быть продолжен дальше.

Может оказаться, что ж„= (а„+ 6„)/2, — в этом случае процесс заканчивается; при необходимости на [агп 6 ] мозкно продолжать поиск минимума аналогичным методом, начиная с выбора новой начальйой точки х„ ~ (а„ Э 6„)/2. Из описания симметричного метода видно, что всякий симметричный метод полностью апре. делается заданием отрезка ]а, Ь] и первой точки х1 (а < ж1 < 6). Отсюда следует, что в качестве другой характеристики симметричного метода можно взять длины /т„отрезков [а, Ь ] (и=1, 2,...), где П~ — -Ь-а, Аз — — шах(6 — хб х1 — а). Очевидно, дь „1) Гь /2 при всех и > [. Как видим, симметричные методы весьма просты и, пожалуй, даже изящны.