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

2004
ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ
МАТЕМАТИКА
Є 1 (500)
УДК 517.929
М.Ю. АНДРАМОНОВ
МЕТОД ДОВЕРИТЕЛЬНЫХ ОКРЕСТНОСТЕЙ ДЛЯ МИНИМИЗАЦИИ
КОДИФФЕРЕНЦИРУЕМЫХ ФУНКЦИЙ
Введение
В данной работе предлагается алгоритм нахождения локального минимума негладких невыпуклых функций. Предполагается, что целевая функция кодифференцируема [1], [2]. Такая
задача имеет многочисленные приложения, но известно мало алгоритмов для ее решения.
Алгоритм принадлежит к классу методов доверительных окрестностей [3], [4], которые были
впервые разработаны в [5] и [6] для минимизации суммы квадратов. Одно из преимуществ методов доверительных окрестностей | их глобальная сходимость. Известно, что использование
доверительных окрестностей в ряде случаев лучше минимизации функции по направлению.
Идея таких методов проста. Строится функция, аппроксимирующая целевую, и минимизируется с ограничениями на шаг, при которых следующая итерационная точка должна принадлежать доверительной окрестности. Если получается достаточное убывание целевой функции,
доверительная окрестность расширяется, и производится переход к новой итерационной точке. В противном случае итерационная точка остается прежней, и доверительная окрестность
сокращается. Вспомогательная задача минимизации аппроксимации целевой функции может
решаться приближенно с помощью двойственных оценок.
1. Постановка задачи
В статье решается задача безусловной минимизации
minff (x) j x 2 Rn g:
Предполагается, что целевая функция f (x) ограничена снизу. Пусть функция m(s) аппроксимирует f (x + s) ; f (x) локально в окрестности x, где s | вектор малой нормы. Будем называть
эту функцию моделью.
В дифференцируемом случае берут
m(s) = hf 0 (x); si:
Для дважды дифференцируемых функций можно использовать квадратичную модель [3]
m(s) = hf 0 (x); si + hf 00 (x)s; si:
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований,
грант Є 01-01-00070.
3
2. Метод доверительных окрестностей
Полагаем k := 0. Выбираются начальный радиус 0 и начальная точка x0 . Выбираются
параметры 0 < < < 1 и 0 < 1 < 1 < 2 . Пусть найдена точка xk и выбран радиус k , k 0.
В точке xk решается задача
minfm(s) j ksk k g;
пусть sk | ее решение. Вычисляется lk = f (xk +ms(ks)k;)f (xk ) .
Если lk , то xk+1 = xk + sk ; иначе xk+1 = xk .
Если при этом lk , то выбираем k+1 2 [k ; 2 k ].
Если > lk , то выбираем k+1 2 [1 k ; k ].
Если lk < , то выбираем k+1 2 (0; 1 k ]. Вычисления повторяются при замене k на k + 1.
Имеется много результатов сходимости для линейной или квадратичной модели ([3], [4],
[7]). Если целевая функция недифференцируема, нами предлагается использовать негладкую
модель.
Предположим, что целевая функция f (x) дважды кодифференцируема на Rn , т. е.
f (x + s) = f (x) + (A;b;cmax
(hAs; si + hb; si + c) + min2 (hPs; si + hq; si + r) + o(ksk2 );
)2d2 (x)
(P;q;r)2d (x)
где A, P | матрицы размерности n n; b; q 2 Rn ; c; r 2 R. Пара [d2 (x); d2 (x)] называется вторым
кодифференциалом функции f в точке x ([1], [2]).
Предлагается использовать в методе доверительных окрестностей модель вида
zx (s) = (A;b;cmax
(hAs; si + hb; si + c) + min2 (hPs; si + hq; si + r):
)2d2 (x)
(P;q;r)2d (x)
В описанном методе доверительных окрестностей модель m(s) заменяется на zx (s), но для доказательства сходимости нужна другая методика.
3. Сходимость алгоритма
Назовем = fx : minksk zx (s) 0g множеством стационарных точек второго порядка.
Здесь > 0 | малый положительный параметр. Пусть " | "-окрестность множества .
Обозначим также L0 = fx : f (x) f (x0 )g, " = L0 n " . Пусть L0 ограничено и выполнены
три предположения.
Предположение 1. Для каждого y 2 " \ L0 и каждого " > 0 существуют такие > 0 и
убывающая на (0; ] функция c(), не зависящие от y, что
z (s) c(); 2 (0; ]; где U = fs 2 Rn : ksk g:
c() < 0; 2 (0; ]; smin
2U y
e
Предположение 2. Для каждого x 2 " \ L0 и каждых " > 0, 0 < < 1 существует такое
, не зависящее от x, что
jf (x + s) ; f (x) ; zx(s)j ksk2 ; ksk 2 (0; ]:
e
2
Предположение 3.
ksk = C > ;1.
lim
ksk!0 c(ksk)
Теорема 3.1. При предположениях 1, 2, 3 для каждого " > 0 среди точек последовательности, строящейся по методу доверительных окрестностей, найдется xk 2 " .
Доказательство. Пусть настолько мало, что
e
2
1 + c(kksskk) ; ksk 2 (0; ]:
4
e
Предположим, что k 2 (0; min(; )). Имеем
f (xk + sk ) ; f (xk ) 1 + ksk k2 ;
zxk (sk )
c(ksk k)
поскольку ksk k . Тогда f (xk + sk ) ; f (xk ) c(ksk k), и итерационная точка пересчитывается.
Выполнено неравенство f (xk + sk ) ; f (xk ) c(k ), т. к. zxk (sk ) c(k ) по предположению 1.
Поэтому имеем убывание функции f (x) на константу.
Если k остается больше, чем min(; ), то на некоторых итерациях радиус доверительной
окрестности растет, и целевая функция убывает по крайней мере на min(; ). Тогда после
некоторого числа итераций также получим убывание функции f (x) на константу. Поскольку f
ограничена снизу, итерационный процесс остановится, и найдется точка из " .
Пусть s | направление наискорейшего спуска в произвольной точке y 2= " . Предположим,
что для некоторого > 0 выполнено
f (y + s) < f (y); 2 (0; ]; f (y + s) < (") < 0:
Тогда можно взять
c() = (A;b;cmax
(hAs; si + hb; si + c) + min2 (hP s; si + hq; si + r):
)2d2 (x)
e
e
e
(P;q;r)2d (x)
Предположим, что максимум и минимум берутся по конечному числу индексов. Тогда для
выполнения условий теоремы сходимости достаточно условия
2
lim
!0 2 h(Aj + Pi )s; si + (h(bj + qi ); si + (cj + ri )) = C > ;1:
Это условие означает, что cj + ri , или hbj + qi ; si, или h(Aj + Pi )s; si не равны нулю для всех
индексов j , i и всех точек y 2= " .
Назовем
Z = fx : kmin
( max (ha; si + b) + min (hq; si + r)) 0g
sk (a;b)2d(x)
(q;r)2d(x)
множеством стационарных точек первого порядка. Здесь пара [d(x); d(x)] | кодифференциал
функции f в x (см. [1]), > 0 | малый параметр. Пусть Z" | "-окрестность множества Z .
Обозначим Z" = L0 n Z" .
Вместо модели второго порядка можно использовать модель первого порядка, предполагая,
что целевая функция только кодифференцируема. В этом случае модель имеет вид
zx (s) = (a;bmax
(ha; si + b) + min (hq; si + r):
)2d(x)
(q;r)2d(x)
Введем три условия.
Условие 1. Для каждого x 2 Z " \ L0 и каждого " > 0 существуют такие > 0 и убывающая
на (0; ] функция c(), не зависящие от x, что
c() < 0; 2 (0; ]; smin
z (s) c(); 2 (0; ];
2U x
где U = fs 2 Rn : ksk g.
Условие 2. Для каждого x 2 Z " \ L0 и каждых " > 0, 0 < < 1 найдется такое , не
зависящее от x, что
jf (x + s) ; f (x) ; zx(s)j ksk; ksk 2 (0; ]:
Условие 3.
e
lim ksk = C > ;1.
ksk!0 c(ksk)
Теорема 3.2.
При выполнении условий 1, 2, 3 для каждого " > 0 найдется xk 2 Z" .
5
e
Доказательство проводится дословным повторением доказательства теоремы 3.1 с заменой
ссылки на предположение 1 ссылкой на условие 1. Сходимость в этом случае медленнее, но легче решать вспомогательную задачу минимизации
модели.
Пусть s | направление наискорейшего спуска в произвольной точке y 2= Z" . Предположим,
что для некоторого > 0 выполняется
f (y + s) < f (y); 2 (0; ]; f (y + s) < !(") < 0:
Тогда можно взять
c() = (a;bmax
(ha; si + b) + min2 (hq; si + r):
)2d2 (x)
(q;r)2d (x)
Предположим, что максимум и минимум берутся по конечному числу индексов. Тогда для
выполнения условий теоремы сходимости достаточно, чтобы
= C > ;1:
lim
!0 h(aj + qi ); si + (bj + ri )
Это условие означает, что bj + ri или h(aj + qi ); si не рaвны нулю для всех индексов j , i.
Для минимизации модели можно использовать методы имитации замораживания (simulated
annealing, см. [8]), т. к. число локальных минимумов в малой окрестности обычно невелико.
4. Решение задачи минимизации модели
В следующих случаях задачу минимизации модели решить легко.
1) zx (s) = min
(hPs; si + hq; si + r), где I | конечное число индексов, Pi | произвольные маi2I
трицы. В этом случае требуется решить ряд задач минимизации квадратичной функции
с ограничением по норме (их можно решать методами из [3], [7]).
Такие методы базируются на следующих теоремах из [7].
Теорема 4.1. Если x | решение задачи
minff + hgT ; wi + 12 wT Bw; kwk g;
(1)
где B | матрица размерности n n, g | вектор, то x | решение уравнения (B + I )x = ;g,
где > 0, (wT w ; 2 ) = 0, B + I | положительно определенная, а I | единичная матрицы.
n удовлетворяют условию (B + I )x = ;g и B + I
Теорема 4.2. Пусть 2 R ; x 2 R
положительно полуопределена. В случаях, когда = 0, kxk и 0, kxk = , x | решение
задачи (1). Если же = 0, kxk = , то x | решение задачи
minff + hgT ; !i + 12 !T B!; k!k = g:
Если матрица B + I положительно определена, то решение x единственно в каждом случае.
2) zx (s) = max
(hAi s; si + hbi ; si + ci ) + min
(hPj s; si + hqj ; si + rj ), где матрицы Ai + Pj положиi2I
j 2J
тельно определены. Тогда нужно применять много раз методы минимизации выпуклых
недифференцируемых функций.
3) Для достаточно малого функция zx (s) имеет единственную точку глобального минимума в окрестности нуля для каждого x 2 " .
Если модель имеет много локальных минимумов, следует модифицировать алгоритм. Вычисляются направление наискорейшего спуска vk , kvk k = 1, в xk и локальный минимум sk функции
zxk (s). Делается сравнение
(f (xk + sk ) ; f (xk ))=zxk (sk ) ;
6
и вычисляется точка
xk + k vk = arg min f (xk + vk ):
2(0;k ]
Тогда полагается xk+1 = arg min(f (xk + sk ); f (xk + k vk )). В этом случае можно увеличивать и
уменьшать k , но оно должно быть ограничено снизу.
Задача
min max
f([Aj s; s] + [bj ; s] + cj ); ksk k g
j 2J
эквивалентна последовательности задач
min Km (s) = [Am s; s] + [bm ; s] + cm ;
Ki (s) = [Ai s; s] + [bi ; s] + ci ; [Am s; s] ; [bm ; s] ; cm 0; i 6= m;
K0 (s) = ksk k ;
у которых целевая функция и ограничения квадратичны. Такие задачи могут решаться методами из [8]. Если решение ищется в подпространстве, то задачи имеют меньшую размерность и
могут быть решены эффективно.
Такие задачи могут решаться методами ветвей и границ с двойственными оценками из [9],
которые строятся следующим образом. Пусть N = jJ j и 2 RN+ . Пусть
L(s; ) = Km (s) + Ki (s)
X
i6=m
| функция Лагранжа, определенная на Rn RN+ . Пусть T | множество допустимых решений
задачи. Если s 2 T , 2 RN+ , то Ki (s) 0 для i 6= m и L(s; ) Km (s). Поэтому
'() = sinf
L(s; ) sinf
L(s; ) sinf
K (s) = K ;
2Rn
2T
2T m
где K | оптимальное решение задачи для всех 2 RN+ . Тогда () = inf s2Rn L(x; ) и =
sup2RN () | нижние оценки для K при 2 RN+ . Функцию Лагранжа можно представить
как
L(s; ) = [A()s; s] + [b(); s] + c();
где
A() = Am + i (Ai ; Am ); b() = bm + i (bi ; bm ); c() = cm + i(ci ; cm ):
X
i6=m
X
X
i6=m
i6=m
Пусть D и D | подмножества RN , на которых A() положительно определена или положительно полуопределена соответственно. Функция () конечна и вогнута на D ([9]). Если 2 D, то
задача вычисления () | задача выпуклого квадратичного программирования. В противном
случае она многоэкстремальна и сложна.
Ввиду этого вместо рассмотрим оценку = sup (). Для 2 D ([10]) () =
2D\RN+
; 14 [A;1()b(); b()] + c(). Функция () непрерывно дифференцируема на
D \ RN+ . Для ее
максимизации можно применить метод эллипсоидов, штрафные функции или метод обобщенного градиентного спуска. Если точная верхняя грань на D \ RN+ достигается на D, то = K и оценка точная.
При использовании модели первого порядка решать вспомогательную задачу легко (можно
использовать k k1 ). Тогда для конечных множеств индексов получаем задачу
min (min
([a ; s] + bi ) + max
([p ; s] + rj ); ksk1 k );
i2I i
j 2J j
или
min
max([a ; s] + bi + [pj ; s] + rj ); ksk1 k :
i2I j 2J i
7
Достаточно решить для каждого i задачу
min max
([a ; s] + bi + [pj ; s] + rj ); ksk1 k ;
j 2J i
которая сводится к задаче линейного программирования.
5. Метод доверительных окрестностей с масштабированием
В данном параграфе методы доверительных окрестностей обобщаются введением масштабирования. В них подзадача имеет вид
minfzxk (s); kDk sk k g;
где Dk | матрицы масштаба. Легко доказать сходимость, если матрицы Dk диагональны и
неотрицательны.
Полагается k := 0. Выбираются начальный радиус 0 и начальная матрица масштаба D0 .
Выбирается начальная точка x0 . Задаются параметры 0 < < < 1 и 0 < 1 < 1 < 2 .
Для каждого k = 0; 1; : : : решается задача
minfm(s); kDk sk k g:
Пусть sk | ее решение. Вычисляется lk = f (xk +ms(ks)k;)f (xk ) .
Если lk , то xk+1 = xk + sk ; иначе xk+1 = xk .
Если lk , то выбирается k+1 2 [k ; 2 k ].
Если > lk , то выбирается k+1 2 [1 k ; k ].
Если lk < , то выбирается k+1 2 (0; 1 k ]. Пересчитывается матрица масштаба и вычисляется Dk+1 .
Приведем теорему сходимости для модели второго порядка.
Теорема 5.1. Пусть выполняются шесть следующих предположений.
1) Для каждого y 2 " \ L0 и каждого " > 0 найдутся такие > 0 и убывающая на (0; ]
функция c(), не зависящие от y, что
c() < 0; 2 (0; ]; smin
z (s) c(); 2 (0; ];
2U y
e
где U = fs 2 Rn : ksk g.
2) Для каждого x 2 " \ L0 и каждых " > 0; 0 < < 1 найдется такое , не зависящее от
x, что
jf (x + s) ; f (x) ; zx(s)j ksk2 ; ksk 2 (0; ]:
3) Для каждого k и каждого > 0 найдется > 0 такое, что
kDk sk ) ksk :
4) Множество kDk sk для всех k включает шар ksk c1 , где c1 > 0.
5)
2 = C () > ;1 8 > 0:
lim
!0 c()
6) k и такие, что ksk () minf; g.
Тогда k () для некоторого > 0 и всех k.
Доказательство. Выполняется
f (xk + sk ) ; f (xk ) ; 1 ksk k2 2() 2() ; 1
m(sk )
c(c1 k ) c(c1 k ) c(c1 ())
для достаточно малого по нашим предположениям.
e
b
b
e
b
8
b
b
Можно решать следующую вспомогательную задачу, требуя, чтобы направление s принадлежало подпространству S малой размерности:
minfzxk (s); ksk k ; s 2 S g:
Например, можно взять S = fx = sN + vg, где v | направление наискорейшего спуска, sN |
направление, найденное методом Ньютона для дважды кодифференцируемых функций ([1]).
Пусть выполняются следующие предположения.
a) Для каждого y 2 " \ L0 и каждого " > 0 найдутся такие > 0 и убывающая на (0; ]
функция c(), не зависящие от y, что
c() < 0; 2 (0; ]; s2Umin
zy (s) c(); 2 (0; ];
;s2S
e
где U = fs 2 Rn : ksk g.
b) Для каждого x 2 " \ L0 и каждых " > 0, 0 < < 1 найдется такое , не зависящее от
x, что
jf (x + s) ; f (x) ; zx(s)j ksk2 ; ksk 2 (0; ]:
ksk2 = C > ;1.
c) kslim
k!0 c(ksk)
e
При предположениях a), b), c) для каждого " > 0 найдется xk 2 " .
Доказательство аналогично доказательству теоремы 5.1.
Автор выражает благодарность В.Ф. Демьянову и Я.И. Заботину за ряд ценных советов и
замечаний.
Теорема 5.2.
Литература
1. Демьянов В.Ф., Рубинов А.М. Основы негладкого анализа и квазидифференциальное исчисление. { М.: Наука, 1990. { 431 с.
2. Demyanov V.F., Rubinov A.M. Constructive non-smooth analysis. { Frankfurt: Peter Lang, 1995.
{ 590 p.
3. More J.J. Recent developments in algorithms and software for trust region methods // Math.
Progr.: State of the Art. { 1982. { P. 259{287.
4. Powell M.J.D. Convergence properties of a class of minimization algorithms // Non. Progr. 2. {
Academ. Press, 1975. { P. 1{27.
5. Levenberg K. A method for the solution of certain nonlinear problems in least squares // Quart.
of Appl. Math. { 1944. { V. 2. { P. 164{168.
6. Marquardt D.W. An algorithm for least squares estimation of nonlinear parameters // SIAM J.
on Appl. Math. { 1963. { V. 11. { P. 431{441.
7. Sorensen D.C. Newton's method with a model trust region modication // SIAM J. on Num. Anal.
{ 1982. { V. 19. { P. 409{426.
8. Horst R., Pardalos P. (Eds.) Handbook on Global Optimization. { Dordrecht: Kluwer Academ.
Publ., 1996. { 900 p.
9. Shor N.Z., Stetsenko S.I. Quadratic Extremal Problems and Nondierentiable Optimization. {
Kiev, Nauk. Dumka, 1989. { 220 с.
10. Shor N.Z. Dual estimates in multiextremal problems // J. of Global Optim. { 1995. { V. 7. {
P. 75{91.
Казанский государственный
университет
Поступила
03.09.2002
9