0
$\begingroup$

Consider a linear optimization program like the following

$\max \frac{\sum_{i=1}^{T} x_i}{T}$ s.t. $a x_i+bx_{i+1}\leq 1, \forall i\geq 1, x_i\geq 0$

Assume that we take $T\rightarrow \infty$. Say that $a>0,b>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\ \forall 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

EDIT: I think I might have found a solution. By adding a new constraint to a system for a fixed T of the form $a x_{T} + b x_1 \leq 1$ the system becomes totally symmetric w.r.t. shifts. This allows us to construct a constant solution $x_i=c$. Now the system with the extra constraint as $T\rightarrow \infty$ is basically unaffected.

$\endgroup$
2
  • $\begingroup$ Since you didn't state this could $a$ or $b$ be negative? $\endgroup$ Nov 20, 2021 at 10:59
  • $\begingroup$ Hello! Assume that a>0,b>0. I edited the description $\endgroup$
    – Cris
    Nov 20, 2021 at 22:33

1 Answer 1

1
$\begingroup$

I am posting the solution I found here just in case anyone can find it useful in the future or if anyone thinks there is some mistake in it.

First note that due to the constraints $x_i \leq \max \{\frac 1 a, \frac 1 b\}, \forall i$

Consider a fixed $T$. Add constraint $a x_T + b x_1 \leq 1$. Now variables are shift invariant. i.e. if you have a solution $\mathbf x^1$, then shifting all the indices by $1$ yields another solution $\mathbf x^2$. this way we can generate $\mathbf x^1, \mathbf x^2, \cdots, \mathbf 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'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^\star \geq B^\star$. 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\} \frac 1 T$.

Then $A^\star \geq B^\star \geq A^\star - 2\max \{1/a,1/b\} \frac 1 T$

for $T\rightarrow \infty$, $A^\star=B^\star$. Also the proposed feasible solution for $B^\star$ is also feasible for $A^\star$. Hence there exists a constant optimal solution for $A$: $x_i=c$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .