2024/10/25 by Kabgani, Alireza, Ahookhosh, Masoud · 3 citations
#49J52 #49J53 #65K05 #90C06 #90C25 #90C26 #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2410.19928
This paper introduces ItsOPT, an inexact two-level smoothing optimization framework designed to find first-order critical points of nonsmooth and nonconvex functions. The framework involves two levels of methodologies: at the upper level, a zero-, first-, or second-order method will be tailored to minimize a smooth approximation; at the lower level, the high-order proximal auxiliary problems will be solved inexactly, generating an inexact oracle for the smooth function. As a smoothing technique, we here introduce the high-order Moreau envelope (HOME) and study its fundamental features under standard assumptions. Next, introducing a boosted high-order proximal-point algorithm (Boosted HiPPA) at the upper level using the inexact oracle from the lower level leads to an instance of ItsOPT. Global convergence rates are established under the Kurdyka-Łojasiewicz (KL) property of the cost and envelope functions, along with some reasonable conditions for the accuracy of the proximal terms. surprisingly, for any KL exponent θ∈ (0,1) of the original cost, setting the regularization order p=(1)/(1-θ) ensures that Boosted HiPPA converges linearly to a proximal fixed point, which is the first algorithm with this property for KL functions. Preliminary numerical experiments on a robust low-rank matrix recovery problem indicate a promising performance of the proposed algorithm, validating our theoretical foundations.