5.3. 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:
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 Theorem 5.1 that:
for which \(F^*\) is the convex conjugate of \(F\). Hence, we can rewrite (5.7) as the following saddle point problem:
To derive the necessary conditions of any minimizing pair \((x,y) \in X \times Y\) of (5.8) we keep one variable fixed and investigate the optimality conditions of the problem with respect to the other variable.
We start by keeping \(x \in X\) fixed and regarding problem (5.8) as a problem solely in \(y \in Y\), i.e.,
(5.9)#\[\max_{y\in Y} \langle Kx, y \rangle \, - \, F^*(y) \ .\]Let us assume there exists a solution \(\hat{y} \in Y\) of (5.9), then we can derive the following equivalent condition for any optimum \(\hat{y}\):
\[\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}\).
Now we keep \(y \in Y\) fixed and regard the problem (5.8) as a problem solely in \(x \in Y\), i.e.,
(5.10)#\[\min_{x\in X} \langle Kx, y \rangle \, + \, G(x) \ .\]Let us assume there exists a solution \(\hat{x} \in X\) of (5.10), then we can derive the following equivalent condition for any optimum \(\hat{x}\):
\[\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 (5.8) as:
Obviously, it is hard to numerically compute an optimal pair \((\hat{x}, \hat{y})\) at once, since the optimality conditions in (5.11) are coupled. Hence, one keeps one variable fixed and optimizes the other variable using a semi-implicit iteration scheme as follows:
For a fixed \(x^k\) we can write:
\[\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
\[\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:
\[y^{k+1} \ \coloneqq \ \operatorname{prox}_{\sigma F^*}(y^k + \sigma Kx^k) \ .\]Now, for a fixed \(y^{k+1}\) we can write:
\[\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
\[\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:
\[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:
The update step (5.14) performs an overrelaxation for \(\Theta \in [0,1]\). The above iterative scheme converges for the following step width restriction \(\tau \sigma ||K||^2 < 1\).