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

или y j = 0 . При этом не исключается возможность того, что для
некоторого j
                            xj = yj = 0 .                                (17)
      Одним из основных результатов данного параграфа будет
доказательство того факта, что для некоторых пар векторов из S+ и S+⊥
ситуация (17) не имеет места, т.е. будет доказано, что существуют x ∈ S + и
 y ∈ S +⊥ , для которых
                           max{x j , y j } > 0, j = 1,..., n .        (18)
Неравенство (18) означает, что для любого j либо x j > 0 , либо y j > 0 .
Свойства (15), (18) вместе составляют условие строгой дополняющей
нежесткости или условие дополняющей нежесткости в строгой форме.

    Теорема 4. Пусть         S,   S⊥    – ортогональные линейные
подпространства в R n . Для любого k ∈{1,..., n} в одном и только одном
линейном подпространстве S или S ⊥ имеется вектор x такой, что
                            xk = 1 , x ≥ 0 .                             (19)
      Доказательство. Рассмотрим задачу
                            ϕ ( x) → min, x ∈ S ,                        (20)
где
                                       1                  1
                            ϕ ( x) =     ∑
                                       2 j ≠k
                                              ( x j ) −2 + (1 − xk ) 2
                                                          2
при
                            ( x j ) − = min{x j , 0} .

Отметим, что при любом x ∈ R n ϕ ( x) ≥ 0.
      Не существует векторов x, z из R n , при которых функция
 f (λ ) = ϕ ( x + λ z ) монотонно убывает при любом увеличении λ. Всегда
найдется такое значение λ, при превышении которого указанная функция
будет неизменна или будет возрастать. Следовательно, задача (20) имеет
оптимальное решение
                            x = arg min ϕ ( x), x ∈ S .
    Оптимальное значение целевой функции рассматриваемой задачи
обозначим
                            ϕ = ϕ (x) .


                                        53