Successive Refinement of Large Multicell Models
Achiya Dax · SIAM Journal on Numerical Analysis · 1985
This paper presents and analyzes a new relaxation method for minimizing a function of many Variables. The minimized function is associated with a model that is composed of a large number of “cells.” (In some applications the terms “elements,” “mesh points” or “facilities” are more appropriate.) Such problems often arise in models that are based on finite difference or finite element methods. The new method, which we call the Successive Refinement method, utilizes the special structure of the model to save on both storage and computations. Although the S.R. method has many features in common with the nonlinear S.O.R. method, there is a basic difference between the two methods. The difference is that the steps of the S.R. method are not using relaxation parameters; instead each of its steps is aimed to reduce the objective function value as much as possible. This gives us a robust algorithm that is able to solve problems that the S.O.R. method cannot handle. Such problems are, for example, minimization of a nonconvex function, minimization when derivatives are not available and minimization of a nonquadratic function subject to simple bounds. The case when the bounds are not simple is also discussed. The paper considers acceleration techniques that speed up the convergence of the S.R. method. These techniques are the Modified S.O.R. method, the Cyclic S.R. method and Successive Mesh Refinement. The use of these techniques was tested on the Clamped Plate Problem, the Minimal Surface Problem and other problems. The results indicate that the proposed method compares favorably with the best of the other methods for large scale minimization.