Diff-convex combinations of Euclidean distances : a search for optima

Abstract

This work presents a study of optimisation problems involving differences of convex (diff-convex) functions of Euclidean distances. Results are provided in four themes: general theory of diff-convex functions, extensions of the Weiszfeld method, interior point methods, and applications to location problems. Within the theme of general theory, new results on optimality conditions and sensitivity to perturbations of diff-convex functions are provided. Additionally, a characterisation of level-boundedness is provided, and the internal structure is studied for a class of diff-convex functions involving symmetric cones. Based on this study, the Jordan-algebraic approach to interior point methods for linear programs on symmetric cones is extended. Local convergence of the method is proved, and a globalisation strategy is studied, based on the concept of the filter method. The Weiszfeld method is extended to “perturbed spatial medians with incomplete data”, where the convex spatial median objective function with scaled Euclidean distances can be perturbed by a concave function. The convergence of the method is studied, along with application to location problems. The location problems of interest include in particular clustering and the Euclidean travelling salesperson problem (TSP). The classical multisource Weber problem is studied, and a new clustering objective is presented, based on a multiobjective interpretation of the problem. It is then shown that the Euclidean TSP can be presented as either of the above clustering objectives perturbed with a path length penalty. The focus of the work is theoretical.