=Paper=
{{Paper
|id=Vol-1623/papermp7
|storemode=property
|title=Matrix Correction Minimal with respect to the Euclidean
Norm of a Pair of Dual Linear Programming Problems
|pdfUrl=https://ceur-ws.org/Vol-1623/papermp7.pdf
|volume=Vol-1623
|authors=Vladimir Erohin, Alexander Krasnikov,Vladimir Volkov, Mikhail Khvostov
|dblpUrl=https://dblp.org/rec/conf/door/ErohinKVK16
}}
==Matrix Correction Minimal with respect to the Euclidean
Norm of a Pair of Dual Linear Programming Problems==
Matrix Correction Minimal with respect to the Euclidean Norm of a Pair of Dual Linear Programming Problems* V.I. Erokhin1, A.S. Krasnikov2, V.V. Volkov3, M.N. Khvostov3 1 Mozhaisky Military Space Academy, St. Petersburg, Russia erohin_v_i@mail.ru 2 Russian State Social University, Moscow, Russia askrasnikov@gmail.com 3 Borisoglebsk Branch of Voronezh State University, Borisoglebsk, Russia volkov@bsk.vsu.ru, khvostov@bsk.vsu.ru Abstract. The paper presents problem formulations, theorems and illustrative numerical examples describing conditions for the existence and a form of solu- tions of the problem of matrix correction minimal with respect to the Euclidean norm of a pair of dual linear programming (LP) problems. The main results of the paper complement classical duality theory and can serve as a tool to tackle improper LP problems, and/or to ensure the achievement of prespecified opti- mal solutions of the primal and dual problems via the minimal with respect to the Euclidean norm correction of the constraint matrix elements, the right-hand sides of the constraints and the objective functions of the original problems. Keywords: dual pairs of linear programs, improper linear programs, the mini- mum matrix correction, the Euclidean norm. 1 Introduction Consider the pair of dual linear programs (LP) L A, b, c : Ax = b, x 0, c x max, L* A, b, c : u A c , u b min, where A R mn , b, u R m , c, x R n . Let us introduce the notation for the feasible sets, the optimal values and the sets of optimal solutions of the problems above: X A, b x Ax = b, x 0 , U A, c u u A c , sup c x, * inf u b, x X A,b uU A, c X opt A, b, c x X A, b c x = , U opt A, b, c u U A, c u b = * . The most important facts of the classical duality theory for the problems LP (see, e.g., [1-3]) can be formulated in the form of the theorem below. Theorem 1. The solvability or the unsolvability of the problems L A, b, c , L* A, b, c is completely characterized by the following four cases. * The reported study was funded by RFBR according to the research project № 16-31-50016 Copyright © by the paper's authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org Minimal Matrix Correction of a Pair of Dual Linear Programming Problems 197 1) X A, b , U A, c . In this case both problems are solvable, are called proper and the following conditions hold true < = * < , x X A, b, u U A, c c x u b . 2) X A, b , U A, c = . In this case = , both problems are unsolvable, the problem L A, b, c is called an improper problem of the first kind, while the problem L* A, b, c is called an improper problem of the second kind. 3) X A, b = , U A, c . In this case * = , both problems are unsolvable, the problem L A, b, c is called an improper problem of the second kind, while the problem L* A, b, c is called an improper problem of the first kind. 4) X A, b = , U A, c = . In this case, both problems are unsolvable and called an improper problems of the third kind. Suppose that the parameters A, b, c are subject to perturbations which makes the optimal solutions of the problems L A, b, c , L* A, b, c unstable or makes them sig- nificantly different from hypothetical exact solutions or makes the linear programs under consideration improper. In this case, it is reasonable to apply regularization and correction procedures that can be formalized, for example, in the following way. The minimal matrix correction of the pair L A, b, c , L* A, b, c that ensures that these problems are proper: C t b , t c : X ( A H , b t b hb ) , U ( A H , c t c hc ) , 2 2 2 (1) H t b hb t c hc min . The problem of finding the regularized (in the sense of Tikhonov) solutions of the approximate pair of dual linear programs: R , b , c : x X opt A H , b hb , c hc , u U opt A H , b hb , c hc , (2) H , hb b , hc c , 2 2 x u min . From this point onwards, the symbol stands for (depending on the context) the Euclidean norm of a vector or a matrix that in the latter case called the spherical or ... norm, Frobenius's, Schur's or Gilbert-Schmidt's norm (see, for example, [4-6]). The parameters t b and tc in formula (1) can only take values {0, 1}, which results in four different formulations of the problem. The scalar parameters > 0 , b 0 and c 0 , used in formula (2), specify the a priori known estimates of the norms of errors (perturbations) of the objects A , b and c . There is already many works devoted to matrix correction of the systems of the linear algebraic equations (SLAE), inequalities and problems of LP in different norms. One may cosider article [7] as one of the first papers dedicated to the specified problem. In paper [8] linear programming problem with inconsistent system of 198 V.I. Erokhin, A.S. Krasnikov, V.V. Volkov, M.N. Khvostov constraints was considered as a two-criteria problem of initial linaer criteria maximization and minimization with respect to the Euclidean norm of the allowable correction of the extended matrix of restrictions. In article [9] problems of matrices koefficients and extended matrices correction for inconsistent systems of linear algebraic equations and problems of regularization of the corrected systems solutions in arbitrary vector norms were considered. In monograph [10] a systematic description of the methods for solving problems of optimal matrix correction of incosistent systems of linear algebraic equations with optimality criteria based on the Euclidean norm was given. Articles [11-14] and monograph [15] were dedicated to the problems of inconsistent systems of linear algebraic equations matrices correction and linear programming problems with block and more complex structure in various norms. In [16] necessary and sufficient conditions for the existence of a solution of the problem of finding the minimum with respect to the Euclidean norm matrix, resolving a conjugate pair of SLAE and a pair of mutually dual LP problems, were obtained. Papers [17-21] considered the problem of correction of inconsistent systems of linear inequalities (or equations and inequalities), including matrices with a block structure, in various norms. Paper [22] is dedicated to “Correction of Improper Linear Programming Problems in Canonical Form by Applying the Minimax Criterion». In article [23] inverse problems of LP were mentioned in the context of matrix correction of LP problems for the first time. This article also describes a method of matrices vectorization under simultaneous matrix correction of a pair of dual LP problems, which had been published in Russian source, inaccessible for the foreign readers. Monograph [24] was dedicated to the application of the method of matrix correction of inconsistent systems of equations and inequalities to the problems of optimization and classification. In papers [25-27] we investigated the solvability of improper LP problems of the 1st kind, after the minimum with respect to the Euclidean norm matrix correction of their feasible region. This work is concentrated on problems of the matrix correction of a dual pair of linear programming problems, minimum on Euclidean norm, guaranteeing existence of the specified solutions of the primal and dual problem. 2 Matrix correction for solving approximated systems of linear algebraic equations and Tikhonov's "fundamental lemma" Consider the following problem formulated by Tikhonov in 1980. Problem T , [28]. Suppose that the compatible system of a linear algebraic equations (SLAE) of the form A0 x = b0 , is given, where A0 R mn , b0 R m , b0 0 , a relation between the sizes of A0 , b0 and its rank are not specified, x 0 R n is a solution of the system with minimal Euclidean norm (a normal solution). The system A0 x = b0 is said to be exact. The numerical values of A0 , b0 and x 0 are unknown. an Instead, the approximate matrix A R mn and vector b R m , b 0 satisfying the Minimal Matrix Correction of a Pair of Dual Linear Programming Problems 199 following conditions A0 A , b0 b < b are given, where 0 and 0 – are known parameters that cannot be equal to zero simultaneously. In the general case, it is not supposed that the matrix A R mn has full rank and that the system Ax = b is compatible. It is required to find a matrix A1 R mn a vectors b1 R m such that the following conditions are valid: A A1 , b b1 , A1 x1 = b1 , x1 min . The problem T , that was later on called by Tikhonov the regularized method of the least squares (RLS) [29, 30], is interesting for two reasons. Firstly, this problem is one of the first known (mentioned in the literature) problems of matrix correction. Secondly, among the tools for solving this problem, there is an important in the con- text of this article result that was called by Tikhonov "the fundamental lemma". Lemma 1. ("The fundamental lemma")[28]. A system of linear algebraic equations of the form Ax = b is solvable with respect to unknown matrix Ax = b for any x R n , x 0 , b R m . Solution of this system with the minimal Euclidean norm is unique and is given by the formula Aˆ = bx x x , where Aˆ = b x . Lemma 1 allows one to reduce the problem T , to the constrained minimiza- tion problem in R n , the optimal solution of which is the required vector x1 . Other required object A1 and b1 that are interpreted in the context of this article as the result of matrix correction of the matrix A b , are calculated directly via A , b , x1 and . The detailed study of this problem is given in [31], while modern modifications and generalizations are presented in the report [32]. 3 A matrix solution of a dual pair of systems of linear algebraic equations By virtue of Theorem 1, the important ''working'' object that is necessary for the study of a dual pair of linear programs is a pair of dual SLAE. Consider this object and the related problem of matrix correction. Problem Z A ( x, v, u, b) [16]: Suppose that known vectors x, v R n , u, b R m , x, u 0 are given. It is required to find a matrix A R mn with the minimal Euclide- an norm that satisfies the following system of equations Ax = b, u A = v . (3) The above problem can be considered as a generalized of Tikhonov's '' fundamen- tal lemma'' to the case of a pair of dual SLAE. The following theorem describes a solution to this problem. Theorem 2 [16]. Under the condition that x, u 0 , the system (3) is solvable with respect to matrix A if and only if the following condition holds true: u b = v x = . 200 V.I. Erokhin, A.S. Krasnikov, V.V. Volkov, M.N. Khvostov Moreover, solution  of the system having the minimal Euclidean norm is unique and is defined as follows bx uv ux Aˆ = , (4) x x u u x x u u 2 2 b v 2 || Aˆ ||2 = 2 2 2 2 . (5) x u x u Corollary 1. If the system is solvable with respect to unknown matrix ..., then all solutions of this system are given by the formula A = Aˆ A, (6) where  is the matrix with the minimal Euclidean norm defined by (4), (5), and A Rmn is a matrix such that u A = 0, Ax = 0. (7) 1 2 1 1 Example 1. x = 2 , u = 0 , b = 1 , v = 2 , = v x = u b = 3, 1 1 1 0 13 22 1 7 2 11 4 4 2 ˆ 1 1 1 A= 5 10 5 , A = 10 10 10 , A = 1 4 1 . 30 30 22 6 4 16 2 14 4 2 4 4 Carrying out the calculations, one can verify that the conditions (3), (5), (6) are sat- isfied. Remark. Above it was shown that the solution of a pair of dual SLAE of the form (3), in the general case, is a family of matrices given by (6), (7), one of the elements of which is the matrix of the form (3) with the minimal Euclidean norm determined by (5). Similar results hold true for matrix correction problems described in the fol- lowing sections. However, for the sake of shortness, families of matrices are not con- sidered below, and our attention is concentrated on the important elements of these families – matrices (augmented matrices) with the minimum Euclidean norm. 4 The minimal with respect to the Euclidean norm matrix solution of a dual pair of linear programming problems with prespecified optimal solutions In this section, we consider the ''key'' problem that is an inverse LP. The publica- tions on inverse LP are quite rare. As an example, let us mention one of the recent articles [33] that is devoted to the problem of minimal with respect to the Euclidean Minimal Matrix Correction of a Pair of Dual Linear Programming Problems 201 norm change (correction) of the vector of the objective function ensuring that a cho- sen vector from the feasible set of LP is an optimal solution. The problem that we study below is an inverse problem in the sense that prespecifed optimal solutions of the primal and dual LP are the input data of this problem, while the constraint matrix is thought to be unknown. Problem M A ( x, v, u, b) [34]: Suppose that known vectors x, c R n , u, b R m , x, u 0 , x 0 are given. It is required to find a matrix A R mn with minimal Eu- clidean norm such that the vectors x, u are the optimal solutions of the linear pro- gramming problems L A, b, c and L* A, b, c , i.e. such that x X opt A, b, c, u U opt A, b, c . (8) A solution of the above problem is described in the following result. Theorem 3 [34]. A matrix A satisfying the conditions (8) for prespecified x , u 0 exists if and only if the following condition is valid c x = u b = . Solution  of system (8), having the minimal Euclidean norm (a solution of the problem M A ) is unique and is defined as follows bx ug ux 0, if c j 0 and x j = 0, Aˆ = x x u u , where g = g j R n , g j = c j , otherwise. x x u u Furthermore, one has 2 2 2b g 2 Aˆ = 2 2 2 2 . (9) x u x u Example 2. 1 1 1 1 1 1 2 3 2 0 ˆ x = 1, u = 0, b = 1, c = 3, g = 3, = 2, A = 1 2 1 2 0 . 0 1 1 1 0 1 2 3 2 0 Carrying out calculation, one can check that the conditions (8)-(9) are valid. 5 The matrix correction of dual pair of linear programming problems with the specified optimal solutions, minimal on Euclidean norm In this section we consider the set of problems of the minimal matrix correction of the pair L A, b, c , L* A, b, c of LP dual problems, which guarantee accessory of the given vectors x R n , u R m to the sets of optimal solutions of the corrected LP problems: 202 V.I. Erokhin, A.S. Krasnikov, V.V. Volkov, M.N. Khvostov C 0 x, u, t b , t c : x X opt A H , b t b hb , c t c hc , u U opt A H , b t b hb , c t c hc , 2 2 2 H t b hb t c hc min . Depending on values of parameters t b , t c 0,1 , there are four kinds of a problem from the noted set, which we consider separately. Problem C 0 x, u,0,0 : Suppose known vectors x, c R n , u, b R m , x, u 0 , x 0 , and known matrix A R mn are given. It is required to find a matrix H R mn with the minimum Euclidean norm such that the vectors x, u are the solutions of the problems of linear programming L A H , b, c and L* A H , b, c , i.e. such that x X opt A H , b, c, u U opt A H , b, c . (10) This problem was firstly considered in work [16] where the problem Z A and theo- rem 2 were used as research instruments. Later in work [34], using the problem M A and theorem 3, the calculations were significantly simplified, and the received result was strengthened. Theorem 4 [16, 34]. The matrix H , providing the validity of conditions (10) at the known vectors x , u 0 , exists if and only if the condition c x = u b = is satis- fied. The solution Ĥ of system (10), minimal with respect to the Euclidean norm (the solution of the problem C 0 x, u,0,0 ), is unique and is defined by the formula Hˆ = b Ax x ug ux , where = u Ax , x x u u x x u u g = g j Rn , g j = 0, if c A u j 0 and x j = 0, c A u j otherwise. (11) Hˆ 2 = b Ax 2 x 2 g 2 u 2 2 x u . 2 2 (12) 1 1 1 1 1 2 0 Example 3. x = 1, u = 0, b = 1, c = 3, A = 2 0 1, = 2, 0 1 1 1 1 1 1 0 1 1 1 4 1 4 0 ˆ = 1, b Ax = 1, c A u = 0, g = 0, H = 1 2 1 2 0 . 1 2 0 3 4 1 4 0 Carrying out calculations, we make sure that conditions (10), (12) are satisfied. Problem C 0 x, u,1,0 [34]: Suppose known vectors x, c R n , u, b R m , x, u 0 , x 0 , and a known matrix A R mn are given. It is required to find a matrix H hb where H R mn , hb R m with the minimum Euclidean norm such that Minimal Matrix Correction of a Pair of Dual Linear Programming Problems 203 the vectors x, u are the solutions of problems of the LP problems L A H , b hb , c and L* A H , b hb , c , i.e. such that x X opt A H , b hb , c , u U opt A H , b hb , c . (13) Theorem 5 [34]. The matrix H hb , providing the validity of conditions (13), exists for any A , b , c , x , u 0 . The solution Hˆ hˆ of system (13), minimal b with respect to the Euclidean norm (the solution of the problem C 0 x, u,1,0 ), is unique and is defined by the formula Hˆ hˆ = b xAxxx 1 1 ugu u x uxx 11u u , b where = u b u Ax , = u b c x, and the vector g is defined by (11). Thus Hˆ hˆ = b Ax x 1 g u x 1 u . b 2 2 2 2 2 2 2 2 2 (14) 1 1 1 2 1 2 0 Example 4. x = 1, u = 0, b = 1 , c = 2, A = 2 0 1, = 1, 0 1 1 1 1 1 1 0 0 0 1 6 2 3 0 5 6 = 2, b Ax = 1, c A u = 1, g = 1, Hˆ = 1 3 1 3 0 , hˆb = 1 3 . 1 2 0 1 6 1 3 0 5 6 Carrying out calculations, we make sure that the conditions (13)-(14) are satisfied. Problem C 0 x, u,0,1 . This problem is considered for the first time. Suppose known vectors x, c R n , u, b R m , x, u 0 , x 0 , and a known matrix H A R mn are given. It is required to find a matrix , where H R mn , hc R n hc with the minimum Euclidean norm such that the vectors x, u are the solutions of the LP problems L A H , b, c hc and L* A H , b, c hc , i.e. such that x X opt A H , b, c hc , u U opt A H , b, c hc . (15) H Theorem 6. The matrix , providing the validity of conditions (15), exists hc Hˆ for any A , b , c , u , x 0 . The solution of system (15), minimal with respect ˆ hc 204 V.I. Erokhin, A.S. Krasnikov, V.V. Volkov, M.N. Khvostov to the Euclidean norm (the solution of the problem C 0 x, u,0,1 ), is unique and is de- fined by the formula Hˆ b Ax x u g u x ˆ = 1 , (16) hc x x 1 u u 1 x x u u 1 where = c x u Ax, = c x u b, (17) and the vector g is defined by formula (11). Thus 2 2 2 2 Hˆ b Ax g 2 ˆ hc = x 2 u 2 1 2 x u 2 . 1 (18) Due to the article volume limitation, theorem 6 is presented without proof. 1 1 1 2 1 2 0 Example 5. x = 1, u = 0, b = 1, c = 2, A = 2 0 1, = 1, = 2, 0 1 1 1 1 1 1 0 0 0 1 6 1 6 0 5 6 b Ax = 1, c A u = 1 , g = 1, Hˆ = 1 2 1 2 0 , hˆc 7 6. 1 2 0 2 3 1 3 0 0 Carrying out calculations, we make sure that conditions (15), (18) are satisfied. Problem C 0 x, u,1,1 . This problem is considered for the first time. Suppose known vectors x, c R n , u, b R m , x, u 0 , x 0 , and a known matrix H hb A R mn are given. It is required to find: a matrix , where H R mn , hc 0 hb R m , hc R n with the minimum Euclidean norm such that the vectors x, u are the solutions of problems of the LP problems L A H , b hb , c hc and L* A H , b hb , c hc , i.e. such that x X opt A H , b hb , c hc , u U opt A H , b hb , c hc . (19) H hb Theorem 7. The matrix 0 , providing the validity of conditions (19), hc Hˆ hˆb exists for any A , b , c , x , u . The solution of system (19), minimal ˆ hc 0 with respect to the Euclidean norm (the solution of the problem C 0 x, u,1,1 ), is unique and is defined by the formula Minimal Matrix Correction of a Pair of Dual Linear Programming Problems 205 b Ax u x 1 g u 1 x 1 Hˆ hb ˆ 1 ˆ = , (20) hc 0 x x 1 u u 1 x x 1 u u 1 where the vector g is defined by formula (11), = x x 1 c u A x u u 1 u b Ax , (21) x x u u 1 x x u u 1 c x u u u b x x u Ax = , = c x , = u b , (22) x x u u 1 2 Hˆ hˆb 2 2 2 2 b Ax g 2 ˆ hc 0 = x 2 1 u 2 1 x 1 u 1. 2 2 (23) ~ Proof. Consider the problem M H hb (~ x , u~, b , c~) , which is a modification of the hc 0 problem M A ( x, u, b, c) : Suppose known vectors x, c R n , u, b R m , x 0 , x 0 , ~ and a known matrix A R mn are given and the vectors ~ x , u~ , b and c~ are con- structed as follows u x ~ b Ax c A u u~ = R m 1 , ~ x = R n 1 , b = R m 1 ~ , c = n 1 R , (24) 1 1 Here , R are some parameters. It is required to find a matrix H hb h R ( m 1)( n 1) with the minimum Euclidean norm such that vectors ~ 0 x c H hb ~ ~ and u~ are the solutions of problems of the LP problems L , b , c and hc 0 H hb ~ ~ L* , b , c , i.e. such that hc 0 H hb ~ ~ ~ H hb ~ ~ x X opt ~ , b , c , u U opt , b , c . 0 0 (25) hc hc ~ The problems C 0 x, u,1,1 and M H hb ( ~x , u~, b , c~) are equivalent as, according hc 0 to (24), there are one-to-one correspondences: x H hb ~ ~ x X opt A H , b hb , c hc X opt , b , c , 1 hc 0 206 V.I. Erokhin, A.S. Krasnikov, V.V. Volkov, M.N. Khvostov u H hb ~ ~ u U opt A H , b hb , c hc U opt , b , c . 1 hc 0 Let us note that the condition u~ 0 is carried out for any u and, including the case u = 0 ,as a result of (24) and the condition ~x 0 is carried out for any x , including the case x = 0 , as a result of (24). A Taking in account this remark and theorem 3, we get that the matrix W R ( m1)( n 1) , providing realization of conditions ~ ~ ~ x X opt W , b , c~ , u~ U opt W , b , c~ . (26) for any given x and u , exists if and only if holds the following condition: ~ c~ ~ x = b u~ = . (27) Condition (27), according to (24), is equivalent to the following system of conditions c x u Ax = = u Ax c x, (28) u b u Ax = = u Ax u b. (29) The system contains two undefined parameters and . With the suitable choice of values of the specified parameters it is possible to satisfy condition (27) for any A , x , u , b and c . Thus, according to theorem 3, the matrix W providing performance of conditions (26) exists for any A , x , u , b and c . Also, owing to theorem 3, for any A , x , u , b and c the corresponding matrix Ŵ with the minimum Euclidean norm exists and is unique. It is as follows ~ ~~ S p b ~ x ug u~~ x Wˆ = ~ ~ ~ ~ = ~ , (30) q x x u u x ~ x u~ u~ ~ where S R mn , p R m , q R n , R , the vectors ~ x , u~ and b are determined by A , x , u , b and c in formulas (24), and the vector g~ R n 1 is defined as g~ = g , where the vector g R n is determined by A , x , u and c in a T formulas (11) and (24). ~ Using block representations (24) for the vectors ~ x , u~ , b and g~ and block repre- sentation (30) for matrix Ŵ , it is possible to gain a representation for the parameter in terms of A , x , u , b and c and the condition = 0 , following from this rep- resentation, which is necessary for transformation of the matrix Ŵ to the matrix H hb h , guaranteeing the validity of conditions (26) and being the solution of c 0 ~ the problem M H hb (~ x , u~, b , c~) : hc 0 Minimal Matrix Correction of a Pair of Dual Linear Programming Problems 207 = x x 1 u u 1 = 0. (31) x x 1 u u 1 The system of conditions (28), (29), (31) represents the linear algebraic equations system, concerning the variables , , which can be written down in the follow- ing vector-matrix form: u Ax u b 1 0 1 0 1 1 = u Ax c x . (32) ( x x 1)1 (u u 1)1 ( x x 1)1 (u u 1)1 0 The solution of system (32) exists and is unique for any x , u , such that x < , u < . It is possible to check this statement, analyzing the range of values of de- x x u u 1 terminant of the system (32) matrix Q : 0 < det Q = 1. x x u u x x u u 1 Solving system (32), we receive the values of the parameters , , corre- sponding to formulas (21)-(22). By virtue of the calculations given above the existence and the uniqueness of the decision of system (32) means the existence and the uniqueness of the matrix Hˆ hˆb ~ ~ ~ ~ ˆ , which is the solution of the problem M H hb ( x , u , b , c ) , and also hc 0 hc 0 means the validity of formulas (20), (23), which characterize the specified matrix. And, as the problems C 0 x, u,0,1 and M H ( x, u~, b , c~) are equivalent, theorem 7 is ~ hc fair, and this theorem describes the conditions of resolvability of the problem C0 x, u,1,1 and the type of its solution. Example 6. 7 5 , 2 5 , 3 5 , = 3 5 , 1 1 1 1 1 2 0 x = 1, u = 0, b = 1, c = 2, A = 2 0 1, 0 1 1 1 1 1 1 4 15 2 5 0 2 15 0 1 1 ˆ ˆ hb 1 3 1 3 0 1 3 b Ax = 1, c A u = 1, g = 1, T H . hˆc 0 3 5 1 15 0 7 15 1 2 0 2 15 8 15 0 0 Carrying out calculations, we make sure that the conditions (19), (23) are satisfied. 208 V.I. Erokhin, A.S. Krasnikov, V.V. Volkov, M.N. Khvostov References 1. Kuhn, H.W., Tucker, A.W., Dantzig G.B., Linear inequalities and related systems, Prince- ton university press, No. 38 (1956). 2. Vasil’ev, F.P. and Ivanitskii, A.Yu., Linear Programming, Faktorial Press, Moscow, 2008 [in Russian]. 3. Eremin, I.I., Mazurov, V.D., and Astaf’ev, N.N., Improper Problems of Linear and Convex Programming, Nauka, Moscow, 1983 [in Russian]. 4. Gantmaher, F.R., The Theory of Matrices, FIZMATLIT, Moscow, 2010 [in Russian]. 5. Voevodin, V.V., Kuznecov, Ju. A., Matrices and Computations, Nauka, Moscow, 1984 [in Russian]. 6. Horn, R.A., Johnson, C.R., Matrix Analysis, Cambridge University Press, 1986. 7. Vatolin, A.A., Approximation of Improper Linear Programming Problems in Accordance with Criteria of the Euclidean Norm, Zh. Vychisl. Mat. Mat Fiz., 24, No. 12, 1907–1908 (1984) [in Russian]. 8. Gorelik, V.A., Matrix Correction of a Linear Programming Problem with Inconsistent Constraints, Comput. Math. Math. Phys., 41, No. 11, 1615-1622 (2001). 9. Erokhin, V.I., Optimal matrix correction and regularization of inconsistent linear models, Diskretn. Anal. Issled. Oper., Ser. 2, 9, No.2, 41-77 (2002) [in Russian]. 10. Gorelik, V.A., Erohin, V.I., Optimal matrix correction of inconsistency systems of linear algebraic equations to minimum Euclidean norm, Dorodnicyn Computing Center of RAS, Moscow, 2004 [in Russian]. 11. Gorelik, V.A., Erokhin, V.I., Pechenkin, R.V. Optimal Matrix Correction of Incompatible Systems of Linear Algebraic Equations with Block Matrices of Coefficients, Diskretn. Anal. Issled. Oper., Ser. 2, 12, No. 2, 3-23 (2005) [in Russian]. 12. Gorelik, V.A., Erokhin, V.I., Pechenkin, R.V., Minimax matrix correction of inconsistent systems of linear algebraic equations with block matrices of coefficients, J. Comp. Syst. Sci. Int., 45, No. 5, 727-737 (2006). 13. Gorelik, V.A., Zoltoeva, I.A., Pechenkin, R.V., Correction methods for incompatible linear systems with sparse matrices. Diskretn. Anal. Issled. Oper., Ser. 2, 14, No. 2, 62-75 (2007) [in Russian]. 14. Erokhin, V.I., Krasnikov, A.S., Matrix Correction of a Dual Pair of Improper Linear Pro- gramming Problems with a Block Structure, Comput. Math. Math. Phys., 48, No. 1, 76–84 (2008). 15. Gorelik, V.A., Erohin, V.I., Pechenkin, R.V., Numerical methods for correction of im- proper linear programming problems and structural systems of equations, Dorodnicyn Computing Center of RAS, Moscow, 2006 [in Russian]. 16. Erokhin, V.I., Matrix Correction of a Dual Pair of Improper Linear Programming Prob- lems, Comput. Math. Math. Phys., 47, No. 4, 564–578 (2007). 17. Murav’eva, O.V., Robustness and Correction of Linear Models, Automation and Remote Control, 72, No. 3, 556–569 (2011). 18. Le, N.D., Decomposition Method in Correction Problems for Inconsistent Systems of Lin- ear Inequalities with Partitioned Matrices, Comput. Math. Math. Phys., 51, No. 10, 1685– 1694 (2011). 19. Le, N.D., Correction of Inconsistent Systems of Linear Inequalities with Block Matrices by Minimax Criterion, Moscow University Computational Mathematics and Cybernetics, 35, No. 4, 167–175 (2011). 20. Murav’eva, O.V., Study of the parametric stability of the solutions of systems of linear in- equalities and the construction of a separating hyperplane. (Russian) Diskretn. Anal. Minimal Matrix Correction of a Pair of Dual Linear Programming Problems 209 Issled. Oper. 21 (2014), no. 3, 53--63, 108; translation in J. Appl. Ind. Math. 8, No. 3, 349– 356 (2014). 21. Murav’eva, O.V.,Consistency and inconsistency radii for solving systems of linear equa- tions and inequalities, Comput. Math. Math. Phys., 55, No. 3, 366–377 (2015). 22. Barkalova, O.S., Correction of Improper Linear Programming Problems in Canonical Form by Applying the Minimax Criterion, Comput. Math. Math. Phys., 52, No. 12, 1624– 1634 (2012). 23. Erokhin, V.I., Krasnikov, A.S., Khvostov, M.N., Matrix Corrections Minimal with Respect to the Euclidean Norm for Linear Programming Problems, Automation and Remote Con- trol, 73, No. 2, 219–231 (2012). 24. Gorelik, V.A., Murav'eva, O.V., Methods of Correction of Improper Problems and their Application to Problems of Optimization and Classification), Dorodnicyn Computing Cen- ter of RAS, Moscow, 2012 [in Russian]. 25. Erokhin, V.I., Krasnikov, A.S., Khvostov, M.N., On sufficient conditions for the solvabil- ity of linear programming for matrix correction of the system of constraints, Proceedings of the Institute of Mathematics and Mechanics, Ural Branch of the RAS, 19, No. 2, 144– 156 (2013) [in Russian]. 26. Erokhin, V.I., On some sufficient conditions for the solvability and insolvability of matrix correction problems for improper linear programming problems, Proceedings of the Insti- tute of Mathematics and Mechanics, Ural Branch of the RAS, 21, No. 3, 110–116 (2015) [in Russian]. 27. Khvostov, M.N., On Sufficient Conditions for the Solvability of Improper Linear Pro- gramming of the First Kind with Minimal Weighted Euclidean Norm for Structural Matrix Correction of the Feasible Region, Proceedings of Voronezh State University. Series: Physics. Mathematics, No. 2, 150–167 (2015) [in Russian]. 28. Tikhonov, A.N., On approximate systems of linear algebraic equations, Zh. Vychisl. Mat. Mat Fiz., 20, No. 6, 1373–1383 (1980) [in Russian]. 29. Tikhonov, A.N., About automation methods of experimental observation processing, Akademiia Nauk SSSR, Vestnik, No. 1, 14–25 (1983) [in Russian]. 30. Tihonov, A.N., Arsenin, V.Ja., Methods for Solving ill-posed Problems, Nauka, Moscow, 1986 [in Russian]. 31. Volkov, V.V., Erokhin, V.I., Tikhonov Solutions of Approximately Given Systems of Lin- ear Algebraic Equations under Finite Perturbations of Their Matrices, Comput. Math. Math. Phys., 50, No. 4, 589–605 (2010). 32. Erohin, V.I., Volkov, V.V., Generalizations of A.N. Tikhonov regularized least squares, Seminar on Constructive Nonsmooth Analysis and Nondifferentiable Optimization «CNSA & NDO», 2014,URL: http://www.aphmath.spbu.ru/cnsa/pdf/2014/ Erochin_Volkov.pdf [in Russian]. 33. Amirkhanova, G.A., Golikov, A.I., Evtushenko, Yu. G., On an Inverse Linear Program- ming Problem, Proceedings of the Institute of Mathematics and Mechanics, Ural Branch of the RAS, 21, No. 3, 13–19 (2015) [in Russian]. 34. Krasnikov, A.S., Matrix Correction of Conflicting Data in the Linear Optimization Mod- els, the thesis of candidate of physical and mathematical sciences, Borisoglebsk, 2010 [in Russian].