2

I have the following optimization problem:

$$ \begin{aligned} & \underset{\alpha, \gamma}{\text{minimize}} & & \end{aligned} \frac{1}{2} \|y - \sum\limits_{i=1}^{S}\gamma_{i}\cdot X_{i}\alpha_{i}\|_{2} + \sum\limits_{i=1}^{S}\frac{\lambda_{i}}{p}\|\alpha_{i}\|_{p}^{p} + \sum\limits_{i=1}^{S} \frac{\eta_{i}}{q}|\gamma|^{q} $$

Is this problem convex if $p, q, \lambda_{i}, \eta_i \geq 1$? If yes than what would make this problem non-convex?

The reason I ask is because this problem is mentioned in the following paper (Equation 2) and the authors claim that this is non-convex (They don't put any constraints on the various parameters though, the way I have.).

paper: www.site.uottawa.ca/~nat/Courses/csi5387_Winter2014/paper17.pdf

MRashid
  • 265

1 Answers1

1

It is the quadratic term in $\gamma$ and $\alpha$ inside that first norm that makes it non-convex. It is convex separately in $\alpha$ and $\gamma$, just not jointly.

Michael Grant
  • 19,450
  • How would you prove it though? Would you show that it doesn't obey the triangle inequality? Or the Hessian is negative? I'll be really glad if you could provide a proof or at least point to the proof. – MRashid Mar 10 '14 at 00:24
  • 1
    I cannot, I'm sorry. But frankly, the way you've asked your question is a bit off. You should never assume that something is convex until you can prove it is. Convexity is actually uncommon, dare I say rare, in the space of possible functions. The burden of proof should be on claims of convexity, not the other way around. – Michael Grant Mar 10 '14 at 01:18
  • In other words: why were you inclined to believe it is convex in the first place? What makes you skeptical of the author's claims? – Michael Grant Mar 10 '14 at 01:19
  • "Why were you inclined to believe it is convex in the first place?"

    • Firstly, I'm relatively inexperienced with optimization and convex problems. Before seeing this problem, I always assumed that every norm is a convex function (http://en.wikipedia.org/wiki/Convex_function). Yes, I did see the joint convexity part in the problem.

    – MRashid Mar 10 '14 at 01:43
  • "What makes you skeptical of the author's claims?"

    • Perhaps I didn't word the question properly. I didn't for once think that the claim is incorrect. I'm just bothered by the fact that I can't readily see or prove that it's not convex.

    – MRashid Mar 10 '14 at 01:44
  • 1
    Fair enough. In my view however you should not be bothered. Again: convexity is the exception not the rule. Sure, a norm is convex, in isolation. But this is the norm of a nonconvex quantity! – Michael Grant Mar 10 '14 at 03:00
  • 1
    Thank you Prof. Grant for your help. Also, thank you for developing CVXR. Your work and Prof. Boyd's online lectures and textbook are helping me immensely. – – MRashid Mar 10 '14 at 14:14