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.

  • 1
    I changed an uppercase $P$ to lowercase $p$ -- I hope that's correct.2011-06-03
  • 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?

  • 0
    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.2011-06-03
  • 0
    Are you expecting the "dual variables" to take the form of arbitrary functions $\Omega\to\mathbb{R}$?2011-06-04
  • 0
    I believe so, yes. The multipliers which would be the dual variables should be of that form2011-06-04
  • 1
    OK, I've added another answer that might be more what you're looking for.2011-06-04