Cutting Plane Methods Without Nested Constraint Sets

摘要

General conditions are given for the convergence of a class of cutting-plane algorithms without requiring that the constraint sets for the subproblems be sequentially nested. Conditions are given under which inactive constraints may be dropped after each subproblem. Procedures for generating cutting-planes include that of Kelley and a generalization of that used by Zoutendisk and Veinott. For algorithms with nested constraint sets, these conditions reduce to a special case of those of Zangwill for such problems and include as special cases the algorithms of Kelley and Veinott. An arithmetic convergence rate is given. (Author)