0
$\begingroup$

I have the following problem:

$$\begin{array}{ll} \text{Solve } A x = b\\\text{subject to} & x_{\min} \le x_i \le x_{\max}, \quad\forall i \in \{1,2,3, M\} \end{array}$$

for $x \in \mathcal{R}^{M \times 1}$, $b \in \mathcal{R}^{3 \times 1}$, $A \in \mathcal{R}^{3 \times M}$, where A have row full rank.

Now I am looking for a method to check wether a solution to the above exist for all $b ={ \begin{bmatrix} b_1 \\b_2\\b_3\end{bmatrix} } $ in the following domain :

$ { - \begin{bmatrix} c_1 \\c_2\\c_3 \end{bmatrix} } \le { \begin{bmatrix} b_1 \\b_2\\b_3\end{bmatrix} } \le{ \begin{bmatrix} c_1 \\c_2\\c_3 \end{bmatrix} } $

where the c's are positive constants

So my suggsted method is as follows:

1) Check $Ax=b_i$ has solution, for all boundaries of b:

$ \{ { b_1= \begin{bmatrix} c_1 \\c_2\\c_3 \end{bmatrix} } ,b_2= \begin{bmatrix} -c_1 \\c_2\\c_3 \end{bmatrix} b_3= { \begin{bmatrix} c_1 \\-c_2\\c_3\end{bmatrix} } , \cdots b_N= \begin{bmatrix} -c_1 \\-c_2\\-c_3 \end{bmatrix} \} $

Thus there are $2^3$ values of B to check.

2) I now want to claim that if I $Ax=b$ is solvable for all boundaries $b_i$(i.e.,the above 8 Equations), then a solution exists for all possible values of b in the domain

$ { - \begin{bmatrix} c_1 \\c_2\\c_3 \end{bmatrix} } \le { \begin{bmatrix} b_1 \\b_2\\b_3\end{bmatrix} } \le{ \begin{bmatrix} c_1 \\c_2\\c_3 \end{bmatrix} } $

So my question is, can this be shown to be true?.

$\endgroup$
0
$\begingroup$

Yes. Suppose $Ax_i=b_i$ for all $b_i$ in the corners. Suppose you have any other point $b$. You represent it as a convex combination $b=\sum t_ib_i$ with $t_i\geq 0, \sum t_i=1$. Then

$$A(\sum t_ix_i) = \sum t_i Ax_i = \sum t_ib_i = b$$

and moreover the point $\sum t_ix_i$ satisfies your box constrains because it is a convex combination of points $x_i$, all of which are in the box.

$\endgroup$
  • $\begingroup$ Seems reasonable!. This may just be the same (and is probably poorly formulated), but is it also possible to say that boundary of b solving the system, not subject to constraints c must form a convex polygon $C_{max} \in \mathcal{R}^3$. Therefore, if $-c<b<c$, also form a convex polygon $D \in \mathcal{R}^3$, and all verteces (corners) of the boundary of b are feasible (thus inside D), then due to convexity, we must have $D \subset C$ to form a convex set $\endgroup$ – Einar U Aug 30 '18 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.