What are the hardness results that we know of for generally convex problems? In particular, I know of the result that every convex problem is in $P$ when we have an oracle for generating a separating functional and we can lose solvability in $P$ if we lack strong duality (but I'm not sure what the particular conditions are necessary for this to be the case).

Additionally, this plays into the next question: are there any hardness results for approximations of general convex problems? What are the canonical papers for reference? I think it would be great to have a collection of these results.


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.