×

Sequential convexification in reverse convex and disjunctive programming. (English) Zbl 0683.90063

Summary: This paper is about a property of certain combinatorial structures, called sequential convexifiability, shown by the first author [“Disjunctive programming: Properties of the convex hull of feasible points”, MSRR No.348, Carnegie Mellon Univ. (Pittsburgh/PA 1974) and Ann. Discrete Math. 5, 3-51 (1979; Zbl 0409.90061)] to hold for facial disjunctive programs. Sequential convexifiability means that the convex hull of a nonconvex set defined by a collection of constraints can be generated by imposing the constraints one by one, sequentially, and generating each time the convex hull of the resulting set. Here we extend the class of problems considered to disjunctive programs with infinitely many terms, also known as reverse convex programs, and give necessary and sufficient conditions for the solution sets of such problems to be sequentially convexifiable. We point out important classes of problems in addition to facial disjunctive programs (for instance, reverse convex programs with equations only) for which the conditions are always satisfied. Finally, we give examples of disjunctive programs for which the conditions are violated, and so the procedure breaks down.

MSC:

90C25 Convex programming
90C09 Boolean programming
52A20 Convex sets in \(n\) dimensions (including convex hypersurfaces)
90B35 Deterministic scheduling theory in operations research

Citations:

Zbl 0409.90061
Full Text: DOI

References:

[1] M. Avriel,Nonlinear Programming: Analysis and Methods (Prentice Hall, Englewood Cliffs, NJ, 1976).
[2] E. Balas, ”Disjunctive programming: Properties of the convex Hull of feasible points,” MSRR No. 348, Carnegie Mellon University (Pittsburgh, PA, 1974). · Zbl 0921.90118
[3] E. Balas, ”Disjunctive programming,”Annals of Discrete Mathematics 5 (1979) 3–51. · Zbl 0409.90061 · doi:10.1016/S0167-5060(08)70342-X
[4] E. Balas, ”On the facial structure of scheduling polyhedra,”Mathematical Programming Study 24 (1985) 179–218. · Zbl 0582.90053
[5] C.E. Blair and R.G. Jeroslow, ”Extensions of a theorem of Balas,”Discrete Applied Mathematics 9 (1984) 11–26. · Zbl 0592.90071 · doi:10.1016/0166-218X(84)90087-8
[6] R.J. Hillestad and S.E. Jacobsen, ”Reverse convex programming,”Applied Mathematics and Optimization 6 (1980) 63–78. · Zbl 0448.90044 · doi:10.1007/BF01442883
[7] R.G. Jeroslow, ”A cutting plane game for facial disjunctive programs,”SIAM Journal on Control and Optimization 18 (1980) 264–281. · Zbl 0434.90063 · doi:10.1137/0318018
[8] R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970). · Zbl 0193.18401
[9] J.B. Rosen, ”Iterative solution of nonlinear optimal control problems,”SIAM Journal on Control 4 (1966) 223–244. · Zbl 0229.49025 · doi:10.1137/0304021
[10] S. Sen and H.D. Sherali, ”Nondifferentiable reverse convex programs and facetial convexity cuts via a disjunctive characterization,”Mathematical Programming 37 (1987) 169–183. · Zbl 0626.90078 · doi:10.1007/BF02591693
[11] H. Tuy, ”Global minimization of a concave function subject to mixed linear and reverse convex constraints,” Institute of Mathematics (Hanoi, Vietnam). To appear in Proceedings of the IFIP Conference on ”Recent Advances in System Modelling and Optimization,” Hanoi, 1983. · Zbl 0699.90083
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.