A ¼
c
T
Àδ
T
ÀB 0
0
B
T
ÀI
0
0
ÀI
2
6
6
6
6
6
6
4
3
7
7
7
7
7
7
5
, b ¼
0
Àδ
c
0
0
2
6
6
6
6
6
6
4
3
7
7
7
7
7
7
5
ð38:12Þ
Hence, from the above result it holds that solving a pair of feasible (consistent)
primal-dual linear programs is equivalent with solving a certain system of linear
inequalities. According to Theorem 5.1, page 181 in Andrei (2011), there are two
more possible cases that can occur beside the feasible one: one of the problem has
feasible solutions and the other does not, and both problems do not have feasible
solutions. In these cases, as Han himself mentioned in Han (1980), the system
(38.11) and (38.12) provides a kind of least squares solution for one or both linear
programs, respectively. Such a situation will be considered in our paper.
In the inconsistent case of (38.11), it results that at least for one index i the
corresponding inequality is violated, i.e. the set I(x) & {1, . . . , m}, defined by
I x
ð Þ ¼ i 2; A i ; x
h
i ! b i
f
g
ð38:13Þ
is nonempty for any x 2 ℝ
n . Moreover, let us suppose that the set I(x) ¼ {i 1 , . . . ,
i p } is ordered such that i 1 < i 2 < . . . < i p ; then, A I(x) , b I(x) will denote the submatrix
of A with the rows A i 1 , . . . , A i p and the subvector of b with components b i 1 , . . . , b i p ,
respectively. For any vector y 2 ℝ
m we define y + 2 ℝ
m by (y + ) i ¼ max {y i , 0}. Han
(1980) proposed the following algorithm for numerical solution of the inconsistent
system (38.11).
Algorithm H Let x
0 2 ℝ
n be arbitrary fixed; for k ¼ 0 , 1 , . . . do:
Step 1. Find I k ¼ I(x
k ) and compute d
k
2 ℝ, the minimal norm solution of the linear
least squares problem
k A I k d À b I k À A I k x
k
À
Á k¼ min!
ð38:14Þ
Step 2. Compute λ
k , j
2 ℝ as the smallest minimizer of
θ λ
ð Þ ¼ f x
k
þ λd
k, j
À
Á
, λ 2 ℝ:
Step 3. Set x
k + 1
¼ x
k + λ
k , j
d
k , j
.
634
D. Carp et al.
c
T
Àδ
T
ÀB 0
0
B
T
ÀI
0
0
ÀI
2
6
6
6
6
6
6
4
3
7
7
7
7
7
7
5
, b ¼
0
Àδ
c
0
0
2
6
6
6
6
6
6
4
3
7
7
7
7
7
7
5
ð38:12Þ
Hence, from the above result it holds that solving a pair of feasible (consistent)
primal-dual linear programs is equivalent with solving a certain system of linear
inequalities. According to Theorem 5.1, page 181 in Andrei (2011), there are two
more possible cases that can occur beside the feasible one: one of the problem has
feasible solutions and the other does not, and both problems do not have feasible
solutions. In these cases, as Han himself mentioned in Han (1980), the system
(38.11) and (38.12) provides a kind of least squares solution for one or both linear
programs, respectively. Such a situation will be considered in our paper.
In the inconsistent case of (38.11), it results that at least for one index i the
corresponding inequality is violated, i.e. the set I(x) & {1, . . . , m}, defined by
I x
ð Þ ¼ i 2; A i ; x
h
i ! b i
f
g
ð38:13Þ
is nonempty for any x 2 ℝ
n . Moreover, let us suppose that the set I(x) ¼ {i 1 , . . . ,
i p } is ordered such that i 1 < i 2 < . . . < i p ; then, A I(x) , b I(x) will denote the submatrix
of A with the rows A i 1 , . . . , A i p and the subvector of b with components b i 1 , . . . , b i p ,
respectively. For any vector y 2 ℝ
m we define y + 2 ℝ
m by (y + ) i ¼ max {y i , 0}. Han
(1980) proposed the following algorithm for numerical solution of the inconsistent
system (38.11).
Algorithm H Let x
0 2 ℝ
n be arbitrary fixed; for k ¼ 0 , 1 , . . . do:
Step 1. Find I k ¼ I(x
k ) and compute d
k
2 ℝ, the minimal norm solution of the linear
least squares problem
k A I k d À b I k À A I k x
k
À
Á k¼ min!
ð38:14Þ
Step 2. Compute λ
k , j
2 ℝ as the smallest minimizer of
θ λ
ð Þ ¼ f x
k
þ λd
k, j
À
Á
, λ 2 ℝ:
Step 3. Set x
k + 1
¼ x
k + λ
k , j
d
k , j
.
634
D. Carp et al.