Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there a notion of "best" convex relaxation of a particular function in a normed vector space? For example, the $\ell^0$ pseudo-norm can be relaxed into the $\ell^1$ norm, and that allows us to solve sparse recovery problems. Is there a general recipe to construct such relaxations given an arbitrary function?

Specifically, I have a function of the form $f(x) = \|x\|_2\|x\|_1$, which is non convex. How would I go about relaxing this? Any resources/links I should look into?

share|improve this question
    
is there any other constraints? otherwise, ofcourse the solution is zero –  dineshdileep Jan 4 '13 at 10:07
add comment

1 Answer

A function is convex if and only if its epigraph $\big\{(\mathbf x,z):z\ge f(\mathbf x)\big\}$ is a convex set. So if your function is nonconvex, take the function corresponding to the convex hull of its epigraph. Other equivalent ways of describing this:

  • Let $\hat f$ be the largest convex function dominated by $f$. $$\hat f(\mathbf x) = \max\big\{g(\mathbf x):\text{$g$ is convex and $g(\mathbf y)\le f(\mathbf y)$ for all $\mathbf y$}\big\}.$$
  • Let $\hat f$ be the maximum of all affine functions dominated by $f$. $$\hat f(\mathbf x) = \max\big\{\mathbf a\cdot\mathbf x + b:\text{$\mathbf a\cdot\mathbf y+b\le f(\mathbf y)$ for all $\mathbf y$}\big\}.$$
  • Let $\hat f(\mathbf x)$ be the smallest $\sum\alpha_i f(\mathbf x_i)$ over all possible convex combinations $\sum\alpha_i\mathbf x_i=\mathbf x$. $$\hat f(\mathbf x) = \textstyle\min\big\{\sum\alpha_i f(\mathbf x_i):\alpha_i\ge0,\sum\alpha_i=1,\sum\alpha_i\mathbf x_i = \mathbf x\big\}.$$

(I'm being sloppy and assuming that the $\max$/$\min$ are attained and we don't need $\sup$/$\inf$ instead; I might be wrong.)

I haven't given any thought to your specific case of $f(\mathbf x)=\lVert\mathbf x\rVert_2\lVert\mathbf x\rVert_1$ yet. If I think of something, I'll edit it into this answer. Surely the symmetry of the function should help a lot here.

share|improve this answer
    
$\min_{z,x}~z^2,~s.t.~||x||_2\leq z,~||x||_1\leq z$, is this problem convex? –  dineshdileep Jan 4 '13 at 10:09
    
@dinesh: I guess so. The minimum is at $x=0, z=0$. But why do you ask? –  Rahul Jan 4 '13 at 10:11
    
adding other constraints which the OP might have, do you think it might be an convex relaxation for the problem he asked for? For instance, $\min_{z_1,z_2,x}~z_1z_2,~s.t.~||x||_2\leq z_1,~||x||_1\leq z_2$, this should exactly solve OP's question along with other constraints. I just put another restriction $z_1=z_2$, thus it should give an upper bound. –  dineshdileep Jan 4 '13 at 10:15
    
But the problem is not to minimize $f$. The problem is to find a convex function that best approximates $f$. –  Rahul Jan 4 '13 at 10:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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