1

In literature,a separable program is formulated like this:

$$\min_{x_{1},...x_{n}}\sum_{i=1}^{n}f_{i}(x_{i})$$

where $f_{i}$ is a closed proper convex function.

My question is what does 'closed' mean? and is the following problem separable?

$$\min_{X \in R^{mn}}||X||_{*}+\lambda||\mathcal AX-b||_{2}^{2}$$

yang
  • 957
  • This may help: https://en.wikipedia.org/wiki/Closed_convex_function – Jack Jun 20 '15 at 02:48
  • I think you are misreading the "literature". The functions $f_i$ do not have to be closed, proper, or convex for the problem to be separable. Separability is a distinct property from the others. Of course, a separable convex function will require convexity of each $f_i$. But again, that's a distinct property. I could easily conceive of a separable non-convex function. – Michael Grant Jun 20 '15 at 02:49
  • 1
    And no, your problem is not separable, because the two terms involve the same variable. – Michael Grant Jun 20 '15 at 02:51

1 Answers1

1

A convex function is called closed iff $f = \operatorname{cl} f$, where $\operatorname{cl} f$ is defined as follows: If $f(x) = -\infty$ for any $x$, then $(\operatorname{cl} f)(x) = -\infty$ for all $x$, otherwise $\operatorname{cl} f$ is the function whose epigraph is given by the $\overline{\operatorname{epi} f}$.

Since the $f$ in the question is proper,the function is closed iff the epigraph is closed iff the function is lower semicontinuous.

Without knowing what $\|\cdot\|_*$ is, it is difficult to give conditions under which the problem might be separable.

copper.hat
  • 172,524