Применение метода золотого сечения

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

,

(13.7)

Откуда получаем и .

Рис. 3 Рис. 4

Из рис. 3 видно, что ; следовательно, отрезок содержит минимум, т.е. интервал неопределенности уменьшился от до . Если (рис.4), то выбираем отрезок . На каждом последующем шаге в соответствии с правилом золотого сечения вводится в рассмотрение только одна точка, в данном случае на втором шаге , и значение функции в этой точке сравнивается со значением функции в оставшейся внутренней точке нового отрезка (на втором шаге рис.3 внутренняя точка ). Этот процесс следует продолжать, пока длина интервала не окажется меньше наперед заданной точности .

Из (13.7) следует, что на каждом шаге интервал неопределенности уменьшается в раз, т.е. за пять итераций длина интервала неопределенности уменьшится в раз, т.е.примерно на порядок.

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

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

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

,

(13.8)

и разложение функции по формуле Тейлора вблизи минимума имеет вид

(13.9)

причем квадратичная форма (13.9) – положительно определенная, иначе эта точка не была бы вырожденным минимумом. А линии уровня знакоопределенной квадратичной формы – это эллипсы.

Рис. 13.2

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

Отметим, что условию (13.8) удовлетворяют также точки максимумов и седловые точки. Но в точках максимумов квадратичная форма (13.9) отрицательно определенная, а в седловинах она знакопеременна.

Вблизи минимума функция мало меняется при заметных изменениях переменных. Поэтому даже если мы не очень точно определим те значения переменных, которые должны минимизировать функцию, то само значение функции при этом обычно будет мало отличаться от минимального.

Все эффективные методы поиска минимума сводятся к построению траекторий, вдоль которых функция убывает; разные методы отличаются способами построения таких траекторий. Метод, приспособленный к одному типу рельефа, может оказаться плохим на рельефе другого типа.

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

Выберем нулевое приближение . Фиксируем значения двух координат , . Тогда функция будет зависеть только от одной переменной ; обозначим ее через . Используя описанные в § 1 методы, найдем минимум функции одной переменной и обозначим его через . Мы сделали шаг из точки по направлению, параллельному оси ; на этом шаге значение функции уменьшилось.

Затем из новой точки сделаем спуск по направлению, параллельному оси , т.е. рассмотрим , найдем ее минимум и обозначим его через . Второй шаг приводит нас в точку . Из этой точки делаем третий шаг – спуск параллельно оси и находим минимум функции . Приход в точку завершает цикл спусков.

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

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

Рис. 13.3

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

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

, , ,

(13.10)

Докажем, что тогда спуск по координатам из данного нулевого приближения сходится к минимуму, причем линейно.

Значения функции вдоль траектории спуска не возрастают; поэтому траектория не может выйти из области , и неравенства (13.10) будут выполняться на всех шагах. Рассмотрим один из циклов, начинающийся в точке (рис. 13.3, а). Предыдущий цикл окончился поиском минимума по направлению , следовательно, и . Первый шаг нового цикла спускает нас по направлению в точку , в которой и . Поскольку вторые производные непрерывны, можно применить теорему о среднем (напомним теорему Лагранжа – или теорему о среднем: если функция непрерывна и имеет на непрерывную производную, то найдётся точка : ); получим

,

,

где через обозначены расстояния между точками. Отсюда получаем (13.11)

Выполним второй шаг цикла – спуск по направлению в точку С, после которого и . Аналогичные рассуждения дают неравенства:

Отсюда получаем соотношение

(13.12)

Объединяя неравенства (13.11) и (13.12), найдем

, , .

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

Значит, когда число циклов , то все первые производные линейно стремятся к нулю:

и .

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

Фактическая скорость сходимости будет неплохой при малых , когда линии уровня близки к эллипсам, оси которых параллельны осям координат. Для эллипсов, сильно вытянутых под значительным углом к осям координат, величина и сходимость очень медленная.

Пример 2.Рассмотрим квадратичную функцию и выберем нулевое приближение , .

Выполняя вычисления, получим

, ; , ; , .