Construction of large-scale global minimum concave quadratic test problems (Q2265952)

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 in \(R^{n+k}\). The constructed function is strictly concave in the variables \(x\in R^ n\) and is linear in the variables \(y\in R^ k\). The number of linear variables k may be much larger than n, so that large- scale global minimization test problems can be constructed by the methods described here.