LARGE SCALE COMPOSITE OPTIMIZATION PROBLEMS WITH COUPLED OBJECTIVE FUNCTIONS: THEORY, ALGORITHMS AND APPLICATIONS

Abstract

The first part of this thesis is focused on solving unconstrained multi-block large scale convex composite optimization problems with coupled objective functions. An inexact majorized accelerated block coordinate descent method is proposed, and the $O(1/k^2)$ iteration complexity is proved. A two-phase implementation of the above framework is applied to an important class of composite least square problems. Numerical results demonstrate that the proposed method outperforms the existing ones, such as the accelerated proximal gradient method and the block coordinate descent method.

The second part of this thesis is devoted to the constrained convex composite optimization problems with joint linear constraints. A majorized alternating direction method of multipliers, which was discussed for problems with separable objective functions in the literature, is extended to deal with these problems. The global convergence and the iteration complexity are presented. We also prove the linear convergence rate of the method for solving quadratically coupled problems under an error bound condition. We characterize the robust isolated calmness of the constrained problems involving the nuclear norm, which has its own interest beyond the implication of the error bound condition, by the second order sufficient optimality condition and the strict Robinson's constraint qualification. For the convex composite nuclear norm problems, several equivalent conditions for the robust isolated calmness are obtained.