0
$\begingroup$

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.

1 Answers 1

1

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.

  • 0
    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?2012-11-09
  • 0
    I have added a comment on necessity.2012-11-09
  • 0
    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.2012-11-09
  • 1
    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]}$.2012-11-09
  • 0
    Thanks. Perhaps you may be interested in [this](http://math.stackexchange.com/questions/232173/max-quadratic-expression) related question.2012-11-09