2
$\begingroup$

I wish to study the following linear program

$$\begin{array}{ll} \text{minimize} & \mathrm c^{\top} \mathrm x\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & \mathrm x \geq 0\end{array}$$

where

  • $\mathrm A$ is an infinite matrix with a finite number of nonzero elements in each row. In other words, each constraint only contains a finite number of variables.
  • $\mathrm c$ only contains a finite number of nonzero elements.

Are there any references on this problem? I would like to know if the standard results of finite linear programming involving basic feasible solutions and extreme points also hold for this situation as well.

If no references are available, any intuition about how the finite programming results would or would not apply would be also appreciated. Thank you!

Improve this question
$\endgroup$
6
  • $\begingroup$ Is $\rm A$ Toeplitz? It would be very nice if it were. Does $\rm x$ start with $x_0$ or $x_{-\infty}$? $\endgroup$
    – Rodrigo de Azevedo
    Dec 3, 2016 at 21:33
  • $\begingroup$ In my case $\mathbf{x}$ starts with $x_0$ and unfortunately, it is not Toeplitz. $\endgroup$
    – user3433489
    Dec 4, 2016 at 3:45
  • $\begingroup$ Is it a band matrix, at least? $\endgroup$
    – Rodrigo de Azevedo
    Dec 4, 2016 at 7:40
  • $\begingroup$ I'm afraid my particular matrix is not even a band matrix. There is something like a band, but it becomes wider and wider as you go further down the matrix. But for now I am just looking for an approach to deal with the problem (see below). $\endgroup$
    – user3433489
    Dec 4, 2016 at 15:17
  • $\begingroup$ Triangular? Hessenberg? $\endgroup$
    – Rodrigo de Azevedo
    Dec 4, 2016 at 23:05

2 Answers 2

Reset to default
1
$\begingroup$

We consider the class of linear programs that can be formulated with infinitely many variables and constraints but where each constraint has only finitely many variables. This class includes virtually all infinite horizon planning problems modeled as infinite stage linear programs. Examples include infinite horizon production planning under time-varying demands and equipment replacement under technological change. We provide, under a regularity condition, conditions that are both necessary and sufficient for strong duality to hold. Moreover we show that, under these conditions, the Lagrangean function corresponding to any pair of primal and dual optimal solutions forms a linear support to the optimal value function, thus extending the shadow price interpretation of an optimal dual solution to the infinite dimensional case. We illustrate the theory through an application to production planning under time-varying demands and costs where strong duality is established.

Improve this answer
$\endgroup$
1
1
$\begingroup$

It sounds weird. You essentially only care about the finitely many $x_i$ for which $c_i \neq 0$. But the constraints involving those variables you like might involves lots of variables you don't care about. Ultimately, this seems equivalent to a finite linear program in the sense that as far as you care, the matrix $Ax = b$ could be replaced by some finite matrix equation $A' x' = b'.$ whose solution set is the projection of $\{x \ : \ Ax =b\}$ onto the variables you actually care about.

But I'm not sure to what extent that even makes sense since for instance we could have the equations $x_0 = x_1$ and for all $n \geq 1$ $$ x_{n+1} - x_{n} + \frac{(-1)^{n}}{n} = 0. $$ This matrix would have the finite row condition you want (and a finite column condition), but it's not at all clear how to solve it. One would be tempted to sum all the equations together yielding the telescoping $$ x_0 = x_1 + \sum_{n\geq 1} \left [x_{n+1} - x_{n} + \frac{(-1)^{n}}{n} \right ] = \sum_{n\geq 1} \frac{(-1)^{n}}{n}, $$ but on the other hand, the value of this sum depends on the order that you add the rows together, whereas the formal sum $\sum_{n} ( x_{n+1} - x_{n} )$ seems not to depend on reordering.

So in short, the problem sounds like you should be able to get rid of all the infinite parts you don't care about, but on the other hand, these infinitely many equations don't seem to make a lot of sense to begin with.

Perhaps if you had some sort of absolute convergence condition or something on $A$?

Improve this answer
$\endgroup$
10
  • $\begingroup$ Let me give the context for this (perhaps ill-posed question). My Ax=b has an infinite number of solutions, but I wish to show that a specific x is the only solution to the matrix equation that satisfies the x_i >= 0 condition. I was thinking I could import some results from linear programming to solve this problem. In this case, I'm assuming that the exact cost function to minimize does not matter, so I thought I could provide a simple 'dummy' cost function. Do you have any suggestions? Should I pose that question instead? $\endgroup$
    – user3433489
    Dec 3, 2016 at 19:36
  • $\begingroup$ Dummy cost function would be just $x_1$. Imposing $x_i \geq 0$ won't help you find a unique solution. The condition $Ax = b$ defines an affine hyperplane, so the only way this hyperplane intersected with the cone $x_i \geq 0$ has a unique solution would be if that solution is the trivial $x = 0$. $\endgroup$
    – Pat Devlin
    Dec 3, 2016 at 19:40
  • $\begingroup$ The first row of my matrix is (1,0,0,0,...) and $b_1$=1, so that $x_1$ must be 1. So $x_i=0$ cannot be a solution. Were you talking about the $b_i=0$ case? $\endgroup$
    – user3433489
    Dec 3, 2016 at 21:31
  • $\begingroup$ Oh. I take back the uniqueness thing from earlier. But in general $x \geq 0$ doesn't usually help. $\endgroup$
    – Pat Devlin
    Dec 3, 2016 at 21:34
  • $\begingroup$ And at the same time, having infinitely many solutions to $Ax = b$ is absolutely to be expected. That's the only situation when the linear program is interesting. $\endgroup$
    – Pat Devlin
    Dec 3, 2016 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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