Problem
Consider the optimization following problem with $f: \mathbf{R}^n\rightarrow \mathbf{R}$ being differentiable but not convex and $g: \mathbf{R}^n\rightarrow \mathbf{R}$ being convex but not differentiable.
$$\text{minimize} \ f(x) + g(x)$$
The optimality criterion is $\nabla f(\hat{x})^T(y-\hat{x})+g(y)-g(\hat{x})\geq 0$. Take $g(x)=\Vert x\Vert_1$, show the optimiality condition is reduced to the following. $$\frac{\partial f(\hat{x})}{\partial x_i}=\begin{cases}-1, \hat{x}_i >0\\ \in [-1, 1], \hat{x}_i=0\\1,\hat{x}_i<0\end{cases}$$
What I Have Done
Based on my previous experiences to solving such problems, I think the optimality condition could be written as $$\text{minimize}\ \nabla f(\hat{x})^T(y-\hat{x})+\Vert y\Vert_1 $$ and $p^* \geq \Vert \hat{x}\Vert_1$ when $p^*$ is the optimal value of this problem.
If I treat $\hat{x}$ as a constant in this optimization problem, then it is equivalent to the following $$\text{minimize}\ \nabla f(\hat{x})^Ty+\Vert y\Vert_1 $$ which seems to be solvable. If I could get the optimal value $p^*$, then I am approaching the desired result. However, I do not know how to proceed. Here is one random thought.
- Using the relationship between norm $\Vert x\Vert_p\leq n^{\frac{1}{p}-\frac{1}{q}}\Vert x\Vert_q$ and make $\nabla f(\hat{x})^Ty+\Vert y\Vert_1 $ differentiable.
Could someone help me, thank you in advance.