2
$\begingroup$

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.

$\endgroup$

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.