Optimization of functions with rank-two variation over a box

This paper deals with optimization of functions that depend on (large-scale) data via a linear transformation of rank two. An algorithm is presented which – under mild assumptions – finds the global solution with polynomial-time complexity in the worst case, provided the critical points of the objective can be controlled with the same effort. Moreover, for important subclasses of objectives including the linear-fractional, and the quadratic case, we arrive at a linear-time algorithm. For both cases, small simulation studies are provided to illustrate the average case runtime behaviour. As a possible application, sensitivity of cost assessment in communication networks is addressed where the problems may have tens of thousands of variables.