Численные методы отыскания безусловного экстремума: оптимальный пассивный поиск

Лекция 4 Тема 2.1. Численные методы отыскания безусловного экстремума в одномерном случае 2.1.3. Оптимальный пассивный поиск Пусть требуется путем пассивного поиска найти точку х * [0, 1], в которой унимодальная на отрезке [0, 1] функция f(x) достигает наименьшего значения f* = f(х*). Минимаксный метод поиска, в котором информация о значениях функции, вычисленных в предшествующих точках, не может быть использована, называют оптимальным пассивным поиском. Рассмотрим алгоритм такого поиска при различном числе N точек, выбираемых на отрезке [0, 1]. Если N= 1, то единственную точку целесообразно выбрать в середине отрезка, т.е. принять х1 = 1/2 (рис. 2.1.4). Рис. 2.1.4 В этом случае вследствие унимодальности функции f(x) имеем f* = f(1/2). Поэтому наименьшая возможная длина интервала неопределенности равна l*1=1 и можно гарантировать, что выбор в качестве точки х* [0, 1] точки х1=1/2 приведет к погрешности не более Δ*1 = l*1/2 = 1/2. При любом ином положении точки х1 погрешность при выборе х* = х1 будет Δ1> Δ*1, так как в действительности точка х* может лежать на большей части отрезка [0, 1]. Если при N = 2 (рис. 2.1.5) две точки расположить на отрезке [0, 1] так, чтобы они делили его на равные части, т.е. выбрать х1 = 1/3 и х2= 2/3, то точка х* [0, 1] будет найдена с точностью Δ*2 = 1/3, а наименьшая длина интервала неопределенности составит l*2 = 2 Δ*2 = 2/3. В самом деле, если f(1/3) < f(2/3) (рис. 2.1.5, а), то в силу унимодальности функции f(x) отрезок [2/3, 1] можно исключить и считать, что х* [0, 2/3]. 1 Рис. 2.1.5 Тогда при выборе х* = 1/3 наибольшая погрешность равна Δ2 = 1/3 и f* f(1/3). Если же окажется, что f(1/3) > f(2/3) (рис. 2.1.5, б), то можно исключить отрезок [0, 1/3] и считать, что х* [1/3, 1]. И в этом случае выбор х* = 2/3 приведет к погрешности не более Δ2 = 1/3, а f* f(2/3). Заметим, что при f(1/3)= f(2/3) можно исключить любой из указанных отрезков, гарантируя ту же точность нахождения точки х* [0, 1]. При ином делении отрезка [0, 1] на части двумя точками длина какой-то из его частей будет больше 1/3 и в действительности точка х* может принадлежать именно этой части, так что получим погрешность Δ2 > Δ*2 = 1/3. Рассуждая аналогично, можно заключить, что при N = 3 нужно также выбирать точки равномерно на отрезке [0, 1]: х1 = 1/4, х2 = 2/4, х3 = 3/4, обеспечив точность Δ*3 = 1/4 нахождения точки х* [0, 1] и наименьшую длину l*3 = 1/2 интервала неопределенности. В случае произвольного N N по тем же соображениям надо выбирать точки xk = [0,1] , k= , (2.1.4) обеспечивая точность Δ*N = 1/(N + 1) нахождения точки х* и наименьшую возможную длину интервала неопределенности l*N = (2.1.5) Таким образом, оптимальный пассивный поиск состоит в выборе точек, равномерно расположенных на отрезке. При этом (2.1.5) дает оценку скорости сходимости пассивного поиска с ростом числа N точек, так как скорость сходимости любого метода прямого поиска можно характеризовать скоростью уменьшения интервала неопределенности с возрастанием N. Пример 2.2. При заданной наибольшей допустимой длине ε* = 0,2 интервала неопределенности, используя оптимальный пассивный поиск, найдем точку х* [0, 1], в которой унимодальная на отрезке [0, 1] функция f(x) = х3 - х + е-х достигает наименьшего на этом отрезке значения. Из (2.1.5) следует, что для этого необходимо принять N = 9 и в соответствии с (2.1.4) вычислить значения функции f(x) в точках xk = k/10 , k = : 2 x 0,1 f(x) 0,81 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 0,63 0,47 0,33 0,23 0,17 0,14 0,16 0,18 Из представленных результатов вычислений можно сделать вывод, что интервалом неопределенности является интервал (0,6, 0,8), а х* = 0,7 ±0,1. Отметим, что при ε* = 0,01 потребуется принять N = 199. Рассуждения, проведенные выше, попутно обосновывают процедуру исключения отрезка, которую используют во всех методах прямого поиска точки минимума унимодальной функции одного переменного. Эта процедура состоит в следующем. Пусть на отрезке [а, b] числовой прямой расположены две точки с и d, а < с < d 0 –некоторое достаточно малое число. 3 Рис. 2.1.7. Вычислим значения f(xk1) и f(xk2) функции f(x) в этих точках и выполним процедуру исключения отрезка. В результате получим новый отрезок [аk+1, bk+1] [аk, bk]. Если длина lk+1 нового отрезка больше заданной наибольшей допустимой длины ε* интервала неопределенности, то алгоритм метода дихотомии переходит к (k + 1)-му шагу, повторяя все описанные для k-го шага действия. Если же lk+1 ≤ ε* , то вычисления прекращают и полагают х* = (аk+1 + bk+1)/2. Так как lk+1 = lk /2+ , или lk+1 - 2 = (lk - 2 )/2, то lk 2 . = Из этого равенства выводим следующую формулу длины lk получаемого на к-м шаге метода дихотомии: +2 lk = . отрезка [ak , bk], (2.1.6) Из (2.1.6) следует, что lk → 2 при k → ∞, но при этом lk > 2 . Поэтому выполнение неравенства lk+1 < ε*, означающее достижение заданной точности нахождения точки х*, возможно лишь при условии выбора 2 < ε*. Кроме того, нужно учитывать неизбежную погрешность, возникающую при вычислении приближенных значений ̃ функции f(x). Это приводит к дополнительной погрешности Δ* при нахождении точки х* (см.формулу (2.1.7)). Поэтому выбор значения ограничен и снизу, т.е. Δ* < 2 < ε* (2.1.7) Если эти неравенства нарушаются, то знак разности ̃(xk1) - ̃(xk2) может не совпадать со знаком разности f(xk1) - f(xk2), что приводит к ошибочному выполнению процедуры исключения отрезка. Итак, метод дихотомии — это последовательное построение на каждом k-м шаге поиска точек xk1= (аk + bk )/2 и xk2 = (аk + bk )/2 + , симметричных относительно середины отрезка [аk, bk] длины lk. После выполнения k-ro шага будет выделен отрезок [аk+1, bk+1] длины lk+1 и вычислено N = 2k значений функции. Используя формулу (2.1.6) для длины отрезка (интервала неопределенности) и полагая l1 = 1, получаем = lk+1 = +2 == +2 (2.1.8) Сравнивая (2.1.8) с (2.1.5), видим, что скорость сходимости метода дихотомии значительно выше скорости сходимости оптимального пассивного поиска. 4 Отметим, что после исключения отрезка на k-м шаге описанного алгоритма точки xk1 и xk2 принадлежат новому отрезку [аk+1, bk+1], причем одна из них является внутренней для этого отрезка. Но вычисленное в этой точке значение функции f(x) в методе дихотомии не используют для исключения отрезка на следующем шаге, а проводят вычисления в двух новых точках. Существуют методы последовательного поиска, в которых на каждом k-м шаге начиная с k = 2 вычисляют лишь одно новое значение функции в точке, принадлежащей отрезку [аk+1, bk+1]. Это значение вместе с уже вычисленным на предыдущем шаге значением функции во внутренней точке отрезка [аk, bk] используют при выполнении процедуры исключения отрезка на следующем шаге последовательного поиска. Метод золотого сечения. Как известно, золотым сечением отрезка называют такое его деление на две неравные части, при котором отношение длины всего отрезка к длине его большей части равно равно отношению длины большей части к длине меньшей. Термин ″золотое сечение" ввел Леонардо да Винчи. Золотое сечение широко применяли при композиционном построении многих произведении мирового искусства, в том числе в античной архитектуре и в эпоху Возрождения. Рассмотрим k-й шаг последовательного поиска. Чтобы выполнить процедуру исключения отрезка на этом шаге, отрезок [аk, bk] необходимо двумя внутренними точками xk1, xk2 , xk1 < xk2 , разделить на три части. Рис. 2.1.8 Эти точки выберем симметрично относительно середины отрезка [аk, bk] (рис. 2.1.8) и так, чтобы каждая из них производила золотое сечение отрезка [аk, bk]. В этом случае отрезок [аk+1, bk+1] внутри будет содержать одну из точек xk1, xk2 (другая будет одним из концов отрезка), причем эта точка будет производить золотое сечение отрезка [аk+1, bk+1]. Это вытекает из равенства длин отрезков [аk, xk1] и [xk2, bk]. Таким образом, на (k + 1)-м шаге в одной из точек xk+1,1 , xk+1,2 значение функции вычислять не нужно. При этом отношение lk / lk+1 длин отрезков сохраняется от шага к шагу, т.е. = = τ = const . (2.1.9) Число τ называют отношением золотого сечения. Последовательный поиск, в котором на k-м шаге каждая из симметрично выбранных на отрезке [аk, bk] точек xk1, xk2 осуществляет золотое сечение этого отрезка, называют методом золотого сечения. В этом методе каждое исключение отрезка уменьшает оставшийся отрезок в τ раз. 5 Выясним, чему равно отношение золотого сечения. Так как точки xk1 и xk2 , xk1 < xk2 , выбраны симметрично относительно середины отрезка [аk, bk], то (рис. 2.1.8) bk - xk2 = xk1 - аk = lk - lk+1 . Для определенности будем считать, что на k-м шаге выбран отрезок [аk, xk2]. Тогда на (k + 1)-м шаге одной из точек деления (а именно правой) будет точка xk1. Значит, длина lk+2 отрезка, выбираемого на (k + 1)-м шаге, совпадает с длиной отрезка [a, xk1] и верно равенство lk+2 = lk - lk+1 . Подставляя найденное выражение для lk+2 в уравнение (2.1.9), получаем = , или τ = 1/( τ — 1). Преобразуя это соотношение, приходим к квадратному уравнению τ2 — τ — 1 = 0, имеющему единственное положительное решение τ = 1,618034. Предположим, что отрезком минимизации унимодальной функции f(x) является [0, 1], т.е. а1 = 0, b1 = 1 и l1 = 1. На первом шаге последовательного поиска (k = 1) на отрезке [0, 1] выбираем две точки x11 = а1 + (1 + 1/ τ)b1 = 1 - 1/ τ и x12 = а1 + b1/ τ =1/τ , осуществляющие золотое сечение отрезка [0, 1]. Вычисляем значения минимизируемой функции в этих точках и выполняем процедуру исключения отрезка. Если f(x11) < f(x12), то выбираем отрезок [a1, x12], т.е. полагаем a2 = a1= 0, b2 = x12; в противном случае выбираем отрезок [x11, b1], т.е,- полагаем а2 = x11, b2 = b1 = 1. Кроме того, в первом случае принимаем ̃ 2= x11, а во втором случае - ̃ 2= x12 . Точка ̃ 2 — одна из точек, осуществляющих золотое сечение отрезка [а2, b2] меньшая в первом случая и большая во втором. Если длина вновь полученного отрезка больше заданной допустимой длины ε* интервала неопределенности, то следует перейти ко второму шагу алгоритма, на котором одна из точек x21, x22 есть точка ̃ 2, а вторую можно найти, например, по формуле а2 + b2 - ̃ 2 .На втором шаге алгоритма вычисляем лишь одно значение функции в точке, симметричной ̃ 2 относительно середины отрезка [a2,b2]. Если же длина l2 отрезка [a2,b2], полученного после первого шага алгоритма, оказалась меньше ε*, то поиск прекращают и полагают x* (а2 + b2)/2. Пусть на k-м шаге, k ≥ 2, последовательного поиска по методу золотого сечения выбран отрезок [аk, bk] и в нем точка ̃ k, осуществляющая золотое сечение этого отрезка. Значение f( ̃ k) функции в этой точке уже вычислено на предыдущем шаге. Находим вторую точку ̂ золотого сечения по формуле ̂ = аk + bk - ̃ k и вычисляем в ней значение функции. Если ̂ < ̃ k, то хк1 = ̂ и хк2 = ̃ k , иначе хк1 = ̃ k и хк2 = ̂ . Пусть для определенности ̂ < ̃ k (см. рис. 2.1.8) и хк1 = ̂ , хк2 = ̃ k . Если f(хк1) < f(хк2), то выбираем отрезок [аk, хк2], т.е. полагаем аk+1 = аk, bk+1 = хк2, ̃ k+1 = хк2, иначе выбираем отрезок [хк1, bk], т.е. полагаем аk+1 = хк1, bk+1 = bk, ̃ k+1 = = хк2 . Длину lk+1 нового отрезка [аk+1, bk+1] сравниваем с ε* и принимаем решение, продолжать поиск (при lk+1 ≥ ε*) или нет (при lk+1 < ε*). В случае прекращения поиска полагаем x* (а2 + b2)/2. Согласно описанию алгоритма, на первом шаге значение функции вычисляют в двух точках, а на каждом из последующих шагов вычисляют лишь одно значение функции. Поэтому после k шагов алгоритма значение функции будет вычислено в 6 N = k+1 точках. Поскольку после каждого шага интервал неопределенности уменьшается в τ раз, то для длины lk+1 отрезка [аk+1, bk+1] получаем lk+1 = l1/ τk = 1/ τk , а зависимость lzN длины интервала неопределенности от количества N вычисленных значений функции выражается формулой lzN = lk+1 = 1/ τk = 1/ τN – 1 . (2.1.10) Алгоритмы методов золотого сечения и дихотомии аналогичны. Различие состоит лишь в том, что в методе дихотомии расстояние 2 между внутренними точками хк1, хк2 отрезка [аk, bk] на каждом k-м шаге остается неизменным, а в методе золотого сечения оно зависит от номера шага поиска и уменьшается с уменьшением длины lk отрезка по мере возрастания номера шага. Действительно, в методе золотого сечения на k-м шаге поиска внутренними точками отрезка [аk, bk] будут хк1 = аk + (1 — 1/τ) lk и хк2 = аk + lk / τ , a расстояние между ними равно хк2 — хк1 = (2/τ — ) lk = (√ — 2) lk 0,236068 lk. 7