Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I'm trying to prove optimality for a continuous linear program. That is, I have a linear program with an uncountable number of variables and constraints. I'm not sure how to demonstrate feasibility of a solution in the primal in this domain.

Here's an example based on a definition in Anderson and Philpott ( Consider the primal continuous LP:

For continuous functions $f_1$ on $X$ and $f_2$ on $Y$, define $\hat f_1$ and $\hat f_2$ on $X\times Y$ by \begin{align*} \hat f_1(x,y)=f_1(x) &\text{ for all } x\in X, y\in Y\\ \hat f_2(x,y)=f_2(y) &\text{ for all } x\in X, y\in Y. \end{align*} \begin{align*} \textbf{Primal: } &\text{minimize } \int_{X\times Y} c(x,y)d\rho (x,y)\\ &\begin{array}{rcllr} \text{subject to }\int_{X\times Y} \hat f_1(x,y) d\rho (x,y) &=& \int_X f_1(x) d\mu_1(x) & \text{ (1)}\\ &&\text{for all continuous functions $f_1$ on $X$}\\ \int_{X\times Y} \hat f_2(x,y) d\rho (x,y) &=& \int_Y f_2(y) d\mu_2(x) & \text{ (2)}\\ && \text{for all continuous functions $f_2$ on $Y$}\\ \rho &\geq& 0\\ \end{array} \end{align*} where $\rho$, $\mu_1$, and $\mu_2$ are nonnegative Radon measures and $c$ is a continuous function. $X$ and $Y$ are compact spaces with $\mu_1(X)=\mu_2(Y)$.

It's easy to formulate the dual continuous linear program, and I know that weak duality holds between the primal and the dual. That is, if I have a primal feasible solution and a dual feasible solution with equal values on the objective functions in the primal and the dual, then the feasible solutions are optimal in the primal and dual respectively.

My goal is to prove that a proposed primal solution $\rho^*$ is optimal by showing that it is primal feasible and that there is a dual feasible solution with the same value of the objective function as $\rho^*$.

My question is in how to show primal feasibility for my proposed optimal $\rho^*$? Is this possible with the uncountably many constraints represented by (1) and (2)? I asked a preliminary question (Continuous Transportation Problem), where it was pointed out that (1) and (2) could equivalently be written as \begin{align*} \begin{array}{rcllr} \mu_1(A) &=& \rho(A\times Y) & \text{ for all } A & \text{ (3)}\\ \mu_2(A) &=& \rho(A\times X) & \text{ for all } A & \text{ (4)} \end{array} \end{align*} In other words, these are marginalization constraints. I believe these constraints can also be written in terms of pdfs as follows. \begin{align*} \begin{array}{rcllr} \int_{x\in X} f_{X\times Y} (x,y) dx &=& f_{P_y}(y) &y\in Y & \text{ (5)}\\ \int_{y\in Y} f_{X\times Y} (x,y) dy &=& f_{P_x}(x) &x\in X & \text{ (6)} \end{array} \end{align*} where the $f_P$'s correspond to pdfs, e.g., if $X$ and $Y$ are probability distributions. Showing feasibility with constraints (5) and (6) is straightforward, but how do I go about showing feasibility for constraints (1) and (2) or for constraints (3) and (4), given I'd have to show feasibility over all continuous $f_1$ and $f_2$ or over all $A$?

Any help, suggestions, or pointers would be very much appreciated.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.