# Concave optimal value?

Let $A \in \mathbb{R}^{n \times m}$ and $B \in \mathbb{R}^{m \times n}$. Consider a compact set $C \subset \mathbb{R}^n$.

For all $x \in C$ define

$$f(x) := \min_{y \in \mathbb{R}^m} \{ x^\top A y \mid \left\| B x + y \right\|_\infty \leq 1 \}.$$

Is the mapping $x \mapsto f(x)$ concave?

Notice that for $B=0$, we have $\displaystyle f(x) = \min_{\left\| y \right\|_\infty \leq 1} x^\top A y = -\left\| A^\top x\right\|_1$ which is concave.

-

I am assuming that $C$ is convex. Compactness has no particular relevance to this problem.

Note that $\{y | \|Bx+y\|\leq 1 \}= \{-Bx\}+\{h | \|h\|\leq 1\}$ (for any norm $\|\cdot\|$). Hence the function can be expressed as $$f(x) = \min_{\|h\|_\infty \leq 1} x^T A (-Bx+h) = -x^TABx + \min_{\|h\|_\infty \leq 1} x^T A h = -x^TABx - \|A^Tx\|_1$$ so concavity of $f$ depends on $AB$.

Then $f$ is concave iff $AB$ is positive semi-definite (as in $x^T AB x \geq 0$ for all $x$).

Sufficiency is clear. To see necessity, suppose for some $v\neq 0$ we have $v^TABv <0$, then look at $\phi(\lambda) = f(\lambda v) = \lambda^2 |v^TABv|-|\lambda|\|A^Tv\|_1$. Then $\phi$ is strictly convex on $[0,\infty)$, hence $f$ is not concave.

Explicitly, let $s =\frac{\|A^Tv\|_1}{|v^TABv|}$. Then $\phi(0) = 0$, and $\phi(s) = 0$, but $\phi(\frac{1}{2}s) < 0$. Hence $\phi(\frac{1}{2}s) < \frac{1}{2} (\phi(0) +\phi(s))$. This means that $f(\frac{1}{2}s v) < \frac{1}{2} (f(0 v) +f(sv))$, hence $f$ is not concave.

-
Thanks for the answer. I am not clear on the necessity. I see that if $AB$ is positive semidefinite then $f$ is concave, but I do not see the converse implication. Can you please explain? – Adam Nov 9 '12 at 18:59
I have added a comment on necessity. – copper.hat Nov 9 '12 at 19:27
Sorry but I do not clearly see why having $\lambda \mapsto \phi(\lambda)$ is convex. In fact $\lambda \mapsto \lambda^2$ is convex while $\lambda \mapsto -|\lambda|$ does not. Then, assuming $\phi$ convex, I also do not see why this would imply that $x \mapsto f(x)$ is not concave. – Adam Nov 9 '12 at 19:49
I have added an elaboration, but it should be fairly clear that on $[0,\infty)$ that $\phi$ is strictly convex (since $|\lambda| = \lambda$). And if $\phi$ is strictly convex on $[a,b]$, then $f$ must also be strictly convex on $\{t v\}_{t \in [a,b]}$. – copper.hat Nov 9 '12 at 20:33
Thanks. Perhaps you may be interested in this related question. – Adam Nov 9 '12 at 20:37