Abstract
This paper develops and proves an algorithm that finds the exact maximum of certain nonlinear functions on polytopes by performing a finite number of logical and arithmetic operations. Permissible objective functions need to be pseudoconcave and allow the closed-form solution of sets of equations\(\partial f(Dy + \hat x^k )/\partial y = 0\), which are first order conditions associated with the unconstrained, but affinely transformed objective function. Examples are pseudoconcave quadratics and especially the homogeneous functioncx +m(xVx)1/2,m < 0, V positive definite, for which sofar no finite algorithm existed.
In distinction to most available methods, this algorithm uses the internal representation [6]|of the feasible set to selectively decompose it into simplices of varying dimensions; linear programming and a gradient criterion are used to select a sequence of these simplices, which contain a corresponding sequence of strictly increasing, relative and relatively interior maxima, the greatest of which is shown to be the global maximum on the feasible set. To find the interior maxima on these simplices in a finite way, calculus maximizations on the affine hulls of subsets of their vertices are necessary; thus the above requirement that\(\partial f(Dy + \hat x^k )/\partial y = 0\) be explicitly solvable.
The paper presents a flow structure of the algorithm, its supporting theory, its decision-theoretic use, and an example, computed by an APL-version of the method.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
G.B. Dantzig,Linear programming and extensions (Princeton University Press, Princeton, N.J., 1963).
G.B. Dantzig and P. Wolfe, “Decomposition principle for linear programs”,Operations Research 8(1) (1960).
J. Dréze and P. Van Moeseke, “An algorithm for homogeneous programming”, CORE Discussion Paper No. 2023 (1971).
O.L. Mangasarian,Nonlinear programming (McGraw-Hill, New York, 1969).
W.C. Mylander, “Finite algorithms for solving quasiconvex quadratic programs”,Operations Research 20 (1) (1972) 167–173.
R.T. Rockafellar,Convex analysis (Princeton University Press, Princeton, N.J., 1970).
J. Rosen, “The gradient projection method for nonlinear programming, I. Linear constraints”,Journal of the Society for Industrial and Applied Mathematics 8 (1960) 181–217.
P. Van Moeseke, “Towards a theory of efficiency”, in: J. Quirk and A. Zabel, eds.,Papers in quantitative economics (University of Kansas Press, St. Louis, 1968).
P. Van Moeseke, “Stochastic linear programming: A study in resource allocation under risk”,Yale Economic Essays 5 (1965) 196–254.
P. Van Moeseke and B. von Hohenbalken, “Efficient and optimal portfolios by homogeneous programming”,Zeitschrift fdr Operations Research 18 (1974) 205–214.
B. von Hohenbalken, “Differentiable programming on polytopes”, Research Paper Series No. 14, Department of Economics, University of Alberta (1972).
B. von Hohenbalken, “Simplicial decomposition in nonlinear programming algorithms”, Research Paper Series No. 21, Department of Economics, University of Alberta (1974).
P. Wolfe, “Methods of nonlinear programming”, in: J. Abadie, ed.,Nonlinear programming (Wiley, New York, 1967), pp. 97–131.
W.I. Zangwill,Nonlinear programming. A unified approach (Prentice-Hall, Englewood Cliffs, N.J., 1969).
Author information
Authors and Affiliations
Additional information
Research supported in part by The Canada Council, Ottawa. Earlier versions of the paper were presented at the European meeting of the Econometric Society in Budapest, September 1972 and at the meeting of the Econometric Society in San Francisco, December 1974.
Rights and permissions
About this article
Cite this article
von Hohenbalken, B. A finite algorithm to maximize certain pseudoconcave functions on polytopes. Mathematical Programming 9, 189–206 (1975). https://doi.org/10.1007/BF01681343
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01681343