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:^: 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 Rⁿ.

Strong variants

The strong variants of the problems are:^: 47

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 in oracle-polynomial time:

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.

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:^: 6

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:^: 50

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 in oracle-polynomial time:

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

Stronger weak variants

Some of these weak variants can be slightly strengthened.^{: Rem.2.1.5(a)} For example, WVAL with inputs c, t' = t+ε/2 and ε' = ε/2 does one of the following:

assert that c^Tx ≤ t+ε for all x in S(K,-ε/2), or -
assert that c^Ty ≥ t for some y in S(K,ε/2).

Implications of weak variants

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:^: 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 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 can be done in oracle-polynomial time:^: Sec.4

An oracle 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 oracle for WVIOL, with a circumscribed radius R, can solve WOPT using binary search.
An oracle 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 oracle 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 oracle for WMEM, with R and r and a₀, can solve WOPT. This follows by transitivity from the implications WMEM→WVIOL and WVIOL→WOPT.
An oracle 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 oracle for WOPT can solve WCCFM.^: 56
- 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.^: 113
An oracle 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 ℝ^{n} : y^{T} x \leq 1 for all x \in K}$ . Note that K**=K.

An oracle for WVAL on an 0-centered convex body (K; n,R,r,0) can solve WMEM on K*.
An oracle for WVIOL on an 0-centered convex body (K; n,R,r,0) can solve WSEP on K*.
An oracle for WOPT can solve WSEP without any further information. The proof uses polarity arguments.
An oracle 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.^: Sec.4.5

An oracle 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 oracle for WVAL, with r and a₀ but without R, cannot solve WVIOL.
An oracle for WVIOL, with r and a₀ but without R, cannot solve WOPT and cannot solve WMEM.
An oracle for WMEM, with r and a₀ but without R, cannot solve WSEP.
An oracle for WSEP, with r and a₀ but without R, cannot solve WVAL.
An oracle for WSEP with r cannot be used to derive a₀, and hence cannot be used to solve WOPT.
An oracle for WVIOL with r cannot be used to derive a₀, and hence cannot be used to solve WOPT.
An oracle 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 in oracle-polynomial time:^: Sec.4.6

Given a well-bounded convex body (K; n, R, r) described by a WSEP oracle, one can find an ellipsoid E(A,a) such that $E (\frac{1}{n (n + 1)^{2}} A, a) \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 (\frac{1}{n^{2}} A, a) \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 an ellipsoid E(A,a) such that $E (\frac{1}{n (n + 1)} A, a) \subseteq K \subseteq E (A, a)$ . Note that a theorem by Jordan proves that there exists an ellipsoid satisfying a stronger relation $E (\frac{1}{n} A, a) \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 an ellipsoid E(A,a) such that $E (\frac{1}{(n + 1)^{2}} A, a) \subseteq K \subseteq E (A, a)$ .
Given a well-bounded, centrally-symmetric convex body (K; n, R, r) given as the solution set of a system of linear inequalities, one can find an ellipsoid E(A,0) such that $E (\frac{1}{n + 1} A, 0) \subseteq K \subseteq E (A, 0)$ .

These results imply that it is possible to approximate any norm by an ellipsoidal norm. Specifically, suppose a norm N is given by a weak norm oracle: for every vector x in Qⁿ and every rational ε>0, it returns a rational number r such that |N(x)-r|<ε. Suppose we also know a constant c₁ that gives a lower bound on the ratio of N(x) to the Euclidean norm, $c_{1} ‖ x ‖ \leq N (x)$ Then we can compute in oracle-polynomial time a linear transformation T of Rⁿ such that, for all x in Rⁿ, $‖ T x ‖ \leq N (x) \leq \sqrt{n (n + 1)} ‖ T x ‖$ .

It is also possible to approximate the diameter and the width of K:

Given a well-bounded convex body (K; n, R, r) described by a WSEP oracle, its diameter can be approximated by finding two points x,y in K, and a ball with radius R* containing K, such that $R^{*} \leq \frac{1}{2} \sqrt{n} ‖ x - y ‖$ .
Given a well-bounded convex body (K; n, R, r) described by a WSEP oracle, its width can be approximated by finding two parallel hyperplanes c^Tx=d₁ and c^Tx=d₂ that lie on two sides of K, and a ball with radius r* contained in K, such that $r^{*} = \frac{d_{2} - d_{1}}{2 (n + 1) \sqrt{n} ‖ c ‖}$

Some problems not yet solved (as of 1993) are whether it is possible to compute in polytime the volume, the center of gravity or the surface area of a convex body given by a separation oracle.

Problems on combinations of convex sets

Some binary operations on convex sets preserve the algorithmic properties of the various problems. In particular, given two convex sets K and L:^: Sec.4.7

For the sum K+L, WOPT can be solved in polytime using WOPT oracles for K and L. The same holds for WVIOL, WSEP and WVAL. However, the same does not hold for WMEM, unless K and L are centered convex bodies.
For the union conv(K u L), the results are the same for the sum: WOPT, WVIOL, WSEP and WVAL (but not WMEM) can be solved in polytime using the respective oracles for K and L.
For the intersection K ח L, it may be impossible to compute the inner radius in polytime, so we need to know the inner radius in advance. With this knowledge, all five problems (WMEM, WOPT, WVIOL, WSEP and WVAL) can be solved in polytime using the respective oracles for K and L.
Given WSEP oracles for K and L, and a rational number r>0, it is possible in oracle-polynomial time to return either (a) an assertion that the intersection K ח L contains a ball with radius r, or (b) a vector c with size 1, and a number d, such that c^Tx ≤ d for all x in S(K,-ε) and c^Tx ≥ d for all x in S(L,-ε), where ε=9nr³(R_K/r_K + R_L/r_L). That is: either the intersection contains a ball, or there is a hyperplane almost-separating K from L.

From weak to strong oracles

In some cases, an oracle for a weak problem can be used to solve the corresponding strong problem.

General convex sets

An algorithm for WMEM, given circumscribed radius R and inscribe radius r and interior point a₀, can solve the following slightly stronger membership problem (still weaker than SMEM): 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.^: 108

Polyhedra

Suppose now that K is a polyhedron. Then, many oracles to weak problems can be used to solve the corresponding strong problems in oracle-polynomial time. The reductions require an upper bound on the representation complexity (facet complexity or vertex complexity) of the polyhedron:^{: Sec. 6.3}

An oracle for WNEMPT, for a full-dimensional polyhedron P with a bound on its representation complexity, can solve SNEMPT.
An oracle for WOPT, for a bounded full-dimensional polyhedron P with a bound on its representation complexity, can solve SOPT.
An oracle for WVIOL, for a bounded full-dimensional polyhedron P with a bound on its representation complexity, can solve SVIOL.
An oracle for WVAL, for a bounded full-dimensional polyhedron P with a bound on its representation complexity, can solve SVAL.
An oracle for WSEP, for a bounded full-dimensional polyhedron P with a bound on its representation complexity, can solve SSEP.
An oracle for WMEM, for a bounded full-dimensional polyhedron P with a bound on its representation complexity, given an interior point in P, can solve SMEM.

The proofs use results on simultaneous diophantine approximation.

Necessity of additional information

How essential is the additional information for the above reductions?^: 173

The assumption that P is full-dimensional is essential: if P is not full-dimensional, then the interior ball S(K,-ε) is empty. Therefore, any oracle for solving a weak problem cannot distinguish between P and the empty set.
The assumption that P is bounded can be relaxed: it is possible to define variants of the weak problems for polyhedra that may be unbounded, and prove reductions analogous to the above results.
For the implication WMEM→SMEM, the assumption that an interior point of P is given is essential. Proof: Suppose we have a polyhedron P with known vertex complexity 2n, and wish to decide whether 0 is in P. If we ask the WMEM oracle fewer than 2ⁿ queries, then the oracle can always answer "no", and it is possible that there exists a unit cube H with vertices whose coefficients are in {0,+1,-1}, that contains zero as a vertex, but does not contain any of the queried points. So it is possible that P=H and the answer is "yes", but it is also possible that P is the convex hull of all non-zero vertices of H and the answer is "no". Therefore, no polytime algorithm can solve SMEM.

Implications of strong variants

Using the previous results, it is possible to prove implications between strong variants. The following can be done in oracle-polynomial time for a well-described polyhedron - a polyhedron for which an upper bound on the representation complexity is known:^: Sec.6.4

An oracle for SSEP can solve SNEMPT,^{: Thm.6.4.1}
An oracle for each SSEP, SVIOL, SOPT can be used to solve the other two.^{: Thm.6.4.9}
In the special case in which P is a cone, SVIOL for P is the same as SSEP for its polar cone P*; therefore, an SSEP oracle for P yields an SSEP algorithm for P*.
If we know in advance that P is nonempty, then the SSEP oracle can be replaced with a slightly weaker separation oracle: given a vector y in Qⁿ, if y is not in P it finds a hyperplane that separates y from P (= a vector c in Rⁿ such that c^Ty > c^Tx for all x in P), but if y is in P, it may still return a hyperplane - a vector c in Rⁿ such that c^Ty ≥ c^Tx for all x in P.

So SSEP, SVIOL and SOPT are all polynomial-time equivalent. This equivalence, in particular, implies Khachian's proof that linear programming can be solved in polynomial time,^{: Thm.6.4.12} since when a polyhedron is given by explicit linear inequalities, a SSEP oracle is trivial to implement. Moreover, a basic optimal dual solution can also be found in polytime.^{: Thm.6.5.14}

Note that the above theorems do not require an assumption of full-dimensionality or a lower bound on the volume.

Other reductions cannot be made without additional information:

If P is not full-dimensional, then SMEM cannot solve SSEP, SVIOL or SOPT.
If P is unbounded, then SVAL cannot solve SSEP, SVIOL or SOPT.

Extension to non-well-described convex sets

Jain extends one of the above theorems to convex sets that are not polyhedra and not well-described. He only requires a guarantee that the convex set contains at least one point (not necessarily a vertex) with a bounded representation length. He proves that, under this assumption, SNEMPT can be solved (a point in the convex set can be found) in polytime.^: Thm.12 Moreover, the representation length of the found point is at most P(n) times the given bound, where P is some polynomial function.^: Thm.13

Geometric problems on polyhedra

Using the above basic problems, one can solve several geometric problems related to nonempty polytopes and polyhedra with a bound on the representation complexity, in oracle-polynomial time, given an oracle to SSEP, SVIOL or SOPT:^: Sec.6.5

Find a vertex of P.
Given a vector c, find a vertex of P that maximizes c^Tx.
Given vectors c₁,c₂, find a vertex of P that maximizes c₁^Tx, and subject to this, maximizes c₂^Tx (lexicographic maximization).
Find the affine hull of P. This also implies finding the dimension of P, and a point in the relative interior of P.
Decide whether any two given vectors are vertices of P, and if so, whether they are adjacent.
Given a point in P, write it as a convex combination of at most n vertices of P (an algorithmic version of Carathéodory's theorem).

References

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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
↑ Yamnitsky, Boris; Levin, Leonid A. (1982). "An old linear programming algorithm runs in polynomial time". 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982). pp. 327–328. doi:10.1109/SFCS.1982.63.
↑ Bland, Robert G.; Goldfarb, Donald; Todd, Michael J. (December 1981). "Feature Article—The Ellipsoid Method: A Survey". Operations Research. 29 (6): 1039–1091. doi:10.1287/opre.29.6.1039. ISSN 0030-364X.
↑ Yudin and Nemirovskii, 1976, https://elibrary.ru/item.asp?id=38308898 (in Russian)
1 2 3 Jain, Kamal (2007). "A Polynomial Time Algorithm for Computing an Arrow–Debreu Market Equilibrium for Linear Utilities". SIAM Journal on Computing. 37 (1): 303–318. doi:10.1137/S0097539705447384. ISSN 0097-5397.
↑ Edmonds, J.; Pulleyblank, W. R.; Lovász, L. (1982-09-01). "Brick decompositions and the matching rank of graphs". Combinatorica. 2 (3): 247–274. doi:10.1007/BF02579233. ISSN 1439-6912. S2CID 37135635.

[:0-1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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

[2] Yamnitsky, Boris; Levin, Leonid A. (1982). "An old linear programming algorithm runs in polynomial time". 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982). pp. 327–328. doi:10.1109/SFCS.1982.63.

[3] Bland, Robert G.; Goldfarb, Donald; Todd, Michael J. (December 1981). "Feature Article—The Ellipsoid Method: A Survey". Operations Research. 29 (6): 1039–1091. doi:10.1287/opre.29.6.1039. ISSN 0030-364X.

[4] Yudin and Nemirovskii, 1976, https://elibrary.ru/item.asp?id=38308898 (in Russian)

[:1-5] 1 2 3 Jain, Kamal (2007). "A Polynomial Time Algorithm for Computing an Arrow–Debreu Market Equilibrium for Linear Utilities". SIAM Journal on Computing. 37 (1): 303–318. doi:10.1137/S0097539705447384. ISSN 0097-5397.

[6] Edmonds, J.; Pulleyblank, W. R.; Lovász, L. (1982-09-01). "Brick decompositions and the matching rank of graphs". Combinatorica. 2 (3): 247–274. doi:10.1007/BF02579233. ISSN 1439-6912. S2CID 37135635.

Algorithmic problems on convex sets

Strong variants

Trivial implications

Examples

Weak variants

Trivial implications

Stronger weak variants

Implications of weak variants

Necessity of additional information

Geometric problems on convex bodies

Problems on combinations of convex sets

From weak to strong oracles

General convex sets

Polyhedra

Necessity of additional information

Implications of strong variants

Extension to non-well-described convex sets

Geometric problems on polyhedra

See also

References