# zbMATH — the first resource for mathematics

A global and quadratically convergent method for linear $$l_ \infty$$ problems. (English) Zbl 0756.65087
Authors’ summary: A new globally and quadratically convergent algorithm is proposed for the linear $$l_ \infty$$ problem. This method works on the piecewise linear $$l_ \infty$$ problem directly be generating descent directions – via a sequence of weighted least squares problems – and using a piecewise linear line search to ensure a decrease in the $$l_ \infty$$ function at every step.
It is proven that the ultimately full Newton-like steps are taken where the Newton step is based on the complementary slackness condition holding at the solution. Numerical results suggest a very promising method; the number of iterations required to achieve high accuracy is relatively insensitive to problem size.

##### MSC:
 65K05 Numerical mathematical programming methods 41A50 Best approximation, Chebyshev systems 90C05 Linear programming
Full Text: