A sequential convex programming algorithm for minimizing a sum of Euclidean norms with non-convex constraints. (2nd January 2016)

• Record Type: Journal Article
• Authors: Trang, L.H.; Kozma, A.; An, P.T.; Diehl, M.
• Is Part Of: Optimization methods and software. Volume 31:Number 1(2016)
• Page Start: 187
• Page End: 203
• Publication Date: 2016-01-02
• Subjects: minimizing a sum of Euclidean norms -- non-convex constraint -- relaxation -- sequentialconvex programming -- shortest path; 90C26 -- 90C30 -- 90C59 -- 68N01 -- 68R01; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2015.1055561
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : Given and a finite set of convex polygons in, we consider the problem of finding the Euclidean shortest path starting at p then visiting the relative boundaries of the convex polygons in a given order, and ending at q . An approximate algorithm is proposed. The problem can be rewritten under a variant of minimizing a sum of Euclidean norms:, where and, subject to is on the relative boundary of, for . The objective function of the problem is convex but not everywhere differentiable and the constraints are non-convex. By using a smooth inner approximation of with parameter t, a relaxed form of the problem is constructed such that its solution, denoted by, is inside but outside the inner approximation. The relaxed problem is then solved iteratively using a sequential convex programming. The obtained solution, however, is actually not on the relative boundary of . Then a so-called refinement of is finally required to determine a solution passing through the relative boundary of, for . It is shown that the solution of the relaxed problem tends to its refined one as . The algorithm is implemented in Matlab using the CVX package. Numerical tests indicate that the solution obtained by the algorithm is close to the global one.