I am trying to understand the difference between the optimization problem types which are basically smooth and non smooth. I also found this question what does a smooth curve mean? I understand that smoothness is a relative concept from this. My question is, in optimization problems we call Least Squares cost function a smooth problem , it only belongs to the set $C^2$, i.e only twice differentiable and L1 regularization $\lambda \sum_{i=1}^n \theta_i$ as non-smooth which belongs to $C^1$ since it is differentiable once.( I am assuming $L1 \in C^1$,since $\partial L1/\partial \theta_i = 1 )$. So what does it mean to call a function smooth in the perspective of optimization.

I am guessing may be in optimization, we either use the gradient or hessian to compute the descent direction, so if any curve is twice differentiable is called as smooth function. Am I correct? And also I am not sure why L1 is called non smooth.


Non-smooth in the context of optimization usually means that the cost or constraints are not differentiable. The $l_1, l_{\infty}$ norms are examples. The $l_1$ norm is not differentiable on the axes, the $l_{\infty}$ is not differentiable on the 'diagonals'. Another, less trivial, is the maximum singular value of a matrix.

A classic non-smooth problem is minimizing a 'max-function', ie, problems of the form: $$P:\; \; \min_{x \in \mathbb{R}^n} \max_{i=1,...n} f_i(x).$$ This function is generally not differentiable when the maximum is attained by more than one function. Both the $l_1$ and $l_{\infty}$ norms can be expressed as a 'max-function'.

There is a non-smooth calculus in which the derivative is replaced by a generalized gradient (cf. subdifferential in convex analysis). Many of the familiar results have equally familiar counterparts. For example, at a solution $\hat x$ of the problem P above, one has $0 \in \partial f (\hat x)$, which is basically saying the derivative is zero.

However, the level of analysis required increases substantially.

  • $\begingroup$ so my understanding of what is not differentiable was wrong. I can see unit sphere in $l1$ norm has corners, hence it is not differentiable in the axes. So how to find if a function is differentiable or not easily? $\endgroup$ – vumaasha May 2 '12 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.