Seminar Details
2025-11-17 (14:00) : Regularized block coordinate descent methods: Complexity and applications
At a.002
Organized by Mathematical Engineering
Speaker :
Ernesto Birgin (Universidade de São Paulo, Brazil)
Abstract :
In this work, we propose block coordinate descent methods for bound-constrained and nonconvex constrained minimization problems. Our approach relies on solving regularized models. For bound-constrained problems, we introduce methods based on models of order $p$, which exhibit asymptotic convergence to $p$th-order stationary points. Moreover, first-order stationarity with precision $\epsilon$ with respect to the variables of each block is achieved in $O(\epsilon^{-(p+1)/p})$; while first-order stationarity with precision $\epsilon$ with respect to all the variables is achieved in $O(\epsilon^{-(p+1)})$. For nonconvex constrained minimization, we consider models with quadratic regularization. Given feasibility/complementarity and optimality tolerances $\delta>0$ and $\epsilon>0$ for feasibility/complementarity and optimality, respectively, it is shown that a measure of $(\delta,0)$-criticality tends to zero; and the number of iterations and functional evaluations required to achieve $(\delta,\epsilon)$-criticality is $O(\epsilon^{-2})$. Numerical experiments illustrate the effectiveness of our methods. We apply the first method to solve the Molecular Distance Geometry Problem, while the second method is used to enhance heuristic approaches for the Traveling Salesman Problem (TSP) with neighbors, a variant of the classical TSP problem where regions in the plane must be visited instead of cities. The case where regions are described by arbitrary (nonconvex) polygons is considered.