Matrix Correction Minimal with respect to the Euclidean Norm of a Pair of Dual Linear Programming Problems*

Abstract

The paper presents problem formulations, theorems and illustrative numerical examples describing conditions for the existence and a form of solutions 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 optimal 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 minimum matrix correction
• the Euclidean norm

-

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 mn , 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 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 proper and the following conditions   <  = * < , x  X A, b, u U A, c  c  x  u b .

1) X A, b   , U A, c   . In this case both problems are solvable, are called hold true 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 significantly 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tb , tc : X ( A  H , b  tb hb )  , U ( A  H , c tc hc )  ,

H 2  tb hb 2  tc hc 2  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 ,

H   , hb   b , hc   c , x 2  u 2  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 tb 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 ( 1 ) ( 2 ) 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 A0x = b0 , is given, where A0  R mn , b0  R m , b0  0 , a relation between the sizes of A0 , b0 and its rank are not specified, x0  R n is a solution of the system with minimal Euclidean norm (a normal solution). The system A0x = b0 is said to be exact. The numerical values of A0 , b0 and x0 are unknown. an Instead, the approximate matrix A R mn 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 mn has full rank and that the system Ax = b is compatible.

It is required to find a matrix A1  R mn 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 context 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 minimization 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 mn with the minimal Euclidean 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 '' fundamental 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 =  .

Aˆ = bx uv xx  uu

 | | Aˆ | |2 =

 2 x 2  u 2 .

A = Aˆ  A, u  A = 0, Ax = 0. ( 4 ) ( 5 ) ( 6 ) ( 7 )

Corollary 1. If the system is solvable with respect to unknown matrix ..., then all solutions of this system are given by the formula where Aˆ is the matrix with the minimal Euclidean norm defined by ( 4 ), ( 5 ), and A  Rmn is a matrix such that

Moreover, solution Aˆ of the system having the minimal Euclidean norm is unique and is defined as follows

1 2 1  1 Example 1. x = 2 , u = 0 , b =  1 , v =  2 ,  = v  x = u b = 3, 1 1 1  0

  7 2 11 1  

 10 10 10, A = 30  14  4 22 13  22 1  4  4  2 1   1   Aˆ =  5 10 5, A =  1 4 1 .

30  4 16  2 6   2  4 4 Carrying out the calculations, one can verify that the conditions ( 3 ), ( 5 ), ( 6 ) are satisfied.

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 following sections. However, for the sake of shortness, families of matrices are not considered 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 publications 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 norm change (correction) of the vector of the objective function ensuring that a chosen 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 mn with minimal Euclidean norm such that the vectors x, u are the optimal solutions of the linear programming 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.

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 Aˆ of system ( 8 ), having the minimal Euclidean norm (a solution of the problem M A ) is unique and is defined as follows Aˆ = bx ug xx  uu

ux 0, if c j  0 and x j = 0,  xx  uu , where g = g j  R n , g j =  c j , otherwise.

Furthermore, one has

Minimal Matrix Correction of a Pair of Dual Linear Programming Problems 201 ( 8 ) ( 9 ) Aˆ 2 =

 2 x 2  u 2 .

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. 1 2  3 2 0  0 1  1   1  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: C0 x, u, tb , tc : x  X opt A  H , b  tb hb , c  tc hc , u U opt A  H , b  tb hb , c  tc hc ,

H 2  tb hb 2  tc hc 2  min.

Depending on values of parameters tb , tc 0,1, there are four kinds of a problem from the noted set, which we consider separately.

Problem C0 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 mn are given. It is required to find a matrix H  R mn 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.

This problem was firstly considered in work [16] where the problem Z A and theorem 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 satisfied. The solution Hˆ of system ( 10 ), minimal with respect to the Euclidean norm (the solution of the problem C0 x, u,0,0), is unique and is defined by the formula Hˆ = b xAxxx   uug u  x uxx u u , where  =   u  Ax , g = g j R n , g j = 0, if ccAAuujj ot0hearnwdisex. j = 0, ( 11 ) Hˆ 2 = b  Ax 2 x 2  g 2 u 2  2  x 2  u 2 . ( 10 ) ( 12 ) Example 3. x = 11, u = 10, b = 11, c = 13, A =  21  20 01,  = 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 C0 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 mn are given. It is required to find a matrix H  hb  where H  Rmn , hb  Rm 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 Uopt 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ˆb  of system ( 13 ), minimal with respect to the Euclidean norm (the solution of the problem C0 x, u,1,0 ), is unique and is defined by the formula  ˆ H  hˆb  = b xAxxx1 1  uguu    xuxx11uu , where  = u b  u  Ax ,  = ub  cx, and the vector g is defined by ( 11 ). Thus  ˆ H  hˆb  2 = b  Ax 2  x 2 1  g 2  2  u 2  2  x 2 1 u 2 . ( 14 ) Example 4. x = 11, u = 10, b = 11, c = 22, A =  21  20 01, = 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 C0 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 mn are given. It is required to find a matrix  hc  , where H  R mn , hc  R n 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 ) Theorem 6. The matrix  H   hc  , providing the validity of conditions ( 15 ), exists

 Hˆ  for any A , b , c , u , x  0 . The solution   of system ( 15 ), minimal with respect  hˆc  to the Euclidean norm (the solution of the problem C0 x, u,0,1 ), is unique and is defined by the formula where and the vector g is defined by formula ( 11 ). Thus Hhˆˆc  = b  Ax xxx  u1 u gu1  u1 x  x  xuu 1 ,

 = cx  u Ax,  = cx  ub,  Hˆ  2  hˆc   = b  Ax 2  2 x 2  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 b  Ax = 011, c  Au = 102, g = 100, Hˆ =  211 263 111 263 000, hˆc   750 66. Carrying out calculations, we make sure that conditions ( 15 ), ( 18 ) are satisfied. Problem C0 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 A R mn are given. It is required to find: a matrix Hhc 0hb  , where H  R mn , 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 Theorem 7. The matrix  hc

0hb  , providing the validity of conditions ( 19 ), exists for any A , b , c , x , u . The solution  Hˆ  hˆb  of system ( 19 ), minimal  hˆc 0  with respect to the Euclidean norm (the solution of the problem C0 x, u,1,1 ), is unique and is defined by the formula

Minimal Matrix Correction of a Pair of Dual Linear Programming Problems 205  Hˆ   hˆc  hˆb  = b Axx  1  u1g  0  x  x 1 u u 1    ux  1 1 x  x 1u u 1 , where the vector g is defined by formula ( 11 ),  =  =  Hˆ   hˆc  hˆb  = 0  xx  uu 1 2 b  Ax 2  2

x 2 1 0hb   R (m1)(n1) with the minimum Euclidean norm such that vectors ~x   H and u~ are the solutions of problems of the LP problems L  hc  0hb , b~, c~  and   L* Hhc

 0hb , b~, c~  , i.e. such that     H ~x  Xopt   hc 

   H 0hb , b~, c~ , u~ Uopt   hc  

 0hb , b~, c~ .

  The problems C0 x, u,1,1 and M  H

hc to ( 24 ), there are one-to-one correspondences: hb  (~x, u~, b~, c~) are equivalent as, according 0  x   H x  X opt A  H , b  hb , c  hc      X opt   hc 1

 0hb , b~, c~ ,   ( 20 ) ( 21 ) ( 22 ) ( 23 ) ( 25 ) Condition ( 27 ), according to ( 24 ), is equivalent to the following system of conditions

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 Wˆ with the minimum Euclidean norm exists and is unique. It is as follows ~x  X opt W , b~, c~, u~ U opt W , b~, c~.

c~ ~x = b~u~ =  . c x  u  Ax  =     = u  Ax  c x, u b  u  Ax  =    = u  Ax  u b. ( 26 ) ( 27 ) ( 28 ) ( 29 ) ( 30 )

 0hb , b~, c~ .

 

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(m1)(n1) , providing realization of conditions for any given x and u , exists if and only if holds the following condition:  S Wˆ =   q p b~~x u~g~ u~~x

 = ~x~x  u~u~  ~x~x  u~u~ ,   the problem M  H hc hb  (~x, u~, b~, c~) : ~ where S  R mn , 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  T , where the vector g  R n is determined by A , x , u and c in a formulas ( 11 ) and ( 24 ). ~

Using block representations ( 24 ) for the vectors ~x , u~ , b and g~ and block repre hc sentation ( 30 ) for matrix Wˆ , 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 representation, which is necessary for transformation of the matrix Wˆ to the matrix  H 0hb  , guaranteeing the validity of conditions ( 26 ) and being the solution of  =



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 determinant of the system ( 32 ) matrix Q : 0 < detQ = x  x  u u  x  x  u u 1

Solving system ( 32 ), we receive the values of the parameters  ,  ,  corresponding 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ˆc 0hˆb  , which is the solution of the problem M Hhc 0hb  (~x, u~, b~, c~) , and also  Hˆ  1 . x  x  u u 1 means the validity of formulas ( 20 ), ( 23 ), which characterize the specified matrix. And, as the problems C0 x, u,0,1 and M Hhc (x, u~, b~, c~) are equivalent, theorem 7 is 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

  x = 1, u = 0, b =  1, c =  2, A =  2 0 1 1  1  1   4 15 2 5 0  2 15  0  1 1   b  Ax = 1, c  Au =  1, g =  1,  Hˆ  hˆb   1 3 1 3 0 1 3.

1  2  0  hˆcT 0    23155 81 1155 00  7 105 Carrying out calculations, we make sure that the conditions ( 19 ), ( 23 ) are satisfied.

References

1. Kuhn , H.W. , Tucker , A.W. , Dantzig G.B. , Linear inequalities and related systems , Princeton 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 Programming 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 improper 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 Problems , 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 Linear 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 inequalities and the construction of a separating hyperplane. (Russian) Diskretn . Anal. 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 equations 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 Control , 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 Center of RAS , Moscow, 2012 [in Russian].

25. Erokhin , V.I. , Krasnikov , A.S. , Khvostov , M.N. , On sufficient conditions for the solvability 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 Institute 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 Programming 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 Linear 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 Programming 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 Models, the thesis of candidate of physical and mathematical sciences, Borisoglebsk , 2010 [in Russian].