A convex quadratic semi-definite programming approach to the partial additive constant problem in multidimensional scaling

Abstract

Bénasséni [Partial additive constant, J. Statist. Comput. Simul. 49 (1994), pp. 179–193] studied the partial additive constant problem in multidimensional scaling. This problem is quite challenging to solve, and Bénasséni proposed a numerical procedure for two special cases: the cross-set partial perturbation and the within-set partial perturbation. This paper casts the problem as a modern quadratic semi-definite programming (QSDP) problem, which is not only capable of dealing with general cases, but also enjoys a number of good properties. One of the good properties is that the proposed approach can find the minimal constant under very weak conditions. Another is that there exists a ready-to-use numerical package such as the QSDP solver in Toh [An inexact path-following algorithm for convex quadratic SDP, Math. Program. 112 (2008), pp. 221–254], allowing a great deal of flexibility in choosing the index set to which the partial constant should be added. Our numerical results show a significant improvement over that reported in Bénasséni (1994).

Keywords:

• partial additive constant
• multidimensional scaling
• positive semi-definite programming
• Farkas’ lemma
• Lagrange multiplier

AMS Subject Classification :

• 90C22
• 90C25
• 90C90

Acknowledgements

We would like to thank one of the referees for the comment that has led to the addition of Harman's example. The work of Xiu was supported by the National Basic Research Program of China (2010CB732501).