What is the main characteristics of separable and non-separable functions?

Question

I have read an article that says, from the optimization point of view, the separable functions are simpler then non-separable functions and optimization algorithms can find their optimal values more easily. What are the main characteristics of separable functions which cause such behavior?

Answer 1

I have a partial knowledge on that subject but this may give you (very ?) few understandings.

Let us say that you want to minimize the function $f : \mathbb{R}^{2} \rightarrow \mathbb{R}$ which can be written:

$$\forall (x,y) \in \mathbb{R}^{2} \; f(x,y) = g(x) + h(y)$$ because it is separable.

Then, $\min_{(x,y)}f(x,y) = \min_{x}g(x) + \min_{y}h(y)$, which transforms your initial problem on $\mathbb{R}^{2}$ into two problems on $\mathbb{R}$. This can be easier to solve.

You could also transform a complex problem of minimization along one variable into two simpler problems of minimization along two variables by simply adding an equality constraint:

$$\min_{x}g(x) + h(Ax) = \min_{(x,y)\; s.t \;y = Ax}g(x) + h(y)$$