Chebyshev projections to a linear manifold

V. I. Zorkal'tsev

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 26 (2020) no. 3, pp. 44-55

Résumé

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.

Détail

Keywords: lexicographic optimization, linear manifold, Chebyshev and Euclidean norms, Chebyshev projections.
Mots-clés : Haar condition

Bibliographie

[1] Eremin I. I., Protivorechivye modeli ekonomiki, Nauka, Moskva, 1980, 160 pp.

[2] Vatolin A. A., “Ob approksimatsii nesovmestnykh sistem lineinykh uravnenii i neravenstv”, Metody approksimatsii nesobstvennykh zadach matematicheskogo programmirovaniya, Izd-vo UrO AN SSSR, Sverdlovsk, 1984, 39–54 | MR

[3] Louson Ch., Khenson R., Chislennoe reshenie zadach metodom naimenshikh kvadratov, Nauka, Moskva, 1986, 232 pp.

[4] Frolov V. N., Optimizatsiya planovykh programm pri soglasovannykh ogranicheniyakh, Nauka, Moskva, 1986, 165 pp.

[5] Cherkassovskii B. V., “Zadachi balansirovki matrits”, Metody matematicheskogo programmirovaniya i programmnoe obespechenie, Izd-vo UrO AN SSSR, Sverdlovsk, 1984, 216–217

[6] Zorkaltsev V. I., Metod naimenshikh kvadratov: geometricheskie svoistva, alternativnye podkhody, prilozheniya, Nauka, Novosibirsk, 1995, 220 pp.

[7] Aganbegyan A. G., Granberg A. G., Ekonomiko-matematicheskii analiz mezhotraslevogo balansa SSSR, Mysl, Moskva, 1968, 357 pp.

[8] Kolmogorov A. N., Fomin S. V., Elementy teorii funktsii i funktsionalnogo analiza, Nauka, Moskva, 1968, 544 pp.

[9] Samarskii A. A., Gulin A. V., Chislennye metody, ucheb. posobie dlya vuzov, Nauka, Moskva, 1989, 432 pp.

[10] Zorkaltsev V. I., “Oktaedricheskie i evklidovy proektsii tochki na lineinoe mnogoobrazie”, Tr. In-ta matematiki i mekhaniki UrO RAN, 18:3 (2011), 106–118

[11] Rokafellar R., Vypuklyi analiz, Mir, Moskva, 1973, 470 pp.

[12] Mudrov V. I., Kushko V. L., Metody obrabotki izmerenii (kvazipravdopodobnye otsenki), Sov. radio, Moskva, 1976, 192 pp.

[13] Mudrov V. I., Kushko V. L., Metody obrabotki izmerenii: kvazipodobnye otsenki, Nauka, Moskva, 1983, 304 pp.

[14] Lakeev A. V., Noskov S. I., “Metod naimenshikh modulei dlya lineinoi regressii: chislo nulevykh oshibok approksimatsii”, Tr. XV Baikalskoi mezhdun. shkoly-seminara “Metody optimizatsii i ikh prilozheniya”, v. 2, RIO IDSTU SO RAN, Irkutsk, 2011, 117–120

[15] Chernikov S. N., Lineinye neravenstva, Nauka, 1968, 488 pp. | MR

[16] Zorkaltsev V. I., “Proektsii tochki na poliedr”, Zhurn. vychisl. matematiki i mat. fiziki, 53:1 (2013), 4–19 | MR | Zbl

[17] Eremin I. I., Astafev N. I., Vvedenie v teoriyu lineinogo i vypuklogo programmirovaniya, Nauka, Moskva, 1970, 141 pp.

[18] Astafev N. I., Lineinye neravenstva i vypuklost, Nauka, Moskva, 1982, 162 pp.

[19] Eremin I. I., Mazurov V. D., Astafev N. I., Nesobstvennye zadachi lineinogo i vypuklogo programmirovaniya, Nauka, Moskva, 1983, 336 pp.

[20] Chebyshev P. L., “Voprosy o naimenshikh velichinakh, svyazannykh s priblizhennym predstavleniem funktsii”, Polnoe sobranie sochinenii, Izd-vo AN SSSR, Moskva; Leningrad, 1944, 151–235

[21] Demyanov V. F., Malozemov V. N., Vvedenie v minimaks, Nauka, Moskva, 1972, 368 pp. | MR

[22] Malozemov V. N., “Poluchenie ravnomernogo priblizheniya funktsii neskolkikh argumentov”, Zhurn. vychisl. matematiki i mat. fiziki, 1970, no. 3, 575–586 | Zbl

[23] Kollatts L., Krabe V., Teoriya priblizhenii. Chebyshevskie priblizheniya i ikh prilozheniya, Nauka, Moskva, 1978, 269 pp.

[24] Haare A., “Die Minkowskische Geometrie und die Annaherung an stetige Funktionen”, Math. Ann., 78:3 (1918), 415–127 | MR

[25] Zorkaltsev V. I., “Metod vnutrennikh tochek: istoriya i perspektivy”, Zhurn. vychisl. matematiki i mat. fiziki, 59:10 (2019), 1649–1665 | Zbl

[26] Zorkaltsev V. I., Kiseleva M. A., Sistemy lineinykh neravenstv, (ucheb. posobie), Irkut. gos. un-t, Irkutsk, 2007, 128 pp.

[27] Gubii E. V., Zorkaltsev V. I., Perzhabinskii S. M., “Chebyshevskie i evklidovy proektsii tochki na lineinoe mnogoobrazie”, Upravlenie bolshimi sistemami, 80, 2019, 6–19 | MR

[28] Zorkaltsev V. I., “Chebyshevskie priblizheniya mogut obkhoditsya bez usloviya Khaara”, Materialy mezhdun. simpoziuma “Dinamicheskie sistemy, optimalnoe upravlenie i matematicheskoe modelirovanie”, Irkut. gos. un-t., Irkutsk, 2019, 29–33