Development and application of multistep computational techniques for constrained and unconstrained mathematical functions

Abstract

The application of incomplete relaxation and multistep concepts in the usage of steepest descent methods for the solution of simultaneous linear equations is recognized in the literature. There has been research in the area with very favorable results. Only recently, however, has there been any recognition of the fact that these concepts can be extended to unconstrained optimization problems, and by penalty formulations, also to constrained optimization problems. This holds true not only for steepest descent methods but also for any other "improving direction."

In the discussion of the application of incomplete relaxation and multistep concepts to mathematical functions, very little has been accomplished in the mechanical applying of these ideas. The primary goal of this research, therefore, is to study these concepts and learn a significant amount about them. Algorithms are developed demonstrating the usage of incomplete relaxation and multistep concepts for unconstrained optimization on two directions - coordinate and gradient directions. Discussion of the performance of these methods follows in an attempt to choose some of the better ones. Ten such promising methods are selected and are applied to some complicated unconstrained functions to investigate the adaptability of these methods.

Next, the application of these methods to constrained optimization is examined. Some well known constrained procedures are discussed to show how these applications can be made. A new algorithm for constrained optimization is then developed and used to solve a real world problem both to demonstrate the use of this algorithm and to show that nonlinear programming does have applications to the "real world." Finally, some areas that need further research are mentioned and discussed.

The results, in general, are quite promising. For unconstrained optimization, underrelaxation yields faster convergence than did complete relaxation for all the problems examined. The difference is highly significant; but this is not startling as the same is true in the solution of simultaneous linear equations. Multistep methods are also quite efficient providing some way of efficiently determining or approximating the multistep multipliers can be obtained. In fact, an efficient multistep method is better than anyone step method for these problems.

This research shows that out of the many algorithms tried only a few seem to offer the efficiency and adaptability that is needed. These methods are isolated so that their usage may be facilitated. Each of these requires its own development and to some extent stands alone. complicated unconstrained functions to investigate the adaptability of these methods.

Next, the application of these methods to constrained optimization is examined. Some well known constrained procedures are discussed to show how these applications can be made. A new algorithm for constrained optimization is then developed and used to solve a real world problem both to demonstrate the use of this algorithm and to show that nonlinear programming does have applications to the "real world." Finally, some areas that need further research are mentioned and discussed.

The results, in general, are quite promising. For unconstrained optimization, underrelaxation yields faster convergence than did complete relaxation for all the problems examined. The difference is highly significant; but this is not startling as the same is true in the solution of simultaneous linear equations. Multistep methods are also quite efficient providing some way of efficiently determining or approximating the multistep multipliers can be obtained. In fact, an efficient multistep method is better than anyone step method for these problems.

This research shows that out of the many algorithms tried only a few seem to offer the efficiency and adaptability that is needed. These methods are isolated so that their usage may be facilitated. Each of these requires its own development and to some extent stands alone.