Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011

Рис. 1.3. Определение точки с

Далее анализируется знак производной в этой точке с. При этом возможны следующие ситуации (рис. 1.4).

Рис. 1.4. Возможные наклоны касательной в точке с

Если f ′(c) > 0 , то в качестве нового отрезка берется отрезок [c, b] , если f ′(c) < 0 , то в качестве нового отрезка берется отрезок

[a, c] .

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

выпуклой, дважды дифференцируемой функцией.

Прежде всего, выбирается начальное приближение х0 и строится последовательность:

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

Метод ломаных. Этот метод может быть использован для поиска глобального минимума функции, удовлетворяющей условию Липшица на отрезке [a, b] . Функция f(x) удовлетворяет

условию Липшица на отрезке [a, b] , если существует число L > 0

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

Метод ломаных невозможно реализовать без знания константы Липшица L. Ее оценку получить можно, но иногда это представляет значительные трудности.

1.2.3. Методы минимизации унимодальных функций

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

1.2.3.1. Метод золотого сечения

Как известно [2; 14], «золотым сечением» называется деление отрезка на две неравные части, такие, что выполняется соотношение:

22

весь отрезок = большая часть . большая часть меньшая часть

Нетрудно проверить, что золотое сечение отрезка [a, b] производится двумя точками:

x1 = a + r1 (b − a) ,

x2 = a + r2 (b − a) ,

где

r1 = 3 −2 5 = 0,381966...,

На рис. 1.5 изображен пример деления отрезка [a, b] в пропорции «золотого сечения».

Рис. 1.5. Пример деления отрезка [a, b] в пропорциях «золотого сечения»

Точки х1 и х2 расположены симметрично относительно середины отрезка, при этом выполняются соотношения:

Замечательно здесь то, что точка х1, в свою очередь, производит «золотое сечение» отрезка [a, x2 ] :

Аналогично, точка x2 производит золотое сечение отрезка

[x1 , b] .

Опираясь на это свойство «золотого сечения», можно предложить следующий метод минимизации унимодальной функции f(x) на отрезке [a, b] .

23

Идея метода такова. На отрезке [a, b] возьмем точки x1 и x2 ,

производящие золотое сечение отрезка, и вычислим значения функций f(x1) и f(x2) в этих точках (рис. 1.6).

Рис. 1.6. Выбор отрезка, содержащего точку минимума

Если f (x1 ) ≤ f (x2 ) , то при x > x2 функция не может убывать, т.е. точка минимума лежит на отрезке [a, x2 ] . Если же f (x1 ) > f (x2 ) , то, наоборот, минимум функции лежит на отрезке

[x1 , b] .

Итак, отрезок, на котором ищется минимум, уменьшился. Процесс повторяется сначала. При этом весьма важно то, что внутри отрезка [a, x2 ] (это справедливо для рассматриваемого

примера) содержится точка х1 с вычисленным значением f(x1), которая производит «золотое сечение» отрезка [a, x2 ].

Следовательно, на данном шаге достаточно вычислить лишь одно значение f(x) во второй, новой точке, производящей золотое сечение.

Аналогично в случае, если выбран отрезок [x1 , b] .

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

1. Вычислить длину отрезка [a, b] − = b − a . Взять внутри отрезка две точки:

24

xл = a + r1 , xп = a + (1 − r1 ) .

2.Вычислить f (xл ) и f (xп ) .

3.Если f (xл ) ≤ f (xп ) перейти к шагу 4, если f (xл ) > f (xп ) – к шагу 5.

2. Численная реализация метода обладает существенным недостатком. Так, приближенные значения чисел r1 и r2 порождают накопление ошибок, которое довольно быстро может привести к нарушению пропорций отрезков в смысле отношения «золотого сечения» и, как следствие, к нарушению условий вложенности отрезков и, тем самым, к расходимости процесса. Таким образом, метод не является устойчивым по отношению к ошибкам в определении параметров r1 и r2.

Рекомендации:

с максимально возможной для используемой ЭВМ точностью определять эти параметры и точки деления отрезка;

при определенных условиях можно воспользоваться модификацией метода, делающей процесс устойчивым [14].

В качестве примеров использования метода «золотого сечения» рассмотрим следующие задачи.

Задача 1. Сколько шагов n метода «золотого сечения» обеспечивают заданную точность ε .

25