# Minimize vector's L-infinity norm

Consider the equation $$\mathbf{v} = \mathbf{v}_0 + A\mathbf{x}$$ where $A$ is an $m\times n$ matrix ($m\gt n$) with entries equal to $-1$, $0$, or $1$ only. Additionally, $1$ and $-1$ only appear once in each row $A$ so the sum of a row is always zero.

$$\mathbf{x}_0 = \mathbf{0}$$

The problem is to find an $\mathbf{x}$ that minimizes the L-infinity norm of $\mathbf{v}$.

What method should I use? Thanks.

-

## 2 Answers

The problem is easily solvable using linear programming.

Alternatively, you can "roll out" the simplex algorithm. Start with the assignment $\mathbf{x} \equiv 0$. At each step, select an extremal entry $v_i$ and one of the two corresponding variables $x_j$. Try either increasing or decreasing $x_j$, depending on its sign, until the situation "balances" at a smaller $L_\infty$ norm (this is also worth doing if the norm doesn't change, though then you need to ensure somehow that you don't "cycle"). Whenever this method offers no improvement for all extremal entries and all corresponding variables, we are at an optimum.

-

Note that to minimize the $\ell_{\infty}$-norm of $v$, you can equivalently minimize an auxiliary variable $t$ such that $\|v\|_{\infty} \leq t$. Thus your problem can be stated as $$\begin{array}{ll} \min_{x,t} & t \\ \text{s.t.} & -t \leq [v_0]_i + [Ax]_i \leq t, \quad i = 1, 2, \ldots, m. \end{array}$$ Note that each $[Ax]_i$ in your case has the form $x_{j_i} - x_{k_i}$, where $j_i$ is the column number of the $+1$ entry in row $i$ and $k_i$ is the column number of the $-1$ entry in row $i$. You can pass the above LP to any Simplex implementation (CPLEX, Gurobi, CLP, ...)

-