Numerical Methods Solving Three Problems Related To Projection Onto Minkowski Sum Of Closed Semi-algebraic Sets

Minkowski sum is an important concept in computational geometry.It plays an important role in both theoretical and practical applications.It is often used in dynamic simulation,path planning,robot learning and other fields.In this paper,we mainly discuss the numerical algorithm of three problems,namely,the numerical algorithm of the distance problem from original point to the projection onto a Minkowski sum of several closed semi-algebraic sets,the numerical algorithm of the distance problem from semi-algebraic sets to the projection onto a Minkowski sum of several closed semi-algebraic sets,and the numerical algorithm of min-max problem related to the projection onto a Minkowski sum.In chapter 1,the background of the projection onto a Minkowski sum problems and the main contents of this paper are briefly described.Chapter 2 mainly introduces the basic concepts,important properties,theorems and Lasserre semi-positive definite relaxation method of polynomial optimization.Chapter 3 focuses on the problem from original point to the projection onto a Minkowski sum of several closed semi-algebraic sets.Firstly,the related problem is transformed into a polynomial optimization problem.Secondly,a numerical algorithm is designed to solve the problem by using Lasserre's semi-positive definite relaxation method.Then,the convergence of the algorithm is analyzed.Finally,the effectiveness of the algorithm is verified by numerical experiments.Chapter 4 focuses on the problem from semi-algebraic sets to the projection onto a Minkowski sum of several closed semi-algebraic sets.Firstly,the related problem is transformed into a polynomial optimization problem.Secondly,a numerical algorithm is designed to solve the problem by using Lasserre's semi-positive definite relaxation method.Then,the convergence of the algorithm is analyzed.Finally,the effectiveness of the algorithm is verified by numerical experiments.Chapter 5 mainly discuss a min-max problem related to the projection onto a Minkowski sum of closed semi-algebraic sets.Assuming that the constraint of the maximize part is convex,the min-max problem can be equivalently transformed into a polynomial optimization problem through the optimality condition.Firstly,a numerical algorithm is designed to solve the problem by using Lasserre's semi-positive definite relaxation method.and then,the convergence of the algorithm is analyzed.Finally,the effectiveness of the algorithm is verified by numerical experiments.The last part,we makes a simple summary and prospect.