Cost function with unique solution plus convex function has a unique solution?

Question

I have an optimization problem with a cost function $J(X)$, $X$ is a matrix, the function is not convex but I can find the analitical solution and it solution is unique. I want to add a regularization term, that is a $\ell_1$ or $\ell_2$ norm or a linear combination of them, the new cost function e.g. $ J_n(X)=J(X)+\lambda||X||_1$ has also a unique solution?. How I can demonstrate that?

Answer 1

In general this might not be true. Even if we restrict ourselves to $\mathbb{R}$ there may not be a unique solution. Let $J(x)=|x-2|$ and $J_n=J(x)+|x|$. Then $J$ has a unique minimizer at $x=2$, but $J_n$ is minimized in the entire interval $[0,2]$.

Instead, if your $J$ is minimized at some $X^*$, then you can choose to make your regularization term also minimized at $X^*$:

$$J_n(X) = J(X) + \lambda\|X - X^*\|.$$

As a sum of functions with unique minimizers at $X^*$, you can directly prove that $J_n(X)\geq J_n(X^*)$ with equality if and only if $X=X^*$.

edit: removed an incorrect statement.

Answer 2

No, this does not hold. Simply take a function which has two local minimizers, one local in the origin, and one unique global minimizer outside the origin. Now add a regularizer. This will not affect the function value in the origin, but it will increase the objective value in the initially global unique solution. Now increase $\lambda$ until the objective value in the initial global minimizer matches the value in the origin. You now have a situation with two global minimizers

MATLAB code for simple illustration

>> x = (-1:0.01:2);
>> plot(x,1 - 2*x.^3 + x.^4);hold on;plot(x,1 - 2*x.^3 + x.^4 + 1.19*abs(x))