Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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
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]}$. –  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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.