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?


1 Answer 1


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

Those approximate optimality definitions are used to measure the suboptimality of the solution that comes out of an algorithm. For instance, if you solve an optimization problem using a penalty method, the solution that you stop at is likely not optimal, in most cases not even feasible. So what can you say about the quality of this solution which is not even feasible? One way to describe their quality is by using approximated definitions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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