Let's solve each part step-by-step, with explanations after each step: --- ### (a) Show that \( f \) is not subdifferentiable at \( x = 0 \). #### **Step 1: Recall the definition of subdifferential** For a convex function \( f \), the subdifferential at \( x_0 \) is the set of all \( g \) such that \[ f(x) \geq f(x_0) + g(x - x_0) \quad \forall x. \] We need to check if such a \( g \) exists at \( x_0 = 0 \). **Explanation:** The subdifferential generalizes the derivative for convex (possibly non-differentiable) functions. If the subdifferential is empty, the function is not subdifferentiable at that point. --- #### **Step 2: Analyze the function at \( x = 0 \)** Given: \[ f(x) = \begin{cases} -\sqrt{x}, & x \geq 0 \\ \infty, & x < 0 \end{cases} \] At \( x = 0 \), \( f(0) = 0 \). For \( x < 0 \), \( f(x) = \infty \), so the subgradient inequality holds trivially. For \( x \geq 0 \), \[ -\sqrt{x} \geq 0 + g(x - 0) \implies g \leq -\frac{\sqrt{x}}{x} \quad \text{for } x > 0. \] **Explanation:** We only need to check \( x \geq 0 \) since for \( x < 0 \), the function is infinite so the inequality always holds. --- #### **Step 3: Compute the limiting value as \( x \to 0^+ \)** \[ \lim_{x \to 0^+} -\frac{\sqrt{x}}{x} = -\infty \] So, for any finite \( g \), there is always some \( x \) close enough to 0 such that \( g > -\frac{\sqrt{x}}{x} \), violating the inequality. **Explanation:** Since the required \( g \) would have to be less than \(-\infty\), *no real number* can satisfy the subgradient inequality at \( x=0 \). Thus, the subdifferential is empty. --- **Final Answer for (a):** **\( f \) is not subdifferentiable at \( x = 0 \) because the subdifferential set is empty there.** --- ### (b) Derive the subdifferential set \( \partial g(x) \). #### **Step 1: Write \( g(x) \) explicitly** \[ g(x) = \frac{1}{2} \|x - y\|_2^2 + \|Ax + b\|_2 \] **Explanation:** This function is the sum of a smooth quadratic and a non-smooth (but convex) norm function. --- #### **Step 2: Compute subdifferential of each term** - The gradient of \( \frac{1}{2} \|x - y\|_2^2 \) is \( x - y \). - The subdifferential of \( \|Ax + b\|_2 \) is \( A^T \partial \|z\|_2 \) at \( z = Ax + b \). Recall: \[ \partial \|z\|_2 = \begin{cases} \left\{ \frac{z}{\|z\|_2} \right\}, & z \neq 0 \\ \{v : \|v\|_2 \leq 1\}, & z = 0 \end{cases} \] **Explanation:** The subdifferential of a norm at 0 is the unit ball, otherwise it's the normalized vector. --- #### **Step 3: Combine the results** \[ \partial g(x) = (x - y) + A^T \cdot S \] where \[ S = \begin{cases} \left\{ \frac{Ax + b}{\|Ax + b\|_2} \right\}, & Ax + b \neq 0 \\ \{v : \|v\|_2 \leq 1\}, & Ax + b = 0 \end{cases} \] **Explanation:** The subdifferential of the sum is the sum of subdifferentials because the first term is differentiable. --- **Final Answer for (b):** \[ \boxed{ \partial g(x) = (x - y) + A^T \cdot S } \] where \( S = \left\{ \frac{Ax + b}{\|Ax + b\|_2} \right\} \) if \( Ax + b \neq 0 \), and \( S = \{v : \|v\|_2 \leq 1\} \) if \( Ax + b = 0 \). --- ### (c) Suppose \( A = I \), \( b = 0 \). Find the global minimizer \( x^* \) of \( g(x) \). #### **Step 1: Write the simplified function** With \( A = I \), \( b = 0 \): \[ g(x) = \frac{1}{2} \|x - y\|_2^2 + \|x\|_2 \] **Explanation:** This is a standard quadratic plus norm regularization (L2). --- #### **Step 2: Write optimality condition** Set \( 0 \in \partial g(x) \): \[ 0 \in (x - y) + \partial \|x\|_2 \] - If \( x \neq 0 \): \( \partial \|x\|_2 = \left\{ \frac{x}{\|x\|_2} \right\} \) - So, \[ 0 = x - y + \frac{x}{\|x\|_2} \] \[ x - y = -\frac{x}{\|x\|_2} \] \[ x + \frac{x}{\|x\|_2} = y \] \[ x \left(1 + \frac{1}{\|x\|_2}\right) = y \] Let \( x = \alpha y \), with \( \alpha \geq 0 \): \[ \alpha y \left(1 + \frac{1}{|\alpha| \|y\|_2}\right) = y \] If \( y \neq 0 \), \( y \) cancels: \[ \alpha \left(1 + \frac{1}{|\alpha| \|y\|_2}\right) = 1 \] Assume \( \alpha > 0 \), so \( |\alpha| = \alpha \): \[ \alpha + \frac{1}{\|y\|_2} = 1 \implies \alpha = 1 - \frac{1}{\|y\|_2} \] Now \( \alpha > 0 \implies \|y\|_2 > 1 \). **Explanation:** We used the fact that the optimal \( x \) is colinear with \( y \) due to the symmetry of the problem. --- #### **Step 3: Handle the case \( x^* = 0 \)** If \( x = 0 \), the optimality condition requires: \[ 0 \in -y + \{v: \|v\|_2 \leq 1\} \implies \|y\|_2 \leq 1 \] So if \( \|y\|_2 \leq 1 \), the minimizer is \( x^* = 0 \). **Explanation:** For small enough \( y \), the minimum is at the origin. --- **Final Answer for (c):** \[ x^* = \begin{cases} 0, & \text{if } \|y\|_2 \leq 1 \\ \left(1 - \frac{1}{\|y\|_2}\right) y, & \text{if } \|y\|_2 > 1 \end{cases} \] This is the **proximal operator of the \( \ell_2 \) norm** at \( y \) with parameter 1. --- Let me know if you'd like further clarification or LaTeX formatting!