On computational aspects of bounded linear least squares problems

ABSTRACT

The paper describes numerical experiments with active set methods for solving bounded linear least squares problems. It concentrates on two problems that arise in the implementation of the active set method. One problem is the choice of a good starting point. The second problem is how to move out of a “dead point.” The paper investigates the use of simple iterative methods to solve these problems. The results of our experiments indicate that the use of Gauss-Seidel iterations to obtain a starting point is likely to provide large gains in efficiency. Another interesting conclusion is that dropping one constraint at a time is advantageous to dropping several constraints at a time.

REFERENCES

• 1: A. Dax, The smallest point of a polytope, Journal of Optimization Theory and Applications, v.64 n.2, p.429-432, Feb. 1990 [doi>10.1007/BF00939458]
• 2: R. Fletcher, Practical methods of optimization; (2nd ed.), Wiley-Interscience, New York, NY, 1987
• 3: FLETCHER, R., AND JACKSON, M.P. Minimization of a quadratic function of many variables subject only to upper and lower bounds. J. Inst. Math. Appl. 14 (1974), 159-174.
• 4: GmL, P. E., MURRAY, W., AND WRIGHT, M. H. Practical Optimization. Academic Press, London, 1981.
• 5: GOLDFARB, D. F. xtensions of Newton's method and simplex methods for solving quadratic programs. In Numerical Methods for Nonlinear Optimization, F. A. Lootsma, Ed. Academic Press, 1972, pp. 239-254.
• 6: LAWSON, C. L., AND HANSON, R.J. Solving Least Squares Problems. Prentice-Hall, Englewood Cliffs, N.J., 1974.
• 7: LENARD, M. L. A computational study of active set strategies in nonlinear programming with linear constraints. Math. Program. 16 (1979), 81-97.
• 8: SCHITTKOWSKI, I~{. The numerical solution of constraints linear least-squares problems. IMA J. Numer. Anal. 3 (1983)~ 11-36.
• 9: WOLFE, P. Algorithm for a least-distance programming problem. Math. Program. Stud. 1 (1974), 190-205.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Least squares methods

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
active set methods, bounded least squares, dead points, numerical experiments, starting point