Abstract
Existing techniques for solving nonconvex programming problems often rely on the availability of lower and upper bounds on the problem variables. This paper develops a method for obtaining these bounds when not all of them are availablea priori. The method is a generalization of the method of Fourier which finds bounds on variables satisfying linear inequality constraints. First, nonlinear inequality constraints are converted to equivalent sets of separable constraints. Generalized variable elimination techniques are used to reduce these to constraints in one variable. Bounds on that variable are obtained and an inductive process yields bounds on the others.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Avriel, M. (1973), Methods for Solving Signomial and Reverse Convex Programming Problems, in Avrielet al. (eds.),Optimization and Design, Prentice Hall Inc., Englewood Cliffs, NJ 307–320.
Benson, H. P. (1975), A Finite Algorithm for Concave Minimzation over a Polyhedron,Naval Research Logistics Quarterly 32, 165–177.
Benson, H. P. (1982), On the Convergence of Two Branch-and-Bound Algorithms for Nonconvex Programming Problems,Journal of Optimization Theory and Applications,36, 129–134.
Falk, J. E. and R. M. Soland (1969), An Algorithm for Separable Nonconvex Programming Problems,Management Science 15, 550–569.
Fiacco, A. V. and G. P. McCormick (1990),Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley & Sons, New York (1968); reprinted asClassics in Applied Mathematics Vol. 4, SIAM, Philadelphia, PA.
Fourier, J. G. J. (1826),Solution d'une Question Particulliere du Calcul des Inegalities, Oeuvres II, Paris, pp. 317–328.
Gabot, A. V. (1973), Variations on a Cutting Plane Method for Solving Concave Minimization Problems with Linear Constraints,Naval Research Logistics Quarterly 21, 265–274.
Hamed, A. (1990), Calculation of Bounds on Variables and Underestimating Convex Functions for Nonconvex Functions, D.Sc. Dissertation, Department of Operations Research, George Washington University, Washington, DC.
Hamed, A. and G. P. McCormick (1991), Calculation of Bounds on Variables Satisfying Nonlinear Inequality Constraints, Technical Paper T-544/91, Department of Operations Research, George Washington University, Washington, DC.
Hillestad, R. J. and S. E. Jacobsen (1980a), Reverse Convex Programming,Applied Mathematics and Optimization 6, 63–78.
Hillestad, R. J. and S. E. Jacobsen, (1980b), Linear Programs with an Additional Reverse Convex Constraint,Applied Mathematics and Optimization 6, 257–269.
Hoffman, K. L. (1981), A Method for Globally Minimizing Concave Functions over Convex Sets,Mathematical Programming 20, 22–32.
Horst, R. (1976a), A New Branch and Bound Approach for Concave Minimization Problems,Lecture Notes in Computer Science 41, 330–337.
Horst, R. (1976b), An Algorithm for Nonconvex Programming Problems,Mathematical Programming 10, 312–321.
Horst, R. (1984), On the Global Minimization of Concave Functions,Operations Research Spektrum 6, 195–205.
Horst, R. (1990a), 'Deterministic Global Optimization; Some Recent Advances and New Fields of Application,Naval Research Logistics Quarterly 37, 433–471.
Horst, R. and H. Tuy (1990b),Global Optimization;Deterministic Approaches, Springer-Verlag Berlin-Heidelberg.
Horst, R. and N. V. Thoai (1988), Branch-and-Bound Methods for Solving Systems of Nonlinear Equations and Inequalities,Journal of Optimization Theory and Application 58, 139–146.
Horst, R., N. V. Thoai and H. P. Benson. (1988), Concave Minimization via Conical Partitions and Polyhedral Outer Approximation, Discussion Paper No. 140, Center for Econometrics and Decision Sciences, University of Florida, submitted.
Jones, A. P. and R. M. Soland (1969), A Branch and Bound Algorithm for Multi-Level Fixed Charge Problems,Management Science 16, 67–76.
Leaver, S. G. (1984), Computing Global Maximum Likelihood Parameter Estimates for Product Models for Frequency Tables Involving Indirect Observations, D.Sc. dissertation, Department of Operations Research, The George Washington University.
Leaver, S. G. and G. P. McCormick. (1984), Formulas for Updating the Generalized Inverse of a Symmetric Rank Two Matrix Composed of Two Nonsymmetric Dyads. Technical Paper Serial T-493/84, Institute for Management Science and Engineering, The George Washington University.
Mancini, L. and G. P. McCormick (1975), Bounding Global Minima,Mathematics of Operations Research 1, 50–53.
Mancini, L. and G. P. McCormick (1979), Bounding Global Minima with Interval Arithmetic,Operations Research 27, 743–754.
McCormick, G. P. (1976), Computability of Global Solutions to Factorable Nonconvex Programs: Part I -Convex Underestimating Problems,Mathematical Programming 10, 147–175.
McCormick, G. P. (1980), Locating an Isolated Global Minimizer of a Constrained Nonconvex Program,Mathematics of Operations Research 5, 435–443.
McCormick, G. P. (1983),Nonlinear Programming: Theory, Algorithms and Applications, John Wiley & Sons, New York.
McCormick, G. P. (1985),Global Solutions to Factorable Nonlinear Optimzation Problems Using Separable Programming Techniques, NBSIR 85-3206, U.S. Department of Commerce, National Bureau of Standard, Gaithersburg, MD.
Moore, R. E. (1966),Interval Analysis, Prentice-Hall, Englewood Cliffs. New Jersey.
Moore, R. E. (1979),Methods and Applications of Interval Analysis, SIAM, Philadelphia.
Rosen, J. B. (1979), Minimization of a Linearly Constrained Concave Function by Partition of Feasible Domain,Matehmatics of Operations Research 8, 215–230.
Sen, S. and H. D. Sherali (1987), Nondifferentiable Reverse Convex Programs and Facial Convexity Cuts via Disjunctive Characterization,Mathematical Programming 37, 169–183.
Sisser, F. S. (1982a), Computer-Generated Interval Extensions of Factorable Functions and Their Derivatives,International J. of Computer Math. 10, 327–336.
Sisser, F. S. (1982b), Inverting an Interval Hessian of a Factorable Function,Computing 29, 63–72.
Soland, R. M. (1971), An Algorithm for Separable Nonconvex Programming Problems II: Nonconvex Constraints,Management Science 11, 759–773.
Taha, H. (1973), Concave Minimization over a Convex Polyhedron,Naval Research Logistics Quarterly 20, 533–548.
Thach, P. T. (1988), The Design Centering Problem as a DC-Programming Problem,Mathematical Programming 41, 229–248.
The Operation Research Society of America and the Institute of Management Science (1990),ORSA/TIMS Bulletin Number 30: of the Joint National Meeting in Philadelphia, Pennsylvania, October 29–31, 1990. Baltimore MD: ORSA and TIMS, 1990.
Thoai, N. V. (1988), A Modified Version of Tuy's Method for Solving DC Programming Problems,Optimization 19, 665–674.
Tuy, H. (1985), Global Minimization of a Difference of Two Convex Functions, in: Hammer, G. and D. Pallaschke (eds.),Selected Topics in Operations Research and Mathematical Economics, Lecture Notes in Economics and Mathematical Systems,226, 98–118.
Tuy, H. (1987a), Global Minimization of a Difference of Two Convex Functions,Mathematical Programming Study 30, 150–182.
Tuy, H. (1987b), Convex Programs with an Additional Reverse Convex Constraint,Journal of Optimization Theory and Applications 52, 463–485.
Tuy, H. and R. Horst (1988), Convergence and Restart in Branch-and-Bound Algorithms for Global Optimization. Application to Concave Minimization and DC-Optimization Problems,Mathematical Programming 41, 161–183.
Tuy, H. and N. V. Thuong. (1985), Minimizing a Convex Function over the Complement of a Convex Set,Methods of Operations Research 49, 85–99.
Williams, H. P. (1986), Fourier's Method of Linear Programming and Its Dual,American Mathematical Monthly 93, 681–695.
Author information
Authors and Affiliations
Additional information
Research Sponsored by the Office of Naval Research Grant N00014-89-J-1537.
Rights and permissions
About this article
Cite this article
Hamed, A.S.E.D., McCormick, G.P. Calculation of bounds on variables satisfying nonlinear inequality constraints. J Glob Optim 3, 25–47 (1993). https://doi.org/10.1007/BF01100238
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01100238