Parametric Linear Program: Continuous Solution?

271 Views Asked by At

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

There are 1 best solutions below

11
On BEST ANSWER

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