I’m reading about a problem, and the author goes from a classical minimization problem to a saddle point problem in order to perform a primal–dual algorithm on it [1].
However, It’s my first problem in optimization theory, and I don’t grasp everything, in particular the steps that are usually used to transform such problem. I’ve read some theory about how to transform this kind of problems, but the examples are very basic in comparison.
The original optimization problem:
$$ \min_{u\in\mathbb{R}^{mn}} \lambda V + W $$
with
$$ V = \sum_{p\in\Omega}\sum_{i=1}^M\sum_{j=1}^N \left|L(p, 0) - L\left(p-u_0(p)\frac{\phi_{s_j,r_i}}{R}, \phi_{s_j,r_i}\right)+(u(p)-u_0(p))\frac{r_i}{R}\nabla_{-\frac{\phi_{s_j,r_i}}{r_i}}L\left(p-u_0\frac{\phi_{s_j,r_i}}{R}, \phi_{s_j,r_i}\right)\right| $$
and
$$ W = \min_w \alpha_1 \lVert D^{\frac{1}{2}}(\nabla u - w)\rVert_\mathcal{M} + \alpha_0 \lVert\nabla w\rVert_\mathcal{M} $$
with
$$ D^{\frac{1}{2}} = \exp(-\gamma|\nabla I|^\beta)nn^T + n^\bot n^{\bot^T} $$
and $\lVert\cdot\rVert_\mathcal{M}$ some vector-valued Radon measure.
They directly say: this problem can be formulated as a saddle problem as:
$$ \min_{u,w} \max_{\lVert p_u\rVert_\infty \leq 1;\ \lVert p_w\rVert_\infty \leq 1;\ \lVert p_{ij}\rVert_\infty \leq 1}\left(\lambda \sum_{i=1}^M\sum_{j=1}^N\langle B_{ij}-A_{ij}(u-u_0), p_{ij}\rangle +\alpha \langle D^{\frac{1}{2}}(\nabla u - w), p_u\rangle + \alpha_0 \langle\nabla w, p_w\rangle\right) $$
with
$$ \tilde{A}_{ij} := \left(\frac{r_i}{R}\nabla_{-\frac{\phi_{s_j,r_i}}{r_i}}L(p-u_0(p)\frac{\phi_{s_j,r_i}}{R}, \phi_{s_j,r_i}\right) $$
$$ A_{ij} := diag(\tilde{A}_{ij}) $$
and
$$ B_{ij} := \left(L(p,0) - L(p-u_0(p)\frac{\phi_{s_j,r_i}}{R}, \phi_{s_j,r_i}\right) $$
$$ \phi_{s_j,r_i} = r(\cos(s_j), \sin(s_j)), \lambda \in \mathbb{R}, p, \lambda, \alpha_k, M, N, R, m,n \in\mathbb{R}. $$
But then… I’m completely lost on how they transformed the original problem into this one.
- Can someone help me with the main steps?
- are there usual ways to transform such problems in the second form?
- why it is a saddle point problem?
- how can we check the convexity?
Bonus: do you have good references ?
[1] Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision 40, 120–145 (2011)
