D) Iterative algorithm for Lasso. (20 points) We want to derive efficient algorithm for solving optimization problem where the objective is a sum of a L-smooth function f and a non-smooth function . minxRqf(x)+(x). As seen in the lectures, a natural ideal is to iteratively approximate f with a simpler function. Let us define x(k+1)=xargminf(x(k))+f(x(k)),xx(k)+2Lxx(k)2+(x). (5 points) The previous approximation was done in the direction d=xxk. However, one can find other interesting direction as well. For example, let us consider the direction d=ej(xjxj(k)) with ej=(0,,0,1,0,,0) where the 1 is at the j th coordinate. For a function (x)=j=1pj(xj), show that the iterates can be written as Proximal Coordinate Gradient Method xj(k+1)=xjargminf(x(k))+ejf(x(k)),xjxj(k)+2Lxjxj(k)2+j(xj).=xjargmin21xj(xj(k)L1ejf(x(k))2+L1j(xj)