(s:primal-dual)=
# Primal-dual optimization

Let us assume $X,Y$ are two finite-dimensional real vector spaces
equipped with an inner product $\langle \cdot, \cdot \rangle$ and the
norm $||\cdot|| = \langle \cdot, \cdot \rangle^\frac{1}{2}$. We are
interested in optimization problems of the following form:
```{math}
:label: eq:CP-primal_problem

\min_{x\in X} \ F(Kx) \, + \, G(x) \ ,
```
for which $K \colon X \rightarrow Y$ is a continuous, linear operator.
We further require that $F \colon Y \rightarrow \mathbb{R}$ and
$G \colon X \rightarrow \mathbb{R}$ are proper, convex, lower
semi-continuous functions. In this case, we know from the Fenchel-Moreau
theorem in {prf:ref}`thm:fenchel_moreau` that:
```{math}
F(Kx) \ = \ F^{**}(Kx) \ = \ \max_{y\in Y} \ \langle Kx, y \rangle - F^*(y) \ ,
```
for which $F^*$ is the convex conjugate of $F$. Hence, we can rewrite
{eq}`eq:CP-primal_problem` as the following saddle point problem:
```{math}
:label: eq:CP-primal_dual_problem

\min_{x\in X} \: \max_{y\in Y} \ \langle Kx, y \rangle \, - \, F^*(y) \, + \, G(x)\ ,
```

To derive the necessary conditions of any minimizing pair
$(x,y) \in X \times Y$ of {eq}`eq:CP-primal_dual_problem` we keep one
variable fixed and investigate the optimality conditions of the problem
with respect to the other variable.

1.  We start by keeping $x \in X$ fixed and regarding problem
    {eq}`eq:CP-primal_dual_problem` as a problem solely in $y \in Y$,
    i.e.,
    ```{math}
    :label: eq:CP-primal_dual_y

    \max_{y\in Y} \langle Kx, y \rangle \, - \, F^*(y) \ .
    ```
    Let us assume there exists a solution $\hat{y} \in Y$ of
    {eq}`eq:CP-primal_dual_y`, then we can derive the following
    equivalent condition for any optimum $\hat{y}$:
    ```{math}
    \begin{aligned}
    & \langle Kx, \hat{y} \rangle \, - \, F^*(\hat{y}) \ \geq \ \langle Kx, z \rangle \, - \, F^*(z) \quad &\forall z \in Y& \\
    \Leftrightarrow & \ F^*(z) \ \geq \ \langle Kx, z - \hat{y} \rangle \, + \, F^*(\hat{y}) \quad &\forall z \in Y& \\
    \Leftrightarrow & \ Kx \in \partial F^*(\hat{y}) & &
    \end{aligned}
    ```
    for which $\partial F^*$ denotes the subdifferential of $F^*$ (which
    exists, since $F^*$ is convex). Hence, for a fixed $x \in X$ the map
    $Kx \in Y$ has to be in the subdifferential of the convex conjugate
    $\partial F^*$ at the solution $\hat{y}$.

2.  Now we keep $y \in Y$ fixed and regard the problem
    {eq}`eq:CP-primal_dual_problem` as a problem solely in $x \in Y$,
    i.e.,
    ```{math}
    :label: eq:CP-primal_dual_x

    \min_{x\in X} \langle Kx, y \rangle \, + \, G(x) \ .
    ```
    Let us assume there exists a solution $\hat{x} \in X$ of
    {eq}`eq:CP-primal_dual_x`, then we can derive the following
    equivalent condition for any optimum $\hat{x}$:
    ```{math}
    \begin{aligned}
    & \langle K\hat{x}, y \rangle \, + \, G(\hat{x}) \ \leq \ \langle Kz, y \rangle \, + \, G(z) \quad &\forall z \in Y& \\
    \Leftrightarrow & \ G(z) \ \geq \ \langle K(\hat{x} - z), y \rangle \, + \, G(\hat{x}) \quad &\forall z \in Y& \\
    \Leftrightarrow & \ G(z) \ \geq \ \langle z - \hat{x}, -K^*y \rangle \, + \, G(\hat{x}) \quad &\forall z \in Y& \\
    \Leftrightarrow & \ -K^*y \in \partial G(\hat{x}) & &
    \end{aligned}
    ```
    for which $K^*$ is the adjoint operator of $K$ and $\partial G$
    denotes the subdifferential of $G$ (which exists, since $G$ is
    convex). Hence, for a fixed $y \in Y$ the map $-K^*y \in X$ has to
    be in the subdifferential $\partial G$ at the solution $\hat{x}$.

Hence, we can formulate the following necessary conditions for any
optimal solution $(\hat{x}, \hat{y}) \in X \times Y$ of the saddle point
problem {eq}`eq:CP-primal_dual_problem` as:
```{math}
:label: eq:CP-optimal_conds

\begin{split}
K\hat{x} &\in \partial F^*(\hat{y}) \\
- K^*\hat{y} &\in \partial G(\hat{x})
\end{split}
```
Obviously, it is hard to numerically compute an optimal pair
$(\hat{x}, \hat{y})$ at once, since the optimality conditions in
{eq}`eq:CP-optimal_conds` are coupled. Hence, one keeps one variable
fixed and optimizes the other variable using a semi-implicit iteration
scheme as follows:

1.  For a fixed $x^k$ we can write:
    ```{math}
    \begin{aligned}
    Kx^k \in \partial F^*(\hat{y}) \ \Leftrightarrow \ & \hat{y} + \sigma Kx^k \: & \in \: \hat{y} + \sigma \partial F^*(\hat{y}) \\
    \Leftrightarrow \ & \hat{y} + \sigma Kx^k \: & \in \: \left(I + \sigma \partial F^* \right) (\hat{y}) 
    \end{aligned}
    ```
    If we assume that the prox operator
    ```{math}
    \operatorname{prox}_{\sigma F^*}(z) \ = \ \operatorname{argmin}_{y \in Y} \frac{1}{2} ||z - y||^2 + \sigma F^*(y) \ = \ (I + \sigma \partial F^*)^{-1}(z)
    ```
    has a closed form or can easily be approximated numerically, then we
    can write:
    ```{math}
    y^{k+1} \ \coloneqq \ \operatorname{prox}_{\sigma F^*}(y^k + \sigma Kx^k) \ .
    ```

2.  Now, for a fixed $y^{k+1}$ we can write:
    ```{math}
    \begin{aligned}
    -K^*y^{k+1} \in \partial G(\hat{x}) \ \Leftrightarrow \ & \hat{x} - \tau K^*y^{k+1} \: & \in \: \hat{x} + \tau \partial G(\hat{x}) \\
    \Leftrightarrow \ & \hat{x} - \tau K^*y^{k+1} \: & \in \: \left(I + \tau \partial G \right) (\hat{x}) 
    \end{aligned}
    ```
    If we assume that the prox operator
    ```{math}
    \operatorname{prox}_{\tau G}(z) \ = \ \operatorname{argmin}_{x \in X} \frac{1}{2} ||z - x||^2 + \tau G(x) \ = \ (I + \tau \partial G)^{-1}(z)
    ```
    has a closed form or can easily be approximated numerically, then we
    can write:
    ```{math}
    x^{k+1} \ \coloneqq \ \operatorname{prox}_{\tau G}(x^k - \tau K^*y^{k+1}) \ .
    ```
    Note that both prox operators are well-defined since $G$ and $F^*$
    are convex.

Embedding the derived iteration steps into an alternating optimization
scheme, we get:
```{math}
:label: eq:CP-update_y_prox

y^{k+1} \ = \ \operatorname{prox}_{\sigma F^*}(y^k + \sigma K\overline{x}^k)
```

```{math}
:label: eq:CP-update_x_prox

x^{k+1} \ = \ \operatorname{prox}_{\tau G}(x^k - \tau K^*y^{k+1})
```

```{math}
:label: eq:CP-update_x_relax

\overline{x}^{k+1} \ = \ x^{k+1} + \Theta(x^{k+1} - x^k)
```
The update step {eq}`eq:CP-update_x_relax` performs an overrelaxation
for $\Theta \in [0,1]$. The above iterative scheme converges for the
following step width restriction $\tau \sigma ||K||^2 < 1$.