Global Optimization for Heilbronn Problem of Convex Polygons Based on Bilinear Matrix Inequalities Solving

This paper primarily focuses on solving the Heilbronn problem of convex polygons, which involves minimizing the area of a convex polygon P₁P₂ … P_n while satisfying the condition that the areas of all triangles formed by consecutive vertices are equal to 12. The problem is reformulated as a polynomial optimization problem with a bilinear objective function and bilinear constraints. A new method is presented to verify the upper and lower bounds for the optimization problem. The upper bound is obtained by the affine regular decagon. Then Bilinear Matrix Inequalities (BMI) theory and the branch-and-bound technique are used to verify the lower bound of the problem. The paper concludes by proving that the lower bound for the area minimization problem of a convex polygon with 10 vertices is 13.076548. The relative error compared to the global optimum is 0.104%.