A Deep-Cutting-Plane Technique for Reverse Convex Optimization

A large number of problems in engineering design and in many areas of social and physical sciences and technology lend themselves to particular instances of problems studied in this paper. Cutting-plane methods have traditionally been used as an effective tool in devising exact algorithms for solving convex and large-scale combinatorial optimization problems. Its utilization in nonconvex optimization has been also promising. A cutting plane, essentially a hyperplane defined by a linear inequality, can be used to effectively reduce the computational efforts in search of a global solution. Each cut is generated in order to eliminate a large portion of the search domain. Thus, a deep cut is intuitively superior in which it will exclude a larger set of extraneous points from consideration. This paper is concerned with the development of deep-cutting-plane techniques applied to reverse-convex programs. An upper bound and a lower bound for the optimal value are found, updated, and improved at each iteration. The algorithm terminates when the two bounds collapse or all the generated subdivisions have been fathomed. Finally, computational considerations and numerical results on a set of test problems are discussed. An illustrative example, walking through the steps of the algorithm and explaining the computational process, is presented.