Minimax Resource Allocation with Continuous Variables: The Definitive Solution


TR Number




Journal Title

Journal ISSN

Volume Title


Department of Computer Science, Virginia Polytechnic Institute & State University


The necessary and sufficient conditions of local global optimization are derived for constrained resource allocation with continuous variables and objective functions of the forms max (sub i) {f-sub i(x-sub i)} and mini{f-sub i(x-sub i)} where {f-sub i} can be nondifferentiable, nonmonotone, nonconvex, multimodal functions. All previous theoretical results, which are sufficient conditions for global optimization with monotone {f-sub i}, are special, restrictive cases of the new criteria. The powerful criteria also enable complete determination of all the global optimal solutions, thus allowing further lexicographic optimization. The criteria also enable determination of all the local maxima and minima, a previously unaddressed facet of the solution, thus providing illuminating information on the behavior of the objective function and its overall "topography", which could be useful in suboptimal multi-criteria trade-offs. The new results admit a straightforward graphical interpretation and implementation, which facilitates their utilization and extends their applicability to practical problems where {f-sub i} are specified only in graphical formats derived from empirical or simulation data. Except for the mild and practically insignificant restrictions of continuity and "local monomodality" retained on {f-sub i} by the analysis, the results of this paper constitute the complete and definitive solution of the problem.