# Tightness of Semidefinite Programming Relaxation to Robust Transmit Beamforming with SINR Constraints

Authors: Yanjun Wang; Ruizhi Shi
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

This paper considers a multiuser transmit beamforming problem under uncertain channel state information (CSI) subject to SINR constraints in a downlink
multiuser MISO system. A robust transmit beamforming formulation is proposed. This robust formulation is to minimize the transmission power subject to worst-case signal-to-interference-plus-noise ratio (SINR) constraints on the receivers. The challenging problem is that the worst-case SINR constraints correspond to an infinite number of nonconvex quadratic constraints. In this paper,
a natural semidifinite programming (SDP) relaxation problem is proposed to solve the robust beamforming problem. The main contribution of this paper is to establish the tightness of the SDP relaxation problem under proper assumption, which means that the SDP relaxation problem definitely yields rank-one solutions under the assumption. Then the SDP relaxation problem provides globally optimum solutions of the primal robust transmit beamforming problem under proper assumption and norm-constrained CSI errors. Simulation results show the correctness of the proposed theoretical results and also provide a counterexample whose solutions are not rank one. The existence of counterexample shows that the guess that the solutions of the SDP relaxation problem must be rank one is wrong, except that some assumptions (such as the one proposed in this paper) hold.


---

## Body

## 1. Introduction

Multiple antenna transmission has been a promising approach for obtaining significant throughput gains in wireless broadcast channels [1]. This paper will focus on a standard unicast antenna receivers using transmit beamforming [2]. A popular measure of quality of service in a multiuser communication system is the signal-to-interference-plus-noise ratio (SINR). However, in the transmit beamforming designs, if SINR is used as the receivers’ quality of service measure, the problem will be challenging because they often involve nonconvex optimization problems, which are known to be difficult in general. Recent developments have shown that the unicast transmit beamforming problem can actually be solved efficiently through proper problem reformulations and the convex optimization theory [2–4].The efficacy of unicast transmit beamforming designs with SINR constraints relies on the channel state information (CSI) of the receivers. In wireless systems, CSI is either estimated via uplink training or acquired through receivers’ feedback. Hence, it is inevitable to have CSI errors in practice due to finite-length training data or due to limited quantization feedback bandwidth. In these cases, the conventional beamforming designs may no longer guarantee the desired quality of service (QoS) requirements, and therefore the SINR outage may occur. Then, the transmit beamforming designs that take into consideration the CSI errors have been a research subject drawing great interests in recent years.There are two classes of transmit beamforming designs that consider the CSI errors: the stochastic design [5, 6] and robust design (worst case) [7–12]. In the stochastic design, the CSI errors are modeled as random vectors, and the design formulation where the transmission power is minimized is subject to probability SINR constraints. The probabilistic SINR constraints guarantee that the beamforming design provides each receiver with a preset, often high, probability that the desired SINR specification is satisfied (i.e., a high SINR satisfaction probability). The associated design problem is difficult because the probabilistic SINR constraints in general do not possess any tractable form. In the robust designs, CSI errors are assumed to be bounded within a predetermined small error set. Robust transmit beamforming design aims to find a most power-efficient beamforming design that guarantees the receiver k a 100% SINR satisfaction probability for all channels satisfying this bounded error model. It is seen that this formulation is a conservative approach. In other words, the robust beamforming formulation that minimizes the transmission power is subject to worst-case SINR constraints on all the receivers. Robust formulation is a challenging task because the problem has infinite number of deterministic SINR constraints and is nonconvex. To overcome the computational difficulties associated with the robust downlink beamforming, researchers have proposed various optimization methods to approximate the problem by restricting the nonconvex feasible region to a small convex set [11]. However, due to convex restriction, these methods cannot necessarily reach the global optimal solution although they do guarantee the satisfaction of the SINR constraints.This paper adopts a natural SDP relaxation problem denoted by(SDR) to solve the robust beamforming problem. It is known that SDP relaxation has been widely used in the context of transmit beamforming [13, 14]. Also the (SDR) of the robust beamforming problem has also been derived and empirically tested in [10, 12, 15, 16]. Some authors found an interesting fact that the (SDR) often yields rank-one solutions when the uncertainty regions are balls or ellipsoidal (as far as the problem is feasible). However, in [17], the authors present three counterexamples under ellipsoidal uncertainty regions whose solutions are not rank one accordingly. Hence, a key issue is whether the problem (SDR) can exactly solve the original robust problem under proper assumption. Although the SDP relaxation problem for nonrobust unicast transmit beamforming has been shown to be an exact solver [2, 3], it has not been known whether the same desirable result holds for robust design. In [17], authors have shown that the solution of the (SDR) is always rank one if the error bound is sufficiently small. In [18], the authors propose sufficient conditions which can assure the tightness of the SDP relaxation. The conditions in [18] are not expressed in terms of the data of the problems, which is an assumption for all the feasible solutions. Inspired by the previous work, in this paper, we try to get the insight into what is happening at the optimal solution and the optimal error vector δk* and propose a new assumption condition. This condition is that at the optimal solution there exists a unique error vector δk* which satisfies some necessary conditions. The main goal of this paper is to show under this condition that the (SDR) problem is tight (i.e., giving a rank-one solution) when the uncertainty regions are balls. In particular, we will prove that under this condition the solution of (SDR) must be rank one; that is, the (SDR) provides globally optimum solutions of the primal robust transmit beamforming problem. Also in the numerical simulation, a counterexample is provided whose solutions are not rank one. Hence, we can conclude that the guess that the solutions of the (SDR) must be rank one is wrong, except that some assumptions (such as the one proposed in this paper) hold.The structure of this paper is organized as follows. In Section2, the signal model and the robust SINR constrained transmit beamforming problem are presented. Section 3 presents the semidefinite relaxation problem (SDR) of the primal robust model. Some properties for (SDR) are explored in this section, especially the properties at the optimal solution. Section 4 shows that the problem (SDR) will yield rank-one solution under proper assumption and then provides globally optimal solutions of the primal problem. Simulation results are provided in Section 5. And Section 6 is the conclusion.Notations. The notation Hn×n stands for the set of n by n complex Hermitian matrices, and Cn stands for the sets of n-dimensional complex vectors. The superscript “H” represents the Hermitian transpose; and A⪰0(≻0) means that matrix A is positive semidefinite (positive definite). Tr(A)andrank(A) denote the trace and rank of matrix A, respectively. ∥·∥ represents the vector Euclidean norm.


## 2. Signal Model and Problem Formulation

### 2.1. Signal Model

We consider aK-user downlink MISO system where the base station (BS) is equipped with M antennas. The BS wants to transmit K-independent data streams s1,s2,…,sk to K users and each sK is complex Gaussian with unit variance. The BS uses linear beamforming vector gk∈CM, k=1,…,K, to send the stream sK. The received signal at receiver k is
(1)s^k=hkH∑i=1K‍sigi+ωk,k=1,…,K,
where hk denotes the channel vector from BS to the kth user. {ωk} are zero-mean independent white complex Gaussian noises, each with a variance of σk2>0. Therefore, the SINR of the kth user is
(2)SINRk=|hkHgk|2∑i≠k|hkHgi|2+σk2.
Since the SINR is directly related to system performance such as the bit error rate, it is commonly used as the receivers’ quality-of-service measure. The goal of the transmitter is to design the beamforming vectors {gi}i=1K such that each of the receivers can meet a desired SINR requirement as
(3)SINRk≥γk,k=1,…,K,
where γk>0 is the target SINR value for the receiver k.


### 2.2. Nonrobust Transmit Beamforming Problem

The transmitter requires the receivers’ CSI, that is,{hi}i=1K. Suppose that the transmitter perfectly knows {hi}i=1K. Then, the optimum beamforming vectors can be obtained by solving the following optimization problem:
(P)min{gk}k=1K∈CM∑k=1K‍∥gk∥2dds.t.ddddd|hkHgk|2∑i≠k|hkHgi|2+σk2≥γk,ddddddddddd.dddddk=1,…,K.
The problem (P) can be rewritten into
(PE)min{Gk}k=1K∑k=1K‍Tr(Gk)s.t.ddddhkHGkhk∑i≠khkHGihk+σk2≥γk,dddsddGk=gkgkH,k=1,…,K.
By replacing these nonconvex constraints Gk=gkgkH by the following constraint: Gk⪰0, then we can obtain the following relaxation programming:
(PR)min{Gk}k=1K∑k=1K‍Tr(Gk)s.t.ddddhkHGkhk∑i≠khkHGihk+σk2≥γk,k=1,…,K,ddddddGk⪰0,k=1,…,K.The problem(PR) is convex, which means that any local minima must be a global minima and the set of optimal solutions is convex (typically a single point). Obviously, the problem (PR) is also a SDP problem. A number of so-called interior point methods or central-path methods have appeared that can solve SDP problems efficiently. Also, several program packages are freely available, for example, CVX, SeDuMi, and YALMIP. Usually, the optimum of (PR) will provide a lower bound on the optimum of (P). However, the specific structure of (PR) enables us to have the following remarkable result [2, 3]. The problem (PR) does always have at least one optimal solution where all Gk(k=1,…,K) are rank one. This result shows that (PR) is not only a semidefinite relaxation, but also an equivalent reformulation of the problem (P) [2, 3].


### 2.3. Robust Transmit Beamforming Problem

In wireless systems, CSI at the transmitter is either estimated via uplink training or acquired through receivers’ feedback. Hence, it is inevitable to have CSI errors in practice due to the finite-length training data or due to the limited quantization feedbacks. Leth~k (k=1,…,K) denote the obtained channel estimates at the transmitter. The channel vector hk lies within a ball with radius ϵk around the estimated channel vector h~k; that is,
(4)hk∈Uk={h~k+δk∣∥δk∥≤ϵk}
for all k=1,…,K, where δk∈CM is the channel estimation error whose norm is assumed to be bounded by ϵk. With the imperfect CSI, the standard transmit beamforming designs in (P) may no longer guarantee the desired SINR specifications in (3), and therefore the SINR outage may occur.When the optimization problem is in the face of data uncertainty in the constraints, robust optimization is one of the powerful deterministic approaches. Within the framework of robust optimization method, the robust counterpart is presented as follows:(RP)min{gk}k=1K∈CM∑k=1K‍∥gk∥2dds.t.dddd|hkHgk|2∑i≠k|hkHgi|2+σk2≥γk,∀hk∈Uk,dddddddddk=1,…,K.
The problem (RP) aims to find a most power-efficient beamforming design that guarantees the receiver k a 100% SINR satisfaction probability for all uncertain cases of {hk}. It is seen that this formulation is a conservative approach. Solving problem (RP) is a challenging task because the problem has infinite number of deterministic SINR constraints and is nonconvex. Similar to the method in deterministic case, the problem (RP) can be rewritten into the following form:
(RPE)min{Gk}k=1K∑k=1K‍Tr(Gk)s.t.ffffffffhkHGkhk∑i≠khkHGihk+σk2≥γk,∀hk∈Uk,dddddddGk=gkgkH,k=1,…,K.
By replacing these nonconvex constraints Gk=gkgkH by the following constraint:Gk⪰0, then we can obtain the following convex relaxation programming:
(RPR)min{Gk}k=1K∑k=1K‍Tr(Gk)s.t.ddddhkHGkhk∑i≠khkHGihk+σk2≥γk,∀hk∈UkddddddGk⪰0,k=1,…,K.
Since the problem (RPR) aims to find the most power-efficient beamforming design that guarantees the receiver k a 100% SINR satisfaction probability for all uncertain cases of {hk}, then the question whether the (RPR) is feasible is highly related to the bound ϵk which is bounding the channel estimation error δk. The following lemma provides a necessary condition for the feasibility of the problem (RPR).Lemma 1.
If the(RPR) problem is feasible, then it must hold that ϵk<∥h~k∥2 for all k=1,…,K.Proof.
Suppose that there exists an indexk0 such that ϵk0≥∥h~k0∥2. Since (RPR) is feasible, then for k=k0, it must hold that
(5)hk0HGk0hk0∑i≠k0hk0HGihk0+σk02≥γk0,∀hk0∈Uk0.
Note that ϵk0≥∥h~k0∥2, then by choosing δk0=-h~k0, we have ∥δk0∥=∥h~k0∥≤ϵk0. So we derive an instance hk0′=δk0+h~k0=0 with hk0′∈Uk0. Substituting hk0′=0 into the left side of the above inequality, it is easy to result in a contradiction.Obviously, the same results as those of Lemma1 hold for (RP).


## 2.1. Signal Model

We consider aK-user downlink MISO system where the base station (BS) is equipped with M antennas. The BS wants to transmit K-independent data streams s1,s2,…,sk to K users and each sK is complex Gaussian with unit variance. The BS uses linear beamforming vector gk∈CM, k=1,…,K, to send the stream sK. The received signal at receiver k is
(1)s^k=hkH∑i=1K‍sigi+ωk,k=1,…,K,
where hk denotes the channel vector from BS to the kth user. {ωk} are zero-mean independent white complex Gaussian noises, each with a variance of σk2>0. Therefore, the SINR of the kth user is
(2)SINRk=|hkHgk|2∑i≠k|hkHgi|2+σk2.
Since the SINR is directly related to system performance such as the bit error rate, it is commonly used as the receivers’ quality-of-service measure. The goal of the transmitter is to design the beamforming vectors {gi}i=1K such that each of the receivers can meet a desired SINR requirement as
(3)SINRk≥γk,k=1,…,K,
where γk>0 is the target SINR value for the receiver k.


## 2.2. Nonrobust Transmit Beamforming Problem

The transmitter requires the receivers’ CSI, that is,{hi}i=1K. Suppose that the transmitter perfectly knows {hi}i=1K. Then, the optimum beamforming vectors can be obtained by solving the following optimization problem:
(P)min{gk}k=1K∈CM∑k=1K‍∥gk∥2dds.t.ddddd|hkHgk|2∑i≠k|hkHgi|2+σk2≥γk,ddddddddddd.dddddk=1,…,K.
The problem (P) can be rewritten into
(PE)min{Gk}k=1K∑k=1K‍Tr(Gk)s.t.ddddhkHGkhk∑i≠khkHGihk+σk2≥γk,dddsddGk=gkgkH,k=1,…,K.
By replacing these nonconvex constraints Gk=gkgkH by the following constraint: Gk⪰0, then we can obtain the following relaxation programming:
(PR)min{Gk}k=1K∑k=1K‍Tr(Gk)s.t.ddddhkHGkhk∑i≠khkHGihk+σk2≥γk,k=1,…,K,ddddddGk⪰0,k=1,…,K.The problem(PR) is convex, which means that any local minima must be a global minima and the set of optimal solutions is convex (typically a single point). Obviously, the problem (PR) is also a SDP problem. A number of so-called interior point methods or central-path methods have appeared that can solve SDP problems efficiently. Also, several program packages are freely available, for example, CVX, SeDuMi, and YALMIP. Usually, the optimum of (PR) will provide a lower bound on the optimum of (P). However, the specific structure of (PR) enables us to have the following remarkable result [2, 3]. The problem (PR) does always have at least one optimal solution where all Gk(k=1,…,K) are rank one. This result shows that (PR) is not only a semidefinite relaxation, but also an equivalent reformulation of the problem (P) [2, 3].


## 2.3. Robust Transmit Beamforming Problem

In wireless systems, CSI at the transmitter is either estimated via uplink training or acquired through receivers’ feedback. Hence, it is inevitable to have CSI errors in practice due to the finite-length training data or due to the limited quantization feedbacks. Leth~k (k=1,…,K) denote the obtained channel estimates at the transmitter. The channel vector hk lies within a ball with radius ϵk around the estimated channel vector h~k; that is,
(4)hk∈Uk={h~k+δk∣∥δk∥≤ϵk}
for all k=1,…,K, where δk∈CM is the channel estimation error whose norm is assumed to be bounded by ϵk. With the imperfect CSI, the standard transmit beamforming designs in (P) may no longer guarantee the desired SINR specifications in (3), and therefore the SINR outage may occur.When the optimization problem is in the face of data uncertainty in the constraints, robust optimization is one of the powerful deterministic approaches. Within the framework of robust optimization method, the robust counterpart is presented as follows:(RP)min{gk}k=1K∈CM∑k=1K‍∥gk∥2dds.t.dddd|hkHgk|2∑i≠k|hkHgi|2+σk2≥γk,∀hk∈Uk,dddddddddk=1,…,K.
The problem (RP) aims to find a most power-efficient beamforming design that guarantees the receiver k a 100% SINR satisfaction probability for all uncertain cases of {hk}. It is seen that this formulation is a conservative approach. Solving problem (RP) is a challenging task because the problem has infinite number of deterministic SINR constraints and is nonconvex. Similar to the method in deterministic case, the problem (RP) can be rewritten into the following form:
(RPE)min{Gk}k=1K∑k=1K‍Tr(Gk)s.t.ffffffffhkHGkhk∑i≠khkHGihk+σk2≥γk,∀hk∈Uk,dddddddGk=gkgkH,k=1,…,K.
By replacing these nonconvex constraints Gk=gkgkH by the following constraint:Gk⪰0, then we can obtain the following convex relaxation programming:
(RPR)min{Gk}k=1K∑k=1K‍Tr(Gk)s.t.ddddhkHGkhk∑i≠khkHGihk+σk2≥γk,∀hk∈UkddddddGk⪰0,k=1,…,K.
Since the problem (RPR) aims to find the most power-efficient beamforming design that guarantees the receiver k a 100% SINR satisfaction probability for all uncertain cases of {hk}, then the question whether the (RPR) is feasible is highly related to the bound ϵk which is bounding the channel estimation error δk. The following lemma provides a necessary condition for the feasibility of the problem (RPR).Lemma 1.
If the(RPR) problem is feasible, then it must hold that ϵk<∥h~k∥2 for all k=1,…,K.Proof.
Suppose that there exists an indexk0 such that ϵk0≥∥h~k0∥2. Since (RPR) is feasible, then for k=k0, it must hold that
(5)hk0HGk0hk0∑i≠k0hk0HGihk0+σk02≥γk0,∀hk0∈Uk0.
Note that ϵk0≥∥h~k0∥2, then by choosing δk0=-h~k0, we have ∥δk0∥=∥h~k0∥≤ϵk0. So we derive an instance hk0′=δk0+h~k0=0 with hk0′∈Uk0. Substituting hk0′=0 into the left side of the above inequality, it is easy to result in a contradiction.Obviously, the same results as those of Lemma1 hold for (RP).


## 3. SDP Relaxation for Problem(RP)

In this section, we will present the SDP relaxation problem denoted by(SDR) for handling problem (RP) efficiently. We adopt the same formulation of the SDP relaxation with that in [17]. Then some properties for (SDR) will be explored, especially the properties at the optimal solution. In the next section, based on these properties, we will show that (SDR) will yield rank-one solutions under proper assumption and then provide globally optimal solutions of (RP).In the previous section, a convex relaxation programming(RPR) is derived. Note that the (RPR) problem has an infinite number of linear inequality constraints. Such an infinite number of inequalities can be turned to a finite number of linear matrix inequalities (LMIs), by using the following S-procedure [19, 20].Lemma 2 (S-procedure).
LetA, C∈Hn×n be complex Hermitian matrices, and b∈Cn, c∈R. The following condition
(6)eHAe+bHe+eHb+c≥0,∀eHCe≤1,
holds if and only if there exists a λ≥0 such that
(7)[A+λCbbHc-λ]⪰0.By applying Lemma2 to the constraints in (RPR), one can reformulate problem (RPR) equivalently as
(SDR)min{αk}k=1K,{gk}k=1K∑k=1K‍Tr(Gk)dds.t.ddddddddαk≥0dddddddddddd[Xk+αkIXkh~kh~kHXkHh~kHXkh~k-σk2-αkϵk2]⪰0,dddddddddddddGk⪰0,k=1,…,K,
where Xk=(1/γk)Gk-∑i≠k‍Gi. One can see that problem (SDR) has a linear objective function and convex constraints. So the problem (SDR) is a SDP relaxation to the problem (RP) and also is a convex SDP problem. This means that any local minima must be a global minima and the set of optimal solutions is convex. It is known that the problem (SDR) can be efficiently solved by CVX, SeDuMi, or YALMIP solvers.Before we finish this section, we explore some more properties of(RPR) or (SDR) (noting that these two problems are equivalent), especially at the optimal solution. Define
(8)fk(δk)=(h~k+δk)H(1γkGk-∑i≠k‍Gi)(h~k+δk)-σk2.
Equivalently, we have
(9)fk(δk)=[δkH1][XkXkh~kh~kHXkHh~kHXkh~k-σk2][δkH1]T.
By reformulating the constraints in (RPR), we can see that the constraint in (RPR) is equivalent to
(10)fk(δk)≥0,∀∥δk∥2≤ϵk2.
For simplification during the proof, denote
(11)Pk=[Xk+αkIXkh~kh~kHXkHh~kHXkh~k-σk2-αkϵk2].
Also define
(12)fk′(δk)=[δkH1]Pk[δk1];
that is,
(13)fk′(δk)=δkH(Xk+αkI)δk+2h~kHXkδk+h~kHXkh~k-σk2-αkϵk2.
According to the definition fk(δk) in (8), we have
(14)fk′(δk)=fk(δk)+αk(∥δk∥2-ϵk2).
In the following lemma, it will be shown that at the optimal solution for k=1,…,K there must exist δk* such that fk(δk*)=0 and ∥δk*∥2=ϵk2, which implies that fk′(δk*)=0 according to (14).Lemma 3.
Let{αk},{Gk} be any optimal solutions of (SDR). Then for each k=1,…,K, there must exist δk* such that (h~k+δk*)HGk(h~k+δk*)/(∑i≠k‍(h~k+δk*)HGi(h~k+δk*)+σk2)=γk, where ∥δk*∥=ϵk.Proof.
First we will show at the optimal solution there existδk* such that
(15)(h~k+δk*)HGk(h~k+δk*)∑i≠k(h~k+δk*)HGi(h~k+δk*)+σk2=γk
and ∥δk*∥≤ϵk. On the contrary, assume that there exists an index j such that
(16)hjHGjhj∑i≠jhjHGihj+σj2>γj,∀hj∈Uj={h~j+δj∣∥δj∥≤ϵj}.
Note that Uj is a compact set, then there must exist h^j∈Uj such that at this instance, the ratio function hjHGjhj/(∑i≠j‍hjHGihj+σj2) can attain its minimum over the compact set Uj. From (16), this implies that
(17)h^jHGjh^j∑i≠jh^jHGihj+σj2=minhj∈UjhjTGjhj∑i≠jhjHGihj+σj2>γj.
Let h^jTGjh^j/(∑i≠j‍h^jHGihj+σj2)=tjγj, then obviously tj>1. Then, a new point {Gk′} will be constructed as follows:
(18)Gk′={Gk′=1tjGk,k=j,Gk′=Gk,k≠j.
Next we will show the feasibility of {Gk′} in (RPR). Obviously Gk′⪰0, so it is just necessary to show that for k=1,…,K, the following inequalities hold in (RPR):
(19)hkHGk′hk∑i≠khkHGi′hk+σk2≥γk,∀hk∈Uk.
For k=j, according to the definition of tj, it holds that forallhk∈Uk,
(20)hkHGk′hk∑i≠khkHGi′hk+σk2=(1/tk)hkHGkhk∑i≠khkHGihk+σk2≥γk.
For k≠j, it holds that forallhk∈Uk,
(21)hkHGk′hk∑i≠khkHGi′hk+σk2≥hkHGkhk∑i≠khkHGihk+σk2≥γk.
The above discussion shows that Gk′ is a feasible point of (RPR). Also from the construction of {Gk′}, it is easy to see that ∑k=1K‍Tr(Gk′)<∑k=1K‍Tr(Gk), which contradicts the assumption that {Gk} is the optimal solution to (RPR). So, for any solution {Gk}, for each k=1,…,K, there exist a δk*∈CM such that
(22)(h~k+δk*)HGk(h~k+δk*)∑i≠k(h~k+δk*)HGi(h~k+δk*)+σk2=γk,
which also means that fk(δk*)=0.
Next we just need to show∥δk*∥=ϵk. Note that the problem (RPR) is equivalent to the problem (SDR); then the solution {αk},{Gk} is also the solution of (SDR). So we have Pk⪰0. Then it holds that
(23)fk′(δk*)=[δk*H1]Pk[δk*H1]H=fk(δk*)+αk(∥δk*∥2-ϵk2)≥0.
Noting the fact that fk(δk*)=0, we have αk∥δk*∥2-αkϵk2≥0. Since ∥δk*∥2≤ϵk2, αk≥0, then we can get
(24)αk∥δk*∥2-αkϵk2=0.
If αk=0, noting the fact that Pk⪰0, we have
(25)[XkXkh~kh~kHXkHh~kHXkh~k-σk2]⪰0.
Note that
(26)fk(δk*)=[δk*T1][XkXkh~kh~kHXkHh~kHXkh~k-σk2][δk*T1]T=0.
Then
(27)[XkXkh~kh~kHXkHh~kHXkh~k-σk2][δk*1]=0.
It follows that Xk(δk*+h~k)=0 which means that
(28)fk(δk*)=(δk*+h~k)HXk(δk*+h~k)-σk2=-σk2<0.
This contradiction shows that αk>0. Then, from (24), we have that ∥δk*∥=ϵk. This completes the proof.Note that the vectorδk* may not be unique; then we can collect all these vectors as a set Λk where
(29)Λk={δk*|∥δk*∥=ϵk,(h~k+δk*)HGk(h~k+δk*)∑i≠k(h~k+δk*)HGi(h~k+δk*)+σk2=γk}.From Lemma3, since at δk*, the constraint is active, then the function value fk(δk) at point δk* is zero; that is,
(30)fk(δk*)=δk*HXkδk*+2hkTXkδk*+hkHXkhk-σk2=0.
So we can conclude that at any solution {Gk},{αk} of (SDR), any point in the set Λk must be the optimal solution of the following nonconvex quadratic programming (QPk) where k=1,…,K:
(31)minfk(δk)=[δkH1][XkXkh~kh~kHXkHh~kHXkh~k-σk2][δkH1]Tss.t.∥δk∥2=ϵk2,
where Xk=(Gk/γk)-∑i≠k‍Gi and the optimal value of (QPk) is 0.In the above lemma, we just discuss the existence ofδk*. In the following lemma, we will explore more properties about these vectors.Lemma 4.
Let{αk},{Gk} be any optimal solutions of (SDR); then it holds that rank(Xk+αkI)=rankPk, and for any δk*∈Λk*, δk* is not in the null space of Xk+αkI.Proof.
Let{αk},{Gk} be any optimal solutions of (SDR); then Pk⪰0. From Lemma 3, it is easy to see that for any δk*∈Λk,
(32)fk′(δk*)=[δk*H1]Pk[δk*H1]H=fk(δk*)+αk(∥δk*∥2-ϵk2)=0.
Then, it holds that [δk*H1]Pk=0, which implies that the last row [h~kHXkHh~kHXkh~k-σk2-αkϵk2] in the matrix Pk can be linearly expressed by the row vectors of the matrix [Xk+αkIXkh~k], so rankPk=rank[Xk+αkIXkh~k]. Also, noting that Pk[δk*1]=0, Xkh~k can be linearly expressed by the column vectors of Xk+αkI, so
(33)rank[Xk+αkIXkh~k]=rank(Xk+αkI).
Then, we have rank(Xk+αkI)=rankPk.
Next we will prove the second conclusion of this lemma. On the contrary, if there existsδk*∈Λk which is in the null space of Xk+αkI, then from Pk[δk*1]=0, it holds that Xkh~k=0 which implies that
(34)h~kHXkh~k-σk2-αkϵk2=-σk2-αkϵk2<0.
This contradicts the fact Pk⪰0.The main goal of the next two lemmas is to construct a basis of the null space of the matrixPk(k=1,…,K) related to the optimal solution. These results will be prepared for proving the tightness of the (SDR) in the next section.Lemma 5.
Let{αk},{Gk} be any optimal solutions of (SDR), and let the vectors β1k,β2k,…,βtkk be a basis for the null space of Xk+αkI; then for any δk*∈Λk, the set of vectors
(35)[δk⋆1],[β1k0],…,[βtkk0]
forms a basis for the null space of the matrix Pk(k=1,…,K).Proof.
From Lemma3, for any δk*∈Λk, we have fk(δk*)=0 and fk′(δk*)=0. Noting that Pk⪰0, then for k=1,…,K,δk* must be the optimal solution to the convex programming
(36)minfk′(δk).
Then
(37)∇fk′(δk*)=(Xk+αkI)δk*+Xkh~k=0.
From the assumption that the set of vectors β1k,β2k,…,βtkk forms a basis for the null space of Xk+αkI, then
(38)(Xk+αkI)βik=0,i=1,…,tk.
From (37), we have
(39)(Xk+αkI)(βik+δk*)+Xkh~k=0,i=1,…,tk;
that is,
(40)∇fk′(βik+δk*)=(Xk+αkI)(βik+δk*)+Xkh~k=0.
From the optimality condition for convex programming (36), the vectors βik+δk*(i=1,…,tk) are also the optimal solutions for (36); that is,
(41)fk′(βik+δk*)=0,i=1,…,tk.
Since Pk⪰0, then
(42)Pk[βik+δk*1]=0,
which implies that
(43)Pk[βik+δk*1]-Pk[δk*1]=Pk[βik0]=0.
From Lemma 4, it is known that δk* is not in the null space, then the family of vectors δk*,β1,…,βtk is linearly independent, which also means that the family of vectors (35) is linearly independent. From Lemma 4, rank(Xk+αkI)=M-tk=rank(Pk). So the dimension of the null space of Pk is M+1-rank(Pk)=tk+1. Then, we can conclude that the set of vectors (35) is a basis for the null space of Pk.In the above Lemma5, we construct a basis for the null space of Pk; then in the next lemma, under proper assumption, we can derive an orthogonal basis for the null space of Pk related to any optimal solution. Let {αk},{Gk} be any optimal solutions of (SDR). Before we present the lemma, the following assumption will be given.Assumption A.
There exists a uniqueδk* such that ∥δk*∥=ϵk and
(44)(h~k+δk*)HGk(h~k+δk*)∑i≠k(h~k+δk*)HGi(h~k+δk*)+σk2=γk.
Note that in Lemma3, we have proved the existence of δk* which satisfies the conditions in Assumption A. But in Assumption A, we restrict that the δk* is unique. Equivalently, Assumption A can be rewritten as the following Assumption B.Assumption B.
Assume that the setΛk is a single point.
Also, we have Assumption C equivalently.Assumption C.
Assume that for anyk=1,…,K, the following nonconvex quadratic programming with one equality constraint has unique solution:
(45)minfk(δk)=[δkH1][XkXkh~kh~kHXkHh~kHXkh~k-σk2][δk1].ss.t.dddd∥δk∥2=ϵk2.
Note that the above Assumptions A, B, and C are equivalent. Under any assumption, we can construct an orthogonal basis for Pk. This result is described in the following lemma.Lemma 6.
Let{αk},{Gk} be any optimal solutions of (SDR). Assume that Assumption A holds, and let the set of vectors β1k,β2k,…,βtkk be an orthogonal basis for the null space of Xk+αkI; then the set of vectors [δk⋆1],[β1k0],…,[βtkk0] must be an orthogonal basis for the null space of Pk.Proof.
From Lemma5, it is easy to see that the set of vectors [δk⋆1],[β1k0],…,[βtkk0] is a basis for the null space of Pk. Noting that the set of vectors β1k,β2k,…,βtkk is an orthogonal basis for the null space of Xk+αkI, it is just necessary to show that δk⋆ is orthogonal to βjk(j=1,…,tk). On the contrary, if δk⋆ is not orthogonal to βjk, then let l=-2δk*Hβjk/∥βjk∥2. Obviously l≠0. It is also easy to check that
(46)∥δk*+lβjk∥2=(δk*+lβjk)H(δk*+lβjk)=ϵk2.
From the proof of Lemma 5, it holds that
(47)Pk[δk*+lβjk1]=0;
then we have
(48)[(δk*+lβjk)H1]Pk[δk*+lβjk1]=0.
So fk′(δk*+lβjk)=[(δk*+lβjk)H1]Pk[δk*+lβjk1]=0. From (46), we have fk(δk*+lβjk)=0, which contradicts Assumption A. Then, δk* must be orthogonal to βik(i=1,…,tk). This completes the proof.


## 4. Tightness of SDR

In order to prove the tightness of(SDR), we need to pay more attention to the dual of the problem (SDR). So firstly we write down the dual of the problem (SDR) denoted by (D-SDR) as follows:
(49)max{λk}k=1K,{yk}k=1K,{Yk}k=1K∑k=1K‍λkσk2ddddd.s.t.sssssssssssλkϵk2-Tr(Yk)≥0,sssssssssssssssssssss[YkykykHλk]⪰0.sssssssssssssssssssssZk=I-1γkssssssssssssssssssssssssss×(Yk+ykh~kH+h~kykH+λkh~kh~kH)ssssssssssssssssssssssssss+∑i≠k‍(Yi+yih~iH+h~iyiH+λih~ih~iH)sssssssssssssssssssssss⪰0,k=1,…,K.From [17], one can see that the dual problem (D-SDR) has the following properties.Proposition 7.
There always exists strictly feasible point for problem (D-SDR).From Proposition7, the feasible region of (D-SDR) has nonempty interior. If, in addition, the primal (SDR) also has nonempty interior, then the following strong duality holds between (SDR) and (D-SDR). Let zP* and zD* denote the optimal objective function values of (SDR) and (D-SDR). Suppose that there exists a strict feasible point for (SDR). Then both (SDR) and (D-SDR) attain their optimal values, and zP*=zD*.From the optimality conditions of convex programming, assume that the problem(SDR) is strictly feasible; then {Gk},{αk} is the solution of (SDR) if and only if there exist {Uk},{Zk},{λk} satisfying the following KKT condition:
(50)Gk⪰0,Pk=[Xk+αkIXkh~kh~kHXkHh~kHXkh~k-σk2-αkϵk2]⪰0,αk≥0,Uk=[YkykykHλk]⪰0,Zk=I-1γk(Yk+ykh~kH+h~kykH+λkh~kh~kH)+∑i≠k‍(Yi+yih~iH+h~iyiH+λih~ih~iH)⪰0,λkϵk2-Tr(Yk)≥0,αk(λkϵk2-Tr(Yk))=0,Tr(PkUk)=0,Tr(GkZk)=0.Based on the above results, under proper assumption, we can show the tightness of the problem(SDR) in the following theorem.Theorem 8.
Let{Gk},{αk} be the optimal solution to (SDR). Assume that the problem (SDR) is strictly feasible and Assumption A holds; then {Gk} must be rank one.Proof.
From Lemma6, we have known that the set of vectors [δk*1], [β1k0],…,[βtkk0] is the orthogonal basis for the null space of Pk where the set of vectors [β1k0],…,[βtkk0] is the orthogonal basis for the null space of Xk+αkI. From the complementarity slackness conditions in the KKT condition, it holds that Tr(PkUk)=0. Since Uk⪰0, then obviously Uk can be expressed as Uk=EΨkEH, where Ψk={ψij}(tk+1)×(tk+1), and
(51)E=[Eme],Em=[δk*β1kβ2k⋯βtkk],e=[100⋯0]. So it follows that
(52)Uk=[EmΨkEmHEmΨkeeΨkEmHeΨkeH]=[YkykykHλk].
Obviously, λk=eΨkeH=ψ11, and Yk=EmΨkEm. Noting that the vectors δk*,β1k,…,βtkk are orthogonal, then it holds that Tr(Yk)=Tr(EmΨkEmH)=Tr(ΨkEmHEm)=λkϵk2+Σi=2tk+1ψii∥βi-1k∥2. From the KKT condition, since λkϵk2-Tr(Yk)≥0, then it must hold that ψii=0, i≥2. Noting that Ψk is positive semidefinite, then it is easy to derive the concrete expression of Ψk as follows:
(53)Ψk=[λk0⋯000⋯0⋮⋮⋱00000],
which implies that Yk=λkδk*δk*H and Uk=[λkδk*δk*Hλkδk*λkδk*Hλk]. Then, the matrix Zk can be expressed in the following form:
(54)Zk=I-1γkλk(h~k+δk*)(h~k+δk*)H+∑i≠k‍λi(h~i+δi*)(h~i+δi*)H.
Considering the rank of Zk, the following result can be derived RankZk≥Rank(I+∑i≠k‍λi(h~i+δi*)(h~i+δi*)H)-Rank((1/γk)λk(h~k+δk*)(h~k+δk*)H)≥M-1. Since {Gk} is the solution to (SDR), then Rank(Gk)≥1 obviously. According to the complementarity slackness condition Tr(ZkGk)=0 in the KKT condition, we have RankZk≤M-1. So it follows that RankZk=M-1, and then RankGk=1. This completes the proof.From Theorem8, it is easy to see that if (SDR) is strictly feasible, then under Assumption A, the dual problem (D-SDR) is equivalent to the following instance problem denoted by (D-SDR′):
(55)max∑k=1K‍λkσk2s.t.ssdsλk≥0,ssssdssZk=I-1γkλk(h~k+δk*)(h~k+δk*)Hsssssdsssss+∑i≠k‍λi(h~i+δi*)(h~i+δi*)H⪰0,ssssssdsssssssssssssssssssssssssk=1,…,K.
Also note that the dual of this deterministic problem (D-SDR′) has the following form:
(SDR′)min{Gk}k=1K∑k=1K‍Tr(Gk)s.t.sssss(h~k+δk*)HGk(h~k+δk*)∑i≠k(h~k+δk*)HGi(h~k+δk*)+σk2≥γk,dddddddGk⪰0,k=1,…,K.
It is known in [2] that the deterministic problem (SDR′) does always have at least one optimum solution where all Gk have rank one which also shows that (SDR′) is actually an equivalent reformulation of (D-SDR′). So we can conclude that under proper assumption, (SDR) always yields rank-one optimal solution, which implies that an optimal solution of (RP) can always be obtained from an instance problem (SDR′).


## 5. Simulation Results

In this section, some simulation results are presented to illustrate the correctness of our conclusions and the performance of the proposedSDR method. In the simulations, the base station has four antennas (i.e., M=4) and serves four users (i.e., K=4); the channel coefficients are i.i.d complex Gaussian random variables with zero mean and unit variance. The channel uncertainty bounds ϵk are all 0.01; the noise variances of all users are set equally to be 0.1. We also assume that the stations have the same target SINRs; that is, γ1=γ2=γ3=γ4=γ.In the first experiment, we investigate the feasibility rate of theSDR. For each data point of γ, we generate 500 realizations of the channel estimates {h~i}i=14. Figure 1 displays the simulation results. As seen, the feasibility rate of SDR will decrease as the value of γ increases. The value of γ is chosen as 1,2,3,4,5,6,7,8,9.Figure 1
Feasibility rate (%) versus target SINR γ.In the second experiment, we examine whether Assumption A (or equivalently B, C) holds in Theorem8. As we know, if at the optimal solution {Gk}{αk}, the matrix Xk+αkI is positive definite, then it is obvious that the assumption holds. So we just need to identify whether the solution matrix Xk+αkI is positive definite. In our numerical experiment, for each data point of γ, and the above generated 500 realizations of {h~i}14, we calculate the minimum of all smallest eigenvalues of Xk+αkI for k=1,…,4. Figure 2 displays that all the matrices Xk+αkI are positive definite in all cases when YALMIP can find the solution of SDR.Figure 2
Smallest eigenvalue ofXk+αkI versus target SINR γ.To demonstrate the tightness ofSDR method, we compute the second eigenvalue defined as τ=maxk=1,2,3,4τ2(Gk) where τ2(Gk) denotes the second largest eigenvalue of Gk. For each data point of γ, and the generated 500 realizations, the simulation result is shown in Figure 3. Figure 3 displays that the maximum of all the second largest eigenvalue of Gk is very close to zero, which means that the solution of the SDR method is indeed rank one combining the fact in the second experiment that the assumption holds in this simulation. From Figure 3, we see that when γ=1 or 2, we have τ=0.1052*10-3 and 0.377*10-4. From theoretical aspect, the value of τ should exactly be zero since Xk+αkI is positive definite. It is the computation error that result in this phenomenon, especially when the value of γ is small.Figure 3
Second eigenvalueτ versus target SINR γ.For fixedγk=1(k=1,2,3,4), we also assume that the stations have the same error bound; that is, ϵ1=ϵ2=ϵ3=ϵ4=ϵ. It is obvious that probability of rank-one solution against the error bound ϵ decreases as the ϵ increases. To show this, we let the value of ϵ be chosen as 0.05, 0.1, 0.15, 0.2, and 0.25. We demonstrate the probability of the rank-one solution in the 500 realizations of the channel estimates against the error bound. In Figure 4, we can see that the probability of the rank-one solution decreases remarkably as the ϵ increases.Figure 4
Probability of rank-one solution against the error boundϵk.At last, we provide a counterexample whose solutions are not rank one. In this counterexample, the three channel vectors areh~1=[0.7063-1.0078i-0.9102-0.0127i-0.5121-0.9088i], h~2=[0.3312-0.7232i-0.8027+0.5017i0.5206+0.5656i], and h~3=[0.1859-0.1013i0.4601-0.1435i0.2953+0.2650i] with SINR requirement γ1=γ2=γ3=1 and σ1=σ2=σ3=1, ϵ1=ϵ2=ϵ3=0.3. The best objective value is 427.109965. But the eigenvalue of G3 is [0.000165.7194147.2167]T.The existence of counterexample shows that the guess that the solutions of the(SDR) must be rank one is wrong, except that some assumptions (such as the one proposed in this paper) hold.In our simulation, we focus on the performance of SDP relaxation method; that is, under proper assumptions, the(SDR) always yields rank-one solution, which also means that the (SDR) can provide globally optimum solutions of the primal robust transmit beamforming problem.


## 6. Conclusion

This paper considers the SDP relaxation to the robust beamforming problem. The main contribution is to get a sufficient condition which can assure the tightness of the SDP relaxation. This condition is that at the optimal solution, there exists a unique error vectorδk* which satisfies some necessary conditions. From the simulation, it can be seen that in most cases of the 500 realizations of the channel estimates this condition holds when the rank-one solution is achieved. This phenomenon inspires us to get more insight into what is happening here at the optimal solution. We also think it is possible to use these conditions to generate some other conditions that are easier to use in practice. This will be a research direction in the future.



---

*Source: 508014-2013-11-24.xml*