Однопараметрическая (одномерная) оптимизация. Методы одномерной оптимизации: метод дихотомии, метод Фибоначчи, метод золотого сечения, метод Ньютона.

2. Метод Фибоначчи. Метод "золотого сечения"

Одним из методов однопараметрической оптимизации является метод Фибоначчи.

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

Предположим, что имеется интервал неопределенности (x1,x3) и известно значение функции f(x2) внутри этого интервала (см. рис. 9.3). Если можно вычислить функцию всего один раз в точке х4, то где следует поместить точку х4, для того чтобы получить наименьший возможный интервал неопределенности?

Положим х2–х1=L и х3–х2=R, причем L > R, как показано на рис. 9.3, и эти значения будут фиксированы, если известны x1, x2 и х3. Если х4 находится в интервале (х1; х2), то:

Поскольку не известно, какая из этих ситуаций будет иметь место, выберем х4 таким образом, чтобы минимизировать наибольшую из длин х3-х4 и х2-х1. Достигнуть этого можно, сделав длины х3 – х4 и х2 – х1 равными т.е. поместив х4 внутри интервала симметрично относительно точки х2, уже лежащей внутри интервала. Любое другое положение точки х4 может привести к тому, что полученный интервал будет больше L. Помещая х4 симметрично относительно х2, мы ничем не рискуем в любом случае. Если окажется, что можно выполнить еще одно вычисление функции, то следует применить описанную процедуру к интервалу (х1, х2), в котором уже есть значение функции, вычисленное в точке х4, или к интервалу (х4,х3), в котором уже есть значение функции, вычисленное в точке х2.

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

На n -м вычислении n -ю точку следует поместить симметрично по отношению к (n — 1) -й точке. Положение этой последней точки в принципе зависит от нас. Для того чтобы получить наибольшее уменьшение интервала на данном этапе, следует разделить пополам предыдущий интервал. Тогда точка х будет совпадать с точкой хn-1. Однако при этом мы не получаем никакой новой информации. Обычно точки хn-1 и хn отстоят друг от друга на достаточном расстоянии, чтобы определить, в какой половине, левой или правой, находится интервал неопределенности. Они помещаются на расстоянии е/2 по обе стороны от середины отрезка Ln-1 ; можно самим задать величину е или выбрать эту величину равной минимально возможному расстоянию между двумя точками.

Интервал неопределенности будет иметь длину Ln, следовательно, Ln-1 = 2Ln - е (рис.9.4, нижняя часть). На предыдущем этапе точки хn-1 и хn-2 должны быть помещены симметрично внутри интервала Ln-2 на расстоянии Ln-2 от концов этого интервала. Следовательно, Ln-2 = Ln-1+Ln (pис.9.4, средняя часть).

Замечание. Из рисунка ясно, что на предпоследнем этапе хn-2 остается в качестве внутренней точки.

Аналогично Ln-3=Ln-2+Ln-1 (pис. 9.4, верхняя часть)

В общем случае Lj-1=Lj + Lj+1 при 1<j<n.

Таким образом,$$\begin{align*} L_{n-1} = 2L_n - \varepsilon , \\ L_{n-2} = L_{n-1} + L_n = 3L_n - \varepsilon, \\ L_{n-3} = L_{n-2} + L_{n-1} = 5L_n - 2 \varepsilon, \\ L_{n-4} = L_{n-3} + L_{n-2} = 8L_n - 3 \varepsilon \quad \text{и т.д.} \end{align*}$$

Если определить последовательность чисел Фибоначчи следующим образом: F0=1, F1=l, и Fk=Fk-1+Fk-2 для k = 2, 3,..., то$$L_{n-j} = F_{j+1} L_n - F_{j-1} \varepsilon, \quad j=1,2,\ldots, n-1.$$

Если начальный интервал (a;b) имеет длину L = (b-а), то$$\begin{align*} L_1 = F_n L_n - \varepsilon F_{n-2}, \; \text{т.е.} \\ L_n = \frac{L_1}{F_n} + \varepsilon \frac{F_{n-2}}{F_n}. \end{align*}$$

Следовательно, произведя n вычислений функции, мы уменьшим начальный интервал неопределенности в l/Fn раз по сравнению с его начальной длиной (пренебрегая е), и это - наилучший результат.

Если поиск начат, то его несложно продолжить, используя описанное выше правило симметрии. Следовательно, необходимо найти положение первой точки, которая помещается на расстоянии L2 от одного из концов начального интервала, причем не важно, от какого конца, поскольку вторая точкa помещается согласно правилу симметрии на расстоянии L2 от второго конца интервала:$$\begin{align*} L_2 = F_{n-1} L_n - \varepsilon F_{n-3} = \\ = F_{n-1} \frac{L_1}{F_n} + \varepsilon \frac{(F_{n-1} F_{n-2} - F_n F_{n-3})}{F_n} = \\ = \frac{F_{n-1}}{F_n} L_1 + \frac{(-1)^n \varepsilon}{F_n} . \end{align*}$$

После того как найдено положение первой точки, числа Фибоначчи больше не нужны. Используемое значение е может определяться из практических соображений. Оно должно быть меньше L1\Fn+x, в противном случае мы будем напрасно тратить время на вычисление функции.

Таким образом, поиск методом Фибоначчи, названный так ввиду появления при поиске чисел Фибоначчи, является итерационной процедурой. В процессе поиска интервала (x1; x2) с точкой х2, уже лежащей в этом интервале, следующая точка х2 всегда выбирается такой, что х3–х4 = х2–х1 или х4-х1 = х3-x2, т.е. x4=х1-х2+х3.

Если f(x2) = f2 и f(x4) = f4, то можно рассмотреть четыре случая (рис. 9.5).

Следующий из методов одномерной оптимизаци называется методом "золотого сечения".

Не всегда можно заранее определить, сколько раз придется вычислять функцию. В методе Фибоначчи это нужно знать для определения L2, т.е. положения начальной точки (см. уравнение 2.4).

Метод "золотого сечения" почти столь же эффективен, как и метод Фибоначчи, однако при этом не требуется знать n - количество вычислений функции, определяемое вначале. После того как выполнено j вычислений, исходя из тех же соображений, что и ранее (см. уравнение 2.1), записываем$$L_{j-1} = L_j + L_{j+1}$$

Однако если n не известно, то мы не можем использовать условие Ln-1 = Ln - е. Если отношение последующих интервалов будет постоянным, т.е.$$\frac{L_{j-1}}{L_j} = \frac{L_j}{L_{j+1}} = \frac{L_{j+1}}{L_{j+2}} = \ldots = \tau ,$$ то$$\frac{L_{j-1}}{L_j} = 1+ \frac{L_{j+1}}{L_j} ,$$ т.е. $$\tau = 1+ 1/ \tau$$

Таким образом, $$\tau^2 - \tau - 1 = 0$$, откуда $$\tau = (1 + \sqrt{5})/2 \approx 1,618033989$$. Тогда$$\frac{L_{j-1}}{L_{j+1}} = \tau^2, \quad \frac{L_{j-2}}{L_{j+1}} = \tau^3 \;\; \text{и т.д.}$$ Следовательно, $$\frac{L_1}{L_n} = \tau^{n-1}$$, т.е.$$L_n = \frac{L_1}{\tau^{n-1}}$$

В результате анализа двух рассмотренных значений функции будет определен тот интервал, который должен исследоваться в дальнейшем. Этот интервал будет содержать одну из предыдущих точек и следующую точку, помещаемую симметрично ей. Первая точка находится на расстоянии L1/t от одного конца интервала, вторая - на таком же расстоянии от другого. Поскольку$$\lim_{n \rightarrow \infty} F_{n-1} / F_n = 1/n ,$$ то из уравнения (2.4) видно, что поиск методом "золотого сечения" является предельной формой поиска методом Фибоначчи. Название "золотое сечение" произошло от названия отношения в уравнении (2.7). Видно, что Lj-1 делится на две части так, что отношение целого к большей части равно отношению большей части к меньшей, т.е. равно так называемому "золотому отношению".

Таким образом, если ищется интервал (х0, х3) и имеются два значения функции f1 и f2 в точках x1 и x2, то следует рассмотреть два случая (рис. 9.6).

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

Схема алгоритма метода "золотого сечения" представлена на рис 9.7

Здесь c - константа,$$c= \begin{cases} \phantom{-} 1 (\text{поиск минимума функции} \; F(x)), \\ -1 (\text{поиск максимума функции} \; F(x)), \end{cases}$$ При выводе x - координата точки, в которой функция F(x) имеет минимум (или максимум), FM – значение функции F(x) в этой точке.

3. Метод Ньютона

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

Метод применим для вогнутой (или выпуклой), функции F(x), что соответствует монотонности ее первой производной f(x).

Известно, что если функция F(x) имеет локальный минимум (или максимум) в точке $$\overline{x}$$, то в этой точке градиент функции F(x) (вектор ее производных) равен нулю, т.е.$$F'(x) \equiv f(x) = 0$$

Следовательно, если функция F(x) дифференцируема, то для нахождения ее экстремума нужно решить уравнение$$f(x) = 0 ,$$ где $$f(x) = F'(x)$$. $$\overline{x}$$ - корень уравнения (3.1), точка, то есть, координата в которой F'(x)=0, а функция F(x) имеет минимум (или максимум) (рис.9.8).

Алгоритм метода Ньютона сводится к линейному представлению функции f(x) и решению уравнения (3.1).

Разложим функцию f(x) в ряд Тейлора:$$f(x_{i+1}) = f(x_i) + h_i \cdot f'(x_i) + \frac{h_i^2}{2!} \cdot f''(x_i) + \frac{h_i^3}{3!} \cdot f'''(x_i) + \ldots ,$$ где hi=xi+1-xi.

Отбросим члены ряда, содержащие $$h_i^2, h_i^3, \ldots$$.

В результате имеем:$$f(x_{i+1}) = f(x_i) + (x_{i+1} - x_i ) f'(x_i).$$ Если в точке (xi+1) достигается экстремум функции F(x), то f(xi+1)=0.

Тогда$$f(x_i)+(x_{i+1}-x_i) f'(x_i)=0.$$

Отсюда точка экстремума равна:$$x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)} = x_i - \frac{F'(x_i)}{F''(x_i)} .$$

Для нахождения экстремума функции F(x) необходимо на каждом шаге итерационного процесса поиска определить первую F1 и вторую F2 производные целевой функции F(x), т.е.$$\begin{align*} F1 = f(x) = F'(x), \\ F2 = f'(x) = F''(x). \end{align*}$$

Начальные приближения х рекомендуется выбирать в той точке интервала [a,b], где знаки функции f(x) и ее кривизны f''(x) совпадают, т.е. выполняется условие$$f(x) \cdot f''(x) > 0 ,$$ где$$f''(x) = F'''(x) = F3$$

Словесный алгоритм метода Ньютона:

На основании (3.2) условие (3.4) можно записать как$$\left| x_i = \frac{f(x_i)}{f'(x_i)} - x_i \right| < \varepsilon$$ В результате условие (3.4) будет иметь вид$$\left| \frac{f(x_i)}{f'(x_i)} - x_i \right| < \varepsilon$$

В точке экстремума $$\overline{x}$$ производная $$F'(x)$$ меняет знак.

Если в точке $$\overline{x}$$ функция F(x) имеет минимум, то производная $$F'(x)$$ в окрестности $$\overline{x}$$ меняет знак с отрицательного на положительный, т.е. $$F'(x)$$ является возрастающей функцией, значит, $$F''(x) > 0$$ (рис. 9.9 a).

Если в точке $$\overline{x}$$ функция F(x) имеет максимум, то производная $$F'(x)$$ в окрестности $$\overline{x}$$ меняет знак с положительного на отрицательный, т.е. $$F'(x)$$ является убывающей функцией, значит, $$F''(x) < 0$$ (рис. 9.9 b).

Следовательно, по знаку $$F''(x)$$ можно судить: в точке $$\overline{x}$$ максимум или минимум функции F(x).

Если функция F(x) не дифференцируема или вычисление ее производных очень сложно, то для определения производных функции F(x) можно воспользоваться приблизительными оценками производных с помощью разностных схем:$$F'(x) = \frac{\Delta F}{h}; \; F''(x) = \frac{\Delta F'}{h}; \;\; \text{и т.д.}$$

Схема алгоритма метода Ньютона представлена на рис. 9.10.

На рис.9.10: $$\overline{x}$$ - координата точки в которой функция F(x) имеет минимальное (или максимальное) значение, FM - значение, функции F(x) в точке $$\overline{x}$$.