Max-min Weighted SINR Optimization : Analytical solution and Algorithm

The analytical solution and a fast algorithm for the max-min weighted SINR optimization presented here has its roots in a series of work published in a 2013 IEEE/ACM Transactions on Networking paper and a 2011 IEEE Transactions on Signal Processing paper. An overview survey is available in Wireless Network Optimization by Perron-Frobenius Theory.

The Problem Statement

Maximizing the minimum weighted signal-to-interference-and-noise radio (SINR) under the total power constraint is formulated as follows :

\begin{equation} \begin{array}[c]{rl} \mbox{maximize} & \displaystyle\min_{l}\frac{{\mathbf{SINR}}_l(\mathbf{p})}{\beta_l}\\ \mbox{subject to} & \mathbf{1}^\top\mathbf{p}\le\bar{P},\mathbf{p}\geq\mathbf{0}\\ \mbox{variables:} & \mathbf{p}. \end{array} \tag{*} \end{equation}

where $\mathbf{SINR_l(\mathbf{p})}=G_{ll}p_l/(\sum_{j\ne l} G_{lj}p_j+n_l)$ for all $l$, and $\boldsymbol{\beta}=(\beta_{1},\dots,\beta_{L})^\top \ge 0$ is a given weight vector to reflect priority among users (larger weight means higher priority). A total power budget is given by $\bar{P}$.

Analytical Solution

Let us define the following nonnegative matrix :

$$ \mathbf{B}=\mathbf{F}+(1/\bar{P})\mathbf{1}\mathbf{1}^\top $$

and denote

$$ \mathbf{v}=(\frac{1}{G_{11}},\dots,\frac{1}{G_{LL}}) $$ \[F_{lj}= \begin{cases} 0,&l=j\\ G_{lj},&l\neq{j}. \end{cases}\]

The optimal value and solution of ($\ast$) are given, respectively, by

$$ \gamma^{\star}=\frac{1}{\rho(\mbox{diag}(\boldsymbol{\beta}\circ\mathbf{v})\mathbf{B})} $$

and

$$ \mathbf{P}^{\star}=\big(\bar{P}/\mathbf{1}^\top\mathbf{x}(\mbox{diag}(\boldsymbol{\beta}\circ\mathbf{v})\mathbf{B})\big)\mathbf{x}(\mbox{diag}(\boldsymbol{\beta}\circ\mathbf{v})\mathbf{B}), $$

where $\circ$ denotes Schur product and $\mathbf{x}(\cdot)$ denotes the right eigenvector corresponding to the Perron-Frobenius eigenvalue $\rho(\cdot)$.

A Short Proof Using the Classical Linear Perron-Frobenius Theorem

It can be shown that solving the optimization problem in ($\ast$) is equivalent to solving the following fixed-point equation:

$$ \frac{1}{\gamma^{\star}}\mathbf{p}^{\star}=\mbox{diag}(\boldsymbol{\beta}\circ\mathbf{v})(\mathbf{F}\mathbf{p}^{\star}+\mathbf{1}), \;\;\;\; \mathbf{1}^\top\mathbf{p}^{\star}=\bar{P} $$

Now, observe that :

$$ \frac{1}{\gamma^{\star}}\mathbf{p}^{\star}=\mbox{diag}(\boldsymbol{\beta}\circ\mathbf{v})(\mathbf{F}+\frac{1}{\bar{P}}\mathbf{1}\mathbf{1}^\top)\mathbf{p}^{\star} $$

therefore ($\ast$) can be solved analytically as an eigenvalue problem by the classical linear Perron-Frobenius theorem.

For a different proof, e.g., the $\it{nonlinear}$ ${\it Perron-Frobenius}$ $\it{theory}$, please see IEEE/ACM Transactions on Networking in 2013 and IEEE Transactions on Signal Processing in 2011.

The MATLAB Code

The algorithm below is a ${\it nonlinear}$ $\it{power}$ $\it{method}$ obtained using the nonlinear Perron-Frobenius theory.

clear;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Problem parameter initialization
% L: number of users.
% G: channel gain.
% F: nonnegative matrix. F_{lj} = G_{lj} if l ~= j, and F_{lj} = 0 if l = j
% v: nonnegative vector. v_l = 1/G_{ll}
% beta: a vector that is a weight assigned to links to reflect priority.
% pmax: upper bound of the total power constraints.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

L = 4; 
G = zeros(L,L); 
F = zeros(L,L); 
v = zeros(L,1); 
beta = rand(L,1); 
pmax = 2;

for l = 1:1:L
    for j = 1:1:L
        if l~= j
            G(l,j) = 0.1+0.1*rand(1,1);
        else
            G(l,j) = 0.6+0.3*rand(1,1);
        end
    end
end

for l = 1:1:L
    for j = 1:1:L
        if l ~= j
            F(l,j) = G(l,j);
        else
            F(l,j) = 0;
        end
    end
    v(l) = 1/G(l,l);
end

itenum = 15;
power_evolution = [];
p = rand(L,1);
power_evolution = [power_evolution;p'];
pnew = zeros(L,1);

for i = 1:1:itenum 
    for l = 1:1:L
        tmp = v(l);
        for j = 1:1:L
    % Algorithm step 1: update power for each user in a distributed way 
           tmp = tmp+F(l,j)*v(l)*p(j);
        end
        pnew(l) = beta(l)*p(l)/(p(l)/tmp);
    end
    % Algorithm step 2: normalize power centrally at the base station
    pnew = pnew*(pmax/sum(pnew));
    power_evolution = [power_evolution;pnew'];
    p = pnew;
end

% plot the power evolution 
figure
plot1 = plot(1:1:(itenum+1),power_evolution(:,1),'-o',1:1:(itenum+1),power_evolution(:,2),
        '-^',1:1:(itenum+1),power_evolution(:,3),'-+',1:1:(itenum+1),power_evolution(:,4),'-*','linewidth',1.5);
legend('User 1',''User 2','User 3','User 4');

A Tiny Numerical Example

The problem parameters are set randomly in the code above. The following figure, obtained by running the code directly, plots the power evolution for a 4-user case.