Supremum of $f(x_1,\dots,x_n)=\sum_{i=1}^n a_i x_i-\sum_{i=1}^n x_i \log x_i$

118 Views Asked by At

Let $a_1,\dots,a_n\in\mathbb{R}$. Find supremum of:

$f(x_1,\dots,x_n)=\sum_{i=1}^n a_i x_i-\sum_{i=1}^n x_i \log x_i$

in the following set:

$D=\{x_1,\dots,x_n\ge0 , \sum_{i=1}^n x_i=1\}$. Note: we define $x_i \log x_i=0$ when $x_i=0$

It's easy to see that $f\in C^1(D)$. However, I've been struggling to present $D$ as zeros of a function in order to use lagrange multipliers.

The natural function to pick is $g(x)=1- \sum_{i=1}^n x_i$. However , this function disregard the constraint that $x_1,\dots,x_n\ge0$.

1

There are 1 best solutions below

0
On

Your objective function is $f:[0, \infty)^n \rightarrow\mathbb{R}$ rather than $f:\mathbb{R}^n\rightarrow\mathbb{R}$ and so the results on the Wikipedia link that you provide do not directly apply. A more general Lagrange multiplier statement for functions defined on arbitrary domains is this:


Assume:

  • $X\subseteq\mathbb{R}^n$ is an arbitrary set (possibly nonconvex).

  • $f:X\rightarrow \mathbb{R}$ and $g:X\rightarrow\mathbb{R}$ are arbitrary functions (possibly nonconvex and nondifferentiable).

Theorem: Fix $\lambda \in \mathbb{R}$. If $x^* \in X$ solves the following problem: \begin{align} \mbox{Minimize:} & \quad f(x) + \lambda g(x) \\ \mbox{Subject to:} & \quad x \in X \end{align} Then $x^*$ also solves this problem: \begin{align} \mbox{Minimize:} & \quad f(x) \\ \mbox{Subject to:} & \quad g(x) = g(x^*)\\ & \quad x \in X \end{align}

This statement is Theorem II.3 (on page 13) in these notes and the proof is easy:

http://ee.usc.edu/stochastic-nets/docs/network-optimization-notes.pdf


So for your problem define $X = \{(x_1, ..., x_n) : x_i\geq 0\quad \forall i \in \{1, ..., n\}\}$ and $f:X\rightarrow\mathbb{R}$ and $g:X\rightarrow\mathbb{R}$ as you already do. For your problem, given any $\lambda \in \mathbb{R}$, it is easy to minimize $f(x) + \lambda g(x)$ subject to $x \in X$. The problem separates over each of the $n$ variables. You can get an analytical solution $x^*_{\lambda}$ (in terms of $\lambda$) that you can adjust to ensure $g(x^*_{\lambda})$ matches the desired constraint.