V.I. Zorkal’tsev. Chebyshev projections to a linear manifold ... P. 44-55

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.

Keywords: lexicographic optimization, linear manifold, Haar condition, Chebyshev and Euclidean norms, Chebyshev projections

Received June 3, 2020

Revised July 25, 2020

Accepted August 10, 2020

Funding Agency: This work was supported by the Russian Academy of Sciences (project no. 0279-2019-0003) and by the Russian Foundation for Basic Research (project no. 19-07-00322).

Valeriy Ivanovich Zorkaltsev, Dr. Tech. Sci., Prof., Limnological Institute SB RAS, Irkutsk, 664033 Russia, e-mail: zork@isem.irk.ru

REFERENCES

1.   Eremin I.I. Protivorechivye modeli ekonomiki [Contradictory models of economics]. Moscow: Nauka Publ., 1980, 160 p.

2.   Vatolin A.A. On the approximation of inconsistent systems of linear equations and inequalities. In: Approximation methods for improper problems of mathematical programming, Collect. Artic. Sverdlovsk, 1984, pp. 39–54 (in Russian).

3.   Lawson C.L., Hanson R.J. Solving least squares problems. Prentice-Hall Series in Automatic Computation. Englewood Cliffs, N J: Prentice-Hall, 1974, 340 p. ISBN: 0138225850 . Translated to Russian under the title Chislennoe reshenie zadach metoda naimen’shikh kvadratov. Moscow: Nauka Publ., 1986, 232 p.

4.   Frolov V.N. Optimizatsiya planovykh programm pri slabo soglasovannykh ogranicheniyakh [Optimization of planning programs under weakly consistent constraints]. Moscow: Nauka Publ., 1986, 165 p.

5.   Cherkassovskiy B.V. Matrix balancing problems. In: Methods of mathematical programming and software. Sverdlovsk: UrO Akad. Nauk Publ., 1984, pp. 216–217.

6.   Zorkal’tsev V.I. Metod naimen’shikh kvadratov: geometricheskie svoistva, al’ternativnye podkhody, prilozheniya [The Least squares method: geometric properties, alternative approaches, and applications]. Novosibirsk: Nauka Publ., 1995, 220 p. ISBN: 5-02-030676-2 .

7.   Aganbegyan A.G., Granberg A.G. Ekonomiko-matematicheskii analiz mezhotraslevogo balansa SSSR [Economic-mathematical analysis of the interindustry balance of the USSR]. Moscow: Mysl’ Publ., 1968, 357 p.

8.   Kolmogorov A.N., Fomin S.V. Elements of the theory of functions and functional analysis. Mineola; N Y: Dover Publ., 1999, 288 p. ISBN: 0486406830 . Original Russian text published in Kolmogorov A.N., Fomin S.V. Elementy teorii funktsii i funktsional’nogo analiza. Moscow: Nauka Publ., 1968, 544 p.

9.   Samarskii A.A., Gulin A.V. Chislennye metody: Ucheb. posobie dlya vuzov [Numerical methods: the manual for high schools]. Moscow: Nauka Publ., 1989, 432 p. ISBN: 5-02-013996-3 .

10.   Zorkal’tsev V.I. Octahedral and Euclidean projections of a point to a linear manifold. Proc. Steklov Inst. Math., 2014, vol. 284, suppl. 1, pp. 185–197. doi: 10.1134/S0081543814020163 

11.   Rockafellar R. Convex analysis. Princeton: Princeton University Press, 1970, 451 p. ISBN: 0691015864 . Translated to Russian under the title Vypuklyi analiz. Moscow: Mir Publ., 1973, 470 p.

12.   Mudrov V.I., Kushko V.L. Metody obrabotki izmerenii (kvazipravdopodobnye otsenki) [Methods of measurement processing (quasi likelihood estimations)]. Moscow: Sov. Radio Publ., 1976, 192 p.

13.   Mudrov V.I., Kushko V.L. Metody obrabotki izmerenii (kvazipravdopodobnye otsenki) [Methods of measurement processing (quasi likelihood estimations)]. Moscow: Nauka Publ., 1983, 304 p.

14.   Lakeev A.V., Noskov S.I. The least module method for linear regression: the number of zero approximation errors. Modern Technologies, System analysis, Modeling, 2012, no. 2 (34), pp. 48–50 (in Russian).

15.   Chernikov S.N. Lineinye neravenstva [Linear inequalities]. Moscow: Nauka Publ., 1968, 488 p.

16.   Zorkal’tsev V.I. Projecting a point on a polyhedron. Zh. Vychisl. Mat. Mat. Fiz., 2013, vol. 53, no. 1, pp. 4–19 (in Russian). doi: 10.7868/S004446691301016X 

17.   Eremin I.I., Astaf’ev N.N. Vvedenie v teoriyu linejnogo i vypuklogo programmirovaniya [Introduction to the theory of linear and convex programming]. Moscow: Nauka Publ., 1970, 141 p.

18.   Astaf’ev N.I. Lineinye neravenstva i vypuklost’ [Linear inequalities and convexity]. Moscow: Nauka Publ., 1982, 162 p.

19.   Eremin I.I., Mazurov V.D., Astaf’ev N.N. Nesobstvennye zadachi lineinogo i vypuklogo programmirovaniya [Improper problems of linear and convex programming]. Moscow: Nauka Publ., 1983, 336 p.

20.   Chebyshev P.L. Questions on smallest quantities connected with the approximate representation of functions. In: Chebyshev P.L. Collected works, vol. 2. Moscow; Leningrad: Izd. Akad. Nauk SSSR, 1947, pp. 151–235.

21.   Dem’yanov V.F., Malozemov V. N. Introduction to minimax. New York: Dover, 1974, 307 p. ISBN: 0486664236 . Original Russian text published in Dem’yanov V.F., Malozemov V.N. Vvedenie v minimaks. Moscow: Nauka Publ., 1972, 368 p.

22.   Malozemov V.N. The best uniform approximation for functions of several arguments. USSR Computational Mathematics and Mathematical Physics, 1970, vol. 10, no. 3, pp. 28–43. doi: 10.1016/0041-5553(70)90112-6 

23.   Collatz L., Krabs V. Approximation theory. Chebyshev approximations and their applications. Wiesbaden: Springer, 1973, 209 p. doi: 10.1007/978-3-322-94885-4 . (In German). Translated to Russian under the title Teoriya priblizhenii. Chebyshevskie priblizheniya i ikh prilozheniya. Moscow: Nauka Publ., 1978, 269 p.

24.   Haar A. Die Minkowskische Geometrie und die Annaherung an stetige Funktionen. Math. Ann., 1917, vol. 78, no. 1, pp. 294–311. doi: 10.1007/BF01457106 

25.   Zorkal’tsev V.I. Interior Point Method: History and Prospects. Comput. Math. and Math. Phys., 2019, vol. 59, no. 10, pp. 1597–1612. doi: 10.1134/S0965542519100178 

26.   Zorkal’tsev V.I., Kiseleva M.A. Sistemy lineinykh neravenstv (Systems of Linear Inequalities). Irkutsk: Irkutsk Gos. Univ., 2007, 128 p. ISBN: 978-5-9624-0197-3 .

27.   Gubiy E., Zorkal’tsev V.I., Perzhabinskii S.M. Chebyshev and euclidean projections of point on linear manifold. Upravlenie Bol’shimi Sistemami, 2019, vol. 80, pp. 6–19 (in Russian). doi: 10.25728/ubs.2019.80.1 .

28.   Zorkal’tsev V.I. Chebyshev approximations can dispense with the Haare condition. In: Proc. Int. Symp. “Dynamic systems, optimal control and mathematical modelling”, Irkutsk: Irkut. State Univ. Publ., 2019, pp. 29–33.

Cite this article as: V.I. Zorkal’tsev. Chebyshev projections to a linear manifold, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 3, pp. 44–55.