Parallel branch and bound for multidimensional scaling with L1 distances formulated as quadratic programming with complementarity constraints

Author

Galiauskas, Nerijus ; Ilinskas, Julius

Author_Institution

Inst. of Math. & Inf., Vilnius Univ., Vilnius, Lithuania

fYear

2013

fDate

28-30 Oct. 2013

Firstpage

509

Lastpage

512

Abstract

We consider the problem of finding the global minimum of the least squares Stress function with L1 distances in multidimensional scaling. The problem can be formulated as a quadratic programming problem with complementarity constraints and solved as a two level optimization problem with combinatorial minimization at the upper level and convex quadratic programming at the lower level. In this paper, we propose a parallel branch and bound algorithm for this two level optimization problem.

Keywords

combinatorial mathematics; convex programming; minimisation; parallel algorithms; quadratic programming; tree searching; L1 distances; combinatorial minimization; complementarity constraints; convex quadratic programming; least squares stress function; multidimensional scaling; optimization problem; parallel branch and bound algorithm; quadratic programming problem; Data visualization; Linear programming; Minimization; Parallel processing; Quadratic programming; Stress; combinatorial optimization; multidimensional scaling; parallel computing; quadratic programming;

fLanguage

English

Publisher

ieee

Conference_Titel

P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC), 2013 Eighth International Conference on

Conference_Location

Compiegne

Type

conf

DOI

10.1109/3PGCIC.2013.87

Filename

6681281