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

решением альтернативной системы.                     Если     альтернативная    система
                ~
несовместна, то δ > 0 и по формуле
                                 ~  −1
                                 x= ~ ~y,
                                    δ
совпадающей с правилом (16), определяется решение системы (1). Причем,
как следует из задачи (21), (22), вектор ~
                                         x будет решением системы (1) с
минимальной нормой, т.е. он будет решением задачи

                                 ∑ x2j → min , Ax = b .
      6.2 Задачи минимизации сумм квадратов невязок исходной и
              альтернативной систем линейных неравенств

     Пусть A – матрица m × n , b ∈ R m . Рассмотрим систему линейных
неравенств относительно вектора переменных x ∈ R n :
                                  Ax ≥ b .                                        (23)
Альтернативной (23) будет следующая система линейных уравнений и
неравенств относительно вектора переменных u ∈ R m :
                                A Τ u = 0, b Τ u = 1, u ≥ 0 .                     (24)
     Для поиска решения и идентификации несовместности системы (23)
могут применяться аналоги двух подходов, рассмотренных в разделе 6.1
применительно к системам линейных уравнений. Оба подхода сводятся к
вычислительной проблеме безусловной минимизации выпуклой функции.
В первом случае число переменных равно n , во втором – m .
     Минимизация суммы квадратов невязок исходной системы.
Рассматривается задача
                                                        2
                                 f ( x) = (b − Ax) +        → min ,               (25)
где
                                               m                 n
                                            = ∑ (max{0, bi − ∑ aij x j }) 2 ,
                                        2
                           (b − Ax) +
                                              i =1              j =1

aij – коэффициенты матрицы A , i = 1, ..., m , j = 1, ..., n .
     Пусть x – решение данной задачи. Если f ( x) = 0 , то x – решение
исходной системы (23). Если f ( x) > 0 , то система (23) несовместна.
     Введя дополнительные переменные, составляющие вектор y ∈ R m ,
задачу (25) можно представить в виде
                                  Ax + y = b ,                                    (26)


                                             91