Файл: Сахарова Людмила Викторовна, Лукьянова Галина Викторовна Методы оптиизации для машинного обучения учебное пособие.doc

;

б) т.е. .

Отсюда получаем, что  = . Длина последнего отрезка равна 2(6 – а)/п, а точка x_mявляется его серединой. Поэтому .

Таким образом, чтобы обеспечить требуемую точность  опреде­ления точки х*, число отрезков разбиения п необходимо выбрать из условия , т.е. .

2. Пусть реализация метода перебора потребовала N вычисле­ний функции f (х). Это означает, что отрезок [а; b] был разбит на n=N–1 частей и достигнутая точность определением x* составила . Поэтому точность решения (N), которую обеспе­чивает метод перебора в результате N вычислений f (х),будет

. (2.10)

Пример 2.3. Метод перебора.

Решить задачу f (х)=x⁴+e^–x min, x[0; 1] с точностью до  = 0,1.

Функция f (х)унимодальна на отрезке [0; 1] (проверьте!). Найдем число n отрезков разбиения: , т.е. можно взять n = 10. Вычислим значения f (x_i),где x_i=0,1i,i= 0, .., 10 и запишем их в табл. 2.1.

Таблица 2.1

xi	0,0	0,1	0,2	0,3	0,4	0,5	0,6	0,7	0,8	0,9	1,0
f (xi)	1.00	0,90	0,82	0.75	0,70	0,67	0.68	0,74	0,86	1,06	1,37

---

В этой таблице подчеркнуто минимальное из вычисленных значенийf (x). Та­ким образом, х*  0,5, f *  0,67.

2.2.2. МЕТОДЫ ИСКЛЮЧЕНИЯ ОТРЕЗКОВ

В методе перебора, рассмотренном выше, точки x_i, в которых оп­ределяются значения f (x), выбирают заранее. Если же для выбора очередной точки вычисления (измерения) f (x) использовать информа­цию, содержащуюся в уже найденных значениях f (x), то поиск точки минимума можно сделать более эффективным, т.е. сократить число определяемых для этого значений f (x), как, например, в методе пораз­рядного поиска.На один из путей такого более эффективного поиска точки х* ука­зывает свойство 3 унимодальных функций (см. формулу (2.3)).Пусть а < x₁<х₂<b. Сравнив значения f (x) в точках x₁ и х₂ (проб­ных точках), можно сократить отрезок поиска точки х *, перейдя к отрезку [а; х₂], если или к отрезку m [x_1; b] если (рис. 2.6). Описанную процедуру можно повторить необходимое число раз, последовательно уменьшая отрезок, содержащий точку миниму­ма. Когда длина последнего из найденных отрезков станет достаточно малой, следует положить , где – одна из точек этого отрезка, например, его середина. Методы минимизации, основанные на этом принципе, называются методами исключения отрезков.Чтобы относительное уменьшение отрезка на каждой итерации не зависело оттого, какая из его частей исключается из дальнейшего рассмотрения, пробные точки следует располагать симметрично относительно середины исходного отрезка. В зависимости от способа вы­бора пробных точек получаются различные методы исключения отрез­ков. На практике используются следующие.Рис. 2.6. Уменьшение отрезка поиска точки минимума методами исключения отрезковПервый метод деления отрезка пополам (дихотомии). В этом методе точки x₁ и х₂располагаются близко к середине очередного отрезка [

---

а; b], т.е:, (2.11)где  > 0 – малое число. При этом отношение длин нового и исходного отрезков близко к 1/2, этим и объясняется название метода.Отметим, что для любых точек x₁ и х₂ величина  > 1/2, поэтому указанный выбор пробных точек объясняется стремлением обеспечить максимально возможное относительное уменьшение отрезка на каж­дой итерации поиска х*.В конце вычислений по методу дихотомии в качестве приближенного значения х* берут середину последнего из найденных отрезков [а; b], убедившись предварительно, что достигнуто неравенство .Опишем алгоритм метода деления отрезка пополам. Шаг 1. Определить x₁ и х₂ по формулам (2.11). Вычислить f (x₁) и f (x₂).Шаг 2. Сравнить f (x₁) и f (x₂). Если , то перейти к отрезку [а; x₂], положив b = x₂ , иначе – к отрезку [x₁; b], положив а = x₁ .Шаг 3. Найти достигнутую точность Если , то пе­рейти к следующей итерации, вернувшись к шагу 1. Если , то за­вершить поиск х*, перейдя к шагу 4.Шаг 4. Положить .Замечания:1. Число  из (2.11) выбирают на интервале (0;2) с учетом сле­дующих соображений:а) чем меньше , тем больше относительное уменьшение длины отрезка на каждой итерации, т.е. при уменьшении  достигается более высокая скорость сходимости метода дихотомии;б) при чрезмерно малом  сравнение значений f (x) в точках x₁ и х_{2 ,} отличающихся на величину , становится затруднительным. Поэтому вы­бор  должен быть согласован с точностью определения f (x) и с количе­ством верных десятичных знаков при задании аргумента х.2. Число п итераций метода дихотомии, необходимое для опреде­ления точки

---

х* с точностью до , определяется неравенством . (2.12)Обозначим длину исходного отрезка [а; b] через ₀. Длина отрезка, полученного после первой итерации, будет ₁ =, после второй итерации , после третьей – , и т.д.Таким образом, в результате п итераций длина отрезка поиска точки х* станет .При этом будет достигнута точность определения точки минимума . Находя п из условия, (2.13)получаем неравенство (2.12).3. Величина  может быть выбрана достаточно малой, поэтому, пренебрегая ею в (2.12), получаем: . На каждой итерации метода дихотомии вычисляют два значения f (x). Поэтому после N вы­численийf (x) производят n=N/2 итераций и достигают точность определения х* :. (2.14)Пример 2.5. Метод деления отрезка пополам.Решить задачу, приведенную в примерах 2.3 и 2.4: , , =0,1.Выберем =0,02. Итерация 1.Шаг 1.x₁ = 0,49, x₂ = 0,51. f (x) = 0,670, f (x₂) = 0,688. Шаг 2.f (x₁) > f (x₂), поэтому полагаем a =x₁ = 0,49. Шаг 3. (b–а)/2 = 0,255 > 0,1, т.е. переходим к следующей итерации. Результаты вычислений на остальных итерациях записаны в табл. 2.2.Таблица 2.2

Номер итерации	а	b	b–a 2	x1	x2	f (x1)	f (x2)	Сравнение f (x1) и f (x2)
2	0,49	1	0,26	0,735	0,755	0,771	0,792	f (x1) < f (x2)
3	0,49	0,755	0,13	0,613	0,633	0,683	0,691	f (x1) < f (x2)
4	0.49	0,633	0,07	0,07 < 0,1 – точность достигнута

---

Таким образом, , f ^*f (0,56)  0,67 (сравните с результатами решения примеров 2.3 и 2.4). Метод золотого сечения. Рассмотрим такое симметричное распо­ложение точек x₁ и х₂ на отрезке [а; b], при котором одна из них ста­новится пробной точкой и на новом отрезке, полученном после иск­лючения части исходного отрезка. Использование таких точек позво­ляет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения f (x), так как дру­гое значение уже найдено на одной из предыдущих итераций.Найдем точки x₁ и х₂ , обладающие указанным свойством.Рассмотрим сначала отрезок [0; 1] и для определенности предпо­ложим, что при его уменьшении исключается правая часть этого от­резка. Пусть х₂ = , тогда симметрично расположенная точка х₁ = 1– (рис. 2.7).Рис. 2.7. Определение пробных точек в методе золотого сеченияПробная точка х₁ отрезка [0; 1] перейдет в пробную точку х₂ = 1– нового отрезка [0; т]. Чтобы точки х₂ = , и х₂ = 1– делили отрезки [0; 1] и [0; ] в одном и том же отношении, должно выполняться равенство или , откуда находим положительное значение … Таким образом, х₁ = 1– = , .Для произвольного отрезка [а; b] выражения для пробных точек примут вид ;  . (2.15)Замечания:1. Точки x₁ и х₂ из (2.15) обладают следующим свойством: каждая из них делит отрезок [а; b] на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньшей частей отрезка. Точки с таким свойством называются

---