Prove formally that multivariate function has global extrema

Question

Consider the following function: $f(x_1, \dots, x_n) = p_1 \log x_1 + \dots + p_n\log x_n$ subject to the constraint that $\sum_i p_i = \sum_i x_i = 1$. It is also known that $p_i \in [0,1]$ and $x_i \in [0,1]$.

I need to prove formally that the function has global maximum when $\frac{p_1}{x_1} = \dots = \frac{p_n}{x_n}$, i.e, $x_i = p_i$ gives the global maximum.

I can prove this formally for two variables by using the standard first and second derivative test (eliminate one of the variables). I can also verify empirically that $x_i = p_i$ is the global maximum of this function when $n > 2$ but want to prove this formally.

Is there a suitable technique for multivariate functions that I can use?

Answer 1

Using the Lagrange multipliers method we obtain $$\nabla f=(\dfrac{p_1}{x_1},\cdots ,\dfrac{p_n}{x_n})=\lambda_1(1,1,\cdots,1)$$which means that $$\dfrac{p_1}{x_1}=\cdots =\dfrac{p_n}{x_n}=\lambda_1$$To complete our proof we need to show that the hessian is negative definite at this point. We have $$H=\begin{bmatrix}-\dfrac{p_1}{x_1^2}&0&\cdots&0\\0&-\dfrac{p_2}{x_2^2}&\cdots&0\\.\\.\\.\\0&0&\cdots&-\dfrac{p_n}{x_n^2}\end{bmatrix}$$which is negative definite (semi-definite) since $p>0$ ($p\ge 0$)

Answer 2

Hint:

Using a Lagrangian multiplier,

$$f(x_i;\lambda)=\sum p_i\log x_i+\lambda\left(1-\sum x_i\right).$$

An extremum is achieved when

$$\frac{\partial}{\partial x_i}f(x_i;\lambda)=\frac{p_i}{x_i}-\lambda=0,\\\frac{\partial}{\partial\lambda}f(x_i;\lambda)=1-\sum x_i=0.$$

After elimination of the $x_i$,

$$1-\frac1\lambda\sum p_i=0$$ gives $\lambda$.

---

Now we have to consider the cases such that one or more variable saturates. If saturation occurs towards $0$, then the term $\log x_i$ goes to minus infinity and cannot achieve a maximum. If saturation is towards $1$, the term $p_i\log x_i$ vanishes. Solving the reduced problem, we have

$$\lambda=\sum_{i\notin S}p_i,$$ $$x_i=\frac{p_i}\lambda$$ and the objective function equals

$$\sum_{i\ne S}p_i\log x_i=\sum_{i\ne S}(p_i\log p_i-p_i\log \lambda).$$