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.