Splitting algorithms for structured optimizationtheory and applications

Abstract

With modern advances in technologies and quantity of information, optimization problems become increasingly large in size and complexity. Successfully handling these ever evolving problems requires a careful processing of the available data, namely, taking advantage of the inherent mathematical structure of the problem. Following the divide-and-conquer paradigm, splitting algorithms specialize in tackling mathematical programs by iteratively solving simpler subtasks, which are defined by separately using some parts of the original problem. This has led this class of algorithms to emerge as one of the most fruitful among modern numerical optimization methods. This thesis contributes to the theory of splitting algorithms for both convex and nonconvex optimization. Our contributions are presented in two clearly differentiated parts, but which share a common core objective: to enhance the efficiency of the algorithms' computational processes. This goal is achieved through distinct approaches tailored to each specific mathematical program faced throughout the thesis. In addition, the effectiveness of our theoretical developments is validated in numerical experiments arising in multiple real-world applications, such as intensity-modulated radiation therapy treatment planning. In Part I, we concentrate on monotone operator splitting methods. These algorithms are employed for solving monotone inclusions. In the last decades, a common anomaly has persisted in the design of algorithms in this family: the dimension of the underlying space, which we denote as lifting, of the algorithms abnormally increases as the problem size grows. This has direct implications on the computational performance of the methods as a result of the escalation of memory requirements. In this framework, we characterize the minimal lifting that can be obtained by splitting algorithms adept at solving certain general monotone inclusions. Moreover, we pioneer the development of splitting methods matching these lifting bounds, and thus having minimal lifting. The analysis developed in this context also leads to a new proof of convergence of the popular Davis-Yin splitting algorithm which allows to double the range of admitted stepsize parameter values. Two independent advances to the family of splitting algorithms are presented in Part 2. In Chapter 8, we move to the nonconvex realm. The analysis of splitting methods for nonconvex problems has not been developed to the same extent as in the convex setting, with convergence guarantees only given for some restricted problem structures. We introduce the Boosted Double-proximal Subgradient Algorithm (BDSA), a novel splitting algorithm designed to address general structured nonsmooth and nonconvex mathematical programs. While BDSA encompasses existing schemes in the literature, it extends its applicability to more diverse problem domains. One of the features of BDSA is the integration of a linesearch procedure to enhance its performance. Numerical experience reveals that this linesearch considerably reduces both the number of iterations and the time that BDSA needs to converge in comparison with algorithms including inertial terms. In addition, we introduce two new families of test functions to illustrate BDSA's ability to effectively escape non-optimal critical points. Finally, in Chapter 9, we study the split minimization problem that consists of two constrained minimization problems in two separate spaces that are connected via a linear operator that maps one space into the other. To handle the data of such a problem, we develop a superiorization approach that can reach a feasible point with reduced objective function values. The superiorization methodology is based on interlacing the iterative steps of two separate and independent iterative processes by perturbing the iterates of one process according to the steps dictated by the other. We include two novel elements. The first one is the permission to restart the perturbations, which results in a significant acceleration. The second element is the ability to independently superiorize subvectors