Лекция: Метод золотого сечения

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

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

В соответствии с данным методом в каждый текущий момент времени рассматривается всегда две точки, например, в начальный момент точки и так, чтобы. При этом возможен один из двух случаев (рис.7.3):

Рис.7.3. Иллюстрация обоснования исключения отрезков

Согласно свойству унимодальной функции в первом случае искомая точка не может находиться на отрезке, во втором случае на отрезке (показаны штриховкой). Значит, область поиска сужается, и следующую точку необходимо брать на одном из укороченных отрезков: — случай 1 или — случай 2.

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

Далее для того, чтобы максимально сузить область поиска, эти точки должны быть поближе к середине исходного отрезка. Однако слишком близко к середине отрезка их тоже брать не следует, т.к. мы хотим построить алгоритм, для реализации которого необходимо общее минимальное количество вычислений целевой функции. Рассмотрим рис. 7.4.

Рис.7.4. Иллюстрация обоснования расположения точек на отрезке

Выбирая на первом шаге сравниваемые точки слишком близко к середине отрезка, мы исключим из рассмотрения большой отрезок для случая 1 или для случая 2. Но на втором шаге величина исключаемого отрезка значительно уменьшится (будет исключен отрезок для случая 1 или отрезок для случая 2).

Таким образом, с одной стороны, точки следует брать рядом с серединой отрезка, а, с другой стороны, слишком близко друг от друга их брать нельзя. Т.е. необходимо найти некую «золотую середину».Для этого рассмотрим для простоты вместо отрезка отрезок [0,1] единичной длины – рис.7.5.

Рис.7.5. Обоснование «золотой середины» расположения точек на отрезке

На этом рисунке .

Для того, чтобы точка B была «выгодной» как на данном, так и на следующем этапе (шаге), она должна делить отрезок AD в таком же отношении, как и AC: AB/AD = BC/AC. При этом в силу симметрии аналогичным свойством будет обладать и точка C: CD/AD = BC/BD. В обозначениях координаты x эти пропорции принимают вид: x/1 = (1 – 2x)/(1 – x). Решим эту пропорцию:

Корни этого уравнения равны:

не приемлем, т.е. уравнение имеет один корень.

О точке, которая расположена на расстоянии длины от одного из концов отрезка, говорят, что она осуществляет «золотое сечение» данного отрезка.

Очевидно, что каждый отрезок имеет две такие точки, расположенные симметрично относительно его середины.

Итак, алгоритм метода «золотого сечения» заключается в следующем (см. также рис.7.6). На исходном отрезке [a,b] выбираются две точки x1 и x2, так, чтобы выполнялось приведенное выше соотношение «золотого сечения» этого отрезка. Вычисляются значения целевой функции в этих точках – и. Они сравниваются, и из дальнейшего рассмотрения исключается отрезок, прилегающий к точке, дающей большее значение целевой функции (здесь отрезок [x2,b] ). Т.е. исходный отрезок [a,b] «стягивается» до отрезка [a,b1]. Для этого нового отрезка находится его середина, и по отношению к ней симметрично оставшейся точке x1 ставится точка x3. Для нее рассчитывается значение целевой функции и сравнивается с. Из дальнейшего рассмотрения опять исключается отрезок, прилегающий к точке с большим значением целевой функции, здесь это отрезок [a,x3]. Текущий отрезок «стягивается» до нового отрезка, здесь это [a1,b1] и т.д.

Рис.7.6. Иллюстрация алгоритма метода «золотого сечения»

Метод «золотого сечения» прост, эффективен и широко применяется в практической оптимизации.