Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 30 / 4

The objective approximates the logarithm of the product-form stationary distribution of a loss network. To make the approximation precise, multiply arrival rates and capacities by $N$ and write $x=n/N$. The Stirling formula gives, uniformly on the feasible compact set,with $0\log 0=0$. The feasible set is $K=\{x\ge 0:Ax\le C\}$. Positive capacities and a nonempty route for each class make $K$ compact with a strictly positive feasible point. Since $H_{\nu }$ is a strictly concave function, its maximizer $x^{\ast }$ is unique; its infinite inward derivative at $x_r=0$ makes every component positive.

The Karush-Kuhn-Tucker conditions give nonnegative link Lagrange multipliers $z_j$ satisfyingFor any neighborhood of $x^{\ast }$, continuity and uniqueness give a strictly positive objective gap outside it. There are only polynomially many feasible lattice states, while their weights differ exponentially in $N$. The feasible point $\lfloor N{x}^{\ast }\rfloor$ has objective tending to $H_{\nu }(x^{\ast })$. It follows that the stationary law concentrates at $x^{\ast }$ on the scale $n/N$; in particular,Thus NETWORK predicts the dominant occupancy and mean occupancy in a large loss network. For unscaled inputs it gives a continuous approximation to the modal integer state.

It also gives an exact useful change of variables. Substituting ${\nu }_r=x_r^{\ast }{e}^{(A^{T}z{)}_r}$ into the equilibrium weights yieldsThis is Poisson exponential tilting for a loss network: independent Poisson random variables centered at the predicted occupancies, restricted to the feasible region and penalized for slack in positively priced resources. It explains why an unconstrained Gaussian approximation should not automatically be applied at a saturated capacity boundary.

Let $x^{\ast }$ maximize SYSTEM. Under the usual positive-capacity, nonempty-route assumptions, the feasible set is compact, contains a positive point, and has a Slater condition point. Strict concavity makes the optimum unique. The condition $U_r^{\prime }(0)=\infty$ forces $x_r^{\ast }>0$: moving from any optimum with a zero component slightly toward a positive feasible point gives an infinite positive directional derivative in that component and only finite losses in the positive components.

By the Karush-Kuhn-Tucker conditions, there are link Lagrange multipliers $p_j^{\ast }\ge 0$ withSet the route congestion price $y_r^{\ast }=(A^T{p}^{\ast }{)}_r=U_r^{\prime }(x_r^{\ast })$ and chooseThen $x_r^{\ast }={\nu }_r^{\ast }{e}^{-y_r^{\ast }}$, as required. For USER with fixed $y_r^{\ast }$, the substitution $x={\nu }_r{e}^{-y_r^{\ast }}$ is a bijection of the nonnegative half-line, and its objective becomes $U_r(x)-y_r^{\ast }x$. This is a strictly concave function whose derivative vanishes at $x_r^{\ast }$, so its unique maximizer is $x_r^{\ast }$ and the corresponding USER optimizer is ${\nu }_r^{\ast }$.

For NETWORK at ${\nu }^{\ast }$, its objective derivative at $x^{\ast }$ isThus $x^{\ast },p^{\ast }$ obey its Karush-Kuhn-Tucker conditions, with the same feasibility and complementary slackness. The NETWORK objective is a strictly concave function, so $x^{\ast }$ is also its unique maximizer. The triple $(x^{\ast },y^{\ast },{\nu }^{\ast })$ solves all three problems simultaneously. This is a user-network decomposition of concave utility maximization.