Stability of the Dual Cutting-Plane Algorithm for Concave Programming.

Demonstration of a computational approach to large-scale optimization of decomposable systems based on a modification of Zangwell's dual cutting-plane algorithm for concave programming. The discussion is concerned with situations in which the subproblems cannot be solved exactly in a finite number of steps, the usual case for nonlinear problems. The problem is reduced to a sequence of Lagrangean maximizations and these separate for a problem with linearly coupled subsystems. It is shown that unless one has a finite algorithm that solves the subproblem to within a given tolerance, the algorithm will not be stable. If the algorithm stops at a given iteration, a near-optimal solution results; if the algorithm does not stop, it converges; and if the convergence is infinite, an optimal solution is approached. A geometrical interpretation is presented. This study is part of RAND's research effort in specialized mathematical programming useful for allocation supply items such as Air Force spares. The dual cutting-plane algorithm is currently being used to solve approximately certain nonconcave programs arising from Air Force logistics problems. (See also RM-5829.) 22 pp. Ref.