Identifying Active Manifolds in Regularization Problems

In 2009, Tseng and Yun [Math. Programming (Ser. B) 117, 387–423 (2009)], showed that the regularization problem of minimizing f(x) + | ​ | x | ​ | 1, where f is a $${\mathcal{C}}^{2}$$ function and | ​ | x | ​ | 1 is the l 1 norm of x, can be approached by minimizing the sum of a quadratic approximation of f and the l 1 norm. We consider a generalization of this problem, in which the l 1 norm is replaced by a more general nonsmooth function that contains an underlying smooth substructure. In particular, we consider the problem 13.1 $${ \min }_{x}\{f(x) + P(x)\},$$ where f is $${\mathcal{C}}^{2}$$ and P is prox-regular and partly smooth with respect to an active manifold $$\mathcal{M}$$ (the l 1 norm satisfies these conditions.) We reexamine Tseng and Yun’s algorithm in terms of active set identification, showing that their method will correctly identify the active manifold in a finite number of iterations. That is, after a finite number of iterations, all future iterates x k will satisfy $${x}^{k} \in \mathcal{M}$$ . Furthermore, we confirm a conjecture of Tseng that, regardless of what technique is used to solve the original problem, the subproblem $${p}^{k} =\mathrm{{ argmin}}_{p}\{\langle \nabla f({x}^{k}),p\rangle + \frac{r} {2}\vert {x}^{k} - p{\vert }^{2} + P(p)\}$$ will correctly identify the active manifold in a finite number of iterations.