A Decomposable Nonlinear Programming Approach

Nonlinear, i.e., pseudo-concave, programming algorithms attempt to maximize an objective function f(x) subject to x in a feasible set. Large step algorithms seek this maximum by recursively generating both a sequence of points {x^k} and a sequence of directions {s^k}. Given a point x^k and a direction s^k the next point x^k+1 is the feasible point that gives the largest value to the objective function along the ray emanating from x^k in the direction s^k. The key difference among large step procedures is in the choice of s_k. This paper explores several means for selecting the direction s_k. Some of these methods are particularly suited for large scale systems with a large number of constraints, as they decompose the problem and require the solution of only a finite number of subproblems. These algorithms have an interesting interpretation in terms of management by exception. They also lead naturally into a discussion of jamming or zigzagging; that phenomenon which plagues all large step methods and can lead to non-convergence. Jamming is studied for its cause and curve via an example and counter-example. For linear constraints a special large step method which proceeds by suboptimization in manifolds is proposed that avoids jamming. It is then shown that the Dantzig quadratic programming algorithm is a special case of this method. A straightforward geometric proof of the Dantzig method is then possible.