0
$\begingroup$

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.

  • 0
    yeah it should be lowercase p, thanks for correcting it2011-06-03

2 Answers 2

1

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.

  • 0
    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 (http://math.stackexchange.com/questions/43110/minimizing-a-function-by-finding-derivative). I dunno if it is the right thing to do to open a related problem.2011-06-04
0

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?

  • 1
    OK, I've added another answer that might be more what you're looking for.2011-06-04