A Global and Quadratically Convergent Method for Linear $l_\infty $ Problems
Authors:
- Thomas F. ColemanTCThomas F. Coleman
- Yuying LiYLYuying Li
- 1 August 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Numerical Analysis
- Vol. 29 (4) , 1166-1186
Abstract
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 by 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 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.
Keywords
This publication has 7 references indexed in Scilit:
- A Globally and Superlinearly Convergent Algorithm for Convex Quadratic Programs with Simple BboundsSIAM Journal on Optimization, 1993
- A globally and quadratically convergent affine scaling method for linearℓ 1 problemsMathematical Programming, 1992
- A Superlinearly Convergent Polynomial Primal-Dual Interior-Point Algorithm for Linear Programming1991
- Primal Methods are Better than Dual Methods for Solving Overdetermined Linear Systems in the $l_\infty $ Sense?SIAM Journal on Numerical Analysis, 1989
- L/sub 1/ and L/sub infinity / minimization via a variant of Karmarkar's algorithmIEEE Transactions on Acoustics, Speech, and Signal Processing, 1989
- On the Method of Weighting for Equality-Constrained Least-Squares ProblemsSIAM Journal on Numerical Analysis, 1985
- Quasi-Newton Methods, Motivation and TheorySIAM Review, 1977