Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

8.6. Метод касательных

Этот метод может оказаться весьма эффективным для минимизации выпуклых функций.

Будем предполагать, что функция φ(х) выпукла и непрерывно дифференцируема на отрезке [а, b]. Обозначим через φl(х, y) следующую линейную по х функцию, определённую в точке y:

φl(x, y)=φ(y)+φ'(y)(x-y)

Метод состоит в следующем. Выбирают произвольную точку х0∈[а,b] и строят функцию φl(x, x0). Для вычисления точки x1 решают следующую задачу:

min ξ

при условиях

ξ≥φl(x, x0)
a≤x≤b

Обозначим через ξ1, x1 решение этой задачи. Для отыскания точки х2 строят функцию φl(x, x1) и вычисляют ξ2, х2-решение задачи

min ξ

при условиях

ξ≥φl(x, x0)
ξ≥φl(x, x1)
a≤x≤b.

Пусть вычислены точки x1, x2,....,xk-1. Для того чтобы найти xk, решают задачу

min ξ

при условиях

(8.22)

Пусть

ψk-1=max{φl(x, x0), φl(x, x1),....,φl(x, xk-1)} (8.23)

или, что то же самое,

ψk-1(x)=max{ψk-2(x), φl(x, xk-1)}(8.24)

Нетрудно убедиться*, что при φ' (xk-1) ≠ 0 задача (8,22) эквивалентна задаче отыскания такой точки хk ∈ [а, b], что

(8.25)

* (Если это вызывает затруднения, то доказательство аналогичного утверждения читатель найдет в гл. 10, п. 10.3 (раздел IV, доказательство теоремы 10.7))

Из рис. 8.1 видно, что для вычисления каждой точки хk достаточно найти на каждом шаге две новые вершины ломаной ψk-1(х) (на рисунке ломаная АСВ изображает график функции ψk-1(х), а ломаная ADEB-график функции ψ2(x)).

Рис. 8.1
Рис. 8.1

Исследуем некоторые свойства функции ψk-1(x). Из выпуклости функции φ(х) следует (см. (2.18)), что

φ(x)≥φ(y)+φ'(y)(x-y)

вследствие чего

φl(x, xi)≤φ(x)

для всех i=0, 1, ..., k-1 и любого x∈[a, b]. Поэтому

φ(x)=max{φl(x, x0), φl(x, x1),....,φl(x, xk-1)}

и, значит, ввиду (8.23) для всех х∈[а, b] справедливо неравенство

ψk-1(x)≤φ(x) (8.26)

Отсюда, а также из определения функции φl(x, у) и соотношения (8.23) следует, что

φ(xi)=φl(xi, xi)≤k-1(xi)≤φ(xi)

то есть

ψk-1(xi)=φ(xi), i=1, 2,...,k-1 (8.27)

Обоснование сходимости метода будем проводить в предположении, что φ' (xk)≠0, k = 0, 1, .. ., поскольку в противном случае хk является точкой минимума, и процесс на этом шаге оканчивается.

Теорема 8.2.Для выпуклой и непрерывно дифференцируемой на отрезке [а, b] функции φ(х) метод касательных сходится:


Если точка минимума х* единственна, то


Доказательство. Из (8.25), (8.24) и (8.26) имеем


Таким образом, последовательность (ψk(xk+1)} - монотонно возрастающая и ограниченная сверху, вследствие чего существует


Из неравенства (8.26) следует, что

(8.28)

Докажем, что ψ* = φ (x*). Пусть


Заметим, что, ввиду выпуклости функции φ(х), будет


и ломаная φk(x) будет удовлетворять условию Липшица на отрезке [а, b] с константой Липшица L.

Так как хk∈[а, b], k = 0, 1, ..., то существует сходящаяся подпоследовательность {xki}:


Из того что


ввиду условия Липшица для функции ψki-1 (х), получаем


Можем считать, что индексы k1<k2<...<ki<...; тогда ki-1≤ki-1 и, значит (см. (8.27)),


Поэтому


Переходя к пределу при i→∞, приходим к неравенству

0≤φ(x̄)-ψ*≤0

откуда и следует φ(х̄) = ψ*. Но φ(x*)≤φ(x̄), поэтому φ(x*)≤ψ*. Таким образом, ввиду неравенства (8.28) будет

ψ* =φ(x*)

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


Замечание. Метод касательных применим и для одномерной минимизации выпуклых функций, свободных от требований непрерывной дифференцируемости. Поскольку, как мы видели (см. теорему 2.10), выпуклая функция φ(x) имеет в каждой внутренней точке y отрезка [а, b] левостороннюю производную φ' (y - 0) и правостороннюю производную φ'(y-0), то метод касательных может быть следующим образом приспособлен и для этого случая. В качестве линейной функции φl(x, xi) будем выбирать следующую функцию:

φl(x, xi) = φ(xi) + γi(x-xi),

где i-любое число из отрезка [φ' (хi-0), φ'(xi+0)]. В частности, γi можно выбирать из условия


Дальнейшая конструкция метода остается прежней. Теорема о сходимости остается справедливой и в этом случае.

Схема метода. Алгоритм ищет точку минимума выпуклой и дифференцируемой функции φ(х) на отрезке [а, b] с заранее заданной точностью ε.

1-й шаг (нестандартный). Полагаем

а1=a, b1=b, φ'(a1)=φ'(a), φ'(b1)=φ'(b).

k-й шаг (k ≥ 1). Если

1/2 (bk-ak)≤ε

то точность достигнута и процесс заканчивается. Если

1/2 (bk-ak)>ε

то определяем абсциссу хk точки пересечения прямых

y=φ(ak)+φ'(ak)(x-ak)
y=φ(bk)+φ'(bk)(x-bk)

Затем вычисляем φ'(xk). Если φ'(xk) = 0, то мини найден (и процесс заканчивается). Если φ' (хk) < 0, то полагаем

ak+1=xk, bk+1=bk

Если φ' (хk) > 0, то полагаем

ak+1=ak, bk+1=xk

и k-й шаг окончен.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"