Past exam of the mathematics course of the University of Cambridge / 2018 / ib / Paper 3 / 21H (Optimisation)

The Lagrange sufficiency theorem says that if a feasible point $x^{\ast }$ and nonnegative multipliers satisfy complementary slackness and $x^{\ast }$ globally maximizes the Lagrangian function in constrained optimization, then $x^{\ast }$ globally solves the constrained maximization problem. Indeed, for every feasible $x$, the signs of the constraints give $f(x)\le L(x)\le L(x^{\ast })=f(x^{\ast })$. Concavity and the Karush-Kuhn-Tucker conditions are a common way to verify the global Lagrangian maximum.

For fixed $y$, A maximizessubject to $x_i\ge 0$ and ${\sum }_i{x}_i=X$. This is a concave function of $x$. On every active coordinate, the multiplier equation isThus A's optimal allocation is given by the water-filling algorithm:where $\lambda >0$ is chosen so that ${\sum }_i{x}_i=X$. Coordinates with zero expression receive no resource. This is a water-filling algorithm. The formula gives the optimum when every $y_i>0$. If $y_i=0$, any $x_i>0$ already gives A the whole market $u_i$ in that region, so A assigns such coordinates arbitrarily small positive amounts and applies water filling to the remaining budget; without a convention for $0/0$, the resulting value can be a supremum rather than an attained maximum.

Let $U={\sum }_i{u}_i$. The candidate strategies areAt this pair, A's partial derivatives $2u_i{y}_i/(x_i+y_i{)}^2$ are independent of $i$, as are the negatives of B's partial derivatives. Since $F$ is concave in $x$ for fixed $y$ and convex in $y$ for fixed $x$, the Lagrange sufficiency theorem provesfor all feasible $x,y$. Hence $(x^{\ast },y^{\ast })$ is a saddle point and gives the optimal strategies in this zero-sum game. Its game value is