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 17:49, 29 January 2024 (→Implications based on the ellipsoid method). 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.

Trivial implications

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.

Examples

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.

Other implications

A major result in convex optimization is that, for any "well-described" polyhedron, the strong-separation problem, the strong-optimization problem and the strong-violation problem are polynomial-time-equivalent. That is, given an oracle for any one of these three problems, the other two problems can be solved in polynomial time.[1]: 158  A polyhedron is called "well-described" if the input contains n (the number of dimensions of the space it lies in), and contains a number p such K can be defined by linear inequalities with encoding-length at most p.[1]: 163  The result is proved using the ellipsoid method.

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,-ε).

Trivial implications

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.

Implications based on the ellipsoid method

Besides these trivial implications, there are highly non-trivial implications, whose proof relies on the ellipsoid method. Some of these implications require additional information about the convex body K. In particular, besides the number of dimensions n, the following information may be needed:[1]: 53 

  • A circumscribed radius R, which is the radius of a ball centered at the origin that contains K. The tuple (K;n,R) is called a circumscribed convex set.
  • An inscribed radius r, which is the radius of a ball contained in K in case K is nonempty. This r also provides a lower bound on the volume of K. The tuple (K;n,R,r) is called a well-bounded convex set.
  • An interior point a0, which is a point such that a ball of radius r around a0 is contained in K. The tuple (K;n,R,r,a0) is called a centered convex set.

The following implications hold:[1]: Sec.4 

  • An algorithm for WOPT can solve WSEP without any further information.
  • An algorithm for WVAL, with a circumscribed radius R, can solve WSEP.
  • An algorithm for WSEP, with a circumscribed radius R, can solve WVIOL.
  • An algorithm for WVIOL, with a circumscribed radius R, can solve WOPT.
  • An algorithm for WMEM, with R and r and a0, can solve WVIOL.

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 f g h i 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=1200518757"