# Patent

## Title
Monotonic optimization method for achieving the maximum weighted sum-rate in multicell downlink MISO systems

## Abstract

A monotonic optimization method is for achieving the maximum weighted sum-rate in multicell downlink MISO systems. It belongs to the wireless communications field. The weighted sum-rate maximization is viewed as a monotonic optimization problem over the achievable rate region. A sensible search scheme, a sequential partition method as well as a vertex relocation method are designed to reduce the complexity and accelerate the convergence.

## Background
CROSS REFERENCE OF RELATED APPLICATION
This is a U.S. National Stage under 35 U.S.C 371 of the International Application PCT/CN2012/001585, filed Nov. 26, 2012, which claims priority under 35 U.S.C. 119(a-d) to CN 201210359384.7, filed Sep. 24, 2012.
BACKGROUND OF THE PRESENT INVENTION
1. Field of Invention
The present invention describes a monotonic optimization method for achieving the maximum weighted sum-rate in multicell downlink MISO systems, which is a technique of wireless communications.
2. Description of Related Arts
Coordinated multicell downlink transmission is a promising technique for suppressing co-channel interference and improving the system performance. Among the different kinds of design criteria, weighted sum-rate maximization is an active research topic, which has attracted significant attention from both academics and industries. However, achieving the global optimum is very difficult as the capacity region remains unknown. A more pragmatic method that adopts single-user detection by simply treating interference as noise has stimulated some efficient algorithms.
In the conventional techniques, the reference L. Venturino, N. Prasad, and X. Wang, “Coordinated linear beamforming in downlink multi-cell wireless networks,” IEEE Transactions on Wireless Communications, vol. 9, no. 4, pp. 1451-1461, April 2010, presents an iterative coordinated beamforming algorithm to solve the Karush-Kuhn-Tucker conditions of the weighted sum-rate maximization problem.
The reference Q. J. Shi, M. Razaviyayn, Z. Q. Luo, and C. He, “An iteratively weighted MMSE approach to distributed sum-utility maximization for a MIMO interfering broadcast channel,” IEEE Transactions on Signal Processing, vol. 59, no. 9, pp. 4331-4340, September 2011, proposes a weighted minimum mean square error method which iteratively update the transmitter, the receiver and the weight matrix.
However, the achievable rate region under single-user detection remains non-convex. For MISO systems, the reference R. Zhang and S. G. Cui, “Cooperative interference management with MISO beamforming,” IEEE Transactions on Signal Processing, vol. 58, no. 10, pp. 5454-5462, October 2010, proves that beamforming techniques can achieve the Pareto-optimal points and describes a method to characterize the Pareto-boundary of the achievable rate region. Although there are already some techniques obtaining Pareto-optimal solutions, it is still a big challenge to search for the global optimality.
The reference L. Liu, R. Zhang, and K. Chua, “Achieving global optimality for weighted sum-rate maximization in the K-user Gaussian interference channel with multiple antennas,” IEEE Transactions on Wireless Communications, vol. 11, no. 5, pp. 1933-1945, 2012, views the weighted sum-rate maximization as a monotonic optimization problem and adopts the outer polyblock approximation algorithm combined with the rate profile technique to approaching the global optimal solution. To improve the efficiency of the monotonic optimization, another reference E. Bjornson, G. Zheng, M. Bengtsson, and B. Ottersten, “Robust monotonic optimization framework for multicell MISO systems,” IEEE Transactions on Signal Processing, vol. 60, no. 5, pp. 2508-2523, 2012, provides a branch-reduce-and-bound based method. Although it converges faster than the outer polyblock approximation algorithm, it still needs too many iterations as the number of users increase.
SUMMARY OF THE PRESENT INVENTION
Based on the conventional techniques, the present invention proposes a novel monotonic optimization method to achieve the maximum weighted sum-rate in multicell downlink MISO systems. The present invention utilizes a sensible search scheme, a sequential partition method and a vertex relocation method to accelerate the convergence.
The present invention is implemented as the following steps of:
Step 1: setting system parameters comprising: a cell/base station number M, a user number in an m-th cell Km, an antenna number of an m-th base station Tm, a maximum transmission power of the m-th base station Pm, wherein m=1, . . . ,M, a 1 by Tn channel vector from a n-th base station to an mk-th user (i.e. the k-th user in the m-th cell) hmk,n, wherein m,n=1, . . . , M, k=1, . . . , Km, a variance of a zero-mean complex Gaussian additive noise at the mk-th user σmk2, a weight of the mk-th user αmk, wherein m=1, . . . , M, k=1, . . . , Km;
Step 2: defining Rmk as a rate of the mk-th user,




  
    R
    
      m
      k
    
  
  =
  
    
      log
      2
    
    (
    
      1
      +
      
        
          
            
            
              
                h
                
                  
                    m
                    k
                  
                  ,
                  m
                
              
              ⁢
              
                w
                
                  m
                  k
                
              
            
            
          
          2
        
        
          
            
              ∑
              
                
                  (
                  
                    n
                    ,
                    j
                  
                  )
                
                ≠
                
                  (
                  
                    m
                    ,
                    k
                  
                  )
                
              
            
            ⁢
            
              
                
                
                  
                    h
                    
                      
                        m
                        k
                      
                      ,
                      n
                    
                  
                  ⁢
                  
                    w
                    
                      n
                      j
                    
                  
                
                
              
              2
            
          
          +
          
            σ
            
              m
              k
            
            2
          
        
      
    
    )
  




wherein wmk is the Tm by 1 beamformer for the mk-th user, wherein m=1, . . . , M, k=1, . . . , Km;

formulating a achievable rate vector




  r
  =
  
    
      (
      
        
          R
          
            1
            1
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          R
          
            1
            
              K
              1
            
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          R
          
            M
            1
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          R
          
            M
            
              K
              M
            
          
        
      
      )
    
    ∈
    
      R
      +
      K
    
  




as well as a weighted sum-rate function





  
    
      f
      ⁡
      
        (
        r
        )
      
    
    =
    
      
        ∑
        
          m
          ,
          k
        
      
      ⁢
      
        
          α
          
            m
            k
          
        
        ⁢
        
          R
          
            m
            k
          
        
      
    
  
  ,




wherein ε+K indicates that r is a positive real vector of a length K with K=Σm=1MKm;

Step 3: defining a box [a,b]={xε+K|a≦x≦b}; initializing the set of boxes as ={[0,b0]}; assuming K0=0, a (Σi=0m−1Ki+k)-th element (associated with the mk-th user) of b0 is log2(1+Pm∥hmk,mH∥2/σmk2), wherein m=1, . . . , k=1, . . . , Km; setting a termination accuracy η and a line search accuracy δ;
Step 4: initializing an upper bound fmax and a lower bound fmin of the weighted sum-rate, wherein

fmax=f(b0), fmin=max(α·b0)

wherein α is a weight vector comprising weights for all the users, i.e.





  
    α
    =
    
      
        (
        
          
            α
            
              1
              1
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            α
            
              1
              
                K
                1
              
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            α
            
              M
              1
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            α
            
              M
              
                K
                M
              
            
          
        
        )
      
      ∈
      
        R
        +
        K
      
    
  
  ;




Step 5: choosing a box [a,b] from that satisfies f(b)=fmax, and then checking feasibility of a: whether a locates in a achievable rate region or not; wherein the feasibility is determined via a problem φ(a);

    
    
        the specified problem φ(a) is:
        
            maximize 0
            subject to √{square root over (βmk)}∥Amkx+nmk∥≦√{square root over (1+βmk)}(hmk,mSmkx),∀m,k
            
                pTx=0
                ∥Gmx∥≦√{square root over (Pm)},∀m

with the following notations

            
            
        
        
    
    






  
    
      x
      m
    
    =
    
      
        [
        
          
            w
            
              m
              1
            
            H
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            w
            
              m
              
                K
                m
              
            
            H
          
        
        ]
      
      H
    
  
  ,
  
    m
    =
    1
  
  ,
  ...
  ⁢
  
    
  
  ,
  M
  ,
  
    

  
  ⁢
  
    x
    =
    
      
        [
        
          
            x
            1
            H
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            x
            M
            H
          
          ,
          0
        
        ]
      
      H
    
  
  ,
  
    
      n
      
        m
        k
      
    
    =
    
      
        [
        
          0
          ,
          
            ...
            ⁢
            
              
            
            ⁢
            0
          
          ,
          
            σ
            
              m
              k
            
          
        
        ]
      
      T
    
  
  ,
  
    

  
  ⁢
  
    
      S
      
        m
        k
      
    
    =
    
      [
      
        0
        ⁢
        
          
        
        ⁢
        0
        ⁢
        
          
        
        ⁢
        ...
        ⁢
        
          
        
        ⁢
        
          I
          
            T
            m
          
        
        ⁢
        
          
        
        ⁢
        ...
        ⁢
        
          
        
        ⁢
        0
      
      ]
    
  
  ,
  
    

  
  ⁢
  
    
      A
      
        m
        k
      
    
    =
    
      diag
      ⁡
      
        (
        
          
            
              
                h
                
                  
                    m
                    k
                  
                  ,
                  1
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                h
                
                  
                    m
                    k
                  
                  ,
                  1
                
              
            
            
              }
              
                K
                1
              
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              
                h
                
                  
                    m
                    k
                  
                  ,
                  M
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                h
                
                  
                    m
                    k
                  
                  ,
                  M
                
              
            
            
              }
              
                K
                M
              
            
          
          ,
          0
        
        )
      
    
  
  ,
  
    

  
  ⁢
  
    
      G
      m
    
    =
    
      
        [
        
          
            S
            
              m
              1
            
            H
          
          ⁢
          ...
          ⁢
          
            
          
          ⁢
          
            S
            
              m
              
                K
                m
              
            
            H
          
        
        ]
      
      H
    
  
  ,
  
    
      β
      
        m
        k
      
    
    =
    
      
        2
        
          a
          
            m
            k
          
        
      
      -
      1
    
  
  ,
  
    p
    =
    
      
        [
        
          0
          ,
          
            ...
            ⁢
            
              
            
            ⁢
            0
          
          ,
          1
        
        ]
      
      T
    
  




wherein σmk is a standard deviation of the zero-mean complex Gaussian additive noise at the mk-th user, ITm denotes a identity matrix with dimension Tm;

Step 6: if the problem φ(a) is feasible, conducting a sensible search scheme for the box [a,b] to obtain a partition point r;
wherein if the problem φ(a) is infeasible, updating the box set as =\[a,b] and calculating the upper bound fmax=max[a,b]εf(b), then going back to the Step 5;
the sensible search scheme is:
denoting lab as the line connecting a and b; finding the intersection point c on the hyperplane {r|f(r)=fmin} with the line lab, i.e.




  c
  =
  
    a
    +
    
      
        (
        
          b
          -
          a
        
        )
      
      ×
      
        
          
            f
            min
          
          -
          
            f
            ⁡
            
              (
              a
              )
            
          
        
        
          f
          ⁡
          
            (
            
              b
              -
              a
            
            )
          
        
      
    
  




checking feasibility of c via the problem φ(a) in the Step 5 with a=c;
wherein if φ(c) is feasible, a bisection line search is conducted along the line lcb to obtain an intersection point on a Pareto-boundary; given a line search accuracy δ, two points rmin and rmax are acquired; the partition point is set as r=rmax while the lower bound is updated as fmin=f(rmin);
if φ(c) is infeasible, just set the partition point as r=c;
Step 7: based on the partition point r, dividing the box [a,b] into K new boxes [a(i),b(i)], i=1, . . . , K using a sequential partition method; then updating the boxes set as




  =
  
    
      \[
      ⁢
      
        a
        ,
        b
      
      ]
    
    ⋃
    
      {
      
        
          ⋃
          
            
              i
              =
              1
            
            ,
            ...
            ⁢
            
              
            
            ,
            K
          
        
        ⁢
        
          [
          
            
              a
              
                (
                i
                )
              
            
            ,
            
              b
              
                (
                i
                )
              
            
          
          ]
        
      
      }
    
  




the sequential partition method is:
i) firstly generating a set of K new vertices {b(1), . . . , b(K)} based on the partition point r, wherein

b(i)=b−(bi−ri)ei, i=1, . . . , K 

wherein the subscript i indicates the i-th element of the vector and ei is a vector with the i-th element being 1 and the others being 0;

ii) sorting the K vertices as {b(i1), . . . , b(iK)} in ascending order of the achievable weighted sum-rate, wherein is denotes an original index of the s-th vertex;
iii) sequentially determining the corresponding vertices {a(i1), . . . , a(iK)} as




  
    a
    
      (
      
        i
        s
      
      )
    
  
  =
  
    {
    
      
        
          
            
              a
              ,
            
          
          
            
              s
              =
              1
            
          
        
        
          
            
              
                
                  a
                  
                    (
                    
                      i
                      
                        s
                        -
                        1
                      
                    
                    )
                  
                
                +
                
                  
                    (
                    
                      
                        r
                        
                          i
                          
                            s
                            -
                            1
                          
                        
                      
                      -
                      
                        a
                        
                          i
                          
                            s
                            -
                            1
                          
                        
                      
                    
                    )
                  
                  ⁢
                  
                    e
                    
                      i
                      
                        s
                        -
                        1
                      
                    
                  
                
              
              ,
            
          
          
            
              s
              >
              1
            
          
        
      
      ;
    
  




Step 8; calculating f(b) for each box [a,b];
wherein if f(b)>fmin, the associated vertex a is relocated as




  
    
      a
      i
    
    =
    
      
        b
        i
      
      -
      
        
          min
          ⁡
          
            (
            
              
                
                  
                    f
                    ⁡
                    
                      (
                      b
                      )
                    
                  
                  -
                  
                    f
                    min
                  
                
                
                  
                    α
                    i
                  
                  ⁡
                  
                    (
                    
                      
                        b
                        i
                      
                      -
                      
                        a
                        i
                      
                    
                    )
                  
                
              
              ,
              1
            
            )
          
        
        ×
        
          (
          
            
              b
              i
            
            -
            
              a
              i
            
          
          )
        
      
    
  
  ,
  
    i
    =
    1
  
  ,
  ...
  ⁢
  
    
  
  ,
  K




wherein, ãi is an i-th element of the relocated vertex;

if f(b)≦fmin, the box [a,b] is removed from the box set, i.e. =\[a,b];
Step 9: resetting the upper bound fmax as fmax=max[a,b]εf(b); and
Step 10: checking a relative error of the upper and lower bound;
wherein if (fmax−fmin)/fmin>η, going back to the Step 5, otherwise, returning fmax and rmin 
The monotonic optimization method proposed in the present invention adopts a sensible search scheme, a sequential partition method and a vertex relocation method to reduce the number of checking feasibility, therefore the computational complexity is decreased and the convergence is accelerated.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is an illustration of an iteration for K=3;
FIG. 2 is a diagram of comparison of convergence performance of the embodiment of the present invention, the conventional outer polyblock approximation method and branch-reduce-and-bound method in the scenario wherein M=3, Km=1, Pm=5, Tm=4;
FIG. 3 is a diagram of comparison of convergence performance of the embodiment of the present invention, the conventional outer polyblock approximation method and branch-reduce-and-bound method in the scenario wherein M=2, Km=2, P=10, Tm=4



DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
The details of the embodiment of the present invention are specified below. The embodiment is based on the technical content of the present invention. The specific implementing process is presented. The scope of the present invention is not limited to the following embodiment.
A weighted sum-rate maximization problem is



  
    
      maximize
      ⁢
      
        
      
      ⁢
      
        
          ∑
          
            m
            ,
            k
          
        
        ⁢
        
          
            α
            
              m
              k
            
          
          ⁢
          
            R
            
              m
              k
            
          
        
      
    
    =
    
      
        ∑
        
          m
          ,
          k
        
      
      ⁢
      
        
          α
          
            m
            k
          
        
        ⁢
        
          
            log
            2
          
          (
          
            1
            +
            
              
                
                  
                  
                    
                      h
                      
                        
                          m
                          k
                        
                        ,
                        m
                      
                    
                    ⁢
                    
                      w
                      
                        m
                        k
                      
                    
                  
                  
                
                2
              
              
                
                  
                    ∑
                    
                      
                        (
                        
                          n
                          ,
                          j
                        
                        )
                      
                      ≠
                      
                        (
                        
                          m
                          ,
                          k
                        
                        )
                      
                    
                  
                  ⁢
                  
                    
                      
                      
                        
                          h
                          
                            
                              m
                              k
                            
                            ,
                            n
                          
                        
                        ⁢
                        
                          w
                          
                            n
                            j
                          
                        
                      
                      
                    
                    2
                  
                
                +
                
                  σ
                  
                    m
                    k
                  
                  2
                
              
            
          
          )
        
      
    
  




  
    
      
    
    ⁢
    
      
        
          subject
          ⁢
          
            
          
          ⁢
          to
          ⁢
          
            
          
          ⁢
          
            
              ∑
              
                k
                =
                1
              
              
                K
                m
              
            
            ⁢
            
              
                
                
                  w
                  
                    m
                    k
                  
                
                
              
              2
            
          
        
        ≤
        
          P
          m
        
      
      ,
      
        ∀
        m
      
    
  



wherein Km is a number of users in an m-th cell, Tm is an antenna number of an m-th base station, Pm denotes a maximum transmission power of the m-th base station, hmk,n, is channel vector from a n-th base station to an mk-th user, σmk2 represents a variance of a zero-mean complex Gaussian additive noise at the mk-th user and αmk is a weight of the mk-th user, wherein m,n=1, . . . , M, k=1, . . . , Km;

The monotonic optimization problem is



  
    
      maximize
      ⁢
      
        
      
      ⁢
      
        f
        ⁡
        
          (
          r
          )
        
      
    
    :=
    
      
        ∑
        
          m
          ,
          k
        
      
      ⁢
      
        
          α
          
            m
            k
          
        
        ⁢
        
          R
          
            m
            k
          
        
      
    
  




  
    
      subject
      ⁢
      
        
      
      ⁢
      to
      ⁢
      
        
      
      ⁢
      r
    
    ∈
    R
  



wherein





  r
  =
  
    
      (
      
        
          R
          
            1
            1
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          R
          
            1
            
              K
              1
            
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          R
          
            M
            1
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          R
          
            M
            
              K
              M
            
          
        
      
      )
    
    ∈
    
      R
      +
      K
    
  




is the achievable rate vector and  denotes the achievable rate region, i.e.





  R
  =
  
    
      ⋃
      
        
          
            
              ∑
              
                k
                =
                1
              
              
                K
                m
              
            
            ⁢
            
              
                
                
                  w
                  
                    m
                    k
                  
                
                
              
              2
            
          
          ≤
          
            P
            m
          
        
        ,
        
          ∀
          m
        
      
    
    ⁢
    
      {
      
        
          
            (
            
              
                r
                
                  1
                  1
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                r
                
                  M
                  
                    K
                    M
                  
                
              
            
            )
          
          |
          
            0
            ≤
            
              r
              
                m
                k
              
            
            ≤
            
              R
              
                m
                k
              
            
          
        
        ,
        
          ∀
          m
        
        ,
        k
      
      }
    
  




The present invention includes the following steps of:
Step 1: setting system parameters comprising: a cell/base station number M, the user number in the m-th cell Km, the antenna number of the m-th base station Tm, the maximum transmission power of the m-th base station Pm, wherein m=1, . . . , M, a 1 by Tn channel vector from the n-th base station to the mk-th user (i.e. the k-th user in the m-th cell) hmk,n, wherein m,n=1, . . . , M, k=1, . . . , Km, the variance of the zero-mean complex Gaussian additive noise at the mk-th user σmk2, the weight of the mk-th user αmk, wherein m=1, . . . , M, k=1, . . . , Km;
In this embodiment, two scenarios are considered: M=3, Km=1, Pm=5, Tm=4 and M=2, Km=2, Pm=10, Tm=4, wherein m=1, . . . , M.
In this embodiment, every entry of hmk,n is a zero-mean unit-variance complex Gaussian random variable, σmk2=1, αmk=1, wherein m,n=1, . . . , M, k=1, . . . , Km.
Step 2: defining Rmk as a rate of the mk-th user,




  
    R
    
      m
      k
    
  
  =
  
    
      log
      2
    
    (
    
      1
      +
      
        
          
            
            
              
                h
                
                  
                    m
                    k
                  
                  ,
                  m
                
              
              ⁢
              
                w
                
                  m
                  k
                
              
            
            
          
          2
        
        
          
            
              ∑
              
                
                  (
                  
                    n
                    ,
                    j
                  
                  )
                
                ≠
                
                  (
                  
                    m
                    ,
                    k
                  
                  )
                
              
            
            ⁢
            
              
                
                
                  
                    h
                    
                      
                        m
                        k
                      
                      ,
                      n
                    
                  
                  ⁢
                  
                    w
                    
                      n
                      j
                    
                  
                
                
              
              2
            
          
          +
          
            σ
            
              m
              k
            
            2
          
        
      
    
    )
  




wherein Wmk is the Tm by 1 beamformer for the mk-th user, wherein m=1, . . . , M, k=1, . . . , Km;

formulating a achievable rate vector




  r
  =
  
    
      (
      
        
          R
          
            1
            1
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          R
          
            1
            
              K
              1
            
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          R
          
            M
            1
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          R
          
            M
            
              K
              M
            
          
        
      
      )
    
    ∈
    
      R
      +
      K
    
  




as well as a weighted sum-rate function





  
    
      f
      ⁡
      
        (
        r
        )
      
    
    =
    
      
        ∑
        
          m
          ,
          k
        
      
      ⁢
      
        
          α
          
            m
            k
          
        
        ⁢
        
          R
          
            m
            k
          
        
      
    
  
  ,




wherein ε+K indicates that r is a positive real vector of a length K with K=Σm=1MKm;

Step 3: defining a box [a,b]={xε+K|a≦x≦b}; initializing the set of boxes as ={[0,b0]}; assuming K0=0, a (Σi=0m−1Ki+k)-th element (associated with the mk-th user) of b0 is log2(1+Pm∥hmk,mH∥2/σmk2), wherein m=1, . . . , k=1, . . . , Km; setting a termination accuracy η and a line search accuracy δ;
In this embodiment, the accuracy parameters are set as η=0.01, δ=0.01.
Since the iterations of the embodiment and the conventional methods are different, it is not meaningful to compare the number of iterations. As the main complexity derives from checking the feasibility of a point, the convergence performance is evaluated as a function of the feasibility checking times. The convergence performance is presented via the relative errors of the upper and lower bound with the optimal value, i.e.

(fmax−fopt)/fopt,(fmin−fopt)/fopt 

wherein fopt is the obtained optimal value of the weighted sum-rate;

Step 4: initializing an upper bound fmax and a lower bound fmin of the weighted sum-rate, wherein

fmax=f(b0), fmin=max(α·b0)

wherein α is a weight vector comprising weights for all the users, i.e.





  
    α
    =
    
      
        (
        
          
            α
            
              1
              1
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            α
            
              1
              
                K
                1
              
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            α
            
              M
              1
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            α
            
              M
              
                K
                M
              
            
          
        
        )
      
      ∈
      
        R
        +
        K
      
    
  
  ;




Step 5: choosing a box [a,b] from that satisfies f(b)=fmax, and then checking feasibility of a: whether a locates in a achievable rate region or not; wherein the feasibility is determined via a problem φ(a);

    
    
        the specified problem φ(a) is:
        
            maximize 0
            subject to √{square root over (βmk)}∥Amkx+nmk∥≦√{square root over (1+βmk)}(hmk,mSmkx),∀m,k
            
                pTx=0
                ∥Gmx∥≦√{square root over (Pm)},∀m

with the following notations

            
            
        
        
    
    






  
    
      x
      m
    
    =
    
      
        [
        
          
            w
            
              m
              1
            
            H
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            w
            
              m
              
                K
                m
              
            
            H
          
        
        ]
      
      H
    
  
  ,
  
    m
    =
    1
  
  ,
  ...
  ⁢
  
    
  
  ,
  M
  ,
  
    x
    =
    
      
        [
        
          
            x
            1
            H
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            x
            M
            H
          
          ,
          0
        
        ]
      
      H
    
  
  ,
  
    
      n
      
        m
        k
      
    
    =
    
      
        [
        
          0
          ,
          
            ...
            ⁢
            
              
            
            ⁢
            0
          
          ,
          
            σ
            
              m
              k
            
          
        
        ]
      
      T
    
  
  ,
  
    

  
  ⁢
  
    
      S
      
        m
        k
      
    
    =
    
      [
      
        0
        ⁢
        
          
        
        ⁢
        0
        ⁢
        
          
        
        ⁢
        ...
        ⁢
        
          
        
        ⁢
        
          I
          
            T
            m
          
        
        ⁢
        
          
        
        ⁢
        ...0
      
      ]
    
  
  ,
  
    
      A
      
        m
        k
      
    
    =
    
      diag
      ⁡
      
        (
        
          
            
              
                h
                
                  
                    m
                    k
                  
                  ,
                  1
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                h
                
                  
                    m
                    k
                  
                  ,
                  1
                
              
            
            
              }
              
                K
                1
              
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              
                h
                
                  
                    m
                    k
                  
                  ,
                  M
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                h
                
                  
                    m
                    k
                  
                  ,
                  M
                
              
            
            
              }
              
                K
                M
              
            
          
          ,
          0
        
        )
      
    
  
  ,
  
    

  
  ⁢
  
    
  
  ⁢
  
    
      G
      
        m
        1
      
    
    =
    
      
        [
        
          
            S
            
              m
              1
            
            H
          
          ⁢
          
            
          
          ⁢
          ...
          ⁢
          
            
          
          ⁢
          
            S
            
              m
              
                K
                m
              
            
            H
          
        
        ]
      
      H
    
  
  ,
  
    
      β
      
        m
        k
      
    
    =
    
      
        2
        
          a
          
            m
            k
          
        
      
      -
      1
    
  
  ,
  
    p
    =
    
      
        [
        
          0
          ,
          
            ...
            ⁢
            
              
            
            ⁢
            0
          
          ,
          1
        
        ]
      
      T
    
  




wherein σmk is a standard deviation of the zero-mean complex Gaussian additive noise at the mk-th user, ITm denotes a identity matrix with dimension Tm;

Step 6: if the problem φ(a) is feasible, conducting a sensible search scheme for the box [a,b] to obtain a partition point r;
wherein if the problem φ(a) is infeasible, updating the box set as =\[a,b] and calculating the upper bound fmax=max[a,b]εf(b), then going back to the Step 5;
the sensible search scheme is:
denoting lab as the line connecting a and b; finding the intersection point c on the hyperplane {r|f(r)=fmin} with the line lab, i.e.




  c
  =
  
    a
    +
    
      
        (
        
          b
          -
          a
        
        )
      
      ×
      
        
          
            f
            min
          
          -
          
            f
            ⁡
            
              (
              a
              )
            
          
        
        
          f
          ⁡
          
            (
            
              b
              -
              a
            
            )
          
        
      
    
  




checking feasibility of c via the problem φ(a) in the Step 5 with a=c;
wherein if φ(c) is feasible, a bisection line search is conducted along the line lcb to obtain an intersection point on a Pareto-boundary; given a line search accuracy δ, two points rmin and rmax are acquired; the partition point is set as r=rmax while the lower bound is updated as fmin=f(rmin);
if φ(c) is infeasible, just set the partition point as r=c;
Step 7: based on the partition point r, dividing the box [a,b] into K new boxes [a(i),b(i)], i=1, . . . , K using a sequential partition method; then updating the boxes set as




  =
  
    
      \[
      ⁢
      
        a
        ,
        b
      
      ]
    
    ⋃
    
      {
      
        
          ⋃
          
            
              i
              =
              1
            
            ,
            ...
            ⁢
            
              
            
            ,
            K
          
        
        ⁢
        
          [
          
            
              a
              
                (
                i
                )
              
            
            ,
            
              b
              
                (
                i
                )
              
            
          
          ]
        
      
      }
    
  




the sequential partition method is:
i) firstly generating a set of K new vertices {b(1), . . . ,b(K)} based on the partition point r, wherein

b(i)=b−(bi−ri)ei, i=1, . . . ,K 

wherein the subscript i indicates the i-th element of the vector and ei is a vector with the i-th element being 1 and the others being 0;

ii) sorting the K vertices as {b(i1), . . . , b(iK)} in ascending order of the achievable weighted sum-rate, wherein is denotes an original index of the s-th vertex;
iii) sequentially determining the corresponding vertices {a(i1), . . . , a(iK)} as




  
    a
    
      (
      
        i
        s
      
      )
    
  
  =
  
    {
    
      
        
          
            
              a
              ,
            
          
          
            
              s
              =
              1
            
          
        
        
          
            
              
                
                  a
                  
                    (
                    
                      i
                      
                        s
                        -
                        1
                      
                    
                    )
                  
                
                +
                
                  
                    (
                    
                      
                        r
                        
                          i
                          
                            s
                            -
                            1
                          
                        
                      
                      -
                      
                        a
                        
                          i
                          
                            s
                            -
                            1
                          
                        
                      
                    
                    )
                  
                  ⁢
                  
                    e
                    
                      i
                      
                        s
                        -
                        1
                      
                    
                  
                
              
              ,
            
          
          
            
              s
              >
              1
            
          
        
      
      ;
    
  




Step 8; calculating f(b) for each box [a,b];
wherein if f(b)>fmin, the associated vertex a is relocated as




  
    
      
        a
        ~
      
      i
    
    =
    
      
        b
        i
      
      -
      
        
          min
          ⁡
          
            (
            
              
                
                  
                    f
                    ⁡
                    
                      (
                      b
                      )
                    
                  
                  -
                  
                    f
                    min
                  
                
                
                  
                    α
                    i
                  
                  ⁡
                  
                    (
                    
                      
                        b
                        i
                      
                      -
                      
                        a
                        i
                      
                    
                    )
                  
                
              
              ,
              1
            
            )
          
        
        ×
        
          (
          
            
              b
              i
            
            -
            
              a
              i
            
          
          )
        
      
    
  
  ,
  
    i
    =
    1
  
  ,
  ...
  ⁢
  
    
  
  ,
  K




wherein ãi is an i-th element of the relocated vertex;

if f(b)≦fmin the box [a,b] is removed from the box set, i.e. =\[a,b];
Step 9: resetting the upper bound fmax as fmax=max[a,b]εf(b); and
Step 10: checking a relative error of the upper and lower bound;
wherein if (fmax−fmin)/fmin>η, going back to the Step 5, otherwise, returning fmin, fmax and rmin.
FIG. 2 compares the convergence performance of the embodiment of the present invention, the conventional outer polyblock approximation method (refer to Polyblock in figure) and branch-reduce-and-bound method (refer to BRB in figure) in the scenario wherein M=3, Km=1, Pm=5, Tm=4;
FIG. 3 compares the convergence performance of the embodiment of the present invention, the conventional outer polyblock approximation method (refer to Polyblock in figure) and branch-reduce-and-bound method (refer to BRB in figure) in the scenario wherein M=2, Km=2, Pm=10, Tm=4.
From FIGS. 2 and 3, it is observed that the embodiment of the present invention converges and achieves the global optimal solution faster compared with the conventional methods.
While only selected embodiment has been chosen to illustrate the present invention, it will be apparent to those skilled in the art from this disclosure that various changes and modifications can be made herein without departing from the scope of the present invention.

## Claims

1. A monotonic optimization method for achieving a maximum weighted sum-rate in a multicell downlink MISO system, wherein the multicell downlink MISO system comprises: cell/base stations, cells, antennas and base stations; the method utilizes a sensible search scheme, a sequential partition method and a vertex relocation method, specifically comprising steps of:
Step 1: setting system parameters by the base stations, wherein the system parameters comprises: a cell/base station number M, a user station number in an m-th cell Km detected by the base stations, an antenna number of an m-th base station Tm, a maximum transmission power of the m-th base station Pm , wherein m=1, . . . ,M, a 1 by Tn channel vector from a n-th base station to an mk -th user station hmk,n, wherein m,n=1, . . . ,M, k=1, . . . ,Km, a variance of a zero-mean complex Gaussian additive noise at the mk -th user station σmk2, a weight of the mk -th user station αmk, wherein m=1, . . . ,M, k=1, . . . ,Km;
Step 2: defining Rmk as a rate of the mk -th user station in the base stations,





  
    R
    
      m
      k
    
  
  =
  
    
      log
      2
    
    (
    
      1
      +
      
        
          
            
            
              
                h
                
                  
                    m
                    k
                  
                  ,
                  m
                
              
              ⁢
              
                w
                
                  m
                  k
                
              
            
            
          
          2
        
        
          
            
              ∑
              
                
                  (
                  
                    n
                    ,
                    j
                  
                  )
                
                ≠
                
                  (
                  
                    m
                    ,
                    k
                  
                  )
                
              
            
            ⁢
            
              
                
                
                  
                    h
                    
                      
                        m
                        k
                      
                      ,
                      n
                    
                  
                  ⁢
                  
                    w
                    
                      n
                      j
                    
                  
                
                
              
              2
            
          
          +
          
            σ
            
              m
              k
            
            2
          
        
      
    
    )
  



wherein Wmk is the Tm by 1 beamformer for the mk -th user station, wherein m=1, . . . ,M,k=1, . . . ,Km;
formulating an achievable rate vector





  r
  =
  
    
      (
      
        
          R
          
            1
            1
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          R
          
            1
            
              K
              1
            
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          R
          
            M
            1
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          R
          
            M
            
              K
              M
            
          
        
      
      )
    
    ∈
    
      R
      +
      K
    
  



 as well as a weighted sum-rate function





  
    
      f
      ⁡
      
        (
        r
        )
      
    
    =
    
      
        ∑
        
          m
          ,
          k
        
      
      ⁢
      
        
          α
          
            m
            k
          
        
        ⁢
        
          R
          
            m
            k
          
        
      
    
  
  ,



 wherein ∈+K indicates that r is a positive real vector of a length K with K =Σm=1M Km;
Step 3: defining boxes [a,b]={x∈+K |a≦x≦b} in the base stations; initializing a box set as N={[0,b0]}; assuming K0 =0, a (Σi=0m−1 Ki+k) -th element (associated with the m k -th user station) of b0 is log2 (1+Pm∥hmk,mH∥2/σmk2), wherein m=1, . . . ,M,k=1, . . . ,Km; setting a termination accuracy η and a line search accuracy δ;
Step 4: initializing an upper bound fmax and a lower bound fmin of the weighted sum-rate by the base stations, wherein


fmax=f(b0), fmin=max(α·b0)


wherein α is a weight vector comprising weights for all user stations,





  
    α
    =
    
      
        (
        
          
            α
            
              1
              1
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            α
            
              1
              
                K
                1
              
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            α
            
              M
              1
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            α
            
              M
              
                K
                M
              
            
          
        
        )
      
      ∈
      
        R
        +
        K
      
    
  
  ;



Step 5: choosing one of the boxes [a,b] from N that satisfies f(b)=fmax by the base stations, and then checking feasibility of a : whether a locates in an achievable rate region or not; wherein the feasibility is determined via a problem φ(a);
Step 6: if the problem φ(a) is feasible, conducting the sensible search scheme for the one of the boxes [a,b] to obtain a partition point r ;
wherein if the problem φ(a) is infeasible, updating the box set as N=N\[a,b] and calculating the upper bound fmax=max[a,b]εNf(b), then going back to the Step 5;
Step 7: based on the partition point r, dividing the the one of the boxes [a,b] into K new boxes [a(i),b(i)], i=1, . . . ,K using the sequential partition method; then updating the box set as





  N
  =
  
    
      N
      ⁢
      
        \[
        ⁢
        
          a
          ,
          b
        
        ]
      
    
    ⋃
    
      {
      
        
          ⋃
          
            
              i
              =
              1
            
            ,
            ...
            ⁢
            
              
            
            ,
            K
          
        
        ⁢
        
          [
          
            
              a
              
                (
                i
                )
              
            
            ,
            
              b
              
                (
                i
                )
              
            
          
          ]
        
      
      }
    
  



Step 8; calculating f(b) for each of the boxes [a,b];
wherein if f(b)>fmin, an associated vertex a is relocated as





  
    
      
        a
        ~
      
      i
    
    =
    
      
        b
        i
      
      -
      
        
          min
          ⁡
          
            (
            
              
                
                  
                    f
                    ⁡
                    
                      (
                      b
                      )
                    
                  
                  -
                  
                    f
                    min
                  
                
                
                  
                    α
                    i
                  
                  ⁡
                  
                    (
                    
                      
                        b
                        i
                      
                      -
                      
                        a
                        i
                      
                    
                    )
                  
                
              
              ,
              1
            
            )
          
        
        ×
        
          (
          
            
              b
              i
            
            -
            
              a
              i
            
          
          )
        
      
    
  
  ,
  
    i
    =
    1
  
  ,
  ...
  ⁢
  
    
  
  ,
  K



wherein ãi is an i-th element of a relocated vertex;
if f(b)≦fmin,the boxes [a,b] is removed from the box set N, i.e. N=N\[a,b];
Step 9: resetting the upper bound fmax as fmax=max[a,b]εNf(b) by the base stations;
Step 10: checking a relative error of the upper and lower bounds by the base stations;
wherein if (fmax−fmin)/fmin>η, going back to the Step 5, otherwise, returning fmin, fmax and rmin; and
Step 11: downlink-communicating with the user stations by the base stations at the defined rates within the upper bound fmax and the lower bound fmin obtained in the Step 10.

2. The monotonic optimization, as recited in claim 1, wherein the problem φ(a) in the Step 5 is:
maximize 0
subject to √{square root over (βmk)}∥Amkx+nmk∥≦√{square root over (1+βmk)}(Hmk,mSmkx), ∀m,k
pTx=0
∥Gmx∥≦√{square root over (Pm)}, ∀m


with following notations




  
    
      x
      m
    
    =
    
      
        [
        
          
            w
            
              m
              1
            
            H
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            w
            
              m
              
                K
                m
              
            
            H
          
        
        ]
      
      H
    
  
  ,
  
    m
    =
    1
  
  ,
  ...
  ⁢
  
    
  
  ,
  M
  ,
  
    x
    =
    
      
        [
        
          
            x
            1
            H
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            x
            M
            H
          
          ,
          0
        
        ]
      
      H
    
  
  ,
  
    
      n
      
        m
        k
      
    
    =
    
      
        [
        
          0
          ,
          
            ...
            ⁢
            
              
            
            ⁢
            0
          
          ,
          
            σ
            
              m
              k
            
          
        
        ]
      
      T
    
  
  ,
  
    

  
  ⁢
  
    
      S
      
        m
        k
      
    
    =
    
      [
      
        0
        ⁢
        
          
        
        ⁢
        0
        ⁢
        
          
        
        ⁢
        ...
        ⁢
        
          
        
        ⁢
        
          I
          
            T
            m
          
        
        ⁢
        
          
        
        ⁢
        ...0
      
      ]
    
  
  ,
  
    
      A
      
        m
        k
      
    
    =
    
      diag
      ⁡
      
        (
        
          
            
              
                h
                
                  
                    m
                    k
                  
                  ,
                  1
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                h
                
                  
                    m
                    k
                  
                  ,
                  1
                
              
            
            
              }
              
                K
                1
              
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              
                h
                
                  
                    m
                    k
                  
                  ,
                  M
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                h
                
                  
                    m
                    k
                  
                  ,
                  M
                
              
            
            
              }
              
                K
                M
              
            
          
          ,
          0
        
        )
      
    
  
  ,
  
    

  
  ⁢
  
    
  
  ⁢
  
    
      G
      
        m
        1
      
    
    =
    
      
        [
        
          
            S
            
              m
              1
            
            H
          
          ⁢
          
            
          
          ⁢
          ...
          ⁢
          
            
          
          ⁢
          
            S
            
              m
              
                K
                m
              
            
            H
          
        
        ]
      
      H
    
  
  ,
  
    
      β
      
        m
        k
      
    
    =
    
      
        2
        
          a
          
            m
            k
          
        
      
      -
      1
    
  
  ,
  
    p
    =
    
      
        [
        
          0
          ,
          
            ...
            ⁢
            
              
            
            ⁢
            0
          
          ,
          1
        
        ]
      
      T
    
  



wherein σmk is a standard deviation of the zero-mean complex Gaussian additive noise at the mk -th user station, ITm denotes a identity matrix with dimension Tm.

3. The monotonic optimization, as recited in claim 1, wherein the sensible search scheme in the Step 6 is:
denoting lab as a line connecting a and b ; finding an intersection point c on the hyperplane {r|f(r)=fmin} with the line lab,





  c
  =
  
    a
    +
    
      
        (
        
          b
          -
          a
        
        )
      
      ×
      
        
          
            f
            min
          
          -
          
            f
            ⁡
            
              (
              a
              )
            
          
        
        
          f
          ⁡
          
            (
            
              b
              -
              a
            
            )
          
        
      
    
  



checking feasibility of c via the problem φ(a) in the Step 5 with a=c ;
wherein if φ(c) is feasible, a bisection line search is conducted along the line lcb to obtain the intersection point on a Pareto-boundary; given a line search accuracy δ, two points rmin and rmax are acquired; the partition point is set as r=rmax while the lower bound is updated as fmin=f(rmin);
if φ(c) is infeasible, just set the partition point as r =c.

4. The monotonic optimization, as recited in claim 1, wherein the sequential partition method in the Step 7 comprises steps of:
i) firstly generating a set of K new vertices {b1, . . . ,b(K)} based on the partition point r , wherein


b(i)=b−(bi−ri)ei, i=1, . . . ,K 



wherein a subscript i indicates an i-th element of a vector and ei, is a vector with the i-th element being 1 and the others being 0;
ii) sorting the K vertices as {b(i1), . . . ,b(ik)}in ascending order of the achievable weighted sum-rate, wherein is denotes an original index of the s-th vertex; and
iii) sequentially determining the corresponding vertices {a(i1), . . . ,a(ik)}as





  
    a
    
      (
      
        i
        s
      
      )
    
  
  =
  
    {
    
      
        
          
            
              a
              ,
            
          
          
            
              s
              =
              1
            
          
        
        
          
            
              
                
                  a
                  
                    (
                    
                      i
                      
                        s
                        -
                        1
                      
                    
                    )
                  
                
                +
                
                  
                    (
                    
                      
                        r
                        
                          i
                          
                            s
                            -
                            1
                          
                        
                      
                      -
                      
                        a
                        
                          i
                          
                            s
                            -
                            1
                          
                        
                      
                    
                    )
                  
                  ⁢
                  
                    e
                    
                      i
                      
                        s
                        -
                        1
                      
                    
                  
                
              
              ,
            
          
          
            
              s
              >
              1
            
          
        
      
      .