5
$\begingroup$

Suppose I have two systems of $n$ homogeneous inequalities of $k$ variables: $$Ax \geq 0$$ and $$Bz \geq 0,$$ where both $A$ and $B$ are $n \times k$ matrices such that for any $i=1, \ldots, n$, and $j=1, \ldots, k$, we have $|a_{ij}-b_{ij}|\leq \epsilon$, where $\epsilon>0$ is very small.

Can I conclude from here that there is some distance $\phi(\epsilon)$ (such that $\phi(\epsilon) \rightarrow 0$ as $\epsilon \rightarrow 0$) with the following property: for any solution $x_0$ to the first system with $\|x_0\|=1$ there is a solution $z_0$ to the second system such that $$\|x_0-z_0\|\leq \phi(\epsilon)$$ for some norm $\|\cdot\|$ in $\mathbb{R}^k$? I am interested in the form (or approximation) of such $\phi(\epsilon)$.

EDIT. I am interested in situations when both systems have non-trivial (non-zero) solutions. I would be even willing to assume that both solution sets have non-empty interiors if this would help.

$\endgroup$
  • $\begingroup$ No; you must take $x_0$ s.t. $||x_0||=1$. $\endgroup$ – loup blanc Nov 11 '17 at 16:05
  • $\begingroup$ @loupblanc Yes, I agree with your comment and will make edits to the question accordingly. $\endgroup$ – Neznajka Nov 11 '17 at 18:05
2
+50
$\begingroup$

Look at the case where $A$ has a large condition-number.

EDIT 1. For example $A=\begin{pmatrix}0&1\\u&-1\end{pmatrix},B=\begin{pmatrix}-2u&1\\u&-1\end{pmatrix}$ where $u$ is a small $>0$ number; take $x_0=(1,0) $. Then $||x_0-z_0||\ge 1$.

EDIT 2. Answer to Neznajka . The above example shows that $\phi$ does not exist.

Indeed, let $\epsilon >0$. If $u=\epsilon/2$, then $|a_{i,j}-b_{i,j}|\leq \epsilon$. One has $Ax_0\geq 0,||x_0||=1$; $Bz\geq 0$ where $z=[x,y]^T$ is equivalent to $ux\geq y\geq 2ux$, that implies $x\leq 0,y\leq 0$. Thus, if $Bz_0\geq 0$, then $||x_0-z_0||\geq 1$ and finally $\phi(\epsilon)\geq 1$.

EDIT 3. I think that a correct formulation of your problem is as follows.

Let $A\in M_{n,k}$ where $\text{rank}(A)=n\leq k$. Show that there are $a>0$ and a function $\phi:t\in (0,a)\rightarrow (0,+\infty)$ that tends to $0$ with $t$, s.t. for every $B\in M_{n,k},x_0\in\mathbb{R}^k$ satisfying $||A-B||<a,Ax_0\geq 0,||x_0||=1$, there is $z_0\in\mathbb{R}^k$ s.t. $Az_0\geq 0,||x_0-z_0||\leq \phi(||A-B||)$.

$\endgroup$
  • $\begingroup$ I see it now. Thank you. $\endgroup$ – Neznajka Nov 14 '17 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.