Before delving into my query, I'd like to provide some context. Consider a continuous function $f:\mathbb{R}^{k}\rightarrow\mathbb{R}^{m}$ and a compact set $\mathcal{B}\subset \mathbb{R}^{k}$ (meaning it is closed and bounded).
Additionally, let's take a matrix $A$ of dimensions $m\times n$. We define $\mathcal{B}_{A}:=\{b\in \mathcal{B} : \exists y\in\mathbb{R}^{n}_{+} \text{ such that } Ay=f(b) \}$, which is the set of vectors $b$ for which the linear system $Ay=f(b)$ has a positive solution. Furthermore, for each $b\in \mathcal{B}_{A}$, we define $\mathcal{Y}_{b}:=\{y\in \mathbb{R}^{n}_{+} : Ay=f(b)\}$, representing the positive solution set of the linear system $Ay=f(b)$. Lastly, $\mathcal{Y}_{\mathcal{B}_{A}}:=\bigcup_{b\in\mathcal{B}_{A}}\mathcal{Y}_{b}$.
Conjecture $\ddagger$: Assuming $\mathcal{B}_{A}\neq\emptyset$, there should exist a bounded set $\mathcal{Y}\subset\mathbb{R}^{n}_{+}$ such that $\mathcal{Y}\cap \mathcal{Y}_{b}\neq\emptyset$ for every $b\in\mathcal{B}_{A}$.
My request: I'm working to prove Conjecture $\ddagger$. Initially uncertain of its veracity, I now believe I have a proof. I'm respectfully requesting assistance in one or more of the following areas:
- A review of my proof, which I've shared under "My attempt". Any feedback on this would be immensely helpful.
- Suggestions for a more straightforward proof. While I believe my current proof is valid, it may be somewhat complex for those less versed in optimization.
- Recommendations for literature references addressing similar problems. Despite extensive research, I haven't found any publications or books presenting results akin to those in the Conjecture.
Remark: While Conjecture $\ddagger$ is presented in a technical and algebraic manner, it can be colloquially described as: "There exists a bounded set containing positive solutions $y$ for the system $Ay=f(b)$ for each $b$ where this system is solvable with positive solutions".
My attempt: We initiate this proof by observing that set $\mathcal{B}_{A}$ can be partitioned into two subsets, expressed as $$ \mathcal{B}_{A}=\mathcal{B}_{A}^{\mathrm{unq}}\cup \mathcal{B}_{A}^{\mathrm{inf}} $$ where $\mathcal{B}_{A}^{\mathrm{unq}}=\{b\in \mathcal{B}_{A} : Ay=f(b) \mbox{ has a unique solution} \}$ and $\mathcal{B}_{A}^{\mathrm{inf}}=\{b\in \mathcal{B}_{A} : Ay=f(b) \mbox{ has infinite solutions} \}$. This allows us to concentrate our analysis separately on each $\mathcal{B}_{A}^{\mathrm{unq}}$ and $\mathcal{B}_{A}^{\mathrm{inf}}$. Our objective is to identify two bounded sets $\mathcal{Y}^{\mathrm{unq}}$ and $\mathcal{Y}^{\mathrm{inf}}$ such that $\mathcal{Y}^{\mathrm{unq}}\cap \mathcal{Y}_{b}\neq \emptyset$ for every $b\in \mathcal{B}_{A}^{\mathrm{unq}}$, and $\mathcal{Y}^{\mathrm{inf}}\cap \mathcal{Y}_{b}\neq \emptyset$ for every $b\in \mathcal{B}_{A}^{\mathrm{inf}}$. Consequently, the bounded set $\mathcal{Y}$ sought in the conjecture will be $\mathcal{Y}=\mathcal{Y}^{\mathrm{unq}}\cup\mathcal{Y}^{\mathrm{inf}}$.
We begin by determining $\mathcal{Y}^{\mathrm{unq}}$. Applying the Gauss-Jordan elimination method, we find that $\mathcal{Y}_{b}=\{g(f(b))\}$ for each $b\in\mathcal{B}_{A}^{\mathrm{unq}}$, where $g$ is the function derived from all elementary operations used in the Gauss-Jordan elimination for this case. Notably, $g$ depends solely on $A$ and is continuous, as it results from a series of continuous operations. Thus, $g\circ f$ is a continuous and positive function.
Given this understanding, we observe that $$\mathcal{Y}_{\mathcal{B}_{A}^{\mathrm{unq}}}:=\bigcup_{b\in \mathcal{B}_{A}^{\mathrm{unq}}}\mathcal{Y}_{b}=\{g(f(b))\::\:b\in\mathcal{B}_{A}^{\mathrm{unq}}\}.$$ Since $g\circ f$ is continuous, $\mathcal{B}$ is compact, and $\mathcal{B}_{A}^{\mathrm{unq}}\subseteq\mathcal{B}$, it follows that $\mathcal{Y}_{\mathcal{B}_{A}^{\mathrm{unq}}}$ is bounded. Therefore, we can set $\mathcal{Y}^{\mathrm{unq}}=\mathcal{Y}_{\mathcal{B}_{A}^{\mathrm{unq}}}$.
Now, turning to the second part of the proof, we focus on finding $\mathcal{Y}^{\mathrm{inf}}$. Employing the Gauss-Jordan elimination method once more, we have $$\mathcal{Y}_{b}=\{y\in\mathbb{R}^{n}_{+} \::\: y=\alpha_{1}\overline{y}_{1}+\cdots \alpha_{\ell}\overline{y}_{\ell}+g(f(b)),\: Ay=f(b),\: \alpha_{i}\in\mathbb{R} \mbox{ for each }i=1,\ldots,\ell \}$$ for each $b\in\mathcal{B}_{A}^{\mathrm{inf}}$, where $g$ again is the function resulting from the Gauss-Jordan elimination's elementary operations, and $\overline{y}_{1},\ldots,\overline{y}_{\ell}$ are fixed vectors dependent solely on $A$. Note that $Ag(f(b))=\mathbf{0}$ for each $b\in\mathcal{B}_{A}^{\mathrm{inf}}$, and $A\overline{y}_{1}=\mathbf{0}$ for each $i=1,\ldots,\ell$.
Acknowledging that $\mathcal{Y}_{b}$ might not be bounded, for each $b\in\mathcal{B}_{A}^{\mathrm{inf}}$, we select an element from $\mathcal{Y}_{b}$. Each element of $\mathcal{Y}_{b}$ is determined by constants $\alpha_{1},\ldots,\alpha_{\ell}$. Therefore, choosing an element from $\mathcal{Y}_{b}$ equates to selecting these constants. Reducing the notation, we denote $\alpha=(\alpha_{1},\ldots,\alpha_{\ell})$. We then select $\alpha$ as an element in $$\Gamma_{b}:=\left\{\begin{array}{ll}\underset{\alpha\in\mathbb{R}^{\ell}}{\mathrm{argmin}} & \|\alpha\|_{\infty}\\ \mathrm{s.t} & \alpha_{1}\overline{y}_{1}+\cdots \alpha_{\ell}\overline{y}_{\ell}+g(f(b))\geq \mathbf{0}. \end{array}\right.$$ Our candidate for $\mathcal{Y}^{\mathrm{inf}}$ is thus characterized as follows: $$ \mathcal{Y}^{\mathrm{inf}}=\left\{\alpha_{1}\overline{y}_{1}+\cdots \alpha_{\ell}\overline{y}_{\ell}+g(f(b))\::\: b\in \mathcal{B}_{A}^{\mathrm{inf}},\: \alpha\in\Gamma_{b}\right\}.$$ The remaining task is to prove that $\mathcal{Y}^{\mathrm{inf}}$ is bounded. Given a norm $\|\cdot\|$ in $\mathbb{R}^{n}$, we aim to demonstrate that $\max_{y\in\mathcal{Y}^{\mathrm{inf}}}\|y\|$ is bounded. In that sense, we observe the following: \begin{align} \max_{y\in\mathcal{Y}^{\mathrm{inf}}}\|y\| &= \max_{ b\in \mathcal{B}_{A}^{\mathrm{inf}}, \alpha\in\Gamma_{b}}\|\alpha_{1}\overline{y}_{1}+\cdots +\alpha_{\ell}\overline{y}_{\ell}+g(f(b))\| \\ &\leq \max_{ b\in \mathcal{B}_{A}^{\mathrm{inf}}, \alpha\in\Gamma_{b}}|\alpha_{1}|\|\overline{y}_{1}\|+\cdots +|\alpha_{\ell}|\|\overline{y}_{\ell}\|+\|g(f(b))\| \\ & \leq \max_{ b\in \mathcal{B}_{A}^{\mathrm{inf}}, \alpha\in\Gamma_{b}} \left(\sum_{i=1}^{\ell}\|\overline{y}_{i}\|\right)\|\alpha\|_{\infty}+\|g(f(b))\|\\ &\leq \left(\sum_{i=1}^{\ell}\|\overline{y}_{i}\|\right)\max_{ b\in \mathcal{B}_{A}^{\mathrm{inf}}, \alpha\in\Gamma_{b}}\|\alpha\|_{\infty}+\max_{ b\in \mathcal{B}_{A}^{\mathrm{inf}}}\|g(f(b))\|. \end{align} Since $g\circ f$ is continuous, $\mathcal{B}$ is compact, and $\mathcal{B}_{A}^{\mathrm{inf}}\subseteq\mathcal{B}$, then $\max_{ b\in \mathcal{B}_{A}^{\mathrm{inf}}}\|g(f(b))\|$ is bounded. Additionally, $\sum_{i=1}^{\ell}\|\overline{y}_{i}\|$ is a constant. The proof concludes if we can demonstrate that $\max_{ b\in \mathcal{B}_{A}^{\mathrm{inf}}, \alpha\in\Gamma_{b}}\|\alpha\|_{\infty}$ is bounded. Indeed, note that $$ \max_{ b\in \mathcal{B}_{A}^{\mathrm{inf}}, \alpha\in\Gamma_{b}}\|\alpha\|_{\infty} =\max_{ b\in \mathcal{B}_{A}^{\mathrm{inf}}}\left\{\begin{array}{ll}\underset{\alpha\in\mathbb{R}^{\ell}}{\mathrm{min}} & \|\alpha\|_{\infty}\\ \mathrm{s.t} & \alpha_{1}\overline{y}_{1}+\cdots + \alpha_{\ell}\overline{y}_{\ell}+g(f(b))\geq \mathbf{0}. \end{array}\right. $$ Therefore, by reformulating the internal minimization problem, considering that $\|\alpha\|_{\infty}=\max\limits_{i=1,\ldots,\ell}\max\{e_{i}^{\intercal}\alpha,-e_{i}^{\intercal}\alpha\}$ where $\{e_1,..,e_l\}$ are the canonical vectors of $\mathbb{R}^{\ell}$, and applying strong duality arguments, we arrive at: \begin{align} \max_{ b\in \mathcal{B}_{A}^{\mathrm{inf}}, \alpha\in\Gamma_{b}}\|\alpha\|_{\infty}&= \max_{ b\in \mathcal{B}_{A}^{\mathrm{inf}}}\left\{\begin{array}{ll}\underset{\alpha\in\mathbb{R}^{\ell}}{\mathrm{min}} & \max\limits_{i=1,\ldots,\ell}\max\{e_{i}^{\intercal}\alpha,-e_{i}^{\intercal}\alpha\}\\ \mathrm{s.t} & \alpha_{1}\overline{y}_{1}+\cdots + \alpha_{\ell}\overline{y}_{\ell}+g(f(b))\geq \mathbf{0}. \end{array}\right. \\ &= \max_{ b\in \mathcal{B}_{A}^{\mathrm{inf}}}\left\{\begin{array}{cll}\underset{\alpha\in\mathbb{R}^{\ell},s\in\mathbb{R}}{\mathrm{min}} & s&\\ \mathrm{s.t} & e_{i}^{\intercal}\alpha\leq s, & \forall i=1,\ldots,\ell.\\ &-e_{i}^{\intercal}\alpha\leq s, & \forall i=1,\ldots,\ell.\\ & \alpha_{1}\overline{y}_{1}+\cdots + \alpha_{\ell}\overline{y}_{\ell}+g(f(b))\geq \mathbf{0}.& \end{array}\right. \\ &=\max_{ b\in \mathcal{B}_{A}^{\mathrm{inf}}}\left\{\begin{array}{cll}\underset{\gamma_{1},\gamma_{2},z}{\mathrm{max}} & -g(f(b))^{\intercal}z&\\ \mathrm{s.t} & \sum_{i=1}^{\ell}\gamma_{1,i}+\sum_{i=1}^{\ell}\gamma_{2,i}=1.& \\ & -\gamma_{1,i}+\gamma_{2,i}+\overline{y}_{i}^{\intercal}z = 0, & \forall i=1,\ldots,\ell. \\ & \gamma_{1}\in\mathbb{R}^{\ell}_{+},\gamma_{2}\in\mathbb{R}^{\ell}_{+},z\in\mathbb{R}^{n}_{+}. & \end{array}\right. \tag{$\bigstar$} \end{align} Strong duality is satisfied as the internal minimization problem is always feasible for every $b\in \mathcal{B}_{A}^{\mathrm{inf}}$, a consequence of how $\mathcal{B}_{A}^{\mathrm{inf}}$ was defined.
Continuing, we note that the feasibility set of the internal maximization problem $$\mathrm{FeasIMP}(\bigstar):=\left\{(\gamma_{1},\gamma_{2},z)\in\mathbb{R}^{2\ell+n}\:\left|\: \begin{array}{ll} \sum_{i=1}^{\ell}\gamma_{1,i}+\sum_{i=1}^{\ell}\gamma_{2,i}=1.& \\ -\gamma_{1,i}+\gamma_{2,i}+\overline{y}_{i}^{\intercal}z = 0, & \forall i=1,\ldots,\ell. \\ \gamma_{1}\in\mathbb{R}^{\ell}_{+},\gamma_{2}\in\mathbb{R}^{\ell}_{+},z\in\mathbb{R}^{n}_{+}. & \end{array}\right. \right\}$$ is a polyhedron, and the optimal value of the internal maximization problem in ($\bigstar$) is finite, indicating that there are extreme points of the $\mathrm{FeasIMP}$ polyhedron that are optimal solutions for that internal maximization problem. Considering $(\overline{\gamma}_{1}^{(1)},\overline{\gamma}_{2}^{(1)},\overline{z}^{(1)}),\ldots,(\overline{\gamma}_{1}^{(\nu)},\overline{\gamma}_{2}^{(\nu)},\overline{z}^{(\nu)})$ as the extreme points of the $\mathrm{FeasIMP}$ polyhedron, we have: $$ \max_{ b\in \mathcal{B}_{A}^{\mathrm{inf}}, \alpha\in\Gamma_{b}}\|\alpha\|_{\infty}=\max_{ b\in \mathcal{B}_{A}^{\mathrm{inf}}}\max_{i=1,\ldots,\nu} \left(-g(f(b))^{\intercal}\overline{z}^{(\nu)}\right). \tag{$\blacklozenge$} $$ Note that ${\displaystyle\max_{i=1,\ldots,\nu} \left(-g(f(b))^{\intercal}\overline{z}^{(\nu)}\right)}$ is a continuous function concerning $b$, hence ($\blacklozenge$) can be viewed as the problem of maximizing a continuous function. Since $\mathcal{B}_{A}^{\mathrm{inf}}\subseteq \mathcal{B}$ and $\mathcal{B}$ is compact, ${\displaystyle\max_{ b\in \mathcal{B}_{A}^{\mathrm{inf}}}\max_{i=1,\ldots,\nu} \left(-g(f(b))^{\intercal}\overline{z}^{(\nu)}\right)}$ is bounded, thus concluding the proof. $\blacksquare$
