Construction of large-scale global minimum concave quadratic test problems

Construction of problems with known global solutions is important for the computational testing of constrained global minimization algorithms. In this paper, it is shown how to construct a concave quadratic function which attains its global minimum at a specified vertex of a polytope inR ^n+k. The constructed function is strictly concave in the variablesx R ⁿ and is linear in the variablesy R ^k. The number of linear variablesk may be much larger thann, so that large-scale global minimization test problems can be constructed by the methods described here.This research was supported by the Computer Science Section of the National Science Foundation under Grant No. MCS-81-01214.