0
$\begingroup$

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.

1 Answers 1

1

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$.

  • 0
    I think this may be the solution. Define $\bar Z := \theta Z$ and $\bar x := \theta x$. Then the problem is equivalent to $\min \bar x$ sub to: $\theta A + BY = CZ$, $\underline{1}^\top Z \leq \bar x \underline{1}^\top$, $0 \leq \bar x \leq \theta$ in which the parameter $\theta$ does not multiply the variables. Therefore the optimal value of the LP is continuous.2012-09-25