Bifurcation Structure of a Class of SN-invariant Constrained Optimization Problems

In this paper we investigate the bifurcations of solutions to a class of constrained optimization problems. This study was motivated by annealing problems which have been used to successfully cluster data in many different applications. Solving these problems numerically is challenging due to the size of the space being optimized over, which depends on the size and the complexity of the data being analyzed. The type of constraints and the form of the cost functions make them invariant to the action of the symmetric group on N symbols, S_N, and we capitalize on this symmetry to describe the bifurcation structure. We ascertain the existence of bifurcating branches, address their stability, and compare the stability to optimality in the constrained problem. These theoretical results are used to explain numerical results obtained from an annealing problem used to cluster data.Dedicated to Professor Shui-Nee Chow on the occasion of his 60th birthday.Albert E. Parker-This research was partially supported by IGERT Grant NSF-DGE 9972824Tomá Gedeon-This research was partially supported by NSF EIA-BITS Grant 426411