Abstract
Given a function on Rn with many multiple local minima we approximate it from below, via concave minimization, with a piecewise-linear convex function by using sample points from the given function. The piecewise-linear function is then minimized using a single linear program to obtain an approximation to the global minimum of the original function. Successive shrinking of the original search region to which this procedure is applied leads to fairly accurate estimates, within 0.57%, of the global minima of synthetic nonconvex piecewise-quadratic functions for which the global minima are known exactly.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Dill K.A., Phillips A.T., Rosen J.B. (1997). CGU: An algorithm for molecular structure prediction. In: Biegler L.T. et al., (ed). IMA Volumes in Mathematics and its Applications: Large Scale Optimization with Applications III: Molecular Structure and Optimization. pp. 1–22
D. Fortin I. Tsevendorj (2002) ArticleTitlePiecewise convex maximization problems: Algorithm and computational experiments Journal of Global Optimization 24 61–77
M. Frank P. Wolfe (1950) ArticleTitleAn algorithm for quadratic programming Naval Research Logistics Quarterly 3 95–110
O.L. Mangasarian (1997) ArticleTitleSolution of general linear complementarity problems via nondifferentiable concave minimization Acta Mathematica Vietnamica 22 IssueID1 199–205
O.L. Mangasarian R.R. Meyer (1979) ArticleTitleNonlinear perturbation of linear programs SIAM Journal on Control and Optimization 17 IssueID6 745–752
Mitchell J.C., Phillips A.T., Rosen J.B., Ten Eyck L.F. (2000). Coupled optimization in protein docking. In: Optimization in Computational Chemistry and Molecular Biology. pp. 191–207, Kluwer Academic Publishers, Dordrecht, Netherlands.
A.T. Phillips J.B. Rosen K.A. Dill et al. (2001) Convex global underestimation for molecular structure prediction P.M.. Pardalos (Eds) From Local to Global Optimization Kluwer Academic Publishers Dordrecht, Netherlands 1–18
R.T. Rockafellar (1970) Convex Analysis Princeton University Press Princeton, New Jersey
Rosen J.B., Marcia R.F. (2004). Convex quadratic approximation. Computational Optimization and Applications 8(3).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mangasarian, O.L., Rosen, J.B. & Thompson, M.E. Global Minimization via Piecewise-Linear Underestimation. J Glob Optim 32, 1–9 (2005). https://doi.org/10.1007/s10898-004-5907-1
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10898-004-5907-1