0
$\begingroup$

I have the following problem:

$$\min_{x\in X}\|Mx-c\|_{\infty}$$

I am considering a particular case, in which: $$M=\left[\begin{array}{cc} a & 1-a\\ b & 1-b \end{array}\right], c=\left[\begin{array}{c} A\\ B \end{array}\right] $$ where $0\leq a<b\leq1$ (so $\det(M)<0$ and thus $M$ is invertible), and $ 0\leq A<B\leq1$.

Also, $X$ is all the vectors whose elements are both in $[0,1]$. I have shown that the optimal unconstrained solution to $Mx=c$ lies outside $X$, so I know that this minimum is strictly positive.

My goal is to find a general upper bound for the above problem; i.e, an $\alpha$ (expressed in terms of the values $a, b, A, B$, which I don't know in advance) such that

$$\min_{x\in X}\|Ax-b\|_{\infty} \leq \alpha$$

I know that this problem can be formulated as an LP (see here), but I'm not sure if that buys me something - are there generic closed-form upper bounds for things that can be solved by an LP? Are there other approaches I can use? I am willing to assume more about the problem, in particular that the difference $B-A$ is somehow tied to the difference $b-a$.

Thanks!

$\endgroup$
  • $\begingroup$ If you solve the LP and obtain the optimal solution to the problem then any number higher than the optimum will be an upper bound to the problem. The optimal solution is also an upper bound (in fact, it is the best upper bound in terms of tightness). Since $A$ is only a $2\times 2$ matrix, it will not be too difficult to obtain optimal solution. $\endgroup$ – YukiJ Oct 8 '18 at 10:41
  • $\begingroup$ A simple a priori estimate is given by $\lVert Ax-b \rVert_{\infty} \leq \lVert A \rVert_{\infty} + \lVert b \rVert_{\infty}$, do you search for something more? $\endgroup$ – Hugo Oct 8 '18 at 10:41
  • $\begingroup$ I have edited the question with further details about the problem. @Hugo I'm afraid this bound will be vacuous (larger than 1). If I could show that there's an instance of my problem for which $ \min_{x\in X}\|Mx-c\|=\|M\|_{\infty}+\|c\|_{\infty}$ that would also be great, but I suspect that's not the case. $\endgroup$ – galoosh33 Oct 8 '18 at 11:13
  • $\begingroup$ @YukiJ why? I think $\det(M)=a-b$ so if $a<b$ it's always strictly smaller than zero, regardless of $b$. $\endgroup$ – galoosh33 Oct 8 '18 at 11:58

Your Answer

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

Browse other questions tagged or ask your own question.