# Parametric Linear Program: Continuous Solution?

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

-
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