Чебышевские проекции на линейное многообразие

Многие задачи прикладной математики представляются в виде проблемы поиска ближайшей к началу координат точки линейного многообразия. В частности, эта проблема может формулироваться в виде задачи минимизации евклидовой (метод наименьших квадратов) или чебышевской норм. Использование этих норм означает, что осуществляется поиск евклидовой или чебышевской проекции начала координат на линейное многообразие. За счет введения и варьирования положительных весовых коэффициентов при компонентах векторов в указанных нормах получаем множества евклидовых и чебышевских норм, порождающих множества евклидовых и чебышевских проекций. Поиск чебышевской проекции на линейное многообразие формулируется как задача линейного программирования, которая может иметь не единственное решение. Причем среди ее решений могут быть явно неудовлетворительные по содержательным соображениям. В целях преодоления возникающих из-за этого проблем в чебышевской аппроксимации используется условие Хаара, означающее требование единственности решения указанной задачи линейного программирования. Это условие не всегда легко проверить, и неясно, что делать, если оно не выполняется. В данной статье предложен алгоритм, всегда приводящий к однозначному определению чебышевской проекции. Алгоритм базируется на поиске относительно внутренних точек оптимальных решений конечной последовательности задач линейного программирования с лексикографически упорядоченными целевыми функциями. Доказано, что множество чебышевских проекций (при использовании приводимого алгоритма) совпадает с множеством евклидовых проекций. Это утверждение позволяет распространить на множество чебышевских проекций доказанные ранее свойства евклидовых проекций, в том числе установленные факты ограниченности и связности множества евклидовых проекций. Доказанное утверждение о совпадении множеств евклидовых и чебышевских проекций может служить также в качестве подтверждения правильности введенного определения чебышевской проекции через алгоритм лексикографической оптимизации.