0

I'm trying to show that the two problems are equivalent

Let $\Bbb A = \{A_1, \dots, A_n\}$ where $A_i \in \Bbb R^{m \times n}$ and $b\in \mathbb{R}^m$

Then

$$\min_{x\in \mathbb{R}^n} \max_{i=1, \dots, k} \|A_ix - b\|$$

is equivalent to

$$\min_{x\in \mathbb{R}^n} \space \sup \{\|Ax - b\| \mid A \in \text{conv}(A_1, \dots, A_n)\}$$

Where $\text{conv}$ is the convex hull.

I know that two problems are equivalent when from the solution from one you can find the solution of the other, but I'm having trouble seeing how to show this.

Anyone have any ideas?

Nathanael Skrepek
  • 2,558
Oliver G
  • 4,792

1 Answers1

1

Note that every element in $A\in\operatorname{conv}(A_1,\dots,A_k)$ can be written as $A = \sum_{i=1}^n \lambda_i A_i$, where $\lambda_i\in [0,1]$ and $\sum_{i=1} \lambda_i = 1$. In particular we also have $b = \sum_{i=1} \lambda_i b$. Consequently we obtain the following inequality \begin{align} \|Ax - b\| &= \Big\|\sum_{i=1}^n \lambda_i A_i x -\sum_{i=1}^n \lambda_i b\Big\| =\Big\|\sum_{i=1}^n \lambda_i(A_ix-b)\Big\| \leq \sum_{i=1}^n \lambda_i\|A_i x-b\|\\ &\leq \sum_{i=1}^n \lambda_i \max_{i=1,\dots,k}\|A_i x-b\| = \max_{i=1,\dots,k}\|A_i x-b\| \end{align} for arbitrary $x\in \mathbb{R}^n$ and $b\in \mathbb{R}^m$. One immediate consequence is $$ \sup_{A\in\operatorname{conv}(A_1,\dots,A_k)} \|Ax - b\| \leq \max_{i=1,\dots,k}\|A_i x-b\|. $$ On the other hand since every $A_i \in \operatorname{conv}(A_1,\dots,A_k)$ we also have $$ \sup_{A\in\operatorname{conv}(A_1,\dots,A_k)} \|Ax - b\| \geq \max_{i=1,\dots,k}\|A_i x-b\|. $$ Hence, we have equality. Clearly this won't change if we minimize over $x\in \mathbb{R}^n$.

So this has nothing to do with the minimization problem. In fact this is the key essence of the simplex algorithm.

Nathanael Skrepek
  • 2,558