Abstract:
In this talk, we introduce three classes of challenging optimization problems, analyze their interconnections, and reveal their inherent difficulties. The most complex is fractional programming (FP), which involves a composition of double nonsmooth functions with linear operators. For FP, we propose an adaptive, fully splitting proximal subgradient algorithm with an extrapolation step. This method decouples the linear operator from the nonsmooth component, circumventing the need to evaluate the composition directly. We prove subsequential convergence to an approximate lifted stationary point and establish global convergence under the Kurdyka–Łojasiewicz (KL) property—without requiring full-row rank assumptions on the linear operators. We also address three key questions demonstrating why our results are tight under our framework.

Next, we study the second-most challenging problem: a class of nonconvex, nonsmooth structured difference-of-convex (DC) programs, which also feature compositions of nonsmooth functions with linear operators. We develop an adaptive double-proximal, fully splitting algorithm with a moving center technique in the final subproblem, again decoupling the linear operator from the nonsmooth term. We show subsequential convergence to an approximate stationary point and prove global convergence under the KL property. Finally, we discuss the tightness of our convergence guarantees and present a series of counterexamples demonstrating their optimality.