A Mathematical Programming Approach for Nonmetric Multidimensional Scaling

Abstract

Multidimensional Scaling (MDS) is a data visualization method for identifying structure or clusters of objects depending on proximity measures between pairs of objects. In this thesis, nonmetric multidimensional scaling is considered, which is prone to local minimum solution when minimizing the stress function, and we do not guarantee obtaining the global optimum. For this reason, a new approach for solving nonmetric MDS problems is proposed based on mathematical programming. Two mathematical programming models are proposed, namely; nonlinear and mixed integer programming models. The proposed nonlinear programming model is compared with the classical nonmetric approach (Shepard-Kruskal algorithm) using the data of the corruption perceptions index (CPI) for 2010 for 19 Middle East countries. The comparison is based on stress value, Shepard diagram, residual diagram and the structure of derived configuration. Although Shepard-Kruskal algorithm came out with very good solution for this data set, the nonlinear programming model showed its superiority, especially for stress value and the structure of configuration. As for the proposed mixed integer programming model, it minimizes the stress function based on city block metric instead of Euclidean distance. It is linear in both objective function and constraints, so that it guarantees obtaining the global minimum solution.