Optimization algorithms for multidimensional scaling with city-block distances and their parallelization

In this dissertation, a problem related to a visualization of elements of a multidimensional data set is considered. Here, for the sake of simplicity, an element of a multidimensional data set is called a multidimensional element. There are many techniques for visualizing multidimensional elements. Multidimensional scaling (MDS) is one of them. In applying MDS, a certain real function has to be constructed and minimized. In order to construct the function, a desired distance function has to be selected. If city-block distances are selected, the problem of minimizing such a function becomes a complicated optimization problem. In this work, this complicated optimization problem is the main research problem. Here, we formulate a new optimization problem and we show that it is equivalent to the original optimization problem arising in MDS with city-block distances. Also, we propose two sequential algorithms and one parallel algorithm for the newly formulated problem. Finally, we present the results of numerical investigations of the proposed algorithms