2
$\begingroup$

Convex optimization is defined here: https://cstheory.stackexchange.com/questions/22314/definition-of-convex-optimization-problem-by-stephen-boyd-and-lieven-vandenbergh

The problem is NP-hard: https://mathoverflow.net/questions/92939/is-that-true-all-the-convex-optimization-problems-can-be-solved-in-polynomial-ti

But is anything known about the approximation complexity of the problem? Does it have a PTAS (poly time approximation scheme)? Or is there a proof that a PTAS is impossible unless P=NP? Are there any known results on upper/lower bounds on its approximability?

Any information will be much appreciated.

$\endgroup$
2
$\begingroup$

You haven't defined convex optimization in general, and indeed it is not clear how one would encode a general convex optimization problem. However, to answer your question it suffices to consider the special case of copositive programming. It is known that Independent Set can be expressed as a copositive program, and this problem is NP-hard to approximate up to a factor of $n^{1-\epsilon}$ for every $\epsilon > 0$. In particular, there is no PTAS.

$\endgroup$
  • $\begingroup$ Thanks.. Let me check to make sure that the reduction from Ind.Set to Copositive Prog is an approximation preserving reduction. $\endgroup$ – Sameer Gupta Jul 26 '16 at 22:49

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.