Exercises

Each halfspace is convex (verified in Section 3.1). By TIntersection of Convex Sets Is Convex, the intersection of convex sets is convex. $\blacksquare$

$|\theta x + (1-\theta)y| \leq |\theta x| + |(1-\theta)y| = \theta |x| + (1-\theta)|y|$. This is exactly the definition of convexity. $\blacksquare$

$f(\mathbf{x}) = \max_i x_i = \max_i \mathbf{e}_i^T \mathbf{x}$. Each $\mathbf{e}_i^T \mathbf{x}$ is linear, hence convex. The pointwise maximum of convex functions is convex (TOperations That Preserve Convexity, rule 2). $\blacksquare$

Rewrite: $\min\; 3x_1 + 2x_2$ s.t. $-x_1 - x_2 \leq -4$, $-x_1 \leq 0$, $-x_2 \leq 0$.

Dual: $\max\; -4\lambda_1$ s.t. $-\lambda_1 - \lambda_2 + 3 \geq 0$, $-\lambda_1 - \lambda_3 + 2 \geq 0$, $\lambda_i \geq 0$. Simplifying: $\max\; 4\mu$ s.t. $\mu \leq 3$, $\mu \leq 2$, $\mu \geq 0$. Optimal: $\mu^\star = 2$, $d^\star = 8$. (Primal: $x_1 = 0, x_2 = 4$, $p^\star = 8$.) Strong duality holds. $\blacksquare$

Stationarity: $2x - \lambda = 0$. Primal feasibility: $x \geq 1$. Dual feasibility: $\lambda \geq 0$. Complementary slackness: $\lambda(1 - x) = 0$.

The constraint is active at $x = 1$ (since the unconstrained minimum $x = 0$ violates $x \geq 1$). So $x^\star = 1$, $\lambda^\star = 2$. $\blacksquare$

$\nabla f(x_0) = 2(0 - 3) = -6$. $x_1 = x_0 - \alpha \nabla f(x_0) = 0 - 0.5 \cdot (-6) = 3$. In this case, one step reaches the exact minimiser because $f$ is quadratic and $\alpha = 1/L$ where $L = 2$. $\blacksquare$

Let $z_i = e^{x_i}$ and $S = \sum_i z_i$. The gradient is $[\nabla f]_i = z_i / S$. The Hessian is $\nabla^2 f = \frac{1}{S}\text{diag}(\mathbf{z}) - \frac{1}{S^2}\mathbf{z}\mathbf{z}^T$.

For any $\mathbf{v}$: $\mathbf{v}^T \nabla^2 f \, \mathbf{v} = \frac{1}{S}\sum_i z_i v_i^2 - \frac{1}{S^2}\left(\sum_i z_i v_i\right)^2$.

By Cauchy–Schwarz applied to the probability distribution $p_i = z_i/S$: $\left(\sum_i p_i v_i\right)^2 \leq \sum_i p_i v_i^2$. Hence $\mathbf{v}^T \nabla^2 f \, \mathbf{v} \geq 0$. $\blacksquare$

$\mathcal{L}(\mathbf{x}, \boldsymbol{\nu}) = \frac{1}{2}\mathbf{x}^T \mathbf{Q}\mathbf{x} + \mathbf{c}^T \mathbf{x} + \boldsymbol{\nu}^T(\mathbf{A}\mathbf{x} - \mathbf{b})$.

$\nabla_{\mathbf{x}} \mathcal{L} = \mathbf{Q}\mathbf{x} + \mathbf{c} + \mathbf{A}^T \boldsymbol{\nu} = \mathbf{0}$, so $\mathbf{x}^\star = -\mathbf{Q}^{-1}(\mathbf{c} + \mathbf{A}^T \boldsymbol{\nu})$.

Substituting back: $g(\boldsymbol{\nu}) = -\frac{1}{2}(\mathbf{c} + \mathbf{A}^T \boldsymbol{\nu})^T \mathbf{Q}^{-1} (\mathbf{c} + \mathbf{A}^T \boldsymbol{\nu}) - \boldsymbol{\nu}^T \mathbf{b}$.

The dual problem: $\max_{\boldsymbol{\nu}}\; g(\boldsymbol{\nu})$ (unconstrained in $\boldsymbol{\nu}$). This is a concave QP in $\boldsymbol{\nu}$. $\blacksquare$

$3\mu = 3 + (1+2+5) = 11$, $\mu = 11/3 \approx 3.67$. $p_3 = 3.67 - 5 = -1.33 < 0$. Remove channel 3.

$2\mu = 3 + (1+2) = 6$, $\mu = 3$. $p_1 = 3 - 1 = 2$, $p_2 = 3 - 2 = 1$, $p_3 = 0$. All non-negative. $\checkmark$

$R = \log_2(3/1) + \log_2(3/2) + 0 = \log_2 3 + \log_2 1.5 \approx 1.585 + 0.585 = 2.170$ bits/s/Hz. $\blacksquare$

$\nabla f(x) = Lx$, so $x_{k+1} = x_k - \alpha L x_k = (1 - \alpha L) x_k$.

$|x_{k+1}| = |1 - \alpha L| \cdot |x_k|$. For $|x_k| \to \infty$, we need $|1 - \alpha L| > 1$. This holds iff $\alpha L > 2$, i.e., $\alpha > 2/L$. $\blacksquare$

Sorted: $y_{(1)} = 3$, $y_{(2)} = 2$, $y_{(3)} = -1$.

$j=1$: $3 - (3-1)/1 = 3 - 2 = 1 > 0$. $\checkmark$ $j=2$: $2 - (3+2-1)/2 = 2 - 2 = 0$. Not $> 0$. So $\rho = 1$, $\tau = (3-1)/1 = 2$.

$[\Pi(\mathbf{y})]_i = (y_i - 2)^+$: $(3-2, -1-2, 2-2)^+ = (1, 0, 0)$. Check: $1 + 0 + 0 = 1$. $\checkmark$ $\blacksquare$

Let $g(t) = -\log\det(\mathbf{X}_0 + t\mathbf{V}) = -\log\det(\mathbf{X}_0) - \log\det(\mathbf{I} + t\mathbf{X}_0^{-1/2}\mathbf{V}\mathbf{X}_0^{-1/2})$. Let $\lambda_1, \ldots, \lambda_n$ be eigenvalues of $\mathbf{X}_0^{-1/2}\mathbf{V}\mathbf{X}_0^{-1/2}$.

$g(t) = \text{const} - \sum_i \log(1 + t\lambda_i)$. $g''(t) = \sum_i \frac{\lambda_i^2}{(1 + t\lambda_i)^2} \geq 0$. Hence $g$ is convex in $t$, and since this holds for all lines, $f$ is convex. $\blacksquare$

Setting $\nabla f = 0$: the unique critical point is $(x_1, x_2) = (1, 1)$ with $f(1,1) = 0$.

The Hessian at $(1,1)$ is $\nabla^2 f = \begin{pmatrix} 802 & -400 \\ -400 & 200 \end{pmatrix}$. Eigenvalues: $\approx 2.0$ and $\approx 1000$. PSD at $(1,1)$.

But at $(0, 0)$: $\nabla^2 f = \begin{pmatrix} 2 - 400\cdot 0 + 1200\cdot 0 & 0 \\ 0 & 200 \end{pmatrix} = \begin{pmatrix} 2 & 0 \\ 0 & 200 \end{pmatrix}$ which is PSD. However, at general points the Hessian can be indefinite (e.g., near $x_1 \approx 0.5$, the $(1,1)$ entry becomes $2 + 1200(0.25) - 400 = 2 + 300 - 400 = -98 < 0$).

So $f$ is not convex globally, but has a unique global minimum at $(1,1)$. $\blacksquare$

$f(\mathbf{x}) = \mathbf{y}^H \mathbf{y} - 2\text{Re}(\mathbf{y}^H \mathbf{H}\mathbf{x}) + \mathbf{x}^H \mathbf{H}^H \mathbf{H}\mathbf{x} + \sigma^2 \mathbf{x}^H \mathbf{x}$.

$\nabla_{\mathbf{x}} f = -2\mathbf{H}^H \mathbf{y} + 2(\mathbf{H}^H \mathbf{H} + \sigma^2 \mathbf{I})\mathbf{x}$. Setting to zero: $\mathbf{x}^\star = (\mathbf{H}^H \mathbf{H} + \sigma^2 \mathbf{I})^{-1} \mathbf{H}^H \mathbf{y}$.

$\nabla^2 f = 2(\mathbf{H}^H \mathbf{H} + \sigma^2 \mathbf{I}) \succ 0$ for $\sigma^2 > 0$, confirming strict convexity. $\blacksquare$

$R_k$ is concave in $p_k$ alone (for fixed interference), but the $\sum_{j \neq k} p_j g_{jk}$ term in the denominator makes $R_k$ non-concave in the joint variable $(p_1, \ldots, p_K)$. Hence $\sum_k \log R_k$ is non-convex.

Fix the interference: $I_k = \sum_{j \neq k} p_j g_{jk} + \sigma^2$. Then $R_k(p_k) = \log_2(1 + p_k g_{kk}/I_k)$ is concave in $p_k$. Each link solves an independent water-filling problem.

Introducing multiplier $\mu_k$ for each $p_k \leq P_{\max}$ gives $\mu_k = \partial(\log R_k)/\partial p_k$, the marginal utility of power. An iterative algorithm alternates between updating powers (primal) and updating interference levels (akin to dual variables). $\blacksquare$

$\|\mathbf{y} - \mathbf{H}\mathbf{x}\|^2 = \mathbf{y}^T \mathbf{y} - 2\mathbf{y}^T \mathbf{H}\mathbf{x} + \mathbf{x}^T \mathbf{H}^T \mathbf{H}\mathbf{x}$. Since $\|\mathbf{x}\|^2 = n$ is constant for $x_i \in \{-1,+1\}$, minimising is equivalent to maximising $2\mathbf{y}^T \mathbf{H}\mathbf{x} - \mathbf{x}^T \mathbf{H}^T \mathbf{H}\mathbf{x}$. Set $\mathbf{Q} = -\mathbf{H}^T \mathbf{H}$, $\mathbf{q} = 2\mathbf{H}^T \mathbf{y}$.

Lift: $\mathbf{X} = \mathbf{x}\mathbf{x}^T$, so $\mathbf{x}^T \mathbf{Q}\mathbf{x} = \text{tr}(\mathbf{Q}\mathbf{X})$. Relax $\text{rank}(\mathbf{X}) = 1$ to $\mathbf{X} \succeq 0$:

$\max\;\text{tr}(\mathbf{Q}\mathbf{X}) + \mathbf{q}^T \mathbf{x}$ s.t. $X_{ii} = 1$, $\mathbf{X} \succeq 0$, $\begin{pmatrix} \mathbf{X} & \mathbf{x} \\ \mathbf{x}^T & 1 \end{pmatrix} \succeq 0$.

Sample $\tilde{\mathbf{x}} \sim \mathcal{N}(\mathbf{0}, \mathbf{X}^\star)$, then round: $\hat{x}_i = \text{sign}(\tilde{x}_i)$. Repeat multiple times and keep the best. $\blacksquare$

By $L$-smoothness and the update rule: $f(\mathbf{x}_{k+1}) \leq f(\mathbf{x}_k) - \frac{1}{2L}\|\mathbf{x}_k - \mathbf{x}_{k+1}\|^2 \cdot L^2 = f(\mathbf{x}_k) - \frac{L}{2}\|\mathbf{x}_k - \mathbf{x}_{k+1}\|^2$. (This uses the gradient Lipschitz condition applied at the projected point.)

By the projection property and first-order convexity: $\|\mathbf{x}_{k+1} - \mathbf{x}^\star\|^2 \leq \|\mathbf{x}_k - \mathbf{x}^\star\|^2 - \frac{2}{L}(f(\mathbf{x}_k) - f(\mathbf{x}^\star))$. Telescoping over $k$ steps gives the $O(1/k)$ bound. $\blacksquare$

$\mathbf{H}_T \mathbf{H}_T^H \succeq \mathbf{H}_S \mathbf{H}_S^H$ for $S \subseteq T$ (adding PSD terms). Since $\log\det$ is operator monotone on PSD matrices, $C(S) \leq C(T)$.

The marginal gain from adding antenna $m$ to set $S$ is $\Delta C(m \mid S) = \log_2\det(\mathbf{I} + \text{SNR} \cdot \mathbf{H}_{S \cup m} \mathbf{H}_{S \cup m}^H) - \log_2\det(\mathbf{I} + \text{SNR} \cdot \mathbf{H}_S \mathbf{H}_S^H)$.

By the matrix determinant lemma: $\Delta C(m \mid S) = \log_2(1 + \text{SNR} \cdot \mathbf{h}_m^H (\mathbf{I} + \text{SNR} \cdot \mathbf{H}_S \mathbf{H}_S^H)^{-1} \mathbf{h}_m)$.

For $S \subseteq T$: $(\mathbf{I} + \text{SNR} \cdot \mathbf{H}_T \mathbf{H}_T^H)^{-1} \preceq (\mathbf{I} + \text{SNR} \cdot \mathbf{H}_S \mathbf{H}_S^H)^{-1}$, so $\Delta C(m \mid T) \leq \Delta C(m \mid S)$. $\blacksquare$

$\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = \sum_k U_k(x_k) - \sum_\ell \lambda_\ell (\sum_{k : \ell \in \mathcal{L}_k} x_k - c_\ell)$.

$\mathcal{L} = \sum_k [U_k(x_k) - x_k \sum_{\ell \in \mathcal{L}_k} \lambda_\ell] + \sum_\ell \lambda_\ell c_\ell$. For fixed $\boldsymbol{\lambda}$, each flow $k$ independently solves $\max_{x_k \geq 0} U_k(x_k) - x_k q_k$ where $q_k = \sum_{\ell \in \mathcal{L}_k} \lambda_\ell$ is the "path price."

• Source update: $x_k^{(t+1)} = (U_k')^{-1}(q_k^{(t)})$.
• Link update: $\lambda_\ell^{(t+1)} = [\lambda_\ell^{(t)} + \alpha(\sum_k x_k^{(t+1)} - c_\ell)]^+$. This is a dual subgradient ascent. Each source needs only its path price; each link needs only its aggregate load.

$\lambda_\ell$ is the "congestion price" of link $\ell$. TCP Vegas and similar protocols implement this decomposition implicitly: the round-trip time acts as the price signal. $\blacksquare$

Define the potential $\Phi_k = t_k^2(f(\mathbf{x}_k) - f^\star) + \frac{L}{2}\|\mathbf{v}_k - \mathbf{x}^\star\|^2$ where $t_k = (k+1)/2$ and $\mathbf{v}_k = \mathbf{x}_k + t_k(\mathbf{x}_k - \mathbf{x}_{k-1})$.

Using the $L$-smoothness descent lemma and the first-order convexity condition, one shows $\Phi_{k+1} \leq \Phi_k$. Since $\Phi_0 = \frac{L}{2}\|\mathbf{x}_0 - \mathbf{x}^\star\|^2$: $f(\mathbf{x}_k) - f^\star \leq \frac{2L\|\mathbf{x}_0 - \mathbf{x}^\star\|^2}{(k+1)^2}$. $\blacksquare$