# Solving the Matrix Nearness Problem in the Maximum Norm by Applying a Projection and Contraction Method

Authors: M. H. Xu; H. Shao
Journal: Advances in Operations Research
 (2012)

---

## Abstract

LetS be a closed convex set of matrices and C be a given matrix. The matrix nearness problem considered in this paper is to find a matrix X in the set S at which max {|xij−cij|} reaches its minimum value. In order to solve the matrix nearness problem, the problem is reformulated to a min-max problem firstly, then the relationship between the min-max problem and a monotone linear variational inequality (LVI) is built. Since the matrix in the LVI problem has a special structure, a projection and contraction method is suggested to solve this LVI problem. Moreover, some implementing details of the method are presented in this paper. Finally, preliminary numerical results are reported, which show that this simple algorithm is promising for this matrix nearness problem.


---

## Body

## 1. Introduction

LetC=(cij)∈Rn×n be a given symmetric matrix and
(1.1)SΛn={H∈Rn×n∣HT=H,λmin⁡I⪯H⪯λmax⁡I},
where λmin,λmax are given scalars and λmin<λmax, I is the identity matrix, and A⪯B denotes that B-A is a positive semidefinite matrix. It is clear that SΛn is a nonempty closed convex set. The problem considered in this paper is
(1.2)min⁡{‖X-C‖inf⁡∣X=(xij)∈SΛn},
where
(1.3)‖X-C‖inf⁡=max⁡{|xij-cij|∣i=1,…,n,j=1,…,n}.
Throughout the paper we assume that the solution set of problem (1.2) is nonempty.Note that whenλmin=0 and λmax=+∞, the set SΛn reduces to the semidefinite cone
(1.4)S+n={H∈Rn×n∣HT=H,H⪰0}.
Using the terminology in interior point methods, S+n is called semidefinite cone, and thus the related problem belongs to the class of semidefinite programming [1].Problem (1.2) can be viewed as a type of matrix nearness problem, that is, the problem of finding a matrix that satisfies some property and is nearest to a given one. A survey on matrix nearness problems can be found in [2]. The matrix nearness problems have many applications especially in finance, statistics, and compressive sensing. For example, one application in statistics is to make adjustments to a symmetric matrix so that it is consistent with prior knowledge or assumptions, and is a valid covariance matrix [3–8]. Paper [9] discusses a new class of matrix nearness problems that measure approximation error using a directed distance measure called a Bregman divergence and proposes a framework for studying these problems, discusses some specific matrix nearness problems, and provides algorithms for solving them numerically.Note that a different norm is used in this paper than in these published papers [3–7] and this makes the objective function of problem (1.2) be nonsmooth, and the problem (1.2) cannot be solved very easily. In the next section, we will find that the problem (1.2) can be converted into a linear variational inequality and thus can be solved effectively with the projection and contraction (PC) method which is extremely simple both in theoretical analysis and numerical implementations [10–15].The paper is organized as follows. The relationship between the matrix nearness problem considered in this paper and a monotone linear variational inequality (LVI) is built in Section2. In Section 3, some preliminaries on variational inequalities are summarized. The projection and contraction method for the LVI associated with the considered problem is suggested. In Section 4, the implementing details for applying the projection and contraction method to the matrix optimization problems are studied. Preliminary numerical results and some concluding remarks are reported in Sections 5 and 6, respectively.


## 2. Reformulating the Problem to a Monotone LVI

For anyd∈Rm, we have
(2.1)‖d‖∞=max⁡ξ∈B1ξTd,
where B1={ξ∈Rm|∥ξ∥1≤1} and ξTd is the Euclidean inner-product of ξ and d.In order to simplify the following descriptions, letvec(A) be a linear transformation which converts the matrix A∈Rl×n into a column vector in Rln obtained by stacking the columns of the matrix A on top of one another, that is,
(2.2)vec⁡(A)=(a11,…,al1,a12,…,al2,…,a1n,…,aln)T,
and let mat(vec(A)) be the original matrix A, that is, (2.3)mat(vec⁡(A))=A.Based on (2.1) and the fact that the matrix X and C are symmetric, problem (1.2) can similarly be rewritten as the following min-max problem:
(2.4)min⁡X∈SΛnmax⁡Z∈Bvec⁡(Z)T(vec⁡(X)-vec⁡(C)),
where
(2.5)B={Z∈Rn×n∣Z=ZT,∑i=1n‍∑j=1n‍|zij|≤1}.Remark 2.1.
SinceX and C are both symmetric matrices, we can restrict the matrices in set ℬ to be symmetric.Let(2.6)Ω1={x=vec⁡(X)∣X∈SΛn},(2.7)Ω2={z=vec⁡(Z)∣Z∈B}.
Since SΛn and ℬ are both convex sets, it is easy to prove that Ω1 and Ω2 are also convex sets.Let(X*,Z*)∈SΛn×ℬ be any solution of (2.4) and x*=vec(X*),z*=vec(Z*). Then
(2.8)zT(x*-c)≤z*T(x*-c)≤z*T(x-c),∀(x,z)∈Ω,
where c=vec(C) and Ω=Ω1×Ω2. Thus, (x*,z*) is a solution of the following variational inequality: find (x*,z*)∈Ω such that
(2.9)(x-x*)Tz*≥0,(z-z*)T(-x*+c)≥0,∀(x,z)∈Ω.
For convenience of coming analysis, we rewrite the linear variational inequality (2.9) in the following compact form: find u*∈Ω such that
(2.10)(u-u*)T(Mu*+q)≥0,∀u∈Ω,
where
(2.11)u*=(x*z*),u=(xz),M=(0I-I0),q=(0c).
In the following, we denote the linear variational inequality (2.10)-(2.11) by LVI(Ω,M,q).Remark 2.2.
SinceM is skew-symmetric, the linear variational inequality LVI(Ω,M,q) is monotone.


## 3. Projection and Contraction Method for Monotone LVIs

In this section, we summarize some important concepts and preliminary results which are useful in the coming analysis.


### 3.1. Projection Mapping

LetΩ be a nonempty closed convex set of Rm. For a given v∈Rm, the projection of v onto Ω, denoted by PΩ(v), is the unique solution of the following problem:
(3.1)min⁡u{‖u-v‖∣u∈Ω},
where ∥·∥ is the Euclidian norm. The projection under an Euclidean norm plays an important role in the proposed method. A basic property of the projection mapping on a closed convex set is
(3.2)(v-PΩ(v))T(u-PΩ(v))≤0,∀v∈Rm,∀u∈Ω.In many cases of practical applications, the closed convex setΩ has a simple structure, and the projection on Ω is easy to carry out. For example, let e be a vector whose each element is 1, and
(3.3)B∞={ξ∈Rm∣‖ξ‖∞≤1}.
Then the projection of a vector d∈Rm on ℬ∞ can be obtained by
(3.4)PB∞(d)=max⁡{-e,min⁡{d,e}},
where the min and max are component wise.


### 3.2. Preliminaries on Linear Variational Inequalities

We denote the solution set of LVI(Ω,M,q) (2.10) by Ω* and assume that Ω*≠∅. Since the early work of Eaves [16], it is well known that the variational inequality LVI(Ω,M,q) problem is equivalent to the following projection equation:
(3.5)u=PΩ[u-(Mu+q)].
In other words, to solve LVI(Ω,M,q) is equivalent to finding a zero point of the continuous residue function
(3.6)e(u):=u-PΩ[u-(Mu+q)].
Hence,
(3.7)e(u)=0⟺u∈Ω*.
In the literature of variational inequalities, ∥e(u)∥ is called the error bound of LVI. It quantitatively measures how much u fails to be in Ω*.


### 3.3. The Projection and Contraction Method

Letu*∈Ω* be a solution. For any u∈Rm, because PΩ[u-(Mu+q)]∈Ω, it follows from (2.10) that
(3.8)(PΩ[u-(Mu+q)]-u*)T(Mu*+q)≥0,∀u∈Rm.
By setting v=u-(Mu+q) and u=u* in (3.2), we have
(3.9)(PΩ[u-(Mu+q)]-u*)T{u-(Mu+q)-PΩ[u-(Mu+q)]}≥0,∀u∈Rm.
Adding the above two inequalities, and using the notation of e(u), we obtain
(3.10){(u-u*)-e(u)}T{e(u)-M(u-u*)}≥0,∀u∈Rm.
For positive semi-definite (not necessary symmetric) matrix M, the following theorem follows from (3.10) directly.Theorem 3.1 (Theorem  1 in [11]).
For anyu*∈Ω*, we have
(3.11)(u-u*)Td(u)≥‖e(u)‖2,∀u∈Rm,
where
(3.12)d(u)=MTe(u)+e(u).Foru∈Ω∖Ω*, it follows from (3.11)-(3.12) that -d(u) is a descent direction of the unknown function (1/2)∥u-u*∥2. Some practical PC methods for LVI based on direction d(u) are given in [11].Algorithm 3.2 (Projection and Contraction Method for LVI Problem (2.10)).
Givenu0∈Ω. for k=0,1…, if uk∉Ω*, then do the following
(3.13)uk+1=uk-γα(uk)d(uk),
where γ∈(0,2), d(u) is defined in (3.12), and
(3.14)α(u)=‖e(u)‖2‖d(u)‖2.Remark 3.3.
In fact,γ is a relaxation factor and it is recommended to be taken from [1,2). In practical computation, usually we take γ∈[1.2,1.9]. The method was first mentioned in [11]. Among the PC methods for asymmetric LVI(Ω,M,q) [10–13], this method makes just one projection in each iteration.
For completeness sake, we include the theorem for LVI (2.10) and its proofs.Theorem 3.4 (Theorem  2 in [11]).
The method (3.13)-(3.14) produces a sequence {uk}, which satisfies
(3.15)‖uk+1-u*‖2≤‖uk-u*‖2-γ(2-γ)α(uk)‖e(uk)‖2.Proof.
It follows from (3.11) and (3.14) that
(3.16)‖uk+1-u*‖2=‖uk-u*-γα(uk)d(uk)‖2=‖uk-u*‖2-2γα(uk)(uk-u*)Td(uk)+γ2α2(uk)‖d(uk)‖2≤‖uk-u*‖2-2γα(uk)‖e(uk)‖2+γ2α2(uk)‖d(uk)‖2=‖uk-u*‖2-γ(2-γ)α(uk)‖e(uk)‖2.
Thus the theorem is proved.The method used in this paper is calledprojection and contraction method because it makes projections in each iteration and the generated sequence is Fejér monotone with respect to the solution set.For skew-symmetricM in LVI (2.10), it is easy to prove that α(u)≡1/2. Thus, the contraction inequality (3.15) can be simplified to(3.17)‖uk+1-u*‖2≤‖uk-u*‖2-γ(2-γ)2‖e(uk)‖2.
Following (3.17), the convergence results of the sequence {uk} can be found in [11] or be proved similarly to that in [17].Since the above inequality is true for allu*∈Ω*, we have
(3.18)dist⁡2(uk+1,Ω*)≤dist⁡2(uk,Ω*)-γ(2-γ)2‖e(uk)‖2,
where
(3.19)dist⁡(u,Ω*)=min⁡{‖u-u*‖∣u*∈Ω*}.
The above inequality states that we get a “great” profit from the kth iteration, if ∥e(uk)∥ is not too small; conversely, if we get a very small profit from the kth iteration, then ∥e(uk)∥ is already very small and uk is a “sufficiently good” approximation of a u*∈Ω*.


## 3.1. Projection Mapping

LetΩ be a nonempty closed convex set of Rm. For a given v∈Rm, the projection of v onto Ω, denoted by PΩ(v), is the unique solution of the following problem:
(3.1)min⁡u{‖u-v‖∣u∈Ω},
where ∥·∥ is the Euclidian norm. The projection under an Euclidean norm plays an important role in the proposed method. A basic property of the projection mapping on a closed convex set is
(3.2)(v-PΩ(v))T(u-PΩ(v))≤0,∀v∈Rm,∀u∈Ω.In many cases of practical applications, the closed convex setΩ has a simple structure, and the projection on Ω is easy to carry out. For example, let e be a vector whose each element is 1, and
(3.3)B∞={ξ∈Rm∣‖ξ‖∞≤1}.
Then the projection of a vector d∈Rm on ℬ∞ can be obtained by
(3.4)PB∞(d)=max⁡{-e,min⁡{d,e}},
where the min and max are component wise.


## 3.2. Preliminaries on Linear Variational Inequalities

We denote the solution set of LVI(Ω,M,q) (2.10) by Ω* and assume that Ω*≠∅. Since the early work of Eaves [16], it is well known that the variational inequality LVI(Ω,M,q) problem is equivalent to the following projection equation:
(3.5)u=PΩ[u-(Mu+q)].
In other words, to solve LVI(Ω,M,q) is equivalent to finding a zero point of the continuous residue function
(3.6)e(u):=u-PΩ[u-(Mu+q)].
Hence,
(3.7)e(u)=0⟺u∈Ω*.
In the literature of variational inequalities, ∥e(u)∥ is called the error bound of LVI. It quantitatively measures how much u fails to be in Ω*.


## 3.3. The Projection and Contraction Method

Letu*∈Ω* be a solution. For any u∈Rm, because PΩ[u-(Mu+q)]∈Ω, it follows from (2.10) that
(3.8)(PΩ[u-(Mu+q)]-u*)T(Mu*+q)≥0,∀u∈Rm.
By setting v=u-(Mu+q) and u=u* in (3.2), we have
(3.9)(PΩ[u-(Mu+q)]-u*)T{u-(Mu+q)-PΩ[u-(Mu+q)]}≥0,∀u∈Rm.
Adding the above two inequalities, and using the notation of e(u), we obtain
(3.10){(u-u*)-e(u)}T{e(u)-M(u-u*)}≥0,∀u∈Rm.
For positive semi-definite (not necessary symmetric) matrix M, the following theorem follows from (3.10) directly.Theorem 3.1 (Theorem  1 in [11]).
For anyu*∈Ω*, we have
(3.11)(u-u*)Td(u)≥‖e(u)‖2,∀u∈Rm,
where
(3.12)d(u)=MTe(u)+e(u).Foru∈Ω∖Ω*, it follows from (3.11)-(3.12) that -d(u) is a descent direction of the unknown function (1/2)∥u-u*∥2. Some practical PC methods for LVI based on direction d(u) are given in [11].Algorithm 3.2 (Projection and Contraction Method for LVI Problem (2.10)).
Givenu0∈Ω. for k=0,1…, if uk∉Ω*, then do the following
(3.13)uk+1=uk-γα(uk)d(uk),
where γ∈(0,2), d(u) is defined in (3.12), and
(3.14)α(u)=‖e(u)‖2‖d(u)‖2.Remark 3.3.
In fact,γ is a relaxation factor and it is recommended to be taken from [1,2). In practical computation, usually we take γ∈[1.2,1.9]. The method was first mentioned in [11]. Among the PC methods for asymmetric LVI(Ω,M,q) [10–13], this method makes just one projection in each iteration.
For completeness sake, we include the theorem for LVI (2.10) and its proofs.Theorem 3.4 (Theorem  2 in [11]).
The method (3.13)-(3.14) produces a sequence {uk}, which satisfies
(3.15)‖uk+1-u*‖2≤‖uk-u*‖2-γ(2-γ)α(uk)‖e(uk)‖2.Proof.
It follows from (3.11) and (3.14) that
(3.16)‖uk+1-u*‖2=‖uk-u*-γα(uk)d(uk)‖2=‖uk-u*‖2-2γα(uk)(uk-u*)Td(uk)+γ2α2(uk)‖d(uk)‖2≤‖uk-u*‖2-2γα(uk)‖e(uk)‖2+γ2α2(uk)‖d(uk)‖2=‖uk-u*‖2-γ(2-γ)α(uk)‖e(uk)‖2.
Thus the theorem is proved.The method used in this paper is calledprojection and contraction method because it makes projections in each iteration and the generated sequence is Fejér monotone with respect to the solution set.For skew-symmetricM in LVI (2.10), it is easy to prove that α(u)≡1/2. Thus, the contraction inequality (3.15) can be simplified to(3.17)‖uk+1-u*‖2≤‖uk-u*‖2-γ(2-γ)2‖e(uk)‖2.
Following (3.17), the convergence results of the sequence {uk} can be found in [11] or be proved similarly to that in [17].Since the above inequality is true for allu*∈Ω*, we have
(3.18)dist⁡2(uk+1,Ω*)≤dist⁡2(uk,Ω*)-γ(2-γ)2‖e(uk)‖2,
where
(3.19)dist⁡(u,Ω*)=min⁡{‖u-u*‖∣u*∈Ω*}.
The above inequality states that we get a “great” profit from the kth iteration, if ∥e(uk)∥ is not too small; conversely, if we get a very small profit from the kth iteration, then ∥e(uk)∥ is already very small and uk is a “sufficiently good” approximation of a u*∈Ω*.


## 4. Implementing Details of Algorithm3.2 for Solving Problem (1.2)

We use the Algorithm3.2 to solve the linear variational inequality (2.10) arising from problem (1.2). For a given u=(x,z)∈Ω, the process of computing a new iterate is listed as follows:
(4.1)Mu+q=(zc-x),e(u)=(ex(u)ez(u))=(x-PΩ1[x-z]z-PΩ2[z+(x-c)]),d(u)=(dx(u)dz(u))=MTe(u)+e(u)=(ex(u)-ez(u)ex(u)+ez(u)),unew=(xnewznew)=(x-γdx(u)2z-γdz(u)2),γ∈(0,2).
The key operations here are to compute PΩ1[x-z] and PΩ2[z+(x-c)], where mat(x),mat(z),andmat(z+(x-c)) are symmetric matrices. In the following, we first focus on the computing method of PΩ1[v], where mat(v) is a symmetric matrix.Sincemat(v) is a symmetric matrix, we have
(4.2)PΩ1[v]=argmin⁡x{‖x-v‖2∣x∈Ω1}=vec⁡(argmin⁡X{‖X-V‖F2∣X∈SΛn}),
where V=mat(v). It is known that the optimal solution of problem
(4.3)min⁡{‖X-V‖F2∣X∈SΛn}
is given by
(4.4)QΛ~QT,
where
(4.5)VQ=QΛ,Λ=diag⁡(λ11,…,λnn),Λ~=diag⁡(λ~11,…,λ~nn),λ~ii=min⁡{max⁡{λii,λmin⁡},λmax⁡},
and ∥·∥F is the Frobenius norm. Thus, we have
(4.6)PΩ1[v]=vec⁡(QΛ~QT).
Now we move to consider the technique of computing PΩ2[v], where mat(v) is a symmetric matrix.Lemma 4.1.
Ifmat(v) is a symmetric matrix and x* is the solution of the problem
(4.7)min⁡x{‖x-v‖∣∑i=1m‍|xi|≤1}
then we have
(4.8)mat(x*)=mat(x*)T.Proof.
Since(4.9)argmin⁡x{‖x-v‖∣∑i=1m‍|xi|≤1}=vec⁡(argmin⁡X{‖X-V‖F∣∑i=1n‍∑j=1n‍|xij|≤1})
and V=VT, where V=mat(v), we have that if x* is the solution of problem (4.7), then vec(mat(x*)T) is also the solution of problem (4.7). As it is known that the solution of problem (4.7) is unique. Thus, x*=vec(mat(x*)T), and the proof is complete.Lemma 4.2.
Ifx* is the solution of problem
(4.10)min⁡x{‖x-sign⁡(v)∘v‖∣∑i=1m‍xi≤1,x≥0},
where sign(v)=(sign(v1),sign(v2),…,sign(vm))T, sign(vi) is the sign of real number vi, and
(4.11)sign⁡(v)∘v=(sign⁡(v1)v1,sign⁡(v2)v2,…,sign⁡(vm)vm)T=|v|,
then sign(v)∘x* is the solution of the problem
(4.12)min⁡x{‖x-v‖∣∑i=1m‍|xi|≤1}.Proof .
The result follows from(4.13)‖x-v‖=‖sign⁡(v)∘(x-v)‖,∑i=1m‍|sign⁡(vi)xi|=∑i=1m‍|xi|≤1.Lemma 4.3.
Letv≥0, T be a permutation transformation sorting the components of v in descending order, that is, the components of v-=Tv are in descending order. Further, suppose that x-* is the solution of the problem
(4.14)min⁡x{‖x-v-‖∣∑i=1m‍xi≤1},
then x*=T-1x-* is the solution of the problem
(4.15)min⁡x{‖x-v‖∣∑i=1m‍xi≤1}.Proof .
SinceT is a permutation transformation, we have that
(4.16)T-1=T,
and the optimal values of objective function of problem (4.14) and (4.15) are equal.
Note that(4.17)‖x*-v‖=‖T(x*-v)‖=‖x-*-v-‖,∑i=1m‍xi*=∑i=1m‍x-i*≤1.
Thus, x* is the optimal solution of problem (4.15). And the proof is complete.Remark 4.4.
Suppose thatmat(v)∈Rn×n is a symmetric matrix for a given v∈Rm. Let v~=T(sign(v)∘v), where T is a permutation transformation sorting the components of sign(v)∘v in descending order. Lemmas 4.1–4.3 show that if x~* is the solution of the following problem
(4.18)min⁡x{12‖x-v~‖2∣∑i=1m‍xi≤1,x≥0},
then
(4.19)PΩ2[v]=sign⁡(v)∘(Tx~*).Hence, to solve the problem (4.18) is a key work to obtain the projection PΩ2[v]. Let e=(1,1,…,1)T∈Rm, then problem (4.18) can be rewritten as
(4.20)min⁡x{12‖x-v~‖2∣eTx≤1,x≥0}.
The Lagrangian function for the constrained optimal problem (4.20) is defined as
(4.21)L(x,y,w)=12‖x-v~‖2-y(1-eTx)-wTx,
where scale y and vector w∈Rm are the Lagrange multipliers corresponding to inequalities eTx≤1 and x≥0, respectively. By KKT condition, we have
(4.22)x-v~+ye-w=0,y≥0,1-eTx≥0,y(1-eTx)=0,w≥0,x≥0,wTx=0,
that is,
(4.23)y≥0,1-eTx≥0,y(1-eTx)=0,x≥0,x+ye-v~≥0,xT(x+ye-v~)=0.
It is easy to check that if eTv~≤1, then (x~*,y~*)=(v~,0) is the solution of problem (4.23). Now we assume that eTv~>1. In this case, let
(4.24)Δv=(v~1-v~2,v~2-v~3,…,v~m-1-v~m,v~m)T.
Note that Δv≥0 and
(4.25)∑i=1m‍i×Δvi=∑i=1m‍v~i>1.
Thus, there exists a least-integer K such that
(4.26)∑i=1K‍i×Δvi≥1.
Since
(4.27)∑i=1K‍v~i={∑i=1K‍i×Δvi+K×v~K+1,1≤K<m,∑i=1K‍i×Δvi,K=m,
we have that
(4.28)∑i=1K‍v~i≥1.
Let
(4.29)y~*=1K(∑i=1K‍v~i-1),(4.30)x~*=(v~1-y~*,v~2-y~*,…,v~K-y~*,0,…,0)T∈Rm.Theorem 4.5.
Letx~* and y~* be given by (4.30) and (4.29), respectively, then (x~*,y~*) is the solution of problem (4.23), and thus
(4.31)PΩ2[v]=sign⁡(v)∘(Tx~*).Proof .
It follows from (4.26), (4.27), and (4.29) that
(4.32)y~*=1K(∑i=1K‍v~i-1)≥1K∑i=1K‍(v~i-i×Δvi)={v~K+1,1≤K<m,0,K=m,y~*=1K(∑i=1K‍v~i-1)≤1K(∑i=1K‍v~i-∑i=1K-1‍i×Δvi)=1K(∑i=1K-1‍v~i-∑i=1K-1‍i×Δvi+v~K)=v~K.
Following from (4.32) it is easy to check that (x~*,y~*) is a solution of problem (4.23). Note that problem (4.18) is convex, thus (x~*,y~*) is the solution of problem (4.18). Further, according to Remark 4.4, we have
(4.33)PΩ2[v]=sign⁡(v)∘(Tx~*).
The proof is complete.Remark 4.6.
Note that ifX~* is the solution of problem
(4.34)min⁡{‖X-1βC‖inf⁡∣X=(xij)∈S~Λn},
where β>0 is a given scalar, and
(4.35)S~Λn={H∈Rn×n∣HT=H,λmin⁡βI⪯H⪯λmax⁡βI},
then X*=βX~* is the solution of problem (1.2). Thus, we can find the solution of problem (1.2) by solving problem (4.34).Let(4.36)Ω~1={x=vec⁡(X)∣X∈S~Λn}.
Now, we are in the stage to describe the implementing process of Algorithm 3.2 for problem (1.2) in detail.Algorithm 4.7 (projection and contraction method for problem (1.2)).
Step  1(Initialization). Let C=(cij)∈Rn×n be a given symmetric matrix, λmin,λmax,β>0 be given scalars. Choose arbitrarily an initial point x0=vec(X0), z0=vec(Z0), and u0=(x0z0), where X0∈Ω~1,Z0∈Ω2, Ω~1, and Ω2 are defined by (4.36) and (2.7), respectively. Let γ∈(0,2), k=0, and ε>0 be a prespecified tolerance.
Step  2 (Computation). Compute PΩ~1[xk-zk] and PΩ2[zk+(xk-c)] by using (4.6) and (4.31), respectively.
Letex(uk)=xk-PΩ~1[xk-zk],ez(uk)=zk-PΩ2[zk+(xk-c)],dx(uk)=ex(uk)-ez(uk),dz(uk)=ex(uk)+ez(uk),where uk=(xkzk).
Step  3. (Verification). If ∥e(uk)∥∞<ε, then stop and output the approximate solution X=βmat(xk), where e(uk)=(ex(uk)ez(uk)).
Step  4.(Iteration).xk+1=xk-γdx(uk)/2,zk+1=zk-γdz(uk)/2,k:=k+1, goto Step  2.


## 5. Numerical Experiments

In this section, some examples are provided to illustrate the performance of Algorithm4.7 for solving problem (1.2). In the following illustrative examples, the computer program for implementing Algorithm 4.7 is coded in Matlab and the program runs on IBM notebook (R51).Example 5.1.
Consider problem (1.2) with C=(C~+C~T)/2+eye(n),λmin=-50, and λmax=50, where C~=rand(n)-0.5, rand and eye are both the Matlab functions, and n is the size of problem (1.2). Let γ=1.5,ε=1×10-7, then we have
(5.1)β=n‖vec⁡(C)‖∞,x0=vec⁡(12(λ~1+λ~2)×eye(n)),z0=vec⁡(zeros(n)),
where zeros is also the Matlab function, λ~1=max{λ1/β,λmin/β}, λ~2=min{λn/β, λmax/β}, and λ1,λn are the smallest and the largest eigenvalue of matrix C, respectively. Table 1 reports the numerical results of Example 5.1 solved by Algorithm 4.7, where k is the number of iterations, the unit of time is second, and X is the approximate solution of problem (1.2) obtained by Algorithm 4.7.Table 1
Numerical results of example 1.
n
λ
1
λ
n
k
CPU time (s)
∥
e
(
u
)
∥
∞
∥
vec
(
X
-
C
)
∥
∞
/
∥
vec
(
C
)
∥
∞
10
0.2947
2.2687
55
0.06
9.2699
×
1
0
-
8
1.9768
×
1
0
-
7
20
-
0.5849
2.8134
58
0.17
7.3282
×
1
0
-
8
2.7002
×
1
0
-
7
30
-
0.9467
2.9938
65
0.35
7.5651
×
1
0
-
8
2.8008
×
1
0
-
7
40
-
1.2405
3.4024
75
0.49
9.6325
×
1
0
-
8
5.0350
×
1
0
-
7
50
-
1.7593
3.7925
89
0.67
8.5592
×
1
0
-
8
3.9993
×
1
0
-
7
60
-
2.0733
4.1648
106
1.29
8.9517
×
1
0
-
8
6.1197
×
1
0
-
7
70
-
2.3450
4.3352
121
2.00
9.5952
×
1
0
-
8
6.6696
×
1
0
-
7
80
-
2.5817
4.5194
140
3.56
8.3927
×
1
0
-
8
3.7658
×
1
0
-
7
90
-
2.8345
4.7512
160
5.23
8.3227
×
1
0
-
8
4.8914
×
1
0
-
7
100
-
2.9193
5.1780
181
7.43
9.3473
×
1
0
-
8
6.2160
×
1
0
-
7
150
-
4.1850
5.7006
302
35.90
7.4435
×
1
0
-
8
6.1552
×
1
0
-
7
200
-
4.6721
6.7545
446
119.07
7.8171
×
1
0
-
8
8.4093
×
1
0
-
7Example 5.2.
Consider problem (1.2) with C=C~C~T,λmin=0, and λmax=20, where C~=2×rand(n)-1. In this test example, let γ, ε be same as that in Example 5.1, β,x0, and z0 be also given according to (5.1). Table 2 reports the numerical results of Example 5.2 and shows the numerical performance of Algorithm 4.7 for solving problem (1.2).Table 2
Numerical results of example 2.
n
λ
1
λ
n
k
CPU time (s)
∥
e
(
u
)
∥
∞
∥
vec
(
X
-
C
)
∥
∞
/
∥
vec
(
C
)
∥
∞
10
0.0090
9.0559
74
0.08
9.9036
×
1
0
-
8
4.2676
×
1
0
-
9
20
0.0048
19.4004
107
0.30
9.4778
×
1
0
-
8
4.2266
×
1
0
-
7
30
0.0184
33.6477
7617
17.98
9.9976
×
1
0
-
8
7.0348
×
1
0
-
2
40
0.0004
46.4279
162
0.76
9.9938
×
1
0
-
8
1.2216
×
1
0
-
1
50
0.0045
55.7072
192
1.46
9.4131
×
1
0
-
8
1.8517
×
1
0
-
1
60
0.0020
73.8863
1259
15.18
9.9708
×
1
0
-
8
2.4254
×
1
0
-
1
70
0.0084
86.8784
245
4.28
8.9912
×
1
0
-
8
3.3916
×
1
0
-
1
80
0.0021
100.3238
614
14.13
9.0897
×
1
0
-
8
3.8534
×
1
0
-
1
90
0.0002
108.6724
384
10.38
7.7490
×
1
0
-
8
4.7801
×
1
0
-
1
100
0.0011
130.7923
326
9.03
9.0180
×
1
0
-
8
5.2592
×
1
0
-
1
150
0.0001
195.6736
2214
98.28
7.0598
×
1
0
-
8
6.6452
×
1
0
-
1
200
0.0013
261.9417
1582
165.29
7.1460
×
1
0
-
8
7.4489
×
1
0
-
1


## 6. Conclusions

In this paper, a relationship between the matrix nearness problem and the linear variational inequality has been built. The matrix nearness problem considered in this paper can be solved by applying an algorithm for the related linear variational inequality. Based on this point, a projection and contraction method is presented for solving the matrix nearness problem, and the implementing details are introduced in this paper. Numerical experiments show that the method suggested in this paper has a good performance, and the method can be improved by setting the parameters in Algorithm4.7 properly. Thus, further studying of the effect of the parameters in Algorithm 4.7 maybe a very interesting work.



---

*Source: 357954-2012-08-13.xml*