On the convergence analysis of a penalty algorithm for nonsmooth optimization and its performance for solving hard-sphere problems

• Published in: Numerical algorithms 2022-10, Vol.91 (2), p.933-957
• Main Authors: Prado, Renan W., Santos, Sandra A., Simões, Lucas E. A.
• Format: Article
• Language: English
• Subjects: Algebra; Algorithms; Computer Science; Convergence; Mathematical programming; Numeric Computing; Numerical Analysis; Optimization; Original Paper; Theory of Computation
• ISSN: 1017-1398; 1572-9265
• DOI: 10.1007/s11075-022-01287-x

This work builds upon the theoretical and numerical results of the recently proposed Penalized Algorithm for Constrained Nonsmooth Optimization (PACNO). Our contribution is threefold. Instead of resting upon approximate stationary points of the subproblems, approximate local minimizers are assumed to be computed. Consequently, a stronger convergence result is obtained, based on a new sequential optimality condition. Moreover, using a blackbox minimization framework and hard-sphere instances, the intrinsic parameters of PACNO have been adjusted, improving outcomes from the literature for the kissing problem, which consists of determining the maximum number of non-overlapping and equal spheres that can touch simultaneously a given sphere of the same size. Finally, the so-called double-kissing problem has been modeled: two equal and touching spheres are provided, and one aims at finding the maximum number of non-overlapping spheres, having the same radius of the given pair, which can be arranged so that each of them touches at least one of the stated spheres. A nonsmooth formulation for the double-kissing problem is devised, and the solutions of bi-, three-, and four-dimensional instances are successfully achieved.