Abstract
A method is presented for the construction of test problems for which the global minimum point is known.
Given a bounded convex polyhedron inR n, and a selected vertex, a concave quadratic function is constructed which attains its global minimum at the selected vertex. In general, this function will also have many other local minima.
References
J.E. Falk and K.L. Hoffman, “A successive underestimation method for concave minimization problems”,Mathematics of Operations Research 1 (1976) 251–259. [See also, K.L. Hoffman, “A successive underestimation method for concave minimization problems”, Ph.D. thesis, The George Washington University (Washington, DC, August 1975).]
C.D. Heising-Goodman, “A survey of methodology for the global minimization of concave function subject to convex constraints”, OMEGA 9(3) (1981) 313–319.
R. Horst, “An algorithm for nonconvex programming problem”,Mathematical Programming 10 (1976) 312–321.
G.P. McCormick, “Computability of global solution to factorable non-convex programs: Part I—Convex underestimating problems”,Mathematical Programming 10 (1976) 147–175.
J.B. Rosen, “Global minimization of a linearly constrained concave function by partition of the feasible domain”,Mathematics of Operations Research 8 (1983) to appear.
H. Tuy, “Concave programming under linear constraints”,Doklady Akademii Nauk USSR 159 (1964) 32–35. [Translated in:Soviet Mathematics Doklady 5 (1964) 1437–1440.]
Author information
Authors and Affiliations
Additional information
This research was supported in part by NSF Grant MCS 81-01214.
Rights and permissions
About this article
Cite this article
Sung, Y.Y., Rosen, J.B. Global minimum test problem construction. Mathematical Programming 24, 353–355 (1982). https://doi.org/10.1007/BF01585116
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585116