Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The continuous max flow problem is posed as follows :

sup $\int_\Omega p_s(x)dx$

subject to :

$|p(x)| \le C(x); \forall x \in \Omega $

$p_s(x) \le C_s(x); \forall x \in \Omega $

$p_t(x) \le C_t(x); \forall x \in \Omega $

$\nabla \cdot p(x) - p_s(x) + p_t(x) = 0; \forall x \in \Omega $

Here $p(x)$ is a field vector and is analogous to the flow in the discrete domain. $\nabla \cdot p$ is the divergence of the field p.

How do i find out the dual of this maximization problem using the lagrangian dual technique, i.e. the equivalent min cut formulation of the problem in the continuous domain.

share|improve this question
1  
I changed an uppercase $P$ to lowercase $p$ -- I hope that's correct. –  Jim Belk Jun 3 '11 at 22:30
    
yeah it should be lowercase p, thanks for correcting it –  AnkurVijay Jun 3 '11 at 22:50

2 Answers 2

up vote 1 down vote accepted

Given arbitrary continuous functions $\lambda,\mu,\nu\colon\Omega\to [0,\infty)$ and $\varphi\colon\Omega\to\mathbb{R}$, define $$ G(\lambda,\mu,\nu,\varphi) \;=\; \sup_{(p_s,p_t,p)}\int_\Omega \Bigl(p_s + (C-|p|)\lambda+(C_s - p_s)\mu + (C_t - p_t)\nu + (\nabla\cdot p - p_s + p_t)\varphi \Bigr) $$

Then clearly $\sup_{(p_s,p_t,p)} \int_\Omega p_s \leq G(\lambda,\mu,\nu,\varphi)$ for any $\lambda,\mu,\nu,\varphi$. I would conjecture that $$ \inf_{(\lambda,\mu,\nu,\varphi)} G(\lambda,\mu,\nu,\varphi) \;=\; \sup_{(p_s,p_t,p)} \int_\Omega p_s\text{,} $$ but I do not know enough about dual problems to determine whether this is necessarily the case.

share|improve this answer
    
Jim, this is exactly what i was thinking, at this step i dont know how to find $G(\lambda, \mu, \nu, \varphi)$ i.e. the values of the variables $p_s, p_t, p$ that would maximize the equation on the right hand side. The usual strategy is to find derivatives and equating to zero. I have opened a new problem in this regard (math.stackexchange.com/questions/43110/…). I dunno if it is the right thing to do to open a related problem. –  AnkurVijay Jun 4 '11 at 1:38

I'm assuming $\Omega$ is an $n$-dimensional manifold with a volume form (such as a region in $\mathbb{R}^n$).

First of all, we may assume that $C_s$ and $C_t$ have disjoint supports, for otherwise we can simplify the problem by replacing $C_s$ by $\max(C_s-C_t,0)$ and $C_t$ by $\max(C_t-C_s,0)$, and adding $\int_\Omega \min(C_s,C_t)$ to our final answer. (Here I'm using support to mean the set of points on which the value of a function is nonzero.)

Given this, the obvious conjecture would be that $$ \sup \int_\Omega p_s \;=\; \inf_{(S,T,M)}\left(\int_{\partial M} C + \int_S C_s + \int_T C_t \right)\text{,} $$ where $S$ and $T$ are open subsets of $\Omega$ and $M$ is an $n$-dimensional submanifold of $\Omega$ with boundary, having the following properties:

  1. The support of $C_s$ is contained in $S\cup M$, and
  2. The support of $C_t$ is contained in $T \cup (\Omega - M)$.

Is this what you're looking for?

share|improve this answer
    
Jim, I don't quite understand what you are suggesting . i was looking for something like this : I add the objective function and the equations multiplied respectively by negative of introduced Lagrange multipliers, then i say that the $sup_{p,p_s,p_t}$ of the resultant function is an upper bound on the original maximization. Ill call this as the lagrange dual function. Therefore by finding inf over the dual variables of the dual function, ill find the optimal value of the objective function. –  AnkurVijay Jun 3 '11 at 23:11
    
Are you expecting the "dual variables" to take the form of arbitrary functions $\Omega\to\mathbb{R}$? –  Jim Belk Jun 4 '11 at 1:17
    
I believe so, yes. The multipliers which would be the dual variables should be of that form –  AnkurVijay Jun 4 '11 at 1:20
1  
OK, I've added another answer that might be more what you're looking for. –  Jim Belk Jun 4 '11 at 1:35

Your Answer

 
discard

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

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