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

Глава 6. Задачи минимизации сумм квадратов невязок систем
линейных неравенств

    В данной главе рассмотрим одно из возможных направлений
конструирования методов решения систем линейных неравенств. Здесь не
будем в деталях описывать методы решения, а ограничимся сведением
проблемы поиска решения к двум классическим задачам. Одна из них –
задача безусловной минимизации кусочно-квадратичной выпуклой
функции. Для решения такой задачи могут эффективно применяться
многие известные алгоритмы, в т.ч. различные модификации методов
наискорейшего спуска, Ньютона.
    Другая задача – минимизация квадратичной выпуклой функции при
ограничениях-неравенствах на отдельные переменные. Для решения этой
задачи также существует много эффективных методов. Обе указанные
задачи относятся к так называемым простым задачам выпуклой
оптимизации.
    Процесс решения указанных задач любым из известных методов
осуществляется     путем     итеративного     построения    некоторой
последовательности приближений. Каждое последующее приближение в
каком-то смысле лучше, чем предыдущее. При этом на каждой итерации
можно определять приближение к множителям Лагранжа ограничений
рассматриваемой задачи.
    Здесь будет рассмотрено два пути сведения проблемы поиска решения
системы линейных неравенств к указанным простым задачам
оптимизации, каждый из которых может быть реализован в двух
вариантах.
    Во-первых, можно решать задачу минимизации суммы квадратов
невязок исходной системы линейных неравенств. Эта задача сводится к
минимизации кусочно-квадратичной функции. На основе приближений к
множителям Лагранжа данной задачи можно формировать приближение к
решению альтернативной системы линейных неравенств. Если в процессе
вычисления окажется, что полученное на очередной итерации
приближение является точным решением альтернативной ситсемы, то, тем
самым, выявляется ситуация противоречивости условий исходной системы
линейных неравенств.
    Данный подход может быть представлен в виде задачи поиска
решения с минимальной нормой некоторой двойственной задачи,
представимой в виде минимизации сепарабельной выпуклой функции при
однородных линейных ограничениях. Приближениями к множителям
Лагранжа этой задачи будут векторы, составляющие приближение к
решению исходной системы неравенств. При решении данной задачи либо
будет получено значение множителей Лагранжа, дающее решение
исходной системы линейных неравенств, либо будут получены


                                 86