0

In 14 dimensional euclidean space, I have 30 linear constraints $c_1$, $\cdots$, $c_{30}$ one of which is, for example, either an equation like

$$x_1+x_3-x_5+x_{10}=5$$

or an inequality like

$$x_1+4x_3-x_5+3x_{10}\ge10.$$

Intersecting all the constraints constitutes a subset $S$ of $R^{14}$. That is,

$$S=\{(x_1,\cdots,x_{14})\in\mathbb R^{14}:c_1\wedge\cdots\wedge c_{30}\}.$$

The set $S$ is either connected or disconnected. I want to get a finite set $P$ of points (the number of such points needs to be minimized) where every component (in the connectedness sense) has at least a point in $P$. Is there any analytical or numerical way for obtaining such $P$?

govindah
  • 107
  • If all the constraints are linear, then your set $S$ is the intersection of a family of convex sets, and is therefore itself convex. In particular, it is connected, so there is only one component. So it would seem you just want to find a single point. – M W Sep 12 '23 at 03:07
  • @MW I see. I wonder why I've thought that it can be disconnected. I've imagine the wrong picture. I'll find the relevant reference related to your saying e.g. (1) intersection of convex sets is convex and (2) a convex set is connected. – govindah Sep 12 '23 at 03:54
  • Just to maybe save you some trouble of looking it up, a set $S$ is convex if whenever $x,y\in S$, the segment $L$ joining them is contained in $S$. So if two points are in the intersection, then that implies the two points lie in each set, which implies the segment joining them lies in each set, which implies the segment joining them lies in the intersection. This holds for arbitrary pairs of points in the intersection, so intersection is convex. As for being connected, it is clearly path-connected (the segment joining two points is in the set), and path connectedness implies connectedness. – M W Sep 12 '23 at 04:02

2 Answers2

1

The RIGHT answer according to the MW's comment. (summary : $S$ is convex and connected.)

Definition : A subset $S$ of $\mathbb R^{14}$ is said to be convex if $S$ satisfies the following condition ; for all $x,y\in S$ and for all $t\in (0,1)$, we have $tx+(1-t)y\in S$.

(1) $C_i$'s are convex

Let $C_i$ be $C_i=\{(x_1,\cdots,x_{14}):c_i\}$. Denote

\begin{align*} a&=\begin{bmatrix}a_1&\cdots a_{14}\end{bmatrix}^T\\ x&=\begin{bmatrix}x_1&\cdots x_{14}\end{bmatrix}^T \end{align*}

If $c_i$ involves an equation like

$$c_i:a^Tx=b$$

then, $C_i$ is convex since for $t\in(0,1)$ and $x,y\in C_i$,

$$a^T\left(tx+(1-t)y\right)=t\cdot a^Tx+(1-t)a^Ty=tb+(1-t)b=b$$

so that $tx+(1-t)y\in C_i$.

If $c_i$ involves an inequality like

$$c_i:a^Tx>b$$

then, $C_i$ is convex since for $t\in(0,1)$ and $x,y\in C_i$,

$$a^T\left(tx+(1-t)y\right)=t\cdot a^Tx+(1-t)a^Ty>tb+(1-t)b=b$$

so that $tx+(1-t)y\in C_i$. The inequality $<$ can be replaced by $>$, $\le$ or $\ge$. Thus, $C_i$ is convex for all cases.

(2) The intersection of convex sets is convex. Thus $S$ is convex.

Let $C_1$, $\cdots$, $C_{30}$ be all convex subsets of $\mathbb R^{14}$. Let $S=C_1\cap\cdots\cap C_{30}$. Suppose that $t\in(0,1)$ and $x,y\in S$. Then, $x,y\in C_i$ for all $i\in\{1,2,\cdots,30\}$. Thus, $tx+(1-t)y\in C_i$ for all $i\in\{1,2,\cdots,30\}$ and $tx+(1-t)y\in S$. Therefore, $S$ is convex.

(3) A convex set is connected.

Let $S$ be a convex set. Let $x,y\in S$, then $$f(t)=tx+(1-t)y$$ for $t\in[0,1]$ is a continuous function from $x$ to $y$. Note that $f(t)\in S$ for all $t$ since $S$ is convex. That is, $f$ is a path in $S$ joining $x$ and $y$. Thus, $S$ is path-connected and therefore $S$ is connected.

Conclusion

Since $S$ is connected, the desired set $P$ of points can be any one-point-set in $S$ ; we don't need to find such points.

govindah
  • 107
0

EDIT : this answer is not adequate. See the RIGHT answer.

Let's assume that inequalities are all nonstrict so that $S$ is closed. Let $c_i'$ be equality instead of ineqaulity ; if $c_1$ and $c_2$ were

\begin{align*} c_1&:x_1+x_3-x_5+x_{10}=5\\ c_2&:x_1+4x_3-x_5+3x_{10}\ge10, \end{align*}

set

\begin{align*} c_1'&:x_1+x_3-x_5+x_{10}=5\\ c_2'&:x_1+4x_3-x_5+3x_{10}=10. \end{align*}

And let $S'$ be the intersection of $c_i'$ ;

$$S=\{(x_1,\cdots,x_{14})\in\mathbb R^{14}:c_1'\wedge\cdots\wedge c_{30}'\}.$$

Obviously, $S'\subset S$ and the number of components of $S$ are that of $S'$. So it is safe to obtain the points $p_j$ with respect to $S'$.

Now, I can evaluate all the points $p_j$ of intersections of $c_i$'. In $\mathbb R^{14}$, the intersection of 14 linear equality is a point (unless bad things happen). So there are $\binom{30}{14}=145422675$ points to evaluate. Such points $p_1$, $\cdots$, $p_{145422675}$ constitute the desired set $P$.

govindah
  • 107