Jump to content

Algorithmic problems on convex sets

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Erel Segal (talk | contribs) at 18:55, 28 January 2024 (→Related problems). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Many problems in mathematical programming can be formulated as problems on convex sets or convex bodies. Six kinds of problems are particularly important:[1]: Sec.2  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 Rn.

Strong variants

The strong variants of the problems are:[1]: 47 

  • Strong optimization problem (SOPT): given a vector c in Rn, find a vector y in K such that cTy ≥ cTx for all x in K, or assert that K is empty.
  • Strong violation problem (SVIOL): given a vector c in Rn and a number t, decide whether cTx ≤ t for all x in K, or find y in K such that cTy > t.
  • Strong validity problem (SVAL): given a vector c in Rn and a number t, decide whether cTx ≤ 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 Rn, decide whether y in K, and if not, find a hyperplane that separates y from K, that is, find a vector c in Rn such that cTy > cTx for all x in K.
  • Strong membership problem (SMEM): given a vector y in Rn, 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 cTy > 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 Rn, 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:[1]: 6 

  • S(K,ε) is the ball of radius ε around K, defined as {x in Rn : |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:[1]: 50 

  • Weak optimization problem (WOPT): given a vector c in Qn and a rational ε>0, either -
    • find a vector y in S(K,ε) such that cTy + ε ≥ cTx for all x in S(K,-ε), or -
    • assert that S(K,-ε) is empty.
  • Weak violation problem (WVIOL): given a vector c in Qn, a rational number t, and a rational ε>0, either -
    • assert that cTx ≤ t + ε for all x in S(K,-ε), or -
    • find a y in S(K,ε) such that cTy > t - ε.
  • Weak validity problem (WVAL): given a vector c in Qn, a rational number t, and a rational ε>0, either -
    • assert that cTx ≤ t+ε for all x in S(K,-ε), or -
    • assert that cTy ≥ 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 Qn and a rational ε>0, either -
    • assert that y in S(K,ε), or -
    • find a vector c in Qn (with ||c||∞=1) such that cTy + ε > cTx for all x in S(K,-ε).
  • Weak membership problem (WMEM): given a vector y in Qn, 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 cTy + ε > 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.

Closely related to the problems on convex sets is the following problem on a convex function f: Rn → R:

  • Strong unconstrained convex function minimization (SUCFM): find a vector y in Rn such that f(y) ≤ f(x) for all x in Rn .

And the following problem on a convex function f: Rn → R and a compact convex set K:

  • Weak constrained convex function minimization (WCCFM): given a rational ε>0, find a vector in S(K,ε) such that f(y) ≤ f(x) + ε for all x in S(K,-ε).

An algorithm for WOPT can solve WCCFM.[1]: 56 

See also

  • Separation oracle - an algorithm for solving the (weak or strong) separation problem for some convex set K.

References

  1. ^ a b c d e Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419
Retrieved from "https://en.wikipedia.org/w/index.php?title=Algorithmic_problems_on_convex_sets&oldid=1200092298"