A penalty continuation method for the ∓∞ solution of overdetermined linear systems |
| |
Authors: | Mustafa C. Pinar Samir Elhedhli |
| |
Affiliation: | (1) Department of Industrial Engineering, Bilkent University Ankara, 06533, Turkey;(2) Graduate Program in Management, McGill University Montréal, H3V1G3, Canada |
| |
Abstract: | A new algorithm for the ∓∞ solution of overdetermined linear systems is given. The algorithm is based on the application of quadratic penalty functions to a primal linear programming formulation of the ∓∞ problem. The minimizers of the quadratic penalty function generate piecewise-linear non-interior paths to the set of ∓∞ solutions. It is shown that the entire set of ∓∞ solutions is obtained from the paths for sufficiently small values of a scalar parameter. This leads to a finite penalty/continuation algorithm for ∓∞ problems. The algorithm is implemented and extensively tested using random and function approximation problems. Comparisons with the Barrodale-Phillips simplex based algorithm and the more recent predictor-corrector primal-dual interior point algorithm are given. The results indicate that the new algorithm shows a promising performance on random (non-function approximation) problems. |
| |
Keywords: | 65K05 65D10 |
本文献已被 SpringerLink 等数据库收录! |
|