Consider a linear optimization program like the following max ∑ i = 1 T x i T s.t. a x i + b x i + 1 ≤ 1 , ∀ i ≥ 1 , x i ≥ 0Assume that we take T → ∞. Say that a &gt; 0 , b &gt; 0 and hence the constraints make sure we have some nice properties like x i have to be in some bounded region.There is a lot of structure in this problem and its almost 'symmetric' if we shift every index by 1. I wonder if something can be said about the solution. For example x i = c ∀ i. Does this hold for more general linear inequalities that are almost shift-invariant?There are some similarities to this problem with MDPs and in particular it resembles an Average reward maximization problem. However nothing is random in this problem

Question

Consider a linear optimization program like the following  max                    ∑                  i          =          1                      T                    x        i              T   s.t.   a      x    i    +  b      x          i      +      1        ≤  1  ,  ∀  i  ≥  1  ,      x    i    ≥  0Assume that we take   T  →  ∞. Say that   a  &amp;gt;  0  ,  b  &amp;gt;  0 and hence the constraints make sure we have some nice properties like       x    i   have to be in some bounded region.There is a lot of structure in this problem and its almost &#039;symmetric&#039; if we shift every index by 1. I wonder if something can be said about the solution. For example       x    i    =  c     ∀  i. Does this hold for more general linear inequalities that are almost shift-invariant?There are some similarities to this problem with MDPs and in particular it resembles an Average reward maximization problem. However nothing is random in this problem

EreneDreaceaw · Accepted Answer

First note that due to the constraints       x    i    ≤  max  {      1    a    ,      1    b    }  ,  ∀  iConsider a fixed   T. Add constraint   a      x    T    +  b      x    1    ≤  1. Now variables are shift invariant. i.e. if you have a solution         x    1  , then shifting all the indices by   1 yields another solution         x    2  . this way we can generate         x    1    ,        x    2    ,  ⋯  ,        x    T   optimal solutions. Averaging these optimal solutions yields an index independent optimal solution (another way to view this is by looking at the solution must be invariant with respect to the symmetry group -however i am not very familiar with group theory jargon).Now let&#039;s compare the optimal solution of this additionally constrained problem (call this problem   B) to that of the original problem, call it   A. It must clearly be the case that       A    ⋆    ≥      B    ⋆  . However if you take the optimal of   A and set       x    1    ,      x    T   to   0, we obtain a feasible solution for   B which can only be smaller by at most   2  max  {  1  /  a  ,  1  /  b  }      1    T  .Then       A    ⋆    ≥      B    ⋆    ≥      A    ⋆    −  2  max  {  1  /  a  ,  1  /  b  }      1    T  for   T  →  ∞,       A    ⋆    =      B    ⋆  . Also the proposed feasible solution for       B    ⋆   is also feasible for       A    ⋆  . Hence there exists a constant optimal solution for       x    i    =  c.

Consider a linear optimization program like the following <mo movablelimits="true" form="prefix

Answered question

Answer & Explanation

New Questions in Algebra I