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.

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

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

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 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.

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 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.

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. 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. 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:

• 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,-ε).Closely related to the problems on convex sets is the following problem on a compact convex set K and a convex function f: Rⁿ → R given by an approximate value oracle:
• 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,-ε).

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 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.

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:

• 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 a₀, which is a point such that a ball of radius r around a₀ is contained in K. The tuple (K;n,R,r,a₀) is called a centered convex set.

The following implications hold:

• An algorithm for WSEP, with a circumscribed radius R, can solve WVIOL. This algorithm uses the central-cut ellipsoid method. Another option is to use another method that uses simplices instead of ellipsoids.
• An algorithm for WVIOL, with a circumscribed radius R, can solve WOPT using binary search.
• An algorithm for WSEP, with a circumscribed radius R, can solve WOPT. This follows by transitivity from the implications WSEP→WVIOL and WVIOL→WOPT, but there is also a direct algorithm WSEP→WOPT using the sliding objective function technique.
• An algorithm for WMEM, with R and r and a₀, can solve WVIOL. This was proved by Yudin and Nemirovskii in 1976, using the shallow-cut ellipsoid method.
• An algorithm for WMEM, with R and r and a₀, can solve WOPT. This follows by transitivity from the implications WMEM→WVIOL and WVIOL→WOPT.
• An algorithm for WMEM, with R and r and a₀, can solve WSEP. This follows by transitivity from the implications WMEM→WVIOL and WVIOL→WSEP. Interestingly, both steps require the ellipsoid method, and no direct algorithm WMEM→WSEP is known.
• An algorithm for WOPT can solve WCCFM.
  • An approximate value oracle for a convex function can be used to construct a WMEM oracle. Combining this with the implications WMEM→WVIOL and WVIOL→WOPT and WOPT→WCCFM implies that WCCFM on a centered convex body (K;n,R,r,a₀) given by a WMEM oracle can be solved in polynomial time.

Some weak oracles can strengthen themselves:

• An algorithm for WMEM, with R and r and a₀, can solve the following slightly stronger membership problem: given a vector y in Qⁿ, and a rational ε>0, either assert that y in S(K,ε), or assert that y not in K. The proof is elementary and uses a single call to the WMEM oracle.
• An algorithm for WOPT, with r, can be used to found r' and a₀ such that S(a₀,r') is contained in K.

The following implications use the polar set of K - defined as $K^{*}:=\{y\in \mathbb {R} ^{n}:y^{T}x\leq 1{\text{ for all }}x\in K\}$. Note that K**=K.

• An algorithm for WVAL on an 0-centered convex body (K; n,R,r,0) can solve WMEM on K*.
• An algorithm for WVIOL on an 0-centered convex body (K; n,R,r,0) can solve WSEP on K*.
• An algorithm for WOPT can solve WSEP without any further information. The proof uses polarity arguments.
• An algorithm for WVAL, with a circumscribed radius R, can solve WSEP. The proof uses polarity arguments.

Necessity of additional information

Some of the above implications provably do not work without the additional information.

• An algorithm for WMEM or even for SMEM, with R and r but without a₀, cannot solve WVIOL in polytime, even for n=1 and r=1 and c=1 and ε=1. Proof. Note that with the given parameters, what we know about K is that K is contained in the interval [-R,R], and contains some interval of length 2r=2. Suppose an SMEM oracle answers "no" to the first R membership queries; this is a valid sequence of answers, since by the pigeonhole principle, there is an interval of length 2 that does not contain any querired point. Therefore, any algorithm solving WOPT needs more than R queries, so it is exponential in the encoding length of R.
• Similarly, an algorithm for WMEM, with R and r but without a₀, cannot solve WOPT.
• An algorithm for WVAL, with r and a₀ but without R, cannot solve WVIOL.
• An algorithm for WVIOL, with r and a₀ but without R, cannot solve WOPT and cannot solve WMEM.
• An algorithm for WMEM, with r and a₀ but without R, cannot solve WSEP.
• An algorithm for WSEP, with r and a₀ but without R, cannot solve WVAL.
• An algorithm for WSEP with r cannot be used to derive a₀, and hence cannot be used to solve WOPT.
• An algorithm for WVIOL with r cannot be used to derive a₀, and hence cannot be used to solve WOPT.
• An algorithm for WSEP with R cannot be used to derive r.

Geometric problems on convex bodies

Using the above basic problems, one can solve several geometric problems related to convex bodies. In particular, one can find an approximate John ellipsoid:

• Given a well-bounded convex body (K; n, R, r) described by a WSEP oracle, one can find in polytime an ellipsoid E(A,a) such that $E\left({\frac {1}{n(n+1)^{2}}}A,a\right)\subseteq K\subseteq E(A,a)$. The algorithm uses the shallow-cut ellipsoid method. Note that, by the Lowner-John theorem, there exists an ellipsoid satisfying a stronger relation $E\left({\frac {1}{n^{2}}}A,a\right)\subseteq K\subseteq E(A,a)$, but that theorem does not yield a polytime algorithm.
• Given a well-bounded, centrally-symmetric convex body (K; n, R, r) described by a WSEP oracle, one can find in polytime an ellipsoid E(A,a) such that $E\left({\frac {1}{n(n+1)}}A,a\right)\subseteq K\subseteq E(A,a)$. The algorithm uses the shallow-cut ellipsoid method. Note that, by the Lowner-John theorem, there exists an ellipsoid satisfying a stronger relation $E\left({\frac {1}{n^{2}}}A,a\right)\subseteq K\subseteq E(A,a)$, but that theorem does not yield a polytime algorithm.
• Given a well-bounded, convex body (K; n, R, r) given as the solution set of a system of linear inequalities, one can find in polytime an ellipsoid E(A,a) such that $E\left({\frac {1}{(n+1)^{2}}}A,a\right)\subseteq K\subseteq E(A,a)$. The algorithm uses the shallow-cut ellipsoid method. Note that, by the Lowner-John theorem, there exists an ellipsoid satisfying a stronger relation $E\left({\frac {1}{n^{2}}}A,a\right)\subseteq K\subseteq E(A,a)$, but that theorem does not yield a polytime algorithm.

See also

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