function induced by optimization

Question

Consider the following optimization

• $\displaystyle\max_{x_1, \ldots, x_n}\sum_{i=1}^n x_i y_i -\sum_{i=1}^n x_i\log(x_i)$

• subject to $a_i\leq x_i\leq b_i$ and $\sum_{i=1}^n x_i =c$

  where $a_i,b_i, c\geq 0$ are constants.

This can be regarded as a function $f$ over $y_1, \cdots, y_n$ and let's assume that $y_1, \cdots, y_n\geq 0$ (i.e, the domain is positive)

The question, is the function $f$ convex?

Answer 1

Let us introduce some little notations in order to ease the reading. First let us write $F$ the set of feasible point of the maximization problem, i.e. $$F := \{x \in \mathbb{R}^n: a_i \leq x_i \leq b_i, i = 1, \ldots,n \text{ and }\sum_{i =1}^n x_i = c\}$$ We may assume $\sum_{i=1}^na_i\leq c \leq \sum_{i=1}^n b_i$, because if this is not true then $F = \emptyset$ and there is nothing to prove. Furthermore by abuse of notation for every $x \in F$, let us write $\log(x):=(\log(x_1), \ldots, \log(x_n))$. With these notations we can write $$f(y):= \max_{x \in F}\langle x, y-\log(x)\rangle.$$ So for every $u,v \in \mathbb{R}^n$ and $\theta \in [0,1]$, holds $$\begin{array}{rcl}f(\theta u + (1-\theta)v) &=& \max_{x \in F}\langle x, \theta u + (1-\theta)v-\log(x)\rangle\\ %&=& \max_{x \in F}\langle x, \theta (u-\log(x)) + (1-\theta)(v-\log(x))\rangle\\ &=& \max_{x \in F}\theta \langle x, u-\log(x)\rangle + (1-\theta)\langle x,v-\log(x)\rangle\\ &\leq & \theta \max_{x \in F}\langle x, u-\log(x)\rangle + (1-\theta)\max_{x' \in F}\langle x',v-\log(x')\rangle\\ &=& \theta f(u)+(1-\theta)f(v), \end{array}$$ which shows that $f$ is convex.

Answer 2

If a function can be expressed as the maximum of convex functions, it is convex. That is, if $f$ is of the following form, where $g$ is a convex function in $y$, then $f$ is convex:

$$ f(y) = \max_{x \in S} g(x,y) $$

Note that there is no restriction on how $g$ depends on $x$ and $S$ is any arbitrary set.

In your case $g$ is convex in $y$ (in fact linear), so $f$ must be convex.