Underestimation functions for a rank-two partitioning method

Low-rank problems are nothing but nonlinear minimization problems over polyhedrons where a linear transformation of the variables provides an objective function which actually depends on very few variables. These problems are often used in applications, for example, in concave quadratic minimization problems, multiobjective/bicriteria programs, location–allocation models, quantitative management science, data envelopment analysis, efficiency analysis and performance measurement. The aim of this paper is to deepen on the study of a solution method for a class of rank-two nonconvex problems having a polyhedral feasible region expressed by means of inequality/box constraints and an objective function of the kind $$\phi (c^Tx+c_0,d^Tx+d_0)$$ . The rank-two structure of the problem allows to determine various localization conditions and underestimation functions. The stated theoretical conditions allow to determine a solution algorithm for the considered class of rank-two problems whose performance is witnessed by means of a deep computational test.