Chebyshev projections to a linear manifold

Many problems of applied mathematics are presented in the form of the problem of finding the point of a linear manifold closest to the origin. In particular, this problem may take the form of a minimization problem for the Euclidean (least squares method) or Chebyshev norms. The use of these norms means that the Euclidean or Chebyshev projection of the origin onto a linear manifold is sought. By introducing and varying positive weight coefficients at the components of vectors in these norms, sets of Euclidean and Chebyshev norms are obtained that generate sets of Euclidean and Chebyshev projections. The search for the Chebyshev projection onto a linear manifold is represented as a linear program, which may have a nonunique solution. Moreover, some of its solutions may be clearly unsatisfactory with regards to the essence of the problem. In order to overcome the arising difficulties, the Haar condition is used in the Chebyshev approximation. This condition corresponds to the uniqueness requirement for the solution of the linear programming problem and is not always easy to check; moreover, it is not clear what to do if the condition is not met. We present an algorithm that always leads to an unambiguous determination of the Chebyshev projection. The algorithm is based on finding relatively interior points of optimal solutions to a finite sequence of linear programming problems with lexicographically ordered objective functions. It is proved that the set of Chebyshev projections (produced by the presented algorithm) coincides with the set of Euclidean projections. This statement allows us to extend the previously proved properties of Euclidean projections to the set of Chebyshev projections, including the established facts of boundedness and connectedness of the set of Euclidean projections. The proved statement about the coincidence of the sets of Euclidean and Chebyshev projections also confirms the correctness of the introduced definition of the Chebyshev projection by means of the lexicographic optimization algorithm.