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.

Consider the parametric linear problem

$$ x^*(\theta) := \min_{Y , \ Z } \left\| Z \right\|_1 $$

$$ \text{sub. to: } \ \theta A + B Y = \theta C Z.$$

where $Y \in \mathbb{R}^{m \times s} $, $Z \in \mathbb{Z} := \{M \in (\mathbb{R}_{\geq 0})^{s \times s} \mid \left\| M \right\|_1 \leq 1 \}$; $\ A \in \mathbb{R}^{n \times s}$, $B \in \mathbb{R}^{n \times m}$, $C \in \mathbb{R}^{n \times s}$ are given non-null matrices; $\underline{1}^\top = (1,1,...,1) \in \mathbb{R}^s$.

Let $\theta \in [\epsilon,1]$ for some $\epsilon>0$.

Is the function $\theta \mapsto x^*(\theta)$ continuous?

Edit: Say what happens if $Y \in \mathbb{Y}$, being $\mathbb{Y} \subset \mathbb{R}^{m \times s}$ a compact set.

Note: this question is simpler than this one.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Since $\theta > 0$, we may divide the first constraint by $\theta$ to obtain $A + \theta^{-1} B Y = C Z$. Since $Y$ is unrestricted except for that constraint, we can replace $\theta^{-1} Y$ by $Y$. So $x^*(\theta)$ is not only continuous, it is constant.

EDIT: In the revised problem, here's a counterexample. Take $s=m=n=1$, $\epsilon = 1/2$, $A = -1$, $B=1$, $C=1$, ${\mathbb Y} = \{1/2, 1\}$. Thus the constraint is $- \theta + Y = \theta Z$. $Y = 1/2$ allows the first constraint to be satisfied if and only if $\theta = 1/2$, in which case $Z = 0$. On the other hand, $Y=1$ allows the first constraint to be satisfied for all $\theta \in [1/2,1]$ with $Z = 1/\theta-1$. Thus $x^*(\theta) = 1/\theta - 1$ for $\theta > 1/2$ but $0$ for $\theta = 1/2$.

share|improve this answer
    
Thanks a lot. What happens if $Y$ is "restricted" to be in a compact set, namely if $Y \in \mathbb{Y} \subset \mathbb{R}^{m \times s}$? –  Adam Sep 23 '12 at 20:07
    
I guess we can rewrite the problem as $x^*(\theta) := \min_{Y,Z} \left\| Y \right\|_1$ sub. to: $A + \theta^{-1} B Y = C Z$, $Y \in \mathbb{Y}$. Is that right? –  Adam Sep 23 '12 at 20:35
1  
The objective is not $\|Y\|_1$, it is $\|Z\|_\infty$. –  Robert Israel Sep 23 '12 at 20:37
    
It is $Z$, that's fine. But $1^\top Z$ gives you the column sum so seems to me it is the $1$-norm. What am I missing? –  Adam Sep 23 '12 at 20:40
1  
OK, in that sense it is $\|Z\|_1$. –  Robert Israel Sep 23 '12 at 21:10

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.