Abstract
A new algorithm is presented for minimizing a linear function subject to a set of linear inequalities and one additional reverse convex constraint. The algorithm utilizes a conical partition of the convex polytope in conjuction with its facets in order to remain on the level surface of the reverse convex constraint. The algorithm does not need to solve linear programs on a set of cones which converges to a line segment.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Avriel and A.C. Williams, Complementary geometric programming, SIAM J. Appl. Math. 19 (1970) 125–141.
M. Avriel and A.C. Williams, An extension of geometric programming with applications in engineering optimization, J. Eng. Math. 5 (1971) 187–194.
P.P. Bansal and S.E. Jacobsen, An algorithm for optimizing network flow capacity under economies of scale. J. Optimization Theory Appl. 15 (5) (1975) 565–586.
P.P. Bansal and S.E. Jacobsen, Characterization of local solutions for a class of nonconvex programs, J. Optimization Theory Appl. 15 (5) (1975).
J. Fulop, 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 (1988).
R.J. Hillestad and S.E. Jacobsen, Reverse convex programming, Appl. Math. Optimization 6 (1980) 63–78.
R.J. Hillestad and S.E. Jacobsen, Linear programs with an additional reverse convex constraint. Appl. Math. Optimization 6 (1980) 257–269.
R.J. Hillestad, Optimization problems subject to a budget constraint with economies of scale, Oper. Res. 23 (6) (1975) 1091–1098.
R. Meyer, The validity of a family of optimization methods, SIAM J. Control 8 (1970) 41–54.
B. M. Murtagh and M.A. Saunders, MINOS 5.1 user's guide, Technical Report SOL 83-20R, Systems Optimization Laboratory, Department of Operations Research, Stanford University (January 1987).
L.D. Muu, A convergent algorithm for solving linear programs with an additional reverse convex constraint, Kybernetika 21 (1985) 428–435.
C. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity (Prentice Hall, Englewood Cliffs, NJ, 1982).
P.M. Pardalos, Generation of large-scale quadratic programs for use as global optimization test problems, ACM Trans. Math. Software 13 (2) (1987) 133–137.
P.M. Pardalos and J.B. Rosen, Methods for global concave minimization: A bibliographic survey, SIAM Rev. (1986).
J.B. Rosen, Iterative solution of nonlinear optimal control problems, SIAM J. Control 4 (1966) 223–244.
S. Sen and H.D. Sherali, Nondifferentiable reverse convex programs and facetial convexity cuts via a disjunctive characterization, Math. Programming 37 (1987) 169–183.
Y.Y. Sung and J.B. Rosen, Global minimum test problem construction, Math. Programming 24 (1982) 353–355.
P.T. Thach Convex programs with several additional reverse convex constraints, Preprint Series, Institute of Mathematics, Hanoi (1985).
P.T. Thach, The design centering problem as a d.c. programming problem, Preprint Series, Institute of Mathematics, Hanoi (1986).
H. Tuy. Concave programming under linear constraints, Sov. Math. 5 (1964) 1437–1440.
H. Tuy, A general deterministic approach to global optimization via d.c. programming,Fermat Days 1985: Mathematics for Optimization (1986) pp. 98–118.
H. Tuy, Convex programs with an additional reverse convex constraint, J. Optimization Theory Appl. 52 (3) (1987) 463–485.
U. Ueing, A combinatorial method to compute a global solution of certain non-convex optimization problems, in:Numerical Methods for Non-linear Optimization, ed. F.A. Lootsma (Academic Press, 1972), pp. 223–230.
L.M. Vidigal and S.W. Director, A design centering algorithm for nonconvex regions of acceptability, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, CAD 1 (1) (Jan. 1982).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Ben Saad, S., Jacobsen, S.E. A level set algorithm for a class of reverse convex programs. Ann Oper Res 25, 19–42 (1990). https://doi.org/10.1007/BF02283685
Issue Date:
DOI: https://doi.org/10.1007/BF02283685