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
    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}$?2012-09-23
  • 0
    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?2012-09-23
  • 1
    The objective is not $\|Y\|_1$, it is $\|Z\|_\infty$.2012-09-23
  • 0
    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?2012-09-23
  • 0
    Sorry, it is the infinity norm of the vector of column sums of $Z$.2012-09-23
  • 0
    And from [http://en.wikipedia.org/wiki/Matrix_norm], the infinity norm of the vector of column sums of $Z$ is actually $\left\| Z \right\|_1$. So let me change the question to make it more compact.2012-09-23
  • 1
    OK, in that sense it is $\|Z\|_1$.2012-09-23
  • 0
    So also for $\mathbb{Y}$ compact I expect to have $x^*$ continuous...2012-09-23
  • 0
    We also have to worry about whether such $Z$ exists. It may be that this is the case only for one particular $\theta$. So $x^*(\theta)$ is finite only for that $\theta$, otherwise it's $+\infty$.2012-09-23
  • 0
    Ok. In my problem, I know that there always exists a finite solution. In particular we always have $\left\| Z \right\|_1 \leq 1$. This is why in the previous formulation I wrote $x \in [0,1]$. Now I made it explicit in the question.2012-09-23
  • 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