Системы линейных неравенств. Зоркальцев В.И - 52 стр.

UptoLike

ВУЗ: 

ИГУ | Иркутск

Составители: 

Рубрика: 

52
необходимо и достаточно выполнения при некотором
n
R
u
∈
равенства
uAxf
Τ
=∇ )( . (13)
При этом для векторов
x
, u выполнится соотношение
ubxxf
Τ
=∇ )),(( . (14)
Данный вектор
u будет состоять из множителей Лагранжа
ограничений задачи (12). Соотношение (14) вытекает из (13) и равенства
b
x
A
= . Действительно,
buxAuxuAxxf
Τ
Τ
Τ
===∇ ),()),(( .
Для задачи минимизации при ограничениях в виде линейной однородной
системы (10) условие (14) выполняется тривиальным образом. Выражения
в правой и левой частях этого равенства равны нулю. Выражение в левой
части равно нулю потому что
S
x
∈
(т.е. по теореме 1а). Выражение в
правой части равно нулю потому что 0
=
b . При 0
≠
b равенство (14)
может выполняться для ненулевых значений.
3.2 Теоремы об альтернативах в геометрической форме
Для произвольного множества
n
QR∈
подмножество его векторов с
неотрицательными всеми компонентами обозначим
.
n
QQR
+
= I
Пусть S и S
⊥
– два взаимно ортогональных подпространства в
n
R
.
Для любых векторов
+
∈ Sx ,
⊥
+
∈
Sy
njyx
jj
,...,1,0},min{
=
=
. (15)
Действительно, из того, что 0≥
x
, 0≥y , следует
njyx
jj
,...,1,0
=
≥ .
Поскольку
+
∈ Sx ,
⊥
+
∈ Sy , то
∑
=
0
jj
yx .
Поэтому из того, что
+
∈Sx и
⊥
+
∈
Sy , следует
njyx
jj
,...,1,0
=
=
, (16)
что дает (15).
Соотношение (15) и равносильное ему соотношение (16) называется
условием дополняющей нежесткости. Оно выполняется для любых
векторов
+
∈Sx ,
⊥
+
∈ Sy . Согласно (15), для любого {1,..., }
j
n
∈
или 0
j
x
=
, 
необходимо и достаточно выполнения при некотором u ∈ R n равенства
                                     ∇f ( x) = AΤ u .                             (13)
При этом для векторов x , u выполнится соотношение
                                     (∇f ( x), x) = bΤ u .                        (14)
     Данный вектор u будет состоять из множителей Лагранжа
ограничений задачи (12). Соотношение (14) вытекает из (13) и равенства
A x = b . Действительно,
                                                                   Τ         Τ
                           (∇f ( x), x) = ( AΤ u , x) = u A x = u b .
Для задачи минимизации при ограничениях в виде линейной однородной
системы (10) условие (14) выполняется тривиальным образом. Выражения
в правой и левой частях этого равенства равны нулю. Выражение в левой
части равно нулю потому что x ∈ S (т.е. по теореме 1а). Выражение в
правой части равно нулю потому что b = 0 . При b ≠ 0 равенство (14)
может выполняться для ненулевых значений.
         3.2 Теоремы об альтернативах в геометрической форме

    Для произвольного множества Q ∈ R n подмножество его векторов с
неотрицательными всеми компонентами обозначим
                              Q+ = Q I R+n .
    Пусть S и S ⊥ – два взаимно ортогональных подпространства в R n .
Для любых векторов x ∈ S + , y ∈ S +⊥
                                    min{x j , y j } = 0,         j = 1,..., n .   (15)
Действительно, из того, что x ≥ 0 , y ≥ 0 , следует
                                    x j y j ≥ 0,      j = 1,..., n .
Поскольку x ∈ S + , y ∈ S +⊥ , то
                                    ∑x   j   yj = 0 .
Поэтому из того, что x ∈ S + и y ∈ S +⊥ , следует
                                    x j y j = 0,        j = 1,..., n ,            (16)
что дает (15).
    Соотношение (15) и равносильное ему соотношение (16) называется
условием дополняющей нежесткости. Оно выполняется для любых
векторов x ∈ S + , y ∈ S +⊥ . Согласно (15), для любого j ∈{1,..., n} или x j = 0 ,


                                                 52

Страницы