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.