\documentclass{seminar}
\input{P:/RBM(Assaf)/INFORMS/myslide-defs.tex}
\input{P:/RBM(Assaf)/INFORMS/mydefinitions.tex}
\newcommand {\ra}{\rightarrow}
\def\vb{\vspace*{0.5in}}
\def\va{\vspace*{0.15in}}
\def\vc{\vspace*{1in}}

\renewcommand{\headrulewidth}{0mm}
\begin{document}
\makeatletter
\def\pst@initoverlay#1{%
\pst@Verb{%
/BeginOL {dup (all) eq exch TheOL le or {IfVisible not {Visible /IfVisible true def} if} {IfVisible {Invisible /IfVisible false def} if} ifelse} def
\tx@InitOL /TheOL (#1) def}} \makeatother

\overlaystrue  % turn overlays on....
%\overlaysfalse

\begin{sffamily}
\iffalse \fancyfoot[C]{} \fancyfoot[R]{\theslide}
%\fancyfoot[R]{\tiny December 2004} %\fancyfoot[C]{}
\renewcommand{\headrulewidth}{0mm}
\fi

%-------------------------- Title Page------------------------------------------------------------------------------------
%\pagenumbering{arabic}
\setcounter{page}{0} \thispagestyle{empty}

\begin{slide}
$\mbox{ }$

\textcolor{Red}{{\Large \textbf{A Linear Programming Algorithm for Steady-State Analysis of Heavy Traffic Approximations}}}
%\end{center}
\vspace*{-0.1em} \rule{4.85in}{.5mm}
%\hrulefill
\vd \vb \vspace{0.5cm} {\large \bl{Denis Saure*}}

\va
Graduate School of Business\\
Columbia University\\

\vspace{1.5cm} \small{* \jg{Join work with Assaf Zeevi (Columbia) and Peter Glynn (Stanford)}}

 \vfill
\end{slide}
%-----------------------------------------------------------------------------------------------------------------------
\pagestyle{fancy}
\begin{slide}
\baselineskip 19pt \heading{Outline}

\tri \textbf{A general numerical algorithm for computing steady-state of diffusions with/without reflecting boundaries}

\tri \textbf{Illustrate ideas in two settings:} \bit

\item \jg{Standard} heavy-traffic analysis\\
~~~~~~~~ -- SRBM in orthant (approximation of multi-class queueing networks)

\item \jg{Many server} heavy-traffic approximations\\
~~~~~~~~ -- Two class queue in \jg{Halfin-Whitt} regime

\eit \vfill
\end{slide}
%-----------------------------------------------------------------------------------------------------------------------
\begin{slide}
\baselineskip 19pt \heading{\rd{I.} SRBM: Background}

\tri \textbf{$(Z(t):t\geq 0)$ is $(\Sigma,\mu,R)$ SRBM $\in \mathbb{R}_+^d$ if:}

~~~~-- $Z(t) = X(t) + R Y(t) \quad t\geq0$,

~~~~-- $(X(t):t\geq 0)$ is a ($\mu$,$\Sigma$) d-dimensional Brownian motion,

~~~~-- $Y(t)=0$, $Y$ non-decreasing and $Y_i$ can increase only when $Z_i(t) =0$

\tri \textbf{Used to model heavily loaded queueing networks: }

~~~~--  s-s of $Z$ used to approximate s-s of original network...

\tri \textbf{Reflection matrix $\boldsymbol{R}$ \jg{completely-$\boldsymbol{S}$: }minimal condition for existence and (weak) uniqueness of SRBM}
[Reiman-Williams (89) Taylor-Williams (93)]

\tri \textbf{Stationary distribution exists if ``deterministic counterpart'' is stable} [Dupuis-Williams (94)]

\vfill
\end{slide}
%-----------------------------------------------------------------------------------------------------------------------
\begin{slide}
\baselineskip 19pt \heading{Characterization of the Stationary Distribution}

\textbf{Basic adjoint relation:} follows from Markovian structure...
$$
\mbox{(\rd{BAR})}\;\;\;\;\; \int_{\mbox{{\small orthant}}} ({\txtcp{\boldsymbol{\cA}}} {\txtcjg{\boldsymbol{f}}})(x) {\txtcb{\boldsymbol{\pi}}}(dx) +
\int_{\mbox{{\small boundary}}} ({\txtcp{\boldsymbol{D}}}{\txtcjg{\boldsymbol{f}}})(x) {\txtcb{\boldsymbol{\eta}}}(dx) = 0
$$

\textbf{Symbol key:} \bit
\item[--] \underline{test functions}~~~ ${\txtcjg{\boldsymbol{f}}}$ twice cont. diff. and bounded

\item[--] \underline{generator}~~~ ${\txtcp{\boldsymbol{\cA}}}$ of the Brownian motion

\item[--] \underline{boundary derivatives}~~~ ${\txtcp{\boldsymbol{D_i}}}{\txtcjg{\boldsymbol{f}}}$ on each orthant face

\item[--] \underline{stationary distribution}~~~ ${\txtcb{\boldsymbol{\pi}}}$ in orthant

\item[--] \underline{boundary stationary  distribution}~~~ ${\txtcb{\boldsymbol{\eta}}}$ on faces \eit
\begin{overlay}{1}
\textbf{\rd{BAR characterization is necessary and sufficient}} [Harrison-Williams (87), Dai-Harrison (92), Dai-Kurtz]
\end{overlay}
\vfill
\end{slide}
%-----------------------------------------------------------------------------------------------------------------------
\begin{slide}
\baselineskip 19pt \heading{Computing the Stationary Distribution}

\textbf{Previous  approaches: exploit orthogonality condition} \\view BAR  as $({\txtcp{\boldsymbol{\cA}}}
{\txtcjg{\boldsymbol{f}}},{\txtcp{\boldsymbol{D}}}{\txtcjg{\boldsymbol{f}}})  \perp ({\txtcb{\boldsymbol{\pi}}},{\txtcb{\boldsymbol{\eta}}})$
[Dai-Harrison (91,92), Shen et. al. (02)] \bit
\item[\tri] Take sequence of spaces $\cF_{\txtcr{\boldsymbol{n}}}\uparrow$ such that $\bigcup \cF_{\txtcr{\boldsymbol{n}}}$ dense
\item[\tri] For each ${\txtcr{\boldsymbol{n}}}$ get estimate of density of stationary distribution
\item[\tri] Use projection properties in $L_2$...
\eit \va

 \center{\textbf{\begin{overlay}{1}Requires a conjecture on the non-negativity of solutions to BAR\end{overlay}}}


\vfill
\end{slide}
%-----------------------------------------------------------------------------------------------------------------------
\begin{slide}
\baselineskip 19pt \heading{The Proposed Algorithm} \vspace{-0.4cm}
\begin{eqnarray*}
\txtcr{\boldsymbol{LP^n_m}} :\,\min && \txtcws{\boldsymbol{\eps}}\\
\mbox{s.t.} && \left|\sum_{x\in \cS^n} (\txtcp{\boldsymbol{A}} \txtcjg{\boldsymbol{f}})(x) \txtcb{\boldsymbol{\pi^n_m}}(x) + \sum_{k=1}^d \sum_{x\in
\cS^n_i} (\txtcp{\boldsymbol{D_i}} \txtcjg{\boldsymbol{f}})(x) \txtcb{\boldsymbol{\eta^n_{m i}}}(x)\right| \leq \txtcws{\boldsymbol{\eps}} \hspace{1.6cm} [ \pr{BAR}]\\ &&  \quad \mbox{for }\txtcjg{\boldsymbol{f}}\in \cF_m \mbox{ \textbf{Test functions}} \\
&& \sum_{x \in \cS^n} \txtcb{\boldsymbol{\pi^n_m}}(x) =1 \hspace{5.7cm} [ \pr{Normalization}]\\
&& \sum_{x\in \cF_i^n} \txtcb{\boldsymbol{\eta^n_{mi}}}(x)\leq K_i \quad \mbox{for }i=1,\hdots,d \hspace{0.5cm} [ \pr{Finite boundary measure}] \\
&& \txtcb{\boldsymbol{\pi^n_m}}(x) , \txtcb{\boldsymbol{\eta^n_{mi}}}(x) \geq 0 \;\;\;\;\;\mbox{for }x\in \cS^n (x\in \cS_i^n) \hspace{1.6cm} [ \pr{Non-negativity}] \\
 \end{eqnarray*}
 \begin{overlay}{1}
\vspace*{-1.8cm} \begin{eqnarray*}
&\hspace{1.75cm}& \sum_{x\in \cS^n} \langle e,x\rangle\txtcb{\boldsymbol{\pi^n_m}}(x)\leq T \hspace{5.6cm} [ \rd{Tightness}] \\
&& \sum_{x\in \cF_i^n} \langle e,x\rangle\txtcb{\boldsymbol{\eta^n_{mi}}}(x)\leq T_i \quad \mbox{for }i=1,\hdots,d \hspace{0.8cm} [ \rd{Boundary Tightness}] \\
 \end{eqnarray*}
 \end{overlay}

\vfill
\end{slide}
%-----------------------------------------------------------------------------------------------------------------------
\begin{slide}
\baselineskip 19pt \heading{LP Algorithm: Theory}
\begin{theorem}
Suppose there exists $(\pi,\eta)$ stationary distribution for SRBM. If \rd{$R^{-1}\mu < 0$}, there exist subsequences $\{n_k\}$ and $\{m_k\}$ such
that $\pi^{n_k}_{m_k}\Rightarrow \pi$ and $\eta^{n_k}_{m_k i}\Rightarrow \eta_i$, where $\pi^n_m$, $\eta^n_{mi} $ optimal solution to $LP^n_m$
\end{theorem}
\begin{overlay}{1}
\tri \rd{Sketch of proof:}\\ - $\cS^n$ gets dense in $\mathbb{R}_+^d$ \\
- $\cF_m$ gets dense in $C_b^2(\mathbb{R}^d)$\\
- \jg{Tightness}\\
- Diagonal argument...
\end{overlay}
 \vfill
\end{slide}
%-----------------------------------------------------------------------------------------------------------------------
\begin{slide}
\baselineskip 19pt \heading{LP Algorithm: Theory (cont.)}

\textbf{\underline{Key Ideas:}} \bit
 \item[\tri] Need to ensure tightness conditions on interior and boundary measures
 \item[\tri] \textbf{Interior:} Use a-priori moments bounds [Budhiraja-Lee (06)]
 \item[\tri] \textbf{Boundary:} ?
\eit
\begin{overlay}{1}
\begin{theorem}
Suppose there exists $(\pi,\eta)$ stationary distribution for SRBM. If \rd{$R^{-1}\mu < 0$}, then exits a vector $\upsilon>0$ such that \BEAS
\int_{F_i} e^{\langle\upsilon,x\rangle}\, \eta_i(dx) <\infty \quad  i=1,\hdots,d \EEAS  \end{theorem}

\va \jg{Remark}: Related to conjecture in Harrison-Williams (87)
\end{overlay}
\vfill
\end{slide}
%-----------------------------------------------------------------------------------------------------------------------
\begin{slide}
\baselineskip 19pt \heading{LP Algorithm: Numerical Results} \textbf{Two Dimensional SRBM:} Approximation of tandem queue
$$ R = \left(\begin{array}{cc} 1 & 0\\-1&1\end{array} \right) \quad \quad \Gamma = \left(\begin{array}{cc} 1 & 0\\0&1 \end{array}\right) \quad \quad \mu = \left(\begin{array}{c} 1\\0\end{array}
\right)$$

\tri \textbf{Density of stationary distribution:} [Harrison (78)]

~~~~~~~ -- $p(x) = Cr^{-1/2}e^{\mu_1(r+x_1)}\cos(\theta/2), \quad x = (x_1,x_2)=(r\cos\theta,r\sin\theta)$

~~~~~~~ -- $m_1 = \txtcp{0.5}$, $m_2 = \txtcp{0.75}$

\jg{\textbf{Algorithm settings:}}

\tri \rd{$\cS^n$}: Grid with $n$ points in each dimension

\tri \rd{$\cF^m$}: Polynomials of degree $m$ or less

\vfill
\end{slide}
%-----------------------------------------------------------------------------------------------------------------------
\begin{slide}
\baselineskip 19pt \heading{LP Algorithm: Numerical Results (cont.)}\vspace*{-0.5cm}
\begin{center}
  \begin{tabular}{c|cccccccc}
  \tiny{True Moments}/ m=& 3 & 4 & 5 & \rd{6} & 7 & 8 & 9 & 10 \\\hline
  $m_1=\txtcp{0.5}$ & 0.5 & 0.5 & 0.5 & \rd{0.5} & 0.5 & 0.5 & 0.5 & 0.5 \\
  $m_2=\txtcp{0.75}$ & 0.793 & 0.821 & 0.764 &\rd{0.768} & 0.762 &0.758 & 0.760 & 0.750 \\
\end{tabular}
\end{center}
\begin{overlay}{1}
\vspace*{0.2cm}\small{\jg{$m$ = degree of polynomials (n=100, points in grid on each dimension)}}\vspace{0.2cm}
\begin{figure}
\hspace*{-0.7cm}\includegraphics[width=13.0cm]{figure1b.eps}\\
\end{figure}
\end{overlay}
\vfill
\end{slide}
%-----------------------------------------------------------------------------------------------------------------------
\begin{slide}
\baselineskip 19pt \heading{\rd{II.} Application to Analysis of Markovian Service Networks}

\tri \textbf{Service systems (e.g. call centers) often have multiple servers}

\tri \textbf{Heavy-traffic analysis in \underline{many server} regime} [Halfin-Whitt (81)]
\begin{overlay}{1}
\begin{tabular}{m{0.3\textwidth}m{0.7\textwidth}}
\hspace{1cm}\includegraphics[width=3.5cm]{Example.eps}
 & \parbox{0.8\textwidth} {\textbf{\rd{Example: }}Two class system:\\
 -- Poisson arrivals: $\lambda_1,\, \lambda_2$\\
 -- Exponential service rates: $\mu_1,\, \mu_2$\\
 -- Single pool ($N$ severs)\\
 -- Static priority to class 1}
\end{tabular}
\end{overlay}
\begin{overlay}{2}
\hspace{-0.1cm}\tri Want steady-state distribution (both queue lengths, waiting times, etc.)

\tri Use diffusion limits to approximate discrete system

\tri \textbf{Halfin-Whitt regime:  $\mathbf{\lambda^{\boldsymbol{N}}_i \rightarrow \infty\,}$  s.t.  $\boldsymbol{\,\rho^N \approx 1
-\frac{\gamma}{\sqrt{N}}}$} as $\boldsymbol{N\rightarrow \infty}$
\end{overlay}
 \vfill
\end{slide}

%-----------------------------------------------------------------------------------------------------------------------
\begin{slide}
\baselineskip 19pt \heading{Diffusion Approximation}

\tri \textbf{Heavy Traffic limit }[Mandelbaum-Massey-Reiman (98)]

\tri \textbf{Normalized queue length converges to diffusion $\boldsymbol{X}$}
$$dX(t) = \txtcp{\boldsymbol{b}}(X(t))dt+ \boldsymbol{\Sigma} dW(t), \quad X(0) = \xi$$
\BEAS \txtcp{\boldsymbol{b}}_1(x) & = & -\mu_1 \gamma_1 - \mu_1 \txtcb{\boldsymbol{x_1}} \\
\txtcp{\boldsymbol{b}}_2(x) & = & \left\{ \begin{array}{ll} -\mu_2 \gamma_2 -\mu_2\txtcr{\boldsymbol{x_2}} & ~~~~~~
\txtcb{\boldsymbol{x_1}}+\txtcr{\boldsymbol{x_2}} \leq 0\\ -\mu_2 \gamma_2 + \mu_2\txtcb{\boldsymbol{x_1}} &
~~~~~~ \txtcb{\boldsymbol{x_1}}+\txtcr{\boldsymbol{x_2}} > 0 \end{array}\right. \\
\EEAS

\tri \textbf{i--th queue length in original system  $\approx\, k_i N + X_i(t)\sqrt{N}$}

\tri \textbf{Existence and uniqueness of stationary distribution of $\mathbf{X}$, and validity of s-s approximation}  [Maglaras-Zeevi (04)]

\center{\rd{\begin{overlay}{1}Need joint distribution of $\txtcr{\mathbf{(X_1,X_2)}}$ and marginal for $\txtcr{\mathbf{X_2}}$!\end{overlay}}}

 \vfill
\end{slide}
%-----------------------------------------------------------------------------------------------------------------------
\begin{slide}
\baselineskip 19pt \heading{Characterization of the Stationary Distribution}

\textbf{Basic adjoint relation:} follows from Markovian structure...
$$
\mbox{(\rd{BAR})}\;\;\;\;\; \int_{\mathbb{R}^2} ({\txtcp{\boldsymbol{\cA}}} \txtcjg{\boldsymbol{f}})(x) \txtcb{\boldsymbol{\pi}}(dx) = 0
$$
\textbf{Symbol key:} \bit
\item[--] \underline{test functions} ~~ ${\txtcjg{\boldsymbol{f}}}$ are  twice cont. diff. and bounded

\item[--] \underline{generator} ~~ ${\txtcp{\boldsymbol{\cA}}}$ of the diffusion process \hspace{0.0cm}$({\txtcp{\boldsymbol{\cA}}} \txtcjg{\boldsymbol{f}})(x) = b(x) \cdot \nabla \txtcjg{\boldsymbol{f}}(x) + tr(\nabla^2
\txtcjg{\boldsymbol{f}}(x) \Sigma)$

\item[--] \underline{stationary distribution} ~~ ${\txtcb{\boldsymbol{\pi}}}$
\eit
\begin{overlay}{1}
\begin{theorem}BAR is \rd{necessary} and \rd{sufficient}...
\end{theorem}\bit
 \item[--] \rd{Necessity}: via Ito's lemma
 \item[--] \rd{Sufficiency}: via \jg{Etcheverria's} theorem...
 \eit
\end{overlay}

\center{\rd{\begin{overlay}{2}Apply LP algorithm to solve for ${\txtcp{\boldsymbol{\pi}}}$\end{overlay}}}

\vfill
\end{slide}
%-----------------------------------------------------------------------------------------------------------------------
\begin{slide}
\baselineskip 19pt \heading{Numerical Examples}

$N = 100$, $\mu_1=1$, $\mu_2 =2$, $\lambda_1=47.5$, $\lambda_2 = 95$

\tri Uniform grid (n=100, m=4)
\begin{center}
\begin{figure}
\includegraphics[width=10cm]{figure3a.eps}\\
\end{figure}
\end{center}

\vfill
\end{slide}

%-----------------------------------------------------------------------------------------------------------------------
\begin{slide}
\baselineskip 19pt \heading{LP Algorithm Revisited}
\begin{eqnarray*}
\,\min && \txtcws{\boldsymbol{\eps}}\\
\mbox{s.t.} && \left|\sum_{x\in \cS^n} (\txtcp{\boldsymbol{A}} \txtcjg{\boldsymbol{f}})(x) \txtcb{\boldsymbol{\pi^n_m}}(x)\right|  \leq \txtcws{\boldsymbol{\eps}} \hspace{0.3cm} \mbox{for }\txtcjg{\boldsymbol{f}}\in \cF_m \hspace{3.6cm} [ \pr{BAR}]\\
&& \sum_{x \in \cS^n} \txtcb{\boldsymbol{\pi^n_m}}(x) =1 \hspace{5.5cm} [ \pr{Normalization}]\\
&& \sum_{x\in \cS^n} \langle e,x\rangle\txtcb{\boldsymbol{\pi^n_m}}(x)\leq T \hspace{5.4cm} [ \pr{Tightness}] \\
&& \txtcb{\boldsymbol{\pi^n_m}}(x) , \txtcb{\boldsymbol{\eta^n_{mi}}}(x) \geq 0 \;\;\;\;\;\mbox{for }x \in \cS^n \hspace{2.65cm} [ \pr{Non-negativity}] \\
\end{eqnarray*}
\begin{overlay}{1}
\vspace*{-1.7cm}
\begin{eqnarray*}
&\hspace{0.6cm}& \abs{\txtcb{\boldsymbol{\pi^n_m}}(x) - \txtcb{\boldsymbol{\pi^n_m}}(y)}\leq \boldsymbol{\delta} \quad \mbox{for }
(x,y) \in \cS^n  \hspace{2.1cm} [\rd{Smoothness}]\\
&& \hspace{3.5cm}\quad \mbox{ s.t. } ||x-y||<r
\end{eqnarray*}
\end{overlay}
\vfill
\end{slide}
%-----------------------------------------------------------------------------------------------------------------------
\begin{slide}
\baselineskip 19pt \heading{Numerical Examples}

$N = 100$, $\mu_1=1$, $\mu_2 =2$, $\lambda_1=47.5$, $\lambda_2 = 95$

\tri Uniform grid + \jg{Smoothing constraints}...(n=100, m=4)
\begin{center}
\begin{figure}
\includegraphics[width=10cm]{figure3b.eps}\\
\end{figure}
\end{center}

\vfill
\end{slide}
%-----------------------------------------------------------------------------------------------------------------------
\begin{slide}
\baselineskip 19pt \heading{Concluding Remarks}

\textbf{LP algorithm for steady-state computation} \bit
\item[\tri] Accurate \underline{moment approximations} [even for low degree polynomials]

\item[\tri] Reasonable \underline{distribution approximations} [even for low degree polynomials and little prior information]

~~~~~ -- Allows to compute tails  of delay / queue length, etc...

\eit

\textbf{General simple tool for approximating steady-state distributions in various queueing networks and service system applications}

~~~~~~~ -- Code available for downloads and use \va \va \va

\center{\begin{overlay}{1}\large{\rd{Questions?}}\end{overlay}}

\vfill
\end{slide}
%-----------------------------------------------------------------------------------------------------------------------
\end{sffamily}
\end{document}
