% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
\usepackage{graphics}
\usepackage{multicol}
\usepackage{multirow}

% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}

\begin{document}

\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
 \title{Semidefinite Programming for Stochastic Wireless OFDMA Networks}
% \thanks[label1]{}
\author[label1]{Pablo Adasme \thanksref{email1}},
\author[label1]{Abdel Lisser \thanksref{email2}}
% \ead{pablo.adasme@lri.fr,abdel.lisser@lri.fr}
% \ead[url]{home page}
\thanks[email1]{Email: pablo.adasme@lri.fr}
\thanks[email2]{Email: abdel.lisser@lri.fr}
% \corauth[paris]{}
\address[label1]{Laboratoire de Recherche en Informatique, Universit$\acute{e}$ Paris-Sud XI, B$\hat{a}$timent 490, 91405, Orsay Cedex France}

% \thanks[label3]{}

%\title{}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

%\author{}

%\address{}

\begin{keyword}
Risk modeling \sep stochastic programming \sep semidefinite programming
\sep resource allocation in OFDMA.
\end{keyword}

\end{frontmatter}

\section{Introduction}

Resource allocation such as maximizing link capacity or minimizing
power consumption in a wireless OFDMA network are commonly
formulated as mathematical programs \cite{Amzallag2007}. These
programs usually involve random variables in the input data. In this paper, we propose a (0-1) stochastic quadratic formulation. The study is made on the basis of an OFDMA quadratic model \cite{AdasmeLisser} in which a probabilistic
constraint based approach is considered \cite{LisserLopez2009}.
Then, a semidefinite programming (SDP) relaxation is derived to
solve the stochastic quadratic model. The paper is organized as
follows: Section 2 presents the stochastic quadratic formulation.
Section 3 presents the SDP relaxation. Finally, section 4 concludes
the paper.

\section{Probabilistic formulation}

We consider an OFDMA network composed by a base station (BS) and
several mobile users. The BS has to assign a set of $N$ sub-carriers
to a set of $K$ users using a modulation size of $c \in
\{1,\ldots,M\}$ bits in each sub-carrier. The goal is to minimize
the total power consumption in the network. We consider the
following probabilistic constrained model
\cite{AdasmeLisser}:
\begin{eqnarray}
\mbox{SQIP0:} && \textstyle{ \min_{\{x_{k,n},y_{n,c}\}} \quad
\sum_{k=1}^{K}\sum_{n=1}^{N} \sum_{c=1}^{M} P_{k,n}^{c} x_{k,n}
 y_{n,c}} \label{QIP0}\\
\mbox{st:} \quad && \mathbb{P}\{\textstyle{ \sum_{n=1}^{N} x_{k,n} \left[ \sum_{c=1}^{M} c\cdot y_{n,c}\right] \geq R_{k}\} \geq (1-\alpha_k), \quad \forall k }\label{rateConstraint} \\
&& \textstyle{ \sum_{k=1}^{K} x_{k,n} \leq 1 \quad \forall n }\label{subcarrierConstraint} \\
&& \textstyle{ \sum_{c=1}^{M} y_{n,c} \leq 1 \quad \forall n }\label{modulationConstraint} \\
&& \textstyle{ x_{k,n},y_{n,c} \in \{0,1\}
}\label{domainConstraints}
\end{eqnarray}
Here, the objective function represents the total power consumption.
The first constraint corresponds to a chance constraint where
$\alpha_k$ is the risk to be taken for each user $k$. In this model,
we consider separated chance constraints. The second constraint
imposes that each sub-carrier should be assigned to only one user at
a time while the third one imposes that each sub-carrier must use
one integer modulation size. The decision variables are given by
$x_{k,n}$ and $y_{n,c}$, respectively. We assume that $R_{k}$ are
random variables with joint probability distribution $H$. Let us
consider the case where $H$ is concentrated in the finite number of
points also called scenarios $R_{k}=\left(r_{k,1},...,r_{k,l},...,r_{k,L_k}\right)$ with probabilities $p_{k,l}$ such that $\sum_{l=1}^{L_k} p_{k,l}=1, p_{k,l}\geq 0, \forall k$.

Then, the problem (\ref{QIP0})-(\ref{domainConstraints}) can be
reformulated as follows \cite{LisserLopez2009}:
\begin{eqnarray}
\mbox{SQIP1:} && \textstyle{ \min_{\{x_{k,n},y_{n,c}\}} \quad
\sum_{k=1}^{K}\sum_{n=1}^{N} \sum_{c=1}^{M} P_{k,n}^{c} x_{k,n}
 y_{n,c}} \label{QIP01}\\
\mbox{st:} \quad && \textstyle{ \sum_{n=1}^{N} x_{k,n} \left[ \sum_{c=1}^{M} c\cdot y_{n,c}\right] \geq r_{k,l}\, \quad \forall l \in \Gamma_k, \forall k }\label{rateConstraint1} \\
&& \textstyle{ \sum_{l\in \Gamma_k} p_{k,l} \geq 1-\alpha_k \quad \forall k}
\label{pcons} \\
&& \textstyle{ \sum_{k=1}^{K} x_{k,n} \leq 1 \quad \forall n }\label{subcarrierConstraint1} \\
&& \textstyle{ \sum_{c=1}^{M} y_{n,c} \leq 1 \quad \forall n }\label{modulationConstraint1} \\
&& \textstyle{ x_{k,n},y_{n,c} \in \{0,1\}
}\label{domainConstraints1}
\end{eqnarray}
Constraints (\ref{pcons}) mean that we have to choose a subset
$\Gamma_k$ of scenarios such that the sum of the probabilities of
this subset is greater than ($1-\alpha_k$). For this subset, the bit rate constraints will be active and valid, whereas for the scenarios not in this subset, the constraints are not activated.

This problem can be reformulated by introducing the auxiliary binary variable $\varphi_{k,l}$ for each observation $l=1:L_k, \forall k$ as follows:
\begin{equation}
\varphi_{k,l}=\left\{
\begin{array}{cl}
0 &\mbox{if~~} l\in \Gamma_k\\
1 &\mbox{otherwise}
\end{array}
\right.
\end{equation}
This yields the following problem:
\begin{eqnarray}
\mbox{SQIP2:} && \textstyle{ \min_{\{x_{k,n},y_{n,c},\varphi_{k,l}\}} \quad
\sum_{k=1}^{K}\sum_{n=1}^{N} \sum_{c=1}^{M} P_{k,n}^{c} x_{k,n}
 y_{n,c}} \label{QIP02}\\
\mbox{st:} \quad && \textstyle{ \sum_{n=1}^{N} x_{k,n} \left[ \sum_{c=1}^{M} c\cdot y_{n,c}\right] \geq r_{k,l} - \mathcal{M}\varphi_{k,l} \quad \forall k, l=1:L_{k}} \label{rateConstraint2} \\
&& \textstyle{ \sum_{l=1}^{L_{k}} p_{k,l} \varphi_{k,l} \leq \alpha_k \quad \forall k } \label{pcons1} \\
&& \textstyle{ \sum_{k=1}^{K} x_{k,n} \leq 1 \quad \forall n }\label{subcarrierConstraint2} \\
&& \textstyle{ \sum_{c=1}^{M} y_{n,c} \leq 1 \quad \forall n }\label{modulationConstraint2} \\
&& \textstyle{ x_{k,n},y_{n,c},\varphi_{k,l} \in \{0,1\}
}\label{domainConstraints2}
\end{eqnarray}
where $\mathcal{M}$ is an arbitrary number such that%
\begin{equation}
\mathcal{M}\geq \max_{k,l} \{r_{k,l}\}+1
\end{equation}

This problem is a quadratic optimization problem with binary
variables. This quadratic problem is NP-hard, and so is its
stochastic formulation. In this case, we seek lower bounds using
strong relaxations, namely SDP relaxations.


\section{Semidefinite relaxation}

In order to write a SDP relaxation for SQIP2, we define the
(0-1) vector $z^{T}= (x_{1,1}, \cdots, x_{1,N} , \cdots , x_{K,1} ,
\cdots , x_{K,N} , y_{1,1} , \cdots , y_{1,M} , \cdots , y_{N,1} ,
\cdots , y_{N,M},\varphi_{1,1}, \cdots , \\ \varphi_{1,L_1}, \cdots , \varphi_{K,1}, \cdots , \varphi_{K,L_k})$. Then, let $Z$ be a symmetric positive semidefinite matrix defined as:
\begin{equation}
Z= \left(
\begin{array}{cc}
zz^{T}     & z  \\
z^{T}      & 1  \\
\end{array} \right)\succeq 0
\end{equation}
We can construct symmetric matrices $\mathcal{P}$ for the objective function in (\ref{QIP02}), $U_{k,l}$ for constraints in (\ref{rateConstraint2}) and $V_{k}$ for constraints in (\ref{pcons1}). We propose the following SDP relaxation for SQIP2:
\begin{eqnarray}
\mbox{SSDP2}: && \min_{Z} \quad Trace(\mathcal{P}Z) \\
\mbox{ st:} && Trace(U_{k,l}Z) \geq r_{k,l}
\quad \forall k,l=1:L_{k} \label{SDP1_1}\\
&& Trace(V_{k}Z) \leq \alpha_{k}
\quad \forall k \label{SDP1_2}\\
&& Trace([ex_{n}][ex_{n}]^{T}Z) \leq 1 \quad \forall n \label{SDP1_3}\\
&& Trace([ey_{n}][ey_{n}]^{T}Z) \leq 1 \quad \forall n \label{SDP1_4}\\
&& Trace(\zeta_{k,n}^{c}Z) \geq 0 \quad \forall k,n,c \label{SDP1_5}\\
&& diag(zz^{T}) = z \label{SDP1_6}\\
&& Z \succeq 0 \label{SDP1_7}
\end{eqnarray}
In this model, $[ex_{n}]$ and $[ey_{n}]$ are coefficient vectors for constraints in (\ref{subcarrierConstraint2}) and (\ref{modulationConstraint2}) according to vector z. Thus, the rank-1 matrices we construct with these vectors are used to strength our SDP relaxation \cite{Helmberg2000}. The symmetric matrices $\zeta_{k,n}^{c}$ for all $\{k,n,c\}$ are used to have positive values in matrix $Z$ only in the positions where $\{\mathcal{P}_{i,j},i<j\}$ is positive, this is, in the entries of $\mathcal{P}$ where we put the elements $\{P_{k,n}^{c},k,n,c\}$ from (\ref{QIP02}). Finally, constraint (\ref{SDP1_6}) together with constraint (\ref{SDP1_7}) form a relaxation constraint for the condition of $z_{i}\in \{0,1\}$ for all $i$. The last constraint also imposes the condition on matrix $Z$ to be positive semidefinite. Our SDP relaxation is tighter than the linear program (LP) we obtain by applying Fortet linearization method \cite{Fortet1960} to SQIP2 as shown by our preliminary results.

\section{Conclusions}

In this paper, we proposed a stochastic quadratic formulation for wireless OFDMA networks. To this purpose, we considered an OFDMA quadratic model \cite{AdasmeLisser} in which probabilistic constraints are added by using the approach of \cite{LisserLopez2009}. Finally, a SDP relaxation is derived. Numerical results are given.

\begin{thebibliography}{00}
\bibitem{Amzallag2007} Amzallag, D. Armarnik, T. Livschitz, M. Raz, D.,{\em ``Multi-Cell Slots Allocation in OFDMA Systems,"} Mobile and Wireless Communications Summit, 16th IST, 2007.
\bibitem{LisserLopez2009} Lisser A., Lopez R. and Hu Xu,  {\em ``Stochastic Quadratic Knapsack with Recourse,"} International Network Optimization Conference, INOC-2009, April 2009.
\bibitem{Helmberg2000} Helmberg, C.,{\em ``Semidefinite Programming for Combinatorial Optimization,"} ZIB-Report ZR-00-34, Konrad-Zuse-Zentrum Berlin, October 2000.
\bibitem{AdasmeLisser} Adasme Pablo, Lisser Abdel and Soto Ismael, {\em ``Robust Semidefinite Relaxations for a New Quadratic OFDMA  Resource Allocation Approach,"} Working Paper Number 1522, LRI, University of Paris Sud, France.
\bibitem{Fortet1960} Fortet R.,{\em ``Applications de $l^{\prime}$algebre de boole en recherche operationelle,"} Revue Francaise de Recherche Operationelle, Vol. 4, pp. 17--26, 1960.
\end{thebibliography}

\end{document}

%\begin{eqnarray}
%&& \textstyle{ \sum_{n=1}^{N} x_{k,n} \left[\sum_{c=1}^{M} c\cdot y_{n,c}\right] \geq R_{k,l}-\mathcal{M}_{k,l}^{\xi}\varphi_{k,l}^{\xi}, \quad \forall l,k }\\
%&& \textstyle{ \sum_{l=1}^{L} \mathbb{P}_{k,l}\varphi_{k,l}^{\xi} \leq \alpha_{k}, \quad \forall k }
%\end{eqnarray}
