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. Perhaps you may be interested in [this](http://math.stackexchange.com/questions/232173/max-quadratic-expression) related question.2012-11-09