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

by Bennett L. Fox


Purchase Print Copy

 FormatList Price Price
Add to Cart Paperback22 pages $20.00 $16.00 20% Web Discount

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.

This report is part of the RAND Corporation Research memorandum series. The Research Memorandum was a product of the RAND Corporation from 1948 to 1973 that represented working papers meant to report current results of RAND research to appropriate audiences.

The RAND Corporation is a nonprofit institution that helps improve policy and decisionmaking through research and analysis. RAND's publications do not necessarily reflect the opinions of its research clients and sponsors.