I.3.6.5: Constrained Problems

Similar calculations can also be carried out in the case of constrained optimization, i.e. when the subproblems optimize over differentiable manifolds and/or convex sets. We then use the implicit function calculations on the Langrangean or Kuhn-Tucker conditions, which makes them a bit more complicated, but essentially the same. In the manifold case, for example, it suffices to replace the matrices $\mathcal{D}_{pq}$ by the matrices $H_p'\mathcal{D}_{pq}H_{q},$ where the matrices $H_p$ contain a local linear coordinate system for $\Omega_p$ near the solution.

The algorithm shows that the update $y_s$ of block $s$ is defined implicitly in terms of $y_1,\cdots,y_{s-1}$ and $x_{s+1},\cdots,x_p$ by the equations $$\mathbf{D}_sf(y_1,\cdots,y_s,x_{s+1},\cdots,x_p)-\mathbf{D}G_s(y_s)\lambda_s=0,$$ and $$G_s(y_s)=0.$$ The equations also implicitly define the vector $\lambda_s$ of Lagrange multipliers.

Let us differentiate this again with respect to $x$. Define $$\begin{align*} H_{sr}&=\mathcal{D}_{sr}^2f,\\ U_{sr}&=\mathcal{D}_{r}y_s,\\ V_{sr}&=\mathcal{D}_{r}\lambda_s, \end{align*}$$ as well as $$W_s(\lambda)=\sum_{r=1} \lambda_r\mathcal{D}^2g_{sr}$$ and $$E_s=\mathcal{D}G_s.$$ From the first set of equations we find for all $r>1$ $$\begin{bmatrix} H_{11}-W_1(\lambda)& -E_1\\ E_1 &0 \end{bmatrix} \begin{bmatrix} U_{1r}\\ V_{1r} \end{bmatrix} = \begin{bmatrix}-H_{1r}\\ 0 \end{bmatrix}.$$ which can easily be solved for $U_{1r}$ and $V_{1r}$.