I am reading a research paper where it is mentioned that the following constraint is non-convex $$a\sum_{t=1}^{T}b_t\log \left(1+\frac{c}{(d^2+||q(t)-p_k||^2)^{m}}\right)\geq s$$ where $a>0, b_t>0, c>0, d>0, s>0, m>1$. $q(t),p_k$ denote the position in a two dimensional coordinate system. Further we have that $q(1)=\text{some starting position}$ and $q(M)=\text{some final position}$. It is written in the paper that the above constraint is non-convex. Can anybody explain why it is non-convex? Thanks in advance.

My Reasoning to show that the above constraint is non-convex:

If I replace $||q(t)-p_k||$ with some variable $x$ (which can have only positive values) then the first term on the left side becomes $$ab_1\log\left( 1+\frac{c}{(d^2+x^2)^m}\right)$$ then it can be shown that the double derivative of $\log\left( 1+\frac{c}{(d^2+x^2)^m}\right)$ is negative for $x=0$ while it becomes positive after certain value of $x$. Therefore it is not concave and not convex. Which, I think, also means that the upper set of the function is also not-convex. Since the right hand side is summation of such functions ($\sum_{t=1}^{T}b_t\log \left(1+\frac{c}{(d^2+||q(t)-p_k||^2)^{m}}\right)$) therefore the whole constraint is non-convex. Is this explanation right or wrong?

  • 2
    $\begingroup$ Your logic is not valid. You can't use composition rules to prove non-convexity in the same manner one proves convexity. You will have to find a direct counterexample. And make no mistake, it is not convex. But Frank, convexity is a fragile and rare property. It is the exception, not the rule. So it is rarely going to be necessary to prove something is NOT convex. That just isn't the interesting case! The real win is to prove that something IS convex when it is not obviously so. $\endgroup$ – Michael Grant Feb 9 '18 at 6:17
  • $\begingroup$ @MichaelGrant thank you for your comment. I can prove that the above constraint is non-convex for one dimensional coordinate system. But I do not know how to prove it for two dimensional coordinate system. Can you please help in proving that $\log \left(1+\frac{c}{(d^2+||q(t)-p_k||^2)^m}\right)\geq s$ is non-convex? $\endgroup$ – Frank Moses Feb 9 '18 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.