Two Simple and Effiffifficient Methods for a Class of Composite Functions Optimization

Abstract In this paper, we focus on optimizing the optimization problems with the objective function formed as a sum of three terms: one is smooth, and the other two are simple convex functions with known structures. This problem is challenging to solve, as the last two functions are both non-smooth and non-separable. Existing algorithms have high computational complexity and do not deal with large-size problems. To effiffifficiently solve this problem, we propose two ways to simplify it. One way is to introduce an additional variable to reformulate it as an equivalent two-block separable convex minimization model. Then we apply an approximate alternating direction method of multipliers(ADMM) to solve the equivalent model and establish a worst-case $O(1/k) $convergence rate for this method. Another way is to research the dual of the equivalent problem, and use an optimal fifirst-order method to solve the dual problem. Furthermore, we show that this method achieves a faster convergence rate of $O( 1/k ^2 )$. Finally, we also demonstrate an application called the fused Lasso problem.