The relationship between NP-hardness and Convexity

(Benyamin T) #1

Hello, Is there a relationship between NP-hardness and Convexity?
For instance, is it possible for a convex objective function to be an NP-hard problem like a partition problem? If yes, can the results be considered as an approximation of optimal answer?

(Mark L. Stone) #2

Copositive Programs are convex and NP-hard. See p.1 of http://sburer.github.io/papers/033-cpchap.pdf .

if you wish further discussion on this, as it is not a CVX-specific matter, I suggest you post elsewhere, such as at https://or.stackexchange.com/ .

(Benyamin T) #3

Thanks for your help.

(Benyamin T) #4

As you suggested correctly that my problem is not directly CVX-specific, I asked my question in 2 other forums including https://or.stackexchange.com/. However, no one could answer me and I wish that due to your skill in the convex problems you help me.
My problem is to minimize8-11-2019%2012-31-17%20AM where the q_i is positive always, 0<=p_{ij}<=1, \sum_jp_{ij}=1, the denominator has to be positive and m_{ij} is random positive number, but the problem seems to be a partition problem as the p_{ij} can partition the problem solution into the sets that the ∑_ip_{ij}q_i of the sets is the same. So can the obtained solution be correct?

(Mark L. Stone) #5

I’m not even sure what your problem is. Are p_{ij} the only optimization (decision) variables? If so, use inv_pos in CVX.

(Benyamin T) #6

Yes, the only decision variable is p_{ij}. I know how to model it in CVX but my question is when a problem is inherently NP-Hard and we solve it by cvx, is the solution accurate or not?

(Mark L. Stone) #7

I believe that any problem you can model in CVX without use of binary or integer variables is not NP-Hard. Although I am not sure that is the case for problems which don’t satisfy the Slater constraint qualification. Problems which don’t satisfy the Slater constraint qualification invalidate the premise of the primal-dual solvers which CVX calls, and at a minimum, can result in unreliable solution, generally evidenced by a status from the solver that it encountered difficulty or failed.

(Benyamin T) #8

Fortunately, none of the solvers show the status of failed or inaccurate. My only doubt is that my problem seems to be reducible to a partition problem as there can be two sets of solutions that optimize my problem. Doesn’t it make the solution unreliable in general?

(Mark L. Stone) #9

Not as far as i know. If the solution is non-unique, you are at the 'whim" of whichever optimal solution the solver returns.

(Benyamin T) #10

Thank you a lot sir. Your answer helped me a lot.