Solving equation that involves the sum of linear terms and the $L_2$ norm $\require{begingroup}\begingroup
\DeclareMathOperator{\sign}{sign}$
I'm trying to solve the following optimization problem:
$$
    \min_{x \in \mathbb{R}^n} \frac{1}{2} x^{\mathrm{T}} A x + b^{\mathrm{T}}x + \lVert Cx + d \rVert_2
$$
where $b \in \mathbb{R}^n$, $d \in \mathbb{R}^m$, $A \in \mathbb{R}^{n \times n}$, $C \in \mathbb{R}^{m \times n}$.
By applying the first order optimality conditions, I obtain that if $\lVert Cx + d \rVert > 0$, then
$$
Ax + b + C^\mathrm{T} \frac{Cx + d}{\lVert Cx + d \rVert_2} = 0
$$
Otherwise, for the case of $\lVert Cx + d \rVert_2 = 0$, by taking the subgradient I obtain
$$
  Ax + b + C^\mathrm{T} g = 0
$$
where $g$ is any vector such that $\lVert g \rVert_2 \leq 1$.
I'm not sure how I should approach solving this problem. In the case where $n=m=1$, assuming that $\lvert Cx + d \rvert > 0$, then
$$
\frac{Cx + d}{ \lVert Cx + d \rVert_2 } = \frac{Cx + d}{ \lvert Cx + d \rvert } = \sign(Cx + d)
$$
Hence,
$$
x = \begin{cases}
    -\frac{b + C}{A} & Cx + d > 0 \\
    -\frac{b - C}{A} & Cx + d < 0 \\
\end{cases}
$$
and this solution is applicable for $C(-\frac{b+C}{A}) + d > 0$ or $C(-\frac{b-C}{A}) + d < 0$. Otherwise, we apply $Cx + d = 0$ to obtain that $x = -\frac{d}{C}$.
However, I'm not sure how to solve this for the case of $m, n > 1$.
$\endgroup$
 A: Your minimization problem is best handled in another set of coordinates.  Done right, one can avoid the square roots from the norm term.
Firstly, your work appears to tacitly assume that $A^{\mathsf{T}}=A$.  I will assume $A$ is symmetric going forward, just for simplicity of notation.  If not, then note that since the transpose is the identity on scalars, when we take the transpose of $x^{\mathsf{T}}Ax$, we obtain $$x^{\mathsf{T}}Ax=x^{\mathsf{T}}A^{\mathsf{T}}x$$  Adding $x^{\mathsf{T}}Ax$ to both sides and dividing by $2$ shows that $$x^{\mathsf{T}}Ax=x^{\mathsf{T}}\left(\frac{A+A^{\mathsf{T}}}{2}\right)x$$  Thus we can replace $A$ by its symmetric part.
Suppose $C$ is invertible.  Let $y=Cx+d$, so that $x=C^{-1}y-C^{-1}d$ and let $P=(C^{-1})^{\mathsf{T}}AC^{-1}$.  Note that $P$ is symmetric.  You seek to minimize the expression $$f(y)=\frac{1}{2}y^{\mathsf{T}}Py-\frac{1}{2}y^{\mathsf{T}}Pd-\frac{1}{2}d^{\mathsf{T}}Py+b^{\mathsf{T}}y+\|y\|_2$$ in $y$, where I have dropped the constant terms $\frac{1}{2}d^{\mathsf{T}}Pd$ and $-b^{\mathsf{T}}C^{-1}d$.  Rearranging a little, $$f(y)=\frac{1}{2}y^{\mathsf{T}}Py+\left(b^{\mathsf{T}}-d^{\mathsf{T}}P\right)y+\|y\|_2$$  To avoid writing that monstrosity inside the parentheses, I call it $\phi^{\mathsf{T}}=b^{\mathsf{T}}-d^{\mathsf{T}}P$.
Write $y=au$, where $u$ is a unit vector.  We can now describe our problem as constrained minimization: we want to minimize $$f(au)=\frac{1}{2}a^2u^{\mathsf{T}}Pu+a\phi^{\mathsf{T}}u+a$$  subject to the constraint that $1=u^{\mathsf{T}}u$.
Applying Lagrange multipliers, an extremum occurs when:
\begin{gather*}
au^{\mathsf{T}}Pu+\phi^{\mathsf{T}}u+1=0\quad\quad(\partial_a) \\
a^2(Pu)^{\mathsf{T}}+a\phi^{\mathsf{T}}=2\lambda u^{\mathsf{T}}\quad\quad(\nabla_u) \\
1=u^{\mathsf{T}}u\quad\quad(\text{constraint})
\end{gather*}  Suppose we examine ($\nabla_u$) in the $u$ direction: then $$2\lambda=2\lambda u^{\mathsf{T}}u=a^2u^{\mathsf{T}}Pu+a\phi^{\mathsf{T}}u=-a$$ where the first equality comes from substituting (constraint) and the last from substituting ($\partial_a$).
Eliminating $\lambda$ and canceling a common factor of $a$, we now find $$aPu+\phi=-u$$  This is an eigenvalue problem, which I leave to you.
If $C$ is not invertible, then we can use the same tricks as above, but the algebra is more complicated.  I will only sketch these cases.  We can't say that $x=C^{-1}y-C^{-1}d$, but we can say that there is some linear transformation $T$ and (nonlinear!) function $v$ such that $x=Ty-Td+v(y)$  and $v(y)\in\ker{(C)}$ for all $y\in d+\text{im}{(C)}$.  (This follows from the first isomorphism theorem of vector spaces, or, more prosaically, the definitions of image and kernel plus some algebra.)
To describe how to handle this, I would recommend changing basis to write $C$ as a block matrix: either $C=\begin{bmatrix}I_n&0\end{bmatrix}$ or $C=\left[\begin{smallmatrix}I_n\\0\end{smallmatrix}\right]$.  (Note that this will change your values of $A$ and $b$.)
In the former case, where $C$ is surjective, we can choose a pseudoinverse to make $v$ linear.  Consider $x$ as two separate vectors $(au-d,z)$ adjoined.  Then $Cx+d=au$, and so your problem is to minimize $a+(\text{a polynomial in $a$, $u$, and $z$})$ subject to $1=u^{\mathsf{T}}u$.
In the latter case, $C$ is only injective.  This is the hardest scenario.  We can write $Cx+d$ as two vectors adjoined, but this does not help us make progress on eliminating the square roots.  Instead, I would interpret your optimization problem as a highly-constrained one.  To wit, let $\pi_1=\begin{bmatrix}I_n&0\end{bmatrix}$ be the projection $\mathbb{R}^m\to\mathbb{R}^n$ and $\pi_2$ the complementary projection, so that $\pi_1C=I_n$ and $\pi_2C=0$.  Then you want to minimize $$a^2u^{\mathsf{T}}\pi_1^{\mathsf{T}}A\pi_1u+ab^{\mathsf{T}}\pi_1u+a$$ subject to the constraints $a\pi_2u=\pi_2d$ and $1=u^{\mathsf{T}}u$.  (Note that this requires $m-n+1$ many Lagrange multipliers!)
