# Approximating a convex program

As I understand it, "approximating" a convex program usually refers to finding a solution that is approximately-feasible approximately-optimal.

For example, in the book "Geometric Algorithms and Combinatorial Optimization" by Grötschel, Lovász and Schrijver the strong optimization problem is defined as follows (page 47):

Given a vector $$c \in \mathbb{R}^n$$, find a vector $$y \in K$$ that maximizes $$c^Tx$$ on $$K$$, or assert that $$K$$ is empty.

while the weak optimization problem is defined as follows (page 50):

Given a vector $$c \in \mathbb{Q}^n$$ and a rational number $$\epsilon >0$$ either

(i) find a vector $$y \in \mathbb{Q}^n$$ such that $$y \in S(K,\epsilon)$$ and $$c^Tx \leq c^T y + \epsilon$$ for all $$x \in S(K, - \epsilon)$$ (i.e., $$y$$ is almost in $$K$$ and almost maximizes $$c^Tx$$ over the points deep in $$K$$), or

(ii) assert that $$S(K, - \epsilon)$$ is empty.

[where $$S(K,\epsilon) = \{x \in \mathbb{R}^n \mid ||x-y|| \leq \epsilon \text{ for some } y \in K\}$$ is called the ball of radius $$\epsilon$$ around $$K$$ and $$S(K, -\epsilon) = \{x \in K \mid S(x, \epsilon) \subseteq K\}$$ is called the interior $$\epsilon$$-ball of $$K$$ (page 6)]

Another example can be found in the book "Interior point polynomial time methods in convex programming" by Nemirovski, in which a family of convex programs of the following form is considered (page 11):

\begin{align*} maximize \quad f(x) \quad s.t. \quad g_j(x) \leq 0, \quad i = 1,\ldots, m, \quad x \in G \end{align*}

And it seems that the goal is to find an $$\epsilon$$-solution to the problem that is defined as any $$x_i$$ that satisfies the following (page 11):

\begin{align*} f(x_i) - f^* \leq \epsilon, \quad g_j(x_i) \leq \epsilon, \quad i = 1,\ldots, m, \quad x_i \in G \end{align*}

where $$f^*$$ is the optimal objective value.

My question is:

Are there any general special cases for the domain $$K$$ in which the strong optimization problem is NP-hard but there is a polynomial time algorithm that achieves a "regular" approximation --- that is, an algorithm that finds a (feasible) solution $$x \in K$$ with approximatly-optimal objective value?

Basically $$S(K, \epsilon) = K + \epsilon B$$. Thus optimizing a function on $$S(K, \epsilon)$$ is not easier than optimization over $$K$$.