Theorem 4.1 — the value function of decomposition with respect to variables is convex, with subgradient $g^x_{L_U}(\bar x, y(\bar x))$

Let $f_0$ and $f_i$, $i = 1,\dots,n$, be jointly convex functions of $(x,y) \in E^x_l \times E^y_m$, let $D(x) = \{y : f_i(x,y) \le 0,\ i = 1,\dots,n\}$ and $\Phi(x) = \min_{y \in D(x)} f_0(x,y)$ (4.5), and let $W \subseteq E^x_l$ be a convex set at each point of which this minimum is attained. Then:

1. $\Phi$ is convex on $W$;
2. if $\bar x \in W$ and the Slater condition holds for $f_i(\bar x, y) \le 0$, then for every optimal $y(\bar x) = \bar y$ of the subproblem (4.3)–(4.4):
   • Kuhn–Tucker multipliers $U = (U_i)$ of (4.3)–(4.4) exist ($U \ge 0$, $U_i f_i(\bar x,\bar y) = 0$, $\bar y$ minimizes $L_U(\bar x,\cdot)$, where $L_U = f_0 + \sum_i U_i f_i$);
   • for every such $U$, the Lagrange function $L_U$ has a subgradient at $(\bar x,\bar y)$ whose projection on $E^y_m$ vanishes;
   • for every such subgradient $(g^x_{L_U}(\bar x, y(\bar x)), 0)$,

is a subgradient of $\Phi$ at $\bar x$: $\Phi(x) - \Phi(\bar x) \ge (x - \bar x, g_\Phi(\bar x))$ for all $x \in W$.

Theorem 4.1 reduces a convex program in $(x,y)$ to the convex minimization of $\Phi$ over $x$, with a subgradient of $\Phi$ read off from the solution and multipliers of the subproblem in $y$; this is the basis of the subgradient decomposition algorithm (steps (a)–(c), p. 96).

Formalization Note The book's "convex on some convex subset $W$ of $E_n$" is read as convexity on every convex set of $x$-values where $\Phi$ is defined. The printed "(3.4)–(4.4)" is read as (4.3)–(4.4). Formula (4.6) is stated, as the book's proof uses it, for a subgradient of $L_U$ whose $y$-projection vanishes; for an arbitrary subgradient of $L_U$ the $x$-projection need not be a subgradient of $\Phi$.