A row relaxation method for large minimax problems (Q688632)

The problem \(\min\|{ A}{ x}-{ b}\|_ \infty\) is considered, where \({ A}\) is a real \(m\times n\) matrix, \({ b}= (b_ 1,\dots,b_ m)^ T\in\mathbb{R}^ m\), \({ x}=(x_ 1,\dots,x_ n)^ T\in\mathbb{R}^ n\), and the norm is given by \(\|{ A}{ x}-{ b}\|_ \infty= \max_{1\leq i\leq m} | (Ax)_ i- b_ i|\), where \((Ax)_ i\) denotes the \(i\)th row of \(Ax\). By solving the dual problem \[ \min\textstyle{{1\over 2}}\|{ A}^ T{ y}\|^ 2_ 2- \varepsilon{ b}^ T{ y}+\textstyle{{1\over 2}}\bigl(\max\{0,\|{ y}\|_ 1- 1\}\bigr)^ 2, \] where \(\varepsilon\) is a given positive constant, a row relaxation method for solving the doubly regularized minimax problem \[ \min\textstyle{{1\over 2}} \varepsilon\bigl(\| x\|^ 2_ 2+\|{ A}{ x}-{ b}\|^ 2_ \infty\bigr)+\|{ A}{ x}-{ b}\|_ \infty \] is given. Numerical results are included.