# Determining whether the following function is convex, concave, or neither of the two

$\mathbf{Question}$: Suppose we have $T\in \mathcal{R}^{p\times n},W\in \mathcal{R}^{p\times m}$ and $h\in \mathcal{R}^p$.

For $Q:\mathcal{R}^n \times \mathcal{R}^m \rightarrow \mathcal{R}\cup \{\pm\infty\}$ we have $Q(\xi,\eta)=\min\limits_y \{\eta^T y|Wy=h-T\xi,y\geq 0\}$.

Now, determine whether the function is convex, concave, or neither of the two in the following cases (and justify why):

1). For a fixed $\xi=\hat{\xi}$.

2). For a fixed $\eta=\hat{\eta}$ such that the polyhedral set $P=\{x|W^Tx\leq\hat{\eta}\}$ is nonempty.

3).$Q(\xi,\eta)$.

$\mathbf{Answer}$: For part (2), my claim is that $Q$ is convex, from the theorem:

$\textbf{Theorem}$: Given $A\in \mathcal{R}^{m\times n}$ and $c\in \mathcal{R}^n$, suppose that the polyhedral set $P:=\{u:A^Tu\leq c\}$ is non-empty. Then the function $\hat{\theta}=\min\limits_x \{c^Tx:Ax=\hat{b},x\geq 0\}$ is convex.

For (2) can such a reasoning be drawn directly from the theorem? Also for part (1), my gut feeling is telling me that its concave, and I tried proving my claim along the definition of an epigraph but am unable to make any progress..

$\textbf{Update on (1):}$ with @LinAlg's and @prubin's advice, since $\eta$ is not fixed, for $\lambda\in[0,1]$, $y\geq0$,

$$\min\limits_y\{f(y),f(y')\}\leq \lambda f(y)+(1-\lambda)f(y')\leq f(\lambda y+(1-\lambda)y')$$

$\forall y,y'$ in the domain of $f$. So it follows that $f$ is concave and quasi-concave. Thus, $Q(\hat{\xi},\eta)$ is concave.

$\textbf{End of update to (1)}$

Is this the right way about doing this? (clarification needed)

For (3), I have no clue as to how I can approach this, but a couple of my pals advised me that it may be neither concave nor convex.

Hence, some clarifications and hints with regards to the above questions will be deeply appreciated.

If there is a more intuitive way of approaching problems such as the above, I'll love to hear it too!

Thanks.

• In your statement of the theorem, is $\hat{\theta}$ a function of $\hat{b}$? – prubin Apr 10 '18 at 15:22
• For 1: the minimum of a set of linear functions is concave. – LinAlg Apr 10 '18 at 15:35
• @prubin Yes. In fact, $\hat{\theta}$ is a function of $c$ and $\hat{b}$. – Stoner Apr 10 '18 at 16:07
• @LinAlg Is there a way to show this with the definition of concavity? And to be precise, what does it mean when $\xi=\hat{\xi}$? Sorry but I am not too certain about this yet.. – Stoner Apr 10 '18 at 16:09
• @Stoner absolutely, see math.stackexchange.com/questions/373229/… – LinAlg Apr 10 '18 at 16:15

In the theorem, $c$ is fixed, so $\hat{\theta}$ is a function of just $\hat{b}$. After mapping the notation of the theorem to the notation of your problem, you can get part 2 directly from the theorem by exploiting the fact that the composition of a convex function with a linear function is convex. (If you haven't seen that derived, the proof is straightforward from the definitions of linearity and convexity.)
• Thank you for the clarification. And yes, I have the proof of the above. With regards to part (1), what does it mean to hold $\hat{b}$ constant? I am interpreting it as having the feasible set bounded, but am still unable to draw any conclusions from it.. – Stoner Apr 11 '18 at 1:01
• Your function $f(y)$ is linear (so both convex and concave), but in any case it's a function of $y$, not $\eta$, so I'm not sure what it has to do with convexity of $Q(\xi, \cdot)$. – prubin Apr 12 '18 at 14:01