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.

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