Некоторые методы минимизации максимума квадратичных функций
Автор: Полякова Людмила Николаевна
Журнал: Владикавказский математический журнал @vmj-ru
Статья в выпуске: 4 т.8, 2006 года.
Бесплатный доступ
В работе рассматривается несколько алгоритмов минимизации функции максимума от квадратичных функций в евклидовом пространстве \Bbb R^n. Показывается, что данную задачу можно свести к нахождению точки с наименьшей евклидовой нормой, принадлежащей пересечению квадрик. Описывается метод минимизации функции максимума на \Bbb R^n с постоянным шагом, аналогичный градиентному методу минимизации с постоянным шагом сильно выпуклой функции. Доказывается геометрическая скорость сходимости генерируемой последовательности к точке минимума.
Короткий адрес: https://sciup.org/14318198
IDR: 14318198
Текст научной статьи Некоторые методы минимизации максимума квадратичных функций
Класс функций максимума от непрерывно дифференцируемых функций является одним из наиболее исследованных среди негладких функций (см., например, [1, 2]). Напомним некоторые свойства таких функций. Пусть f (x) = max fi(x), fi(x) = 1 hAiX,x) + hbi,xi + Ci, i G Ii = 0 U I, I = 1,...,m, x G Rn, ieii 2
где A i — симметричные матрицы размера n x n, b i G R n , c i G R , i G I i .
В каждой точке x ∈ R n функция f непрерывна и дифференцируема по любому направлению g ∈ R n , при этом ее производная по направлению имеет вид (см, например, [1])
f Wx^^ max J vgi^ df ( x ) = co * v E df ( x )
U (A i x + b i ) L R f (x) = { i G I i I f i (x) = f(x) } .
^i^ R f ( x )
Здесь через co { X } обозначена выпуклая оболочка множества X. Множество df (x * ) называется субдифференциалом функции f в точке x ∗ .
Рассмотрим оптимизационную задачу: найти
inf f (x). x ∈ R n
(с) 2006 Полякова Л. Н.
Для нее сформулируем необходимые условия минимума.
Теорема 1. [1] 1) Для того чтобы точка х* Е R n была точкой минимума функции f на R n , необходимо, чтобы выполнялось включение
O n Е df (х * ).
-
2) Для того чтобы точка х* Е R n была точкой минимума функции f на R n , необходи- m
мо, чтобы нашлись такие неотрицательные коэффициенты р*, i Е I i , 22 Р * = 1, чтобы
*=0 выполнялись условия mm
Е р^х* = -£ р*Ь*,(3)
i=0
Р* (fi(x) — f (х))=0, i Е Ii.(4)
Точка x ∗ ∈ R n , для которой выполняется условие (2) или условия (3), (4) называется стационарной точкой функции f на R n . Из условия (4) следует, что если в стационарной точке i Е R f (х * ), то P i = 0.
Пусть точка х * Е R n — стационарная точка функции f на R n и числа р * , i Е К, таковы, что для них в x ∗ выполнены соотношения (3), (4). Введем множество
m
M f (х * ) = { р = (р 0 , Р 1 ,...,р т ) Е R m+1 | р ** > 0, i Е I 1 , ^р* = 1 } .
=0
Если все матрицы A * , i Е I, — неотрицательно определенные, то функции f * , i Е I i , являются выпуклыми, и тогда необходимые условия минимума, сформулированные в теореме 1, являются также достаточными условиями. Если все матрицы A * , i Е Ii, — положительно определенные, то решение задачи (1) единственно.
Рассмотрим невырожденное преобразование х = Dy. В результате такого преобразования квадратичные формы h A * x, х ^ i Е I i , будут приведены к квадратичным формам h Ajy,y i , i Е I i . Причем матрицы A * , A * связаны соотношениями
A* = (DT)-i A*D-1, A* = DTAD, i Е Ii, где через DT обозначена транспонированная матрица.
Определим функцию
^(y)=maxy * (y), y Е R n ,
∈I где
P * (y) = 2h"^ * y,y i + hA y i + c«, b * = D T b * Е R n , i Е I i .
Рассмотрим оптимизационную задачу: найти
inf y(y). y ∈ R n
Множество dp(y) = co
( U (^i,
(* eR ^ ( y )
ч y + b*
есть субдифференциал функции ϕ в точ-
ке y Е R n . Нетрудно видеть, что при таком преобразовании R f (х) = R ^ (y).
Пусть точка y ∗ ∈ R n является решением задачи (5), тогда необходимо, чтобы
O n G co
• U (Aiy - + b,) >.
ii e R ^ ( y * )
Лемма 1. 1. Если точка x * G R n является стационарной точкой функции f на R n , то y * = D -1 x * есть стационарная точка функции ^ на R n .
-
2. Если точка y * G R n является стационарной точкой функции ^ на R n , то x* = Dy * есть стационарная точка функции f на R n .
-
3. В обоих случаях справедливо равенство M f (x * ) = M ^ (y * ).
C Докажем первое утверждение леммы. Пусть x ∗ ∈ R n — стационарная точка функции f на R n . Тогда выполнено включение (2), т. е.
O n G co
и jeRf (x*)
(A , x * + b i )
= co
< U (A , Dy * + b i ) > ,i € R ^ ( y * )
= co
< U (D T ) 1 (A , y * + b i ) >.
ii G R v ( y * )
Отсюда следует, что O n G co
I
и
i e R ^ ( y * )
(A i y * + b i ) }
= d^(y * ).
Второе утверждение леммы доказывается аналогично.
Из доказательства также следует справедливость равенства M f (x * ) = M - (y * ). B
Из линейной алгебры известно (см., например, [3, 4]), что любую квадратичную форму с положительно определенной матрицей можно привести невырожденным преобра- зованием к нормальному виду.
В дальнейшем будем предполагать, что матрица A q — положительно определенная. Тогда инфимум в задаче (1) достигается. Предположим, что невырожденное преобразование x = Dy приводит квадратичную форму h A o x. x' i к нормальному виду. В этом случае, A q = E , где через E обозначена единичная матрица размера [n х п]. Затем рассмотрим преобразование y = z — b o и квадратичные функции
2 h> l i Z,z i + h b i ,z i + c , , i G I,
= h b i ,z i — 2 h A i Z,b i i ,
' hbi, b o i , i G I.
^0(z) = 2 hz,zi + Cq, ^i(z) = где
C q = c q — ^ k b o k 2 , bi 1 7 7
c i = c , + 2 h A i b Q , b Q i -
Обозначим ^(z) = max ^ i (z). Рассмотрим оптимизационную задачу: найти i ∈ I 1
m i ni ^(z).
Если точка z ∗ ∈ R n является стационарной точкой функции ψ на R n , то несложно показать, что y * = z * — b o есть стационарная точка функции ^ на R n , а x * = D -1 y * — стационарная точка функции f на R n .
Таким образом, для того чтобы решить задачу (1), необходимо уметь минимизировать функцию f (x) = max fi (x), i∈I1
где fo(x) = 2hx,xi, fi(x) = 2hAix,xi + hbi,xi + ci, x £ Rn,
A i , — симметричные матрицы размера [n x n], b i £ R n , c i £ R , i £ I .
Если матрицы Ai, i ∈ I, — положительно определенные, то решение задачи (1) существует и единственно. В дальнейшем будем предполагать, что в точке минимума x∗ функции f на Rn все функции fi, i £ Ii, активны, т. е. выполнено равенство Rf (x*) = Ii. Тогда задача (1) эквивалентна задаче условной оптимизации: найти min -hx, xi, xex 2
где
-
X = {x £ R n | 2 h A i x,x i + h b i , x i + a = 2 h x,x i , i £ /} .
-
2. Минимизации максимума двух квадратичных функций
Множество X может быть записано в виде
X = { x £ R n | f i (x) - f o (x) = 0, i £ I } .
Пусть задана квадратичная функция
q(x) = 2 hAx, xi + hb, xi + c, множество X(q) = {x £ Rn | q(x) = 0} называется квадрикой. Если обозначить через qi(x) = fi(x) - f0(x), i £ I, то множество X есть пересечение квадрик, определяемых квадратичными функциями qi , i ∈ I . Поэтому задача минимизации функции f на Rn сводится к нахождению точки из множества X , имеющей наименьшую евклидову норму.
Рассмотрим случай минимизации функции максимума от двух квадратичных функций в предположении, что матрица A0 положительно определена. Из линейной алгебры известно, что существует невырожденное преобразование x = Dy, приводящее квадратичную форму hA1x, xi к каноническому виду, а форму hA0 x, xi — к нормальному виду. Таким образом, можно считать, что функции f0 и f1 имеют вид fo(x) = 2hx,xi, fi(x) = 2h©x,xi + hb, xi + c, x,b £ Rn, c £ R, где матрица 0 — диагональная матрица (0 = diag {^j}, j £ J = 1..n), полученная в результате соответствующего невырожденного преобразования, и f (x) = max{fo(x), fi(x)}.
Отметим тот факт, что если в результате преобразования оказалось, что число c 6 0, то решение задачи (1) есть нулевая точка. Поэтому будем считать c > 0. Рассмотрим множество точек x∗ , которые являются стационарными для функции f1 на Rn, т. е. точки, для которых
0x * + b = 0 n , (6)
и выполнено неравенство f o (x * ) < f i (x * ). Если все числа S j > 0, j E J , то функция f l сильно выпукла и точка x * = — 0 - 1 b i будет единственным решением задачи (1). Если среди чисел S j есть отрицательные, то может оказаться, что точка x * = — 0 -1 b являющаяся решением системы (6) не есть точка локального минимума функции f на R n .
Предположим, что числа S j > 0 при любом j E J . Нас будет интересовать случай, когда R f (x * ) = { 0,1 } . Тогда если точка x * E R n является решением задачи (1), то необходимо, чтобы нашлось положительное число µ ∗ , для которого справедливо равенство
0x * + b = — ^ * x * .
Уравнение (7) можно переписать в виде (0 + ц * E ) x * = — b. Отсюда имеем
x * = — (0 + ц * Е) - 1 b.
Так как матрица 0 + ц*Е диагональная, то и обратная к ней также будет диагональной,
(0+ ц E) -1 =diag {jb*}- j e J
-
b j
, где b j —
S j + Ц
Следовательно, j-ая координата вектора x* будет равна величине x* = j-ая координата вектора b. Покажем, что нахождение числа µ∗ сводится к нахождению корня многочлена с действительными коэффициентами степени 2n.
b j
Зафиксируем произвольное число ц E R , x j = — ----- . Подставляя в выражение (8)
J Sj + ц значение xj , получим уравнение
n
X j=1
(S j — 1)b 2 — b 2
2(6 j + ц) 2 S j + ц
+ c = 0.
Если обозначить через p j (ц) = 2ц + S j +1, j E J , то уравнение (9) можно записать в виде
n
X j=1
P j (ц)ь 2 2(S j + ц) 2
— c = 0.
Пусть nn n
P (ц) = 5> (ц)ь 2 П (S k + ц) 2 — 2c П^ + ц) 2 - j =1 k =1 ,k 6 = j k =1
Очевидно, что многочлен P (ц) является многочленом степени 2n, и, в силу нашего предположения, имеет единственный положительный корень µ ∗ .
Заметим также, что если точка x ∗ ∈ R n является решением задачи (1), то необходимо и достаточно, чтобы нашлось такое положительное число ν ∗ , чтобы выполнялись равенство
v * (0x * + b) = — xX
Из этого уравнения следует, что x * = — v * (v * 0 + E ) -1 b. (В нашем случае, v * = —).
νb j
Пусть v G R и j-ая координата вектора х* равна величине х* =-------. Подставляя j vOj + 1
в выражение (8) значение x ∗ , получим уравнение
n
X j=1
(O j - 1)v 2 b 23 2(vO j + 1) 2
-
νb j 2
vO j + 1
I
+ c = 0.
Если обозначить через Sj(v) = v2(1 + Oj)+2v, j G J, то уравнение (10) можно записать в виде
n
X j=1
s j (v)b 2
2(vO j + 1) 2
- c = 0.
Нахождение нужного нам числа ν∗ также сводится к определению единственного положительного корня многочлена S (v) степени 2n следующего вида nn n
S(v) = £s j (v) П (v9 j + 1) 2 - 2c ПИк + 1) 2 .
j =1 k =1 ,k 6 = j k =1
Остановимся на одном варианте определения преобразования D (см., например, [3]). Рассмотрим спектральное разложение матрицы A o : A o = Q o AQ T , где Q o — ортогональная матрица, матрица Л — диагональная матрица, на главной диагонали которой стоят собственные числа λ j матрицы A 0 , расположенные в порядке невозрастания, т. е.
Л = diag { A j } , A i > A 2 > ... > A n > 0.
Невырожденное преобразование х = S(Л)Q T у, где
S (Л) = (VЛ)
- 1
= diag
, при-
водит квадратичную форму h A 0 x, x i к нормальному виду h y, y i , а квадратичную форму
_ hA1x, xi — к виду hA1y, yi. Заметим, что
A i = Q o S (Л)A 1 S(Л)Q T .
Рассмотрим спектральное разложение матрицы A 1 : A 1 = Q 1 0Q T , где матрица Q 1 — ортогональная, а 0 — диагональная матрица, на главной диагонали которой находятся собственные числа θ j , j ∈ J, матрицы A 1 , расположенные в порядке невозрастания, т. е.
0 = diag { O j } , O i > в 2 > ... > O n > 0.
Тогда невырожденное преобразование у = Q T z, приводит квадратичную форму h y, y i к виду h z, z i , а квадратичную форму h A i у, y i к виду h 0z,z i .
Таким образом, невырожденное преобразование у = Dx, где D = S(Л)Q T Q T приводит к нормальному виду квадратичную форму h A 0 x, x i , а форму h A 1 x, x i — к каноническому виду.
-
3. Минимизация функции максимума на плоскости
В двумерном случае при минимизации функции максимума мы сталкиваемся с тремя вариантами:
-
1) точка минимума функции максимума совпадает с точкой минимума одной из функций;
-
2) в точке минимума активны две функции;
-
3) в точке минимума активны три функции.
Если оказалось, что в точке минимума активны более трех функций, то нулевая точка должна содержаться в выпуклом многоугольнике, натянутом на градиенты активных функций в этой точке. Но в двумерном случае, как следует из теоремы Каратеодори, для представления любой точки из выпуклой оболочки, натянутой на конечный набор векторов, в виде выпуклой комбинации этих векторов достаточно не более трех точек. Стало быть, в точке минимума можно рассматривать не более трех активных функций.
Если в точке минимума функции максимума активны две функции, то задача минимизации может быть сведена к нахождению положительного корня многочлена четвертой степени. Рассмотрим
Пример 1. Пусть f (x) = max{fo(x), fi(x)}, x = (xi, X2) G R2, где
f o (x) = 2 h x,x i , f i (x) = 2 h ©x,x i + h b,x' i + c.
0 = diag { 4, 6 } , b = ( — 3, - 4) G R 2 , c = 2.5.
Найдем точку минимума функции f (x). Так как коэффициент c > 0, то нулевая точка не является точкой минимума функции f на R 2 . Точка x * = (4, 4) G R 2 есть точка минимума функции f i на R 2 . В ней f o (x * ) = 288 , f i (x * ) = 24 . Следовательно, точка x * также не является точкой минимума функции f . Таким образом, функция f достигает минимума в точке x * , для которой R f (x * ) = { 0,1 } . Тогда
Р 1 (ц) = 2ц + 5, Р 1 (ц) = 2ц + 7,
P (ц) = 9(2ц + 5)(6 + ц) 2 + 16(2ц + 7)(4 + ц) 2 — 5(4 + ц) 2 (6 + ц) 2 = 5ц 4 + 50ц 3 + 111ц 2 — 196ц — 532 = (ц — 2)(5ц 3 + 60ц 2 + 231ц + 266).
Многочлен 5ц 3 + 60ц 2 + 231ц + 266 не имеет положительных корней, поэтому число ц * =2 является единственным положительным корнем многочлена P (ц), и точкой минимума функции f на R 2 будет точка x * = (2, 2).
Рассмотрим задачу минимизации на плоскости функции максимума от трех квадратичных функций:
fo(x) = 2hx,xi, fi(x) = 2h^x,xi + hbi,xi + ci, f2(x) = 2hAx,xi + hb2, xi + C2, где матрица Л — диагональная, матрица A — симметричная, x, bi b2 G R2, ci, c2 G R. Предположим, что в точке минимума x∗ активны три функции. Тогда точку минимума следует искать среди решений системы нелинейных уравнений:
{ 2 h Лx, x i + h b i , x i + c i = 2 h x, x i , 2 h Ax, x i + h b 2 , x i + c 2 = 2 h x, x i .
Среди этих точек выбирается точка x ∗ , для которой нулевая точка содержится в треугольнике, натянутом на векторы x * , Лx * + b i , Ax * + b 2 .
Следует отметить тот факт, что если найденная точка минимума не является точкой минимума ни одной из функций f p , p = 0,1, 2, то она будет точкой строгого локального минимума функции f .
-
4. Минимизация функции максимума квадратичных функций с постоянным шагом
Пусть
f (x) = maxf i (x), f i (x) = 1 h A i X,x i + h b i ,x i + c i , i E I = { 1,...,s } , i e i 2
где матрицы Ai — положительнно определенные, x, bi ∈ Rn , ci ∈ R, i ∈ I . Известно, что функция f является сильно выпуклой на Rn . В качестве константы сильной выпуклости можно взять константу m = min mi, где mi — наименьшее собственное число матрицы Ai. i∈I 2
Т. е., f (Axi + (1 - A)x2) 6 Af(xi) + (1 - A)f(X2) - mA(1 - A)|xi - X2||2,
V A E [0,1], V x i ,X 2 E R n , i E I.
Рассмотрим задачу: найти
min f (x). x ∈ R n
Решение задачи (11) существует и точка минимума функции f на R n единственна.
Обозначим через M = max{1, max Mi}, где Mi — наибольшее собственное число мат-i∈I рицы Ai . Тогда справедливо неравенство hAiX,xi 6 M||xk2 Vx E Rn, Vi E I. (12)
С каждой точкой x ∈ Rn свяжем оптимизационную задачу: найти min max w∈Rn i∈I
(f i (x)
- f (x))M + h f 0 (x),w i + 2 k w | 2} .
Этот минимум достигается в единственной точке w(x) E R n . Обозначим через
p(x) = max |(f i (x) - f (x))M + h f^x^w^ i + 1 k w(x) k 2| . i e i 2 J
Из необходимых условий минимума задачи (13) следует существование коэффициентов
s
Ai(x) > 0, i E I, X Ai(x) = 1, i=1
таких, что ss
w(x) = - Ai(x)fi0(x) = Ai(x)(Aix + bi), i=1 i=1
s 1
P(x) = 52A i (x)(f i (x) - f (x))M - ^||w(x) k 2 6 0.
i =1
Несложно доказать утверждения:
Лемма 2. 1) Функция p(x) тогда и только тогда равна нулю, когда точка x является точкой минимума функции f на R n .
-
2) Если вектор w(x) = 0 n , то p(x) = 0 .
Таким образом, если точка x * — точка минимума функции f на R n , то w(x * ) = 0 n .
В дальнейшем будет показано, что если точка x не есть точка минимума функции f на R n , то направление w(x) является направлением спуска функции f в точке x.
Опишем метод минимизации функции f на всем пространстве R n .
Выберем произвольную точку x g G R n . Если точка x g есть точка минимума функции f на R n , то процесс останавливается.
Пусть уже найдена точка x k ∈ R n . Если точка x k является точкой минимума функции f на R n , то процесс закончен. Предположим, что точка x k не является точкой минимума функции f на R n . Найдем направление спуска w(x k ), т. е., решим оптимизационную задачу (13) при х = X k . Тогда найдутся такие коэффициенты
s
Xi(xk) = Xk > 0, i G I, ^Xk = 1, i=1
что справедливо
s
w(X k ) = - 52 Xi f i (x k ), w(x k ) = 0 n i =1
s
p(x k ) = ^X i (x k )(f i (x k ) i =1
- f (X k ))M - 2 k w(x k ) k 2 < 0.
Положим a = —, M ,
X k +1 = X k + aw(x k ).
Лемма 3. В каждой точке x k выполняется неравенство
f ( x k +i ) - f(x k ) 6 MP( x k )•
C В силу свойств функций f i справедливо
« 2
f i (x + aw) = f i (x) + a h f i (x), w i + — hA i w, w i V i G I, V x G R n , w G R n , V a.
Тогда из (12) для любого i ∈ I имеем a2
f i (x k + aw(x k )) - f(X k ) 6 f i (x k ) - f (X k ) + a h f i (x k ), w(x k ) i + — M k w(x k )|| 2
= f i (x k ) - f (x k ) + ' h f i ( x k ) ,w ( x k ) i + k w(x k ) | 2 .
21V±
Отсюда вытекает неравенство max fi(xk + aw(xk)) - f (xk) = f (xk+i) - f (xk) i∈I
-
6 mmax {f i (x k ) - f(x k )+ MM h f i (x k ) ,w ( x k ) i + 2Mv k w(x k ) | 2}
= max 1 ( f i ( x k ) - f (x k ))M + h f i^ ( x k ) ,w ( x k ) i + 1 ||w(x k ) k 2 I = P( x k ) < 0. B M i E l ( 2 J M
Неравенство (14) показывает, что процесс является релаксационным, следовательно, последовательность { f (x k ) } является сходящейся.
Следствие 1. Если последовательность { x k } бесконечна, то p(x k ) ^ 0 при k ^ + го .
Так как для любой сильно выпуклой функции множество
L(xo) = {x е Rn | f (x) 6 f (xo)} компактно, то последовательность {xk}, генерируемая этим методом принадлежит лебегову множеству L(xo).
Лемма 4. Для данного метода в каждой точке x k справедливо неравенство
p(x k ) 6 m (f (x * ) - f (x k )). (15)
C Для точек xk , x∗ и для каждого индекса i ∈ I верно неравенство fi(x*) — fi(xk) > hfi(xk),x* — xki + mmkx* — xk 112, i е I.
Тогда, умножая это неравенство на m, получим hfi(xk),m(x* - xk)i 6 m(fi(x*) - fM)) - —kx* - xkk2, i е I.
Положим в (13) w = m(x * - x k ). Тогда имеем
p(x k ) 6 max^ (f i (x k ) - f (x k ))M + <Л ° (x k ),m(x * - x k ) ) i ∈ I
+ - k x *
- x k k 2 1 6 inax|(/ i (x k ) - f (x k ))m + m(f i (x * ) - f i (x k ))}
6 mmax { f i (x * ) - f (x k ) } 6 m(f (x * ) - f (x k )). B i ∈ I
Следствие 2. Из формул (14) и (15) вытекает неравенство
m f (xk+i) - f (xk) 6 m(f (x )- f (xk)).
Следовательно, последовательность { x k } является сходящейся и ее предельной точкой является точка минимума функции f на R n .
Теорема 2. В данном методе при произвольной начальной точке x 0 ∈ R n последовательность { x k } сходится к точке минимума x ∗ функции f со скоростью геометрической прогрессии:
f (x k +1 ) - f(x * ) 6 q(f (x k ) - f (x * )),
m где q = 1 - m , и существует положительное число Q, что справедливо неравенство kxk - x*k 6 Q(Vq)k.
C Из (16) получим
f(x k +i )
= (1
-
-
f (x * ) 6 f (x k ) - f (x * ) + -(f (x * ) - f (x k )) M) (f (x k ) - f (x * ))= q(f (x k ) - f (x * )).
Следовательно, для каждого фиксированного k > 0 имеем f (xk) - f (x*) 6 qk(f (xo) - f (x*)).
Поскольку точка x∗ есть точка минимума функции f на Rn , то f (xk) - f (x*) > mm kxk—x*k2.
Поэтому kxk - x*k2 6 -(f(xk) - f(x*))qk.
m
Обозначим через
Q = J —(f (x o ) - f (x * )),
m тогда kxk - x*k 6 ^m|(f (xk) - f (x*))qk 6 Q(Vq)k• B
Рассмотрим более подробно вычислительный аспект решения задачи (13). Для того чтобы найти направление w(xk), необходимо решить задачу квадратичного программирования min {hG(xk)A,Ai + Mhq(xk), Ai} , λ∈Λ где s
Л = {A = (Ai,...,As) gRs | XAi = 1, Ai > 0, i G I}, i=1
G(x k ) — матрица Грама векторов f i (x k ), т. е.,
Af i (x k ),f 1 (x k ) i ... h f 1 (x kf (x k )Д
G(x k ) = I •• • I,
\ hf s (x k ),f 1 (x k ) i ... h f s (x k ),f s (x k )i/
и
q(x k ) = (q i (x k ),..., q s (x k )) e R s , q i (x k ) = f (x k ) - f i (x k ), i G I.
Таким образом, необходимо определить коэффициенты λi , i ∈ I , и выразить через них s вектор w(xk) по формуле w(xk) = - P Akfi(xk).
i =1
Пример 2. В качестве тестовой функции была рассмотрена функция максимума [5]
f (x) = max fi(x), x G R10, I = 1,..., 5, i∈I где fi(x) = hAix,xi + hbi,xi, bi G R10, i G I, ai(j, k) = ej/k cos(j • k) sini, j < k, ai(j, k) = ai(k,j), j > k, ai(j,j) = 2 1 sini| i + X |ai(j, k)|, j k6=j bi(j) = ej/i sin(i • j), j,k G 1:10.
Матрицы A i , i ∈ I , являются положительно определенными и в таблице 1 приведены, соответственно, максимальное (λ max ) и минимальное (λ min ) собственные числа матриц
2A i , значение каждой из функций f i , i ∈ I , в точке минимума и норма градиента этих функций в точке минимума.
Для данной функции M = 36.32, m = 0.67. Точка x ∗ = ( - 0.0546, - 0.0241, - 0.0057, 0.0231, 0.0558, - 0.2434, 0.0685, 0.1321, 0.0772, 0.0336) T ∈ R 10 — точка минимума функции f(x) на R n , f(x ∗ ) = - 0.72576 — решение задачи, k w(x ∗ ) k = 0.000092, R(x ∗ ) = { 2, 3, 4, 5 } , где
R(x * = { i e 1 1 f i (x * ) = f(x * ) } .
Таблица 1
i |
1 |
2 |
3 |
4 |
5 |
λ max |
53.947 |
59.585 |
9.470 |
55.017 |
72.613 |
λ min |
14.301 |
16.661 |
2.754 |
19.337 |
25.919 |
f i (x ∗ ) |
- 311.19750 |
- 0.725756 |
- 0.725756 |
- 0.725756 |
- 0.725756 |
k f i 0 (x ∗ ) k |
12805.888 |
155.679 |
37.765 |
14.479 |
5.934 |
Из таблицы видно, что первая функция не является активной в оптимальной точке, но поскольку ее градиент в x ∗ достаточно большой, то в точке x ∗ +αf 1 0 (x ∗ ) при небольших α она становится активной.
Очевидно, что в большинстве случаях заранее не известно число M . Поэтому можно использовать данный алгоритм при различных M , начиная с заведомо большого. Для данного примера оптимальная точка x ∗ была получена при M = 145.28 за 85 шагов, при M = 72.64 за 38 шагов, при M = 36.32 за 19 шагов, при M = 18.16 за 11 шагов. При M = 9 и меньше алгоритм не сходился. Задача считалась решенной, если выполнялось условие k w(x k ) k < 10 -4 .
Список литературы Некоторые методы минимизации максимума квадратичных функций
- Демьянов В. Ф., Малоземов В. Н. Введение в минимакс.-М.: Наука, 1972.-368 с.
- Пшеничный Б. Н. Метод линеаризации.-М.: Наука, 1983.-136 с.
- Гантмахер Ф. Р. Теория матриц.-М.: Наука, 1967.-552 c.
- Мишина А. П., Проскуряков И. В. Высшая алгебра. СМБ.-М.: Физматгиз, 1962.-300 с.
- Lemarechal C. An extension of Davidon methods to nondifferentiable problems//Mathematical programming.-1975.-Study 3.-P. 95-100.