Некоторые методы минимизации максимума квадратичных функций

Класс функций максимума от непрерывно дифференцируемых функций является одним из наиболее исследованных среди негладких функций (см., например, [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 ⁿ функция f непрерывна и дифференцируема по любому направлению g ∈ R ⁿ , при этом ее производная по направлению имеет вид (см, например, [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 ⁿ

(с) 2006 Полякова Л. Н.

Для нее сформулируем необходимые условия минимума.

Теорема 1. [1] 1) Для того чтобы точка х* Е R n была точкой минимума функции f на R ⁿ , необходимо, чтобы выполнялось включение

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 ⁿ , для которой выполняется условие (2) или условия (3), (4) называется стационарной точкой функции f на R ⁿ . Из условия (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 ⁿ

Множество dp(y) = co

( U   (^i,

(* e^R ^ ( y )

ч y + b*

есть субдифференциал функции ϕ в точ-

ке y Е R n . Нетрудно видеть, что при таком преобразовании R f (х) = R ^ (y).

Пусть точка y ^∗ ∈ R ⁿ является решением задачи (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 ⁿ .

• 3.    В обоих случаях справедливо равенство M f (x * ) = M ^ (y * ).

C Докажем первое утверждение леммы. Пусть x ^∗ ∈ R ⁿ — стационарная точка функции f на R ⁿ . Тогда выполнено включение (2), т. е.

O n G co

и jeRf (x*)

(A , x * + b i )

= co

< U (A , Dy * + b i ) >  ,i € R ^ ( y * )

= co

< U   (D T ) ¹ (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 ² , bi ¹    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 ⁿ является стационарной точкой функции ψ на R ⁿ , то несложно показать, что y * = z * — b o есть стационарная точка функции ^ на R n , а x * = D ^-1 y * — стационарная точка функции f на R ⁿ .

Таким образом, для того чтобы решить задачу (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 ⁿ .

Предположим, что числа S j >  0 при любом j E J . Нас будет интересовать случай, когда R f (x * ) = { 0,1 } . Тогда если точка x * E R ⁿ является решением задачи (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 + ц) ²    S j + ц

+ c = 0.

Если обозначить через p j (ц) = 2ц + S j +1, j E J , то уравнение (9) можно записать в виде

n

X j=1

P j ⁽ц^{)ь 2} 2(S j + ц) ²

— c = 0.

Пусть nn   n

P (ц) = 5> (ц)ь 2 П (S k + ц) ² — 2c П^ + ц) ² - j =1          k =1 ,k 6 = j                k =1

Очевидно, что многочлен P (ц) является многочленом степени 2n, и, в силу нашего предположения, имеет единственный положительный корень µ ^∗ .

Заметим также, что если точка x ^∗ ∈ R ⁿ является решением задачи (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 2₃ 2(vO j + 1) 2

-

νb _j ²

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 ² ,    c = 2.5.

Найдем точку минимума функции f (x). Так как коэффициент c >  0, то нулевая точка не является точкой минимума функции f на R ² . Точка x * = (4, 4) G R ² есть точка минимума функции f i на R ² . В ней 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 + ц) ² + 16(2ц + 7)(4 + ц) ² — 5(4 + ц) ² (6 + ц) ² = 5ц ⁴ + 50ц ³ + 111ц ² — 196ц — 532 = (ц — 2)(5ц ³ + 60ц ² + 231ц + 266).

Многочлен 5ц ³ + 60ц ² + 231ц + 266 не имеет положительных корней, поэтому число ц * =2 является единственным положительным корнем многочлена P (ц), и точкой минимума функции f на R ² будет точка 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) = ¹ 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 ⁿ

Решение задачи (11) существует и точка минимума функции f на R ⁿ единственна.

Обозначим через 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 | ²} .

Этот минимум достигается в единственной точке w(x) E R n . Обозначим через

p^(x) = max |^(f i ^{(x) - f (x))}M ⁺ h f^x^w^ i ^{+ 1} k ^w(x) k ²| . 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 ² 6 0.

i =1

Несложно доказать утверждения:

Лемма 2. 1) Функция p(x) тогда и только тогда равна нулю, когда точка x является точкой минимума функции f на R ⁿ .

• 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 ⁿ .

Выберем произвольную точку x g G R n . Если точка x g есть точка минимума функции f на R ⁿ , то процесс останавливается.

Пусть уже найдена точка x k ∈ R ⁿ . Если точка x k является точкой минимума функции f на R ⁿ , то процесс закончен. Предположим, что точка 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 ² < 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 )|| ²

= ^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

• ⁶ 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 ² 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 ² 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 ⁿ .

Теорема 2. В данном методе при произвольной начальной точке x 0 ∈ R ⁿ последовательность { 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 ¹⁰ — точка минимума функции f(x) на R ⁿ , 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 ₁ ⁰ (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 .