5
$\begingroup$

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.

1 Answers 1

2

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.

  • 0
    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?2012-05-02