I am concerned with proving the existence of the dual of an infinite linear program. In addition to the writings of Rockafellar, Luenberger, and Boyd & Vandenberghe on: subdifferentials, Legendre-Fenchel transforms and the convex conjugate of a function, indicator functions, support functions/hyperplanes etc, I have consulted the following resources that seem to address this problem directly:

While I am able to follow the development of the duality formalism developed therein, I am having trouble explicitly proving the existence of a dual problem for my infinite linear program in $\ell_1$. I know the dual problem ought to be in $\ell_\infty$, if it exists, but I am unsure how to proceed with an explicit formulation. Rockafellar's Conjugate Duality SIAM Publication only requires continuity of the optimal value function in the infinite dimensional case. My objective function $f:\ell_1\to\mathbb{R}$, which I seek to minimize, in the variable $x=\{x_{ij}\}\in \ell_1$, with $\{a_{ij}\}\in\ell_1$ being parameters, is: $$ f(x) = \sum_{i=0}^{\infty}\sum_{j=0}^{\infty}a_{ij}x_{ij} $$

The constraints for my problem are all equality constraints. Rockafellar's discussion of existence, especially in Theorem 11, didn't seem concerned with the constraints, so I haven't considered them for proving existence of the dual problem. My question is as follows:

  • Is it necessary to frame my objective function as Rockafellar does on page 18? That is to say: specifying a representation $f(x) = F(x,u) \quad u\in U, x\in X$, where $X$ and $U$ are Banach spaces, and $u=0$, which I believe would be the case to relate this representation to my objective function. Then, setting $\varphi (u) = \inf_{x\in X} F(x,u)$, and attempting to show the dual exists via Theorem 11? If not, what would be the correct way of framing my objective function to show the dual exists?

Please let me know if you need more information, or if I am misunderstanding anything, since I simply just want to show the dual exists for this problem. I have been using this site for years, but have recently joined and this is my first question, and I wasn't sure if it should be split up into separate questions or anything like that, so I hope it provides enough context and is answerable :)



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.