# Variables Reduction in Sequential Resource Allocation Problems
## 6 The Variables Reduction Technique
In what follows, we recall the notion \(\
abla g\) of the so-called _sub-gradient_ of a convex function \(g:\mathbb{R}^{n}\to\mathbb{R}\cup\{\infty\}\), \((n\in\mathbb{N})\) which is defined at each point \(u\in\mathbb{R}^{n}\) as the family of linear functionals  
\[C_{t}^{e,z}(\xi)+\tilde{V}_{t+1}(e+E_{t}^{e,z}(\xi),z)\leq C_{t}^{e^{\prime},z }(\xi^{\prime})+\tilde{V}_{t+1}(e^{\prime}+E_{t}^{e^{\prime},z}(\xi^{\prime} ),z)\]4  
For a function \(V\) on \(I\times\mathbb{R}^{d}\to\mathbb{R}\) as in (65) which is convex in the first component on \(I\), we agree to consider its sub-gradient in the first component, only for arguments in \(I\). More precisely, for \((e,z)\in I\times\mathbb{R}^{d}\) we write \(\
abla V(e,z)\) to denote the set of linear functionals \(l:\mathbb{R}\to\mathbb{R}\) satisfying  
\[C_{t}^{e,z}(\xi)+\tilde{V}_{t+1}(e+E_{t}^{e,z}(\xi),z)\leq C_{t}^{e^{\prime},z }(\xi^{\prime})+\tilde{V}_{t+1}(e^{\prime}+E_{t}^{e^{\prime},z}(\xi^{\prime} ),z)\]5  
Now, let us elaborate on the fixed-point property of the virtual resource price in the optimal regime in the spirit of the remark before Section 4. Lemma 2: _Assume that the costs and resource consumption functions are given as in (18). Let \(t\in\{0,\ldots,T-1\}\) and \(\tilde{V}_{t+1}\) be a function which satisfies (65), furthermore, suppose that (21) holds. If for \((e,z)\in\mathbb{R}^{d}\) there exists \(A^{*}\in\mathcal{A}^{e,z}\) satisfying the fixed-point equation_  
\[C_{t}^{e,z}(\xi)+\tilde{V}_{t+1}(e+E_{t}^{e,z}(\xi),z)\leq C_{t}^{e^{\prime},z }(\xi^{\prime})+\tilde{V}_{t+1}(e^{\prime}+E_{t}^{e^{\prime},z}(\xi^{\prime} ),z)\]6  
_then \(\xi^{*}=\mathcal{X}_{t}^{e,z}(A^{*})\) is a minimizer to (11)._  
Proof: By assumption (21) the minimizer \(\xi^{*}=\mathcal{X}_{t}^{e,z}(A^{*})\) to (12) satisfies  
\[C_{t}^{e,z}(\xi)+\tilde{V}_{t+1}(e+E_{t}^{e,z}(\xi),z)\leq C_{t}^{e^{\prime},z }(\xi^{\prime})+\tilde{V}_{t+1}(e^{\prime}+E_{t}^{e^{\prime},z}(\xi^{\prime} ),z)\]7  
for each \(\xi\in\Xi\), which is equivalent to  
\[C_{t}^{e,z}(\xi)+\tilde{V}_{t+1}(e+E_{t}^{e,z}(\xi),z)\leq C_{t}^{e^{\prime},z }(\xi^{\prime})+\tilde{V}_{t+1}(e^{\prime}+E_{t}^{e^{\prime},z}(\xi^{\prime} ),z)\]8  
On the other hand, since \(A^{*}\in\
abla\tilde{V}_{t+1}(e+E_{t}^{e,z}(\xi^{*}),z)\) by assumption (66), we conclude that  
\[C_{t}^{e,z}(\xi)+\tilde{V}_{t+1}(e+E_{t}^{e,z}(\xi),z)\leq C_{t}^{e^{\prime},z }(\xi^{\prime})+\tilde{V}_{t+1}(e^{\prime}+E_{t}^{e^{\prime},z}(\xi^{\prime} ),z)\]9  
By combining (68) and (69)  
\[\frac{\delta}{2}+V_{t}(e,z) \geq C_{t}^{e,z}(\xi)+\tilde{V}_{t+1}(e+E_{t}^{e,z}(\xi),z),\]0  
we obtain the desired assertion  
\[\frac{\delta}{2}+V_{t}(e,z) \geq C_{t}^{e,z}(\xi)+\tilde{V}_{t+1}(e+E_{t}^{e,z}(\xi),z),\]1  
The above lemma suggests determining a minimizer \(\xi^{*}\) to (11) as \(\xi^{*}=\mathcal{X}_{t}^{e,z}(A^{*})\) where \(A^{*}\) is obtained as a solution to the fixed-point relation (66). However, according to the dynamic programing principle, the virtual resource price \(A^{*}\in\mathcal{A}^{e,z}\) shall be determined by the minimization (27) rather than by solving a fixed-point relation. The result below shows that under natural assumptions, (27) in fact implies (66). Lemma 3: _Given costs and resource consumption (18), let \(t\in\{0,\ldots,T-1\}\) and \((e,z)\in I\times\mathbb{R}^{d}\), suppose that (65) holds and assume that (21) holds and (23) is satisfied. If \(A^{*}=A^{e,z}\) fulfills (27), then \(A^{*}\) also fulfills the fixed-point equation (66)._  
Proof: Given \((e,z)\in I\times\mathbb{R}^{d}\), suppose that \(A^{*}=A^{e,z}\in\mathcal{A}^{e,z}\) satisfies (27). Recall that by assumption (23) there exists \(A_{0}\in\mathcal{A}^{e,z}\) there exists a root such that \(E_{t}^{e,z}(\mathcal{X}_{t}^{e,z}(A_{0}))=0\).