Algorithmic problems on convex sets

Many problems in mathematical programming can be formulated as problems on convex sets or convex bodies. Six kinds of problems are particularly important: optimization, violation, validity, separation, membership and emptiness. Each of these problems has a strong (exact) variant, and a weak (approximate) variant.

In all problem descriptions, K denotes a compact and convex set in Rⁿ.

Strong variants

The strong variants of the problems are:

• Strong optimization problem (SOPT): given a vector c in Rⁿ, find a vector y in K such that c^Ty ≥ c^Tx for all x in K, or assert that K is empty.
• Strong violation problem (SVIOL): given a vector c in Rⁿ and a number t, decide whether c^Tx ≤ t for all x in K, or find y in K such that c^Ty > t.
• Strong validity problem (SVAL): given a vector c in Rⁿ and a number t, decide whether c^Tx ≤ t for all x in K.
• Strong nonemptyness problem (SNEMPT): Decide whether K is empty, and if not, find a point in K.
• Strong separation problem (SSEP): given a vector y in Rⁿ, decide whether y in K, and if not, find a hyperplane that separates y from K, that is, find a vector c in Rⁿ such that c^Ty > c^Tx for all x in K.
• Strong membership problem (SMEM): given a vector y in Rⁿ, decide whether y in K.

From the definitions, it is clear that algorithms for some of the problems can be used to solve other problems:

• An algorithm for SOPT can solve SVIOL, by checking whether c^Ty > t;
• An algorithm for SVIOL solves SVAL trivially.
• An algorithm for SVIOL can solve SNEMPT, by taking c=0 and t=-1.
• An algorithm for SSEP solves SMEM trivially.

The solvability of a problem crucially depends on the nature of K and the way K it is represented. For example:

• If K is represented by a set of some m linear inequalities, then SSEP (and hence SMEM) is trivial: given a vector y in Rⁿ, we simply check if it satisfies all inequalities, and if not, return a violated inequality as the separating hyperplane. SOPT can be solved using linear programming, but it is not so trivial.
• If K is represented as the convex hull of some m points, then SOPT (and hence SVIOL, SVAL and SNEMPT) is easy to solve by evaluating the objective on all vertices. SMEM requires to check whether there is a vector that is a convex combination of the vertices, which requires linear programming. SSEP also requires a certificate in case there is no solution.
• If K is represented as the epigraph of some computable convex function, then SMEM is trivial; if a subgradient can be computed, then SSEP is easy too.

Weak variants

Each of the above problems has a weak variant, in which the answer is given only approximately. To define the approximation, we define the following operations on convex sets:

• S(K,ε) is the ball of radius ε around K, defined as {x in Rⁿ : |x-y| ≤ ε for some y in K}. Informally, a point in S(K,ε) is either in K or "almost" in K.
• S(K,-ε) is the interior ε-ball of K, defined as {x in K : every y with |x-y| ≤ ε is in K}. Informally, a point in S(K,-ε) "deep inside" K.

Using these notions, the weak variants are:

• Weak optimization problem (WOPT): given a vector c in Qⁿ and a rational ε>0, either -
  • find a vector y in S(K,ε) such that c^Ty + ε ≥ c^Tx for all x in S(K,-ε), or -
  • assert that S(K,-ε) is empty.
• Weak violation problem (WVIOL): given a vector c in Qⁿ, a rational number t, and a rational ε>0, either -
  • assert that c^Tx ≤ t + ε for all x in S(K,-ε), or -
  • find a y in S(K,ε) such that c^Ty > t - ε.
• Weak validity problem (WVAL): given a vector c in Qⁿ, a rational number t, and a rational ε>0, either -
  • assert that c^Tx ≤ t+ε for all x in S(K,-ε), or -
  • assert that c^Ty ≥ t-ε for some y in S(K,ε).
• Weak nonemptyness problem (WNEMPT): Given a rational ε>0, either -
  • assert that S(K,-ε) is empty, or -
  • find a point y in S(K,ε).
• Weak separation problem (WSEP): given a vector y in Qⁿ and a rational ε>0, either -
  • assert that y in S(K,ε), or -
  • find a vector c in Qⁿ (with ||c||_∞=1) such that c^Ty + ε > c^Tx for all x in S(K,-ε).
• Weak membership problem (WMEM): given a vector y in Qⁿ, and a rational ε>0, either -
  • assert that y in S(K,ε), or -
  • assert that y not in S(K,-ε).

Analogously to the strong variants, algorithms for some of the problems can be used to solve other problems:

• An algorithm for WOPT can solve WVIOL, , by checking whether c^Ty + ε > t;
• An algorithm for WVIOL solves WVAL trivially.
• An algorithm for WVIOL can solve WNEMPT, by taking c=0 and t=-1.
• An algorithm for WSEP can be used to solve WMEM.