The Study Of Penetration Distance Between Special Sets By Some First-Order Optimization Algorithms

The penetration distance,which characterizes the degree of intersection between two sets,is an important computational geometry problem with a wide variety of applications in image processing and robotics.The traditional penetration distance,also known as the Euclidean penetration distance,is the minimal translation distance such that the interior of one of the sets does not intersect with the other set.In addition,the gauge function of a special set is essentially a standard norm.The Euclidean penetration distance can be extended to the generalized penetration distance under non-Euclidean metrics such as Manhattan distance and Chebyshev distance through the gauge function.In fact,the Eu-clidean penetration distance is a special case of the generalized penetration distance.The calculation of the generalized penetration distance is very difficult because it is essen-tially equivalent to solving a constrained optimization problem whose feasible region is the boundary of Minkowski difference.In general,the boundary of Minkowski difference is a non-convex set,which makes it difficult to obtain the global optimal solution of the constrained optimization problem by optimization methods.In order to solve the penetration distance on the perspective of mathematical opti-mization,the generalized penetration distance is redefined by using the one-sided Haus-dorff distance in this thesis.The generalized penetration distance can be formulated as a maximization problem,and its feasible region is described by the inclusion relationship between sets.The one-sided Hausdorff distance can just convert the inclusion relationship between sets into the corresponding functional relationship.Therefore,the problem of the penetration distance is reformulated into finding the maximal root of a nonlinear equation in this thesis.In particular,the nonlinear function involved in this equation is essentially a minimax problem.This transformation provides another way to solve the penetration distance.In this thesis,based on the theoretical analysis,the algorithmic framework for solv-ing the penetration distance is proposed.The outer algorithm of the framework is a root-finding algorithm of nonlinear equations,and the inner algorithm is a minimax optimiza-tion algorithm.It is worth noting that the accuracy of the solution to the minimax problem affects the accuracy of the penetration distance.Specifically,in this thesis,the secant method and the primal-dual algorithm are used to solve the penetration distance based on some special sets such as the unit ball with?^p-norm and the unit ball with hexagon norm.Numerical experiments on compact convex sets demonstrate that the proposed algorithm is efficient and can present solutions with high accuracy.In addition,there is another vari-ant algorithm based on the bisection method and Hi BSA algorithm under this framework,and the Hi BSA algorithm can find the?-stationary solution of the penetration distance subproblem.