×
Gurlitz, T. R.; Jacobsen, S. E.

On the use of cuts in reverse convex programs. (English) Zbl 0699.90085

J. Optimization Theory Appl. 68, No. 2, 257-274 (1991).
A cutting method, using the idea of Tuy cuts, has been suggested in earlier papers as a possible means of solving reverse convex programs. However, the method is fraught with theoretical and numerical difficulties. Stringent sufficient conditions for convergence in n dimensions are given. However, examples of nonconvergence are given and reasons for this nonconvergence are developed. A result of the discussion is a convergent algorithm which combines the idea of the cutting plane method with vertex enumeration procedures in order to numerically improve upon the edge search procedure of R. J. Hillestad [see Oper. Res. 23, 1091-1098 (1975; Zbl 0335.90039)].
Reviewer: T.R.Gurlitz

Cited in 4 Documents

MSC:

90C26 Nonconvex programming, global optimization
65K05 Numerical mathematical programming methods
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C30 Nonlinear programming

Keywords:

nonconvex programming; cutting method; Tuy cuts; reverse convex programs; examples of nonconvergence; vertex enumeration

Citations:

Zbl 0335.90039
Cite Review PDF
Full Text: DOI

References:

[1] Rosen, J. B.,Iterative Solution of Nonlinear Optimal Control Problems, SIAM Journal on Control, Vol. 4, pp. 223-244, 1966. · Zbl 0229.49025 · doi:10.1137/0304021
[2] Avriel, M., andWilliams, A. C.,Complementary Geometric Programming, SIAM Journal on Applied Mathematics, Vol. 19, pp. 125-141, 1970. · Zbl 0319.90035 · doi:10.1137/0119011
[3] Avriel, M., andWilliams, A. C.,An Extension of Geometric Programming with Applications in Engineering Optimization, Journal of Engineering Mathematics, Vol. 5, pp. 187-194, 1971. · doi:10.1007/BF01535411
[4] Vidigal, L. M., andDirector, S. E.,A Design Centering Algorithm for Nonconvex Regions of Acceptability, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. CAD-1, pp. 13-24, 1982. · doi:10.1109/TCAD.1982.1269992
[5] Thach, P. T.,The Design Centering Problem as a D.C. Programming Problem, Preprint Series, Institute of Mathematics, Hanoi, Vietnam, 1986. · Zbl 0651.90065
[6] Meyer, R.,The Validity of a Family of Optimization Methods, SIAM Journal on Control, Vol. 8, pp. 41-54, 1970. · Zbl 0194.20501 · doi:10.1137/0308003
[7] Ueing, U.,A Combinatorial Method to Compute a Global Solution of Certain Nonconvex Optimization Problems, Numerical Methods for Nonlinear Optimization, Edited by F. A. Lootsma. Academic Press, New York, New York, pp. 223-230, 1972. · Zbl 0267.90088
[8] Bansal, P. P., andJacobsen, S. E.,Characterization of Local Solutions for a Class of Nonconvex Programs, Journal of Optimization Theory and Applications, Vol. 15, pp. 549-564, 1975. · Zbl 0281.90078 · doi:10.1007/BF00933745
[9] Bansal, P. P., andJacobsen, S. E.,An Algorithm for Optimizing Network Flow Capacity under Economies of Scale, Journal of Optimization Theory and Applications, Vol. 15, pp. 565-586, 1975. · Zbl 0281.90077 · doi:10.1007/BF00933746
[10] Hillestad, R. J.,Optimization Problems Subject to a Budget Constraint with Economies of Scale, Operations Research, Vol. 23, pp. 1091-1098, 1975. · Zbl 0335.90039 · doi:10.1287/opre.23.6.1091
[11] Hillestad, R. J., andJacobsen, S. E.,Reverse Convex Programming, Applied Mathematics and Optimization, Vol. 6, pp. 63-78, 1980. · Zbl 0448.90044 · doi:10.1007/BF01442883
[12] Tuy, H.,Concave Programming under Linear Constraints, Soviet Mathematics, Vol. 5, pp. 1437-1440, 1964. · Zbl 0132.40103
[13] Tuy, H.,Convex Programs with an Additional Reverse Convex Constraint, Journal of Optimization Theory and Applications, Vol. 52, pp. 463-485, 1987. · Zbl 0585.90071 · doi:10.1007/BF00938217
[14] Tuy, H.,A General Deterministic Approach to Global Optimization via D.C. Programming, Proceedings of Fermat Days 1985: Mathematics for Optimization, Montreal, Canada, pp. 98-118, 1986.
[15] Pardalos, P. M., andRosen, J. B.,Methods for Global Concave Minimization: A Bibliographic Survey, SIAM Review, Vol. 28, pp. 367-379, 1986. · Zbl 0602.90105 · doi:10.1137/1028106
[16] Sen, S., andSherali, H. D.,Nondifferentiable Reverse Convex Programs and Facetial Convexity Cuts via a Disjunctive Characterization, Mathematical Programming, Vol. 37, pp. 169-183, 1987. · Zbl 0626.90078 · doi:10.1007/BF02591693
[17] Thach, P. T.,Convex Programs with Several Additional Reverse Convex Constraints, Preprint Series, Institute of Mathematics, Hanoi, Vietnam, 1985. · Zbl 0609.90091
[18] Muu, L. D.,A Convergent Algorithm for Solving Linear Programs with an Additional Reverse Convex Constraint, Kybernetika, Vol. 21, pp. 428-435, 1985. · Zbl 0596.90081
[19] Fulop, J.,A Finite Cutting Plane Method for Solving Linear Programs with an Additional Reverse Convex Constraint, Working Paper, Department of Operations Research, Hungarian Academy of Science, Budapest, Hungary, 1988.
[20] Carvajal-Moreno, R.,Minimization of Concave Functions Subject to Linear Constraints, Report ORG-72-3, Operations Research Center, University of California, Berkeley, California, 1972.
[21] Hillestad, R. J., andJacobsen, S. E.,Linear Programs with an Additional Reverse Convex Constraint, Applied Mathematics and Optimization, Vol. 6, pp. 257-269, 1980. · Zbl 0435.90065 · doi:10.1007/BF01442898
[22] Bohringer, M. C.,Linear Programs with Additional Reverse Convex Constraints, PhD Thesis, University of California, Los Angeles, California, 1983.
[23] Dyer, M. E., andProll, L. G.,An Algorithm for Determining All Extreme Points of a Convex Polyhedron, Mathematical Programming, Vol. 12, pp. 81-91, 1977. · Zbl 0378.90059 · doi:10.1007/BF01593771
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.