Past exam of the mathematics course of the University of Cambridge / 2018 / ib / Paper 3 / 21H / i

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.