# function induced by optimization

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?

• Your function $f$ is $f(x, y)=\sum_{i=1}^{n}x_iy_i-\sum_{i=1}^{n}x_i\log x_i$. Why you said only $f(y)$?
– Jika
Jun 19, 2014 at 11:56
• no, $x_i$' are optimization variables, i.e., f is defined by the optimization problem. Jun 19, 2014 at 11:58
• So, it is $f(x)$. You said $f$ over $y_1$, $y_2$, $\cdots$. No?
– Jika
Jun 19, 2014 at 13:25
• @Jika I think $f(y)$ can be seen as the optimal value of the optimization problem with parameters $y=(y_1,\ldots,y_n)$.
– Surb
Jun 20, 2014 at 10:18

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.
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.