Equivalence of Linear Programming Problem

155 Views Asked by At

Problem

Given $p+1$ matrices $A_0, A_1, \cdots, A_p \in \mathbb{R}^{m\times n}$, find the vector $x \in \mathbb{R}^p$ that minimizes $$ \max_{\Vert y\Vert_1=1}\Vert (A_0 + x_1A_1+\cdots+x_pA_P)y\Vert_1 $$

What I Have Done

Edit: There are something mistakes in my previous post and I deleted them for clarity.

What I then noticed is the fact that $$ \max_{\Vert y \Vert_1}(Ay)=\max_{j=1,2,\cdots,n}\sum_{i=1}^{m}\vert A_{ij}\vert $$ which is the maximum column sum with entries of absolute value. Note here $A$ stands for $A_0+x_1A_1+\cdots+x_pA_p$ in the problem.

Then if we let $t=\max_{j=1,2,\cdots,n}\sum_{i=1}^{m}\vert (A_0+x_1A_1+\cdots+x_pA_p)_{ij}\vert$, the problem could be written as

$$\min t\\ {t \geq \sum_{i=1}^{m}\vert (A_0+x_1A_1+\cdots+x_pA_p)_{ij}\vert}$$

However, I do not think I have done everything, since in this way the unknowns are on both sides of the inequality in the constraint (which is $x_i$ and $t$). Now I do not know what to do to proceed.

Could anyone help me, thank you in advance.