Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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.

share|improve this answer

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, ...)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.