A sequential convex programming algorithm for minimizing a sum of Euclidean norms with non-convex constraints. (2nd January 2016) - Trang, L.H.; Kozma, A.; An, P.T.; Diehl, M.
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.