An algorithm for separable nonconvex programming problems. (English) Zbl 0172.43802

Falk, James E.; Soland, Richard M.

Manage. Sci., Theory 15, 550-569 (1969).

Summary: We present an algorithm for solving mathematical programming problems of the form: Find \(x = (x_{1},\cdots , x_{n})\) to minimize \(\sum \varphi _{i}(x_{i})\) subject to x \(\in G\) and \(l\leq x \leq L\). Each \(\varphi _{i}\) is assumed to be lower semicontinuous, possibly nonconvex, and \(G\) is assumed to be closed. The algorithm is of the branch and bound type and solves a sequence of problems in each of which the objective function is convex. These problems correspond to successive partitions of the feasible set. Two different rules for refining the partitions are considered; these lead to convergence of the algorithm under different requirements on the problem functions. Examples are given, and computational considerations are discussed.

MSC:

90C26	Nonconvex programming, global optimization
90C57	Polyhedral combinatorics, branch-and-bound, branch-and-cut

Keywords:

operations research