Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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
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
OK, in that sense it is $\|Z\|_1$. – Robert Israel Sep 23 '12 at 21:10

Your Answer


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.