Abstract
Branch and bound approaches for nonconvex programming problems had been given in [1] and [4]. Crucial for both are the use of rectangular partitions, convex envelopes and separable nonconvex portions of the objective function and constraints. We want to propose a similar algorithm which solves a sequence of problems in each of which the objective function is convex or even linear. The main difference between this approach and previous approaches is the use of general compact partitions instead of rectangular ones and a different refining rule such that the algorithm does not rely on the concept of convex envelopes and handles non-separable functions.
First we describe a general algorithm and prove a convergence theorem under suitable regularity assumptions. Then we give as example an algorithm for concave minimization problems.
Similar content being viewed by others
References
J.E. Falk and R.M. Soland, “An algorithm for separable nonconvex programming problems”,Management Science 15 (1969) 550–569.
R. Horst, “Zur Charakterisierung affin-linearer Hüllfunktionale”,Zeitschrift für A'ngewandte Mathematik und Mechanik, to appear.
R.T. Rockafellar,Convex analysis (Princeton University Press, Princeton, N.J., 1970).
R.M. Soland, “An algorithm for separable nonconvex programming problems II: nonconvex constraints”,Management Science 17 (1971) 759–773.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Horst, R. An algorithm for nonconvex programming problems. Mathematical Programming 10, 312–321 (1976). https://doi.org/10.1007/BF01580678
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF01580678