# 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{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{*}$$

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.