2
$\begingroup$

Is it possible to do linear programming with (countably) infinitely many variables and finitely many constraints? If not, what do you propose?

(Example Link): Maximum and minimum of an integral under integral constraints.

$\endgroup$
  • $\begingroup$ Depends on what you mean by "do", and what do you mean by "finite constraints". For example, variable in $\ell^1$ can be expanded into infinitely many variables with "one" constraint on their sum. However, to properly define an infinite sum, it involves the definition of the limit, and I am not sure if you count that as $1$ linear constraint or not. If you say it is, $\ell^1$ would give you plenty of easy examples. $\endgroup$ – Tunococ Aug 10 '13 at 12:03
  • $\begingroup$ Thanks for you reply. As mentioned above, I mean countably infinite variables and countably finite constraints. Please see the example link I have added above. In my numerical solution of this example, when I use more variables, maximum and minimum by LP get closer to each other. I feel that my example has only one feasible solution for infinite variables. $\endgroup$ – Amir Kazemi Aug 10 '13 at 12:09
  • $\begingroup$ In that link, you have uncountably many variables, don't you? $\endgroup$ – Tunococ Aug 10 '13 at 12:16
  • $\begingroup$ Yes, I have. But to solve it I should discretize the integrals. I do not know whether I am allowed to solve it by LP or not. If I am allowed, why for large number of variables, max and min are almost the same (except for c=0), does it mean that it has a simple solution without resort to LP, etc? $\endgroup$ – Amir Kazemi Aug 10 '13 at 12:20
  • $\begingroup$ Of course you are allowed to approximate a solution by a discretized LP. Then you don't even need infinitely many variables. The problem is you can't easily recover the analytical solution, if there is one. You could be right that the convergence of minimizers and maximizers suggests uniqueness of the feasibly solution. (But if that is what you are aiming for, why don't you set the objective function to a constant?) Regarding the original problem in the link, I believe it depends heavily on $f$ and $C$. (You don't impose $p(x) \ge 0$ for all $x \in [0, a]$?) $\endgroup$ – Tunococ Aug 10 '13 at 12:27

Your Answer

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

Browse other questions tagged or ask your own question.