Geodesic
Minimum-Euclidean-norm matrix correction for a pair of dual linear programming problems
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 57 (2017) no. 11, pp. 1788-1803 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

For a pair of dual (possibly improper) linear programming problems, a family of matrix corrections is studied that ensure the existence of given solutions to these problems. The case of correcting the coefficient matrix and three cases of correcting an augmented coefficient matrix (obtained by adding the right-hand side vector of the primal problem, the right-hand-side vector of the dual problem, or both vectors) are considered. Necessary and sufficient conditions for the existence of a solution to the indicated problems, its uniqueness is proved, and the form of matrices for the solution with a minimum Euclidean norm is presented. Numerical examples are given. 
@article{ZVMMF_2017_57_11_a3,
     author = {V. V. Volkov and V. I. Erokhin and A. S. Krasnikov and A. V. Razumov and M. N. Khvostov},
     title = {Minimum-Euclidean-norm matrix correction for a pair of dual linear programming problems},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1788--1803},
     year = {2017},
     volume = {57},
     number = {11},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_11_a3/}
}
TY  - JOUR
AU  - V. V. Volkov
AU  - V. I. Erokhin
AU  - A. S. Krasnikov
AU  - A. V. Razumov
AU  - M. N. Khvostov
TI  - Minimum-Euclidean-norm matrix correction for a pair of dual linear programming problems
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2017
SP  - 1788
EP  - 1803
VL  - 57
IS  - 11
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_11_a3/
LA  - ru
ID  - ZVMMF_2017_57_11_a3
ER  - 
%0 Journal Article
%A V. V. Volkov
%A V. I. Erokhin
%A A. S. Krasnikov
%A A. V. Razumov
%A M. N. Khvostov
%T Minimum-Euclidean-norm matrix correction for a pair of dual linear programming problems
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2017
%P 1788-1803
%V 57
%N 11
%U http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_11_a3/
%G ru
%F ZVMMF_2017_57_11_a3
V. V. Volkov; V. I. Erokhin; A. S. Krasnikov; A. V. Razumov; M. N. Khvostov. Minimum-Euclidean-norm matrix correction for a pair of dual linear programming problems. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 57 (2017) no. 11, pp. 1788-1803. http://geodesic.mathdoc.fr/item/ZVMMF_2017_57_11_a3/

[1] Vaida S., “Teoriya igr i lineinoe programmirovanie”, Lineinye neravenstva i smezhnye voprosy, Cb. perevodov pod red. L.V. Kantorovicha i V.V. Novozhilovoi, eds. G.U. Kun, A.U. Takker, IL, M., 1959, 469 pp.

[2] Vasilev F. P., Ivanitskii A. Yu., Lineinoe programmirovanie, Faktorial Press, M., 2008, 328 pp. | MR

[3] Eremin I. I., Mazurov V. D., Astafev N. N., Nesobstvennye zadachi lineinogo i vypuklogo programmirovaniya, Nauka, M., 1983, 336 pp. | MR

[4] Gantmakher F. R., Teoriya matrits, Fizmatlit, M., 2010, 560 pp. | MR

[5] Voevodin V. V., Kuznetsov A. Yu., Matritsy i vychisleniya, Nauka, M., 1984, 320 pp. | MR

[6] Khorn R., Dzhonson Ch., Matrichnyi analiz, Mir, M., 1989, 655 pp. | MR

[7] Vatolin A. A., “Approksimatsiya nesobstvennykh zadach lineinogo programmirovaniya po kriteriyu evklidovoi normy”, Zh. vychisl. matem. i matem. fiz., 24:12 (1984), 1907–1908 | MR

[8] Tikhonov A. N., “O priblizhennykh sistemakh lineinykh algebraicheskikh uravnenii”, Zh. vychisl. matem. i matem. fiz., 20:6 (1980), 1373–1383 | MR

[9] Tikhonov A. N., “O metodakh avtomatizatsii obrabotki nablyudenii”, Vestn. AN SSSR, 1983, no. 1, 14–25

[10] Tikhonov A. N., Arsenin V. Ya., Metody resheniya nekorrektnykh zadach, Nauka, M., 1986, 288 pp. | MR

[11] Van Huffel S., Vandewalle J., The total least squares problem: computational aspects and analysis, Home frontiers in applied mathematics, 9, Siam, 1991, 300 pp. | MR

[12] Volkov V. V., Erokhin V. I., “O tikhonovskikh resheniyakh priblizhennykh sistem lineinykh algebraicheskikh uravnenii pri konechnykh vozmuscheniyakh ikh matrits”, Zh. vychisl. matem. i matem. fiz., 50:4 (2010), 618–635 | MR

[13] Erokhin V. I., Volkov V. V., “Obobscheniya regulyarizovannogo metoda naimenshikh kvadratov A. N. Tikhonova”, Seminar “CNSA NDO”. Izbr. dokl. (16 oktyabrya 2014 g.) http://www.apmath.spbu.ru/cnsa/pdf/2014/Erochin_Volkov.pdf

[14] Gorelik V. A., “Matrichnaya korrektsiya zadachi lineinogo programmirovaniya s nesovmestnoi sistemoi ogranichenii”, Zh. vychisl. matem. i matem. fiz., 41:11 (2001), 1697–1705 | MR

[15] Amaral P., Barahona P., “Connections between the total least squares and the correction of an infeasible system of linear inequalities”, Linear Algebra and its Applications, 395 (2005), 191–210 | DOI | MR

[16] Erokhin V. I., “Optimalnaya matrichnaya korrektsiya i regulyarizatsiya nesovmestnykh lineinykh modelei”, Diskretnyi analiz i issled. oper. Ser. 2, 9:2 (2002), 41–77 | MR

[17] Gorelik V. A., Erokhin V. I., Optimalnaya matrichnaya korrektsiya nesovmestnykh sistem lineinykh algebraicheskikh uravnenii po minimumu evklidovoi normy, VTs RAN, M., 2004, 193 pp. | MR

[18] Amaral P., Judice J., Sherali H. D., “A reformulation-linearization-convexification algorithm for optimal correction of an inconsistent system of linear constraints”, Computers Operat. Research, 35 (2008), 14941509 | MR

[19] Muraveva O. V., “Vozmuschenie i korrektsiya sistem lineinykh neravenstv”, UBS, 28 (2010), 40–57

[20] Muraveva O. V., “Robastnost i korrektsiya lineinykh modelei”, Avtomatika i telemekhan, 2011, no. 3, 98–112 | MR

[21] Le Nyat Zyui, “Metod dekompozitsii v zadachakh korrektsii nesovmestnykh sistem lineinykh neravenstv s matritsami blochnoi struktury”, Zh. vychisl. matem. i matem. fiz., 51:10 (2011), 1796–1805 | MR

[22] Le Nyat Zyui, “Korrektsiya nesovmestnykh sistem lineinykh neravenstv s matritsami blochnoi struktury po minimaksnomu kriteriyu”, Vestn. MGU. Ser. 15. Vychisl. matem. i kibernetika, 2011, no. 4, 18–25

[23] Muraveva O. V., “Issledovanie parametricheskoi ustoichivosti reshenii sistem lineinykh neravenstv i postroenie razdelyayuschei giperploskosti”, Diskretnyi analiz i issled. oper., 21:3 (2014), 53–63 | MR

[24] Muraveva O. V., “Radiusy sovmestnosti i nesovmestnosti sistem lineinykh uravnenii i neravenstv”, Zh. vychisl. matem. i matem. fiz., 55:3 (2015), 372–384 | DOI | MR

[25] Erokhin V. I., “Matrichnaya korrektsiya nesobstvennykh zadach lineinogo programmirovaniya po minimumu evklidovoi normy s proizvolnymi vesami i fiksirovannymi elementami”, Tr. XIII Baikalskoi mezhd. shk.-sem. “Metody optimizatsii i ikh prilozheniya”, v. 1, Izd-vo ISEM SO RAN, Irkutsk, 2005, 105–110

[26] Gorelik V. A., Erokhin V. I., Pechenkin R. V., “Optimalnaya matrichnaya korrektsiya nesovmestnykh sistem lineinykh algebraicheskikh uravnenii s blochnymi matritsami koeffitsientov”, Diskretnyi analiz i issled. oper. Ser. 2, 12:2 (2005), 3–22 | MR

[27] Gorelik V. A., Erokhin V. I., Pechenkin R. V., “Minimaksnaya matrichnaya korrektsiya nesovmestimykh sistem lineinykh algebraicheskikh uravnenii s blochnymi matritsami koeffitsientov”, Izv. RAN. TISU, 2006, no. 5, 52–62

[28] Gorelik V. A., Zoltoeva I. A., Pechenkin R. V., “Metody korrektsii nesovmestnykh lineinykh sistem s razrezhennymi matritsami”, Diskretnyi analiz i issled. oper., 14:2 (2007), 62–75 | MR

[29] Gorelik V. A., Erokhin V. I., Pechenkin R. V., Chislennye metody korrektsii nesobstvennykh zadach lineinogo programmirovaniya i strukturnykh sistem uravnenii, VTs RAN, M., 2006, 153 pp. | MR

[30] Amaral P., Fernandes L. M., Shcrali H. D., “On optimal zero-preserving corrections for inconsistent linear systems”, J. Glob. Optim., 45:4 (2009), 645–666 | DOI | MR

[31] Erokhin V. I., “Matrichnaya korrektsiya dvoistvennoi pary nesobstvennykh zadach lineinogo programmirovaniya”, Zh. vychisl. matem. i matem. fiz., 47:4 (2007), 587–601 | MR

[32] Erokhin V. I., Krasnikov A. S., “Matrichnaya korrektsiya dvoistvennoi pary nesobstvennykh zadach lineinogo programmirovaniya s blochnoi strukturoi”, Zh. vychisl. matem. i matem. fiz., 48:1 (2008), 80–89 | MR

[33] Barkalova O. S., “Korrektsiya nesobstvennykh zadach lineinogo programmirovaniya v kanonicheskoi forme po minimaksnomu kriteriyu”, Zh. vychisl. matem. i matem. fiz., 52:12 (2012), 2178–2189 | MR

[34] Gorelik V. A., Muraveva O. V., Metody korrektsii nesobstvennykh zadach i ikh primenenie k problemam optimizatsii i klassifikatsii, VTs RAN, M., 2012, 148 pp.

[35] Erokhin V. I., Krasnikov A. S., Khvostov M. N., “Minimalnye po evklidovoi norme matrichnye korrektsii zadach lineinogo programmirovaniya”, Avtomat. i telemekhan., 2012, no. 2, 11–24 | MR

[36] Erokhin V. I., Krasnikov A. S., Khvostov M. N., “O dostatochnykh usloviyakh razreshimosti zadach lineinogo programmirovaniya pri matrichnoi korrektsii ikh ogranichenii”, Tr. IMM UrO RAN, 19, no. 2, 2013, 144–156

[37] Erokhin V. I., Krasnikov A. S., Khvostov M. N., “Kvazinyutonovskie algoritmy matrichnoi korrektsii nesobstvennykh zadach lineinogo programmirovaniya s proizvolnym mnozhestvom korrektiruemykh koeffitsientov”, Izv. SPbGTI(TU), 2014, no. 23(43), 87–92

[38] Erokhin V. I., “O nekotorykh dostatochnykh usloviyakh razreshimosti i nerazreshimosti zadach matrichnoi korrektsii nesobstvennykh zadach lineinogo programmirovaniya”, Tr. IMM UrO RAN, 21, no. 3, 2015, 110–116 | MR

[39] Khvostov M. N., “O dostatochnykh usloviyakh razreshimosti nesobstvennykh zadach LP 1-go roda posle matrichnoi korrektsii ikh dopustimoi oblasti po minimumu vzveshennoi evklidovoi normy s uchetom strukturnykh ogranichenii”, Vestn. VGU. Ser.: Fizika. Matematika, 2015, no. 2, 150–167

[40] Erokhin V., Krasnikov A., Volkov V., Khostov M., “Matrix correction minimal with respect to the euclidean norm of a pair of dual linear programming problems”, Proc. DOOR 2016 (Vladivostok, Russia, September 19–23, 2016), CEUR-WS, 1623, 2016, 196–209 http://ceur-ws.org/Vol-1623/papermp7.pdf

[41] Amirkhanova G. A., Golikov A. I., Evtushenko Yu. G., “Ob odnoi obratnoi zadache lineinogo programmirovaniya”, Tr. IMM UrO RAN, 21, no. 3, 2015, 13–19 | MR

[42] Krasnikov A. S., Matrichnaya korrektsiya protivorechivykh dannykh v lineinykh optimizatsionnykh modelyakh, Diss. ... kand. fiz.-matem. nauk: 05.13.17, Borisoglebsk, 2010