Confusing Lagrange multipliers question

Question

Let $a_1,a_2, \dots, a_n$ be reals, we define a function $f: \mathbb R^n \to \mathbb R$ by $f(x) = \sum_{i=1}^{n}a_ix_i-\sum_{i=1}^{n}x_i\ln(x_i)$, in addition, we are also given that $0 \cdot \ln(0)$ is defined to be $0$.

Find the supremum of $f$ on the domain $\Omega = \{x \in \mathbb R^n: x_i \geq 0, \sum_{i=1}^{n}x_i = 1\}$.

What I did:

$\Omega$ is closed and bounded and hence compact, and $f$ is continuous. It follows that $f$ admits a minimum and maximum (which confuses me as to why they asked for supremum and not maximum).

Let's look for the maximum when $x_i > 0$, by solving the system $\begin{cases}a_i-\ln(x_i)-1 = \lambda \\ \sum_{i=1}^{n}x_i = 1 \end{cases}$.

From the first $n$ equations we get $\ln(x_i) = a_i-1-\lambda$ or in other words $x_i = e^{a_i -1 -\lambda} > 0$

Plugging this to the constraint to find $\lambda$, we get $\lambda = \ln(\sum_{i=1}^{n}e^{a_i}) - 1$, so $x_i = e^{a_i-\ln(\sum_{i=1}^{n}e^{a_i})}$ is a potential maximum, or minimum, remember $f$ also attains a minimum.

Now we need to check what happens when $x_i$ is zero. This gives us an identical problem, but one dimension smaller. After that we need to check when $(x_i,x_j)$ are zero over all pairs. Then over all triples and so forth.

Surely this isn't the intended way. What's going on here?

Answer 1

This is quite correct way.

Obtained solution for the stationary point $$\hat x_i = \dfrac{e^{a_i}}{\sum\limits_{j=1}^ne^{a_j}}$$ corresponds to the constraints.

The value is $$f\left(\hat x\right) = \sum\limits_{i=1}^n \dfrac{a_ie^{a_i}}{\sum\limits_{j=1}^ne^{a_j}} - \sum\limits_{i=1}^n\dfrac{e^{a_i}}{\sum\limits_{j=1}^ne^{a_j}}\log\dfrac{e^{a_i}}{\sum\limits_{j=1}^ne^{a_j}} = \sum\limits_{i=1}^n \dfrac{e^{a_i}}{\sum\limits_{j=1}^ne^{a_j}} \left(a_i - \log\dfrac{e^{a_i}}{\sum\limits_{j=1}^ne^{a_j}}\right)\\ = \sum\limits_{i=1}^n \dfrac{e^{a_i}}{\sum\limits_{j=1}^ne^{a_j}} \left(\log e^{a_i} - \log e^{a_i}+\log{\sum\limits_{j=1}^ne^{a_j}}\right) = \sum\limits_{i=1}^n\dfrac{e^{a_i}\log{\sum\limits_{j=1}^ne^{a_j}}}{\sum\limits_{j=1}^ne^{a_j}} = \log{\sum\limits_{j=1}^ne^{a_j}}.$$ The task in every border is similar, with some subset of $\{a_i\}$ instead the issue set $\{a_i\}.$ So the stationary points values in the borders contain some part of the issue sum terms. At this time, last level sums, every of which contains the single value $a_i,$ present $1D$ tasks with zeros on the edges and correspond with the maxima.

Since $\forall(i)e^{a_i}>0,$ the value $f\left(\hat x\right)$ is maximum.

Answer 2

The problem is a convex optimization problem (maximizing a convex function over a convex domain). The KKT conditions are therefore necessary and sufficient for global optimality.

The KKT conditions are: (1) stationarity, (2) primal feasibility, and (3) complementary slackness. The Lagrangian (including nonnegativity) is: $$L(x,\lambda,\mu) = \left(\sum_{i=1}^n a_ix_i - x_i \ln(x_i) + \mu_i x_i + \lambda x_i \right) - \lambda$$ The KKT conditions are:

1. $a_i - \ln(x_i)-1+\mu_i+\lambda=0$
2. $\sum_{i=1}^n x_i = 1$ and $x \geq 0$
3. $\mu_i x_i = 0$

The solution you found satisfies all conditions with $\mu_i=0$ and is therefore optimal.