Максимизация нормы на произвольном компакте

Задача максимизации нормы на некотором множестве является частным случаем общей задачи максимизации выпуклой функции, которая, как известно, относится к классу NP-hard задач. Методы отсечения для задачи выпуклой максимизации впервые были предложены Х.Туй в 1964 году [9]. До 1990-х годов основными методами решения задач этого класса были такие методы, как: метод отсечения [9], метод погружения [1] и метод ветвей и границ [3, 4, 5, 6]. Условия глобальной для этой задачи были сформулированы А.С. Стрекаловским в 1987 году [8]. Первый алгоритм, основанный на условиях глобальной оптимальности и понятии разрешающего набора, был предложен в работе [2, 7]. Этот алгоритм был предназначен для решения выпуклых задач на простых множествах, таких как: параллелепипед, шар и симплекс. В этой работе мы обсуждаем возможность нахождения £ -приближенного решения задачи максимизации нормы на невыпуклом компакте.

• 1.    Аппроксимация линии уровня функции и её свойства

Рассматривается задача

||х || ^ max, x e D с R n ,                    (1)

где D – произвольный компакт.

Пусть даны числа z >  0 и 8 <  z V2. Обозначим

U ( z ) = { x e R n l || x | = z } .

Рассмотрим на сфере U ( z ) сеть A ( z )

A ( z ) = { y V.., y \ 11 y i || = z , i = 1, _ , N } , N > 2 n . обладающую следующими свойствами:

• 1)    V i = 1,..., N ; 5 = 5 i @ min { \\ y i - y j || \j * i } .

• 2)    V x g U ( z ), З У^У ² ,..., У g A ( z ):

У = У Ч x ), У — У ^j || = 5 , x g B ( У , 5 ) , i , j = 1,..., n , где У^к = y i^k :

B ( У ^к , 5 ) = { x g R ⁿ | \\ x - У ^к \ ^ 5 } , k = 1,..., n .

Аппроксимацию A ( z ) назовём 5 -сетью.

Далее, семейство точек { У ¹ , ^ , У ” } с A ( z ), определённое свойством 2) и зависящее от x , обозначим через A ( x ). Из определения же вытекает единственность такого семейства.

Покажем, что

• У , У > = (2 z ² - 5 ² ) / 2, i * j , i, j = 1, _ , n .             (2)

Действительно, поскольку \\ у ¹ - У ^J \\ = 5 , то

\\УЦ2 -2+\\SJl2 = 52, так как \\ Si \\= z, то получаем (2).

Теперь подсчитаем Ц У ¹ + У ² + „. + S ⁿ \ \, используя ту же информацию. С учётом (5) имеем следующее

ЦУ1 + У2 +_ + yn Ц2 = <9\У> + <У2,У2> + _ +

+2[<У¹, У²) + <У², У³) + _ + <У^n-1, Уⁿ)] = nr²+ n⁽n^ 1) (2z²- 5²) =

_{2 2}n (n -1)5² = n z--.

Таким образом,

• | \ У¹+ У²+ _ + У \ \= (n²z²- ⁿ⁽ⁿ -^¹⁾⁵ )^1/2.                  (3)

Лемма 1. Элементы У¹,У²,^,У" g A(x) являются линейно независимыми.

Доказательство. Пусть, наоборот, существуют числа Xi,i = 1,^,n та- кие что n

Ё ХУ= 0.                          (4)

i=1

Умножая (4) на 2У^j с учётом (2), получаем следующую систему уравнений

(2 z²- 5)V Xi + 2Xr²= 0, j = 1,., n .                (5)

i * j

Нетрудно привести матрицу этой системы к диагональному виду. Это можно сделать, например, следующим образом.

Сначала надо вычесть первую строку из каждой строки матрицы системы (5), за исключением первой, а затем первый столбец сложить со всеми другими столбцами. Получим матрицу следующего вида

(2z²+ (n -1)(2z²-5²) 2z²-5²       2z²-5²^

0                  5²      ...      0

_v 0                    0       ...      5²,

Определитель этой матрицы очевидно равен

(5²)^n-1[2z²+ (n -1)(2z²- 5²)] > 0 .

Отсюда Xi = 0,Vi = 1,.,n , что и доказывает линейную независимость 9,.,9.

Теперь проведём через точки 9¹,...,9" касательные гиперплоскости к сфере U(z):

Hi = {x е Rⁿ / <9i,x} = {9‘,9‘} = z²},i = 1,.,n .

Найдём точку x⁰ пересечения этих гиперплоскостей. Очевидно, она удовлетворяет системе уравнений:

<9i,x⁰) = z²,i = 1,.,n .                           (6)

В силу Леммы 2 такая точка x0 существует и единственна. Обозначим р =|| x01| и покажем, что р > z. Действительно, z2 = <У,x0)<||9'||x||x0|у zp .

Отсюда z< р . Если z = р, то тогда

9 = /x⁰,У, * 0,i = 1,...,n.

Последнее противоречит линейной независимости векторов 9',.,9*. Итак р > z.(7)

Далее в силу линейной независимости 9¹,.,У существует единственная гиперплоскость H0, проходящая через У,.,У :

H0 @ H0(У,.,У) = { x е Rn | < a, x ) = a}, a е Rn, ae R.(8)

При этом, поскольку 9‘ e H₀, i = 1,., n, мы имеем

Далее, поскольку x⁰ является решением системы (6), то

<9i, x⁰) = z².

Отсюда, в силу линейной независимости 91 ,.,У вытекает, что a = 4 x °.                           (10)

z²

и уравнение для H0 принимает вид

H0 ={xeRn /<x0,x) = z²}.                   (11)

Далее нетрудно понять, что в гиперплоскости H0 существует единственный элемент c, коллинеарный с вектором x⁰, при этом

II c ll< P.

Последнее неравенство вытекает из того, что x⁰e H0 в силу (7) и (11).

Лемма 2. На гиперплоскости H0 существует единственная точка u, удовлетворяющая следующим соотношениям:

|| u - »\\=\\u - 3j\\, ', j = 1,..., n .                   (12)

При этом справедливо представление

n и = -^З'.                      (13)

n '=1

Доказательство.

1ⁿ

• а)    Прежде всего, ясно, что и = — 5,3' e H0, поскольку в силу (6)

П '=1

< x0, и ) = и = ¹I <3, x⁰ ) = z².

n '=1

• b)    Далее, V ' = 1, _, n, имеем

nn

II и - 3 II²=\\ и II²-2< и ,3')+ \\ 3 II²=\\ - ^У II²- - £<3j,3') + z².

n '=1             n '=1

Отсюда с помощью формул (2) и (3) получаем

2     1

II и - 3'\^ = — n²

2 2   n⁽n^-1) 2

n z--о

2 (n -1)(2z²- 0²)+ z2 n        2

= 2z² -n-¹5²-n-¹ (2z² -5²)-2z2. 2nnn

Производя очевидные упрощения, окончательно заключаем 1/2

11 и - 3'II²= 5|-— I ,' = 1,_,n .                 (14)

V 2 n V

• с)    Теперь покажем единственность точки, для которой справедливы соотношения (12). Из равенств (12), возведённых в квадрат, сразу же вы-

• текает

в =<и,3') = <и,У),1, j = 1,_,n.

Если в ^ 0, то это означает, что точка и, удовлетворяющая (12), является решением системы уравнений

<3',и) = в,' = 1,^,n .

В силу Леммы 1 эта система имеет единственное решение.

Условие же в = 0 означает, что u ортогонально линейно независимой системе векторов {д\д¹,^,д^п}, то есть u = 0. Последнее противоречит тому, что u e H₀, поскольку z > 0.

Следствие 1. Справедливы равенства: n У¹ ni -9- .

i=1 n

Кроме того, точка c является решением следующих экстремальных задач:

II x |Н min, x e H0, ||x - x⁰|p min,x e H₀.

Очевидно, второе утверждение Следствия 1 вытекает из перпендикулярности решения z задач (15) и (16) к векторам (x - z), Vx e H₀.

Следствие 2. Числа р и 8 связаны соотношением

имеет

^Р (2z²n - (n -1)8²)^1/2.

Доказательство. Прежде всего, поскольку c = yx0 e H0, имеем < x 0, c ) = YP2 = z2, откуда y = z2/ Р . Тогда Vi = 1,^,n z4

Р 2 .

|| c - 9'1²=1И²-< c ,9'>+P'1²= z⁴^ - 2 z4L + z² = z²

P P

Отсюда с помощью равенств (14) и Следствия 1 заключаем, что место равенство

2 z⁴^2 Г n - 1

.

z--2" = 8 I-----

P V 2 n

Разрешая это уравнение относительно р, получаем (17). Следствие 3. При 8 = zV2 из (17) следует

Далее, введём следующее обозначение

M = { x e Rⁿ I< yi, x )< z², i = 1,..., N; yi e A (z)} .

что если

Очевидно, что M – выпуклое замкнутое множество.

Теорема 1. Многогранник M ограничен.

Доказательство. Очевидно, что 0 e M . Покажем теперь, 3h e Rn такой, что th e M ,V t > 0, то, непременно, h = 0.

Очевидно, что соотношение (20) возможно в том и только в том случае, когда

< У, h >< 0,V i = 1,., N.                     (21)

Предположим, что для некоторого k g{1,.,N} имеет место строгое неравенство

< У^к, h >< 0.

Обозначим теперь z = - yk. Тогда нетрудно увидеть, что z G U (z) = {x G Rn /||x | = z} и 0 . Поскольку h ^ 0, то можно считать, что h g U (z).

По определению 5 -сети существуют n линейно независимых элементов 9,92.. 9n g A(z) таких, что z G clB(9,5),pil= z,i = 1,.,n.

Покажем, что элемент z g cone{9,., 9n}. Другими словами, что n z = Ё«9,                     (23)

i=1

ai> 0, i = 1,., n; j ai> 0.                    (24)

i=1

Поскольку {9¹,.,9ⁿ} - линейно независимая система, то представление (23) имеет место. Далее, из неравенства || z - 9' ||< 5 следует, что

2-Л2

<z,9)>---2--->0,i = 1,.,n .

Значит, ai > 0,Vi = 1,.,n . Второе неравенство в (24) выполнено, поскольку z ^ 0.

А теперь, принимая во внимание (22), получаем:

n

0 <<z,h) = jai<9,h).

i=1

Отсюда следует, что 3p g {1,., n}

<9p, h >> 0.                              (25)

Это означает, что h G M . Итак, (25) не может иметь места и потому

< yi, h > = 0, V i = 1,., N.

Из последних равенств заключаем, что h = 0, поскольку среди элементов сети A(z) существует система из n линейно независимых векторов. Итак, теорема полностью доказана.

Теперь мы в состоянии ответить на вопрос, какую сеть необходимо построить для того, чтобы утверждать, является ли данная точка £ -решением задачи (1) или нет.