Is the following claim true about the domain of solutions of a linear system with constraints?

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
0
down vote

favorite












I have the following problem:



$$beginarrayll textSolve A x = b\textsubject to & x_min le x_i le x_max, quadforall i in 1,2,3, M endarray$$



for $x in mathcalR^M times 1$, $b in mathcalR^3 times 1$,
$A in mathcalR^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 = beginbmatrix b_1 \b_2\b_3endbmatrix $ in the following domain :



$ - beginbmatrix c_1 \c_2\c_3 endbmatrix le beginbmatrix b_1 \b_2\b_3endbmatrix le beginbmatrix c_1 \c_2\c_3 endbmatrix $



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= beginbmatrix c_1 \c_2\c_3 endbmatrix ,b_2= beginbmatrix -c_1 \c_2\c_3 endbmatrix b_3= beginbmatrix c_1 \-c_2\c_3endbmatrix , cdots b_N= beginbmatrix -c_1 \-c_2\-c_3 endbmatrix $



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



$ - beginbmatrix c_1 \c_2\c_3 endbmatrix le beginbmatrix b_1 \b_2\b_3endbmatrix le beginbmatrix c_1 \c_2\c_3 endbmatrix $



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







share|cite|improve this question
























    up vote
    0
    down vote

    favorite












    I have the following problem:



    $$beginarrayll textSolve A x = b\textsubject to & x_min le x_i le x_max, quadforall i in 1,2,3, M endarray$$



    for $x in mathcalR^M times 1$, $b in mathcalR^3 times 1$,
    $A in mathcalR^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 = beginbmatrix b_1 \b_2\b_3endbmatrix $ in the following domain :



    $ - beginbmatrix c_1 \c_2\c_3 endbmatrix le beginbmatrix b_1 \b_2\b_3endbmatrix le beginbmatrix c_1 \c_2\c_3 endbmatrix $



    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= beginbmatrix c_1 \c_2\c_3 endbmatrix ,b_2= beginbmatrix -c_1 \c_2\c_3 endbmatrix b_3= beginbmatrix c_1 \-c_2\c_3endbmatrix , cdots b_N= beginbmatrix -c_1 \-c_2\-c_3 endbmatrix $



    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



    $ - beginbmatrix c_1 \c_2\c_3 endbmatrix le beginbmatrix b_1 \b_2\b_3endbmatrix le beginbmatrix c_1 \c_2\c_3 endbmatrix $



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







    share|cite|improve this question






















      up vote
      0
      down vote

      favorite









      up vote
      0
      down vote

      favorite











      I have the following problem:



      $$beginarrayll textSolve A x = b\textsubject to & x_min le x_i le x_max, quadforall i in 1,2,3, M endarray$$



      for $x in mathcalR^M times 1$, $b in mathcalR^3 times 1$,
      $A in mathcalR^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 = beginbmatrix b_1 \b_2\b_3endbmatrix $ in the following domain :



      $ - beginbmatrix c_1 \c_2\c_3 endbmatrix le beginbmatrix b_1 \b_2\b_3endbmatrix le beginbmatrix c_1 \c_2\c_3 endbmatrix $



      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= beginbmatrix c_1 \c_2\c_3 endbmatrix ,b_2= beginbmatrix -c_1 \c_2\c_3 endbmatrix b_3= beginbmatrix c_1 \-c_2\c_3endbmatrix , cdots b_N= beginbmatrix -c_1 \-c_2\-c_3 endbmatrix $



      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



      $ - beginbmatrix c_1 \c_2\c_3 endbmatrix le beginbmatrix b_1 \b_2\b_3endbmatrix le beginbmatrix c_1 \c_2\c_3 endbmatrix $



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







      share|cite|improve this question












      I have the following problem:



      $$beginarrayll textSolve A x = b\textsubject to & x_min le x_i le x_max, quadforall i in 1,2,3, M endarray$$



      for $x in mathcalR^M times 1$, $b in mathcalR^3 times 1$,
      $A in mathcalR^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 = beginbmatrix b_1 \b_2\b_3endbmatrix $ in the following domain :



      $ - beginbmatrix c_1 \c_2\c_3 endbmatrix le beginbmatrix b_1 \b_2\b_3endbmatrix le beginbmatrix c_1 \c_2\c_3 endbmatrix $



      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= beginbmatrix c_1 \c_2\c_3 endbmatrix ,b_2= beginbmatrix -c_1 \c_2\c_3 endbmatrix b_3= beginbmatrix c_1 \-c_2\c_3endbmatrix , cdots b_N= beginbmatrix -c_1 \-c_2\-c_3 endbmatrix $



      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



      $ - beginbmatrix c_1 \c_2\c_3 endbmatrix le beginbmatrix b_1 \b_2\b_3endbmatrix le beginbmatrix c_1 \c_2\c_3 endbmatrix $



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









      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Aug 29 at 8:27









      Einar U

      245




      245




















          1 Answer
          1






          active

          oldest

          votes

















          up vote
          0
          down vote



          accepted










          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_igeq 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.






          share|cite|improve this answer




















          • 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 mathcalR^3$. Therefore, if $-c<b<c$, also form a convex polygon $D in mathcalR^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
            – Einar U
            Aug 30 at 11:55











          Your Answer




          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "69"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          convertImagesToLinks: true,
          noModals: false,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );













           

          draft saved


          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2898100%2fis-the-following-claim-true-about-the-domain-of-solutions-of-a-linear-system-wit%23new-answer', 'question_page');

          );

          Post as a guest






























          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes








          up vote
          0
          down vote



          accepted










          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_igeq 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.






          share|cite|improve this answer




















          • 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 mathcalR^3$. Therefore, if $-c<b<c$, also form a convex polygon $D in mathcalR^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
            – Einar U
            Aug 30 at 11:55















          up vote
          0
          down vote



          accepted










          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_igeq 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.






          share|cite|improve this answer




















          • 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 mathcalR^3$. Therefore, if $-c<b<c$, also form a convex polygon $D in mathcalR^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
            – Einar U
            Aug 30 at 11:55













          up vote
          0
          down vote



          accepted







          up vote
          0
          down vote



          accepted






          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_igeq 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.






          share|cite|improve this answer












          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_igeq 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.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Aug 29 at 9:15









          Michal Adamaszek

          1,71948




          1,71948











          • 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 mathcalR^3$. Therefore, if $-c<b<c$, also form a convex polygon $D in mathcalR^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
            – Einar U
            Aug 30 at 11:55

















          • 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 mathcalR^3$. Therefore, if $-c<b<c$, also form a convex polygon $D in mathcalR^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
            – Einar U
            Aug 30 at 11:55
















          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 mathcalR^3$. Therefore, if $-c<b<c$, also form a convex polygon $D in mathcalR^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
          – Einar U
          Aug 30 at 11:55





          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 mathcalR^3$. Therefore, if $-c<b<c$, also form a convex polygon $D in mathcalR^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
          – Einar U
          Aug 30 at 11:55


















           

          draft saved


          draft discarded















































           


          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2898100%2fis-the-following-claim-true-about-the-domain-of-solutions-of-a-linear-system-wit%23new-answer', 'question_page');

          );

          Post as a guest













































































          這個網誌中的熱門文章

          How to combine Bézier curves to a surface?

          Mutual Information Always Non-negative

          Why am i infinitely getting the same tweet with the Twitter Search API?