Is there an algorithm to find if the intersection of two convex sets is empty or not. The projection onto convex method (POCS) and similar methods finds a point in the intersection, but will they output if the intersection is empty ?
6
-
4$\begingroup$ How are the convex sets represented? $\endgroup$Robert Israel– Robert Israel2024-05-14 23:52:08 +00:00Commented May 14, 2024 at 23:52
-
$\begingroup$ Same way as in the input of POCS algorithm $\endgroup$user221985– user2219852024-05-14 23:55:22 +00:00Commented May 14, 2024 at 23:55
-
$\begingroup$ So all that you can do is compute projections onto the convex sets $S_{1}$ and $S_{2}$? $\endgroup$Brian Borchers– Brian Borchers2024-05-15 00:52:07 +00:00Commented May 15, 2024 at 0:52
-
$\begingroup$ Are the two convex sets subsets of $R^{n}$? Or, do they live in some Hilbert space? $\endgroup$Brian Borchers– Brian Borchers2024-05-15 01:09:09 +00:00Commented May 15, 2024 at 1:09
-
$\begingroup$ They are subsets of $\mathbb{R}^n$. $\endgroup$user221985– user2219852024-05-15 01:55:54 +00:00Commented May 15, 2024 at 1:55
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
For a wide variety of convex sets that can be described by linear systems of equations and inequalities, second order cone constraints, and semidefiniteness constraints, you can apply a primal-dual interior point optimization method and obtain a numerical certificate of infeasibility. Many convex optimization software packages can be used to do this computation.
If you want to limit yourself to POCS, then ...
Cheney and Goldstein showed in 1959, that if the two sets $S_{1}$ and $S_{2}$ are closed and convex and at least one of the two sets is compact, then POCS will converge to a minimum distance pair of points $x_{1} \in S_{1}$ and $x_{2} \in S_{2}$.
Cheney, Ward, and Allen A. Goldstein. "Proximity maps for convex sets." Proceedings of the American Mathematical Society 10, no. 3 (1959): 448-450.
If you can convince yourself that POCS has converged and the distance is positive, you could conclude that the sets are disjoint.
