A Decomposable Nonlinear Programming Approach

Willard I. Zangwill
Additional contact information
Willard I. Zangwill: University of California

Operations Research, 1967, vol. 15, issue 6, 1068-1087

Abstract: 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.

Date: 1967
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.15.6.1068 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:15:y:1967:i:6:p:1068-1087

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().