How is the expression for the optimal entanglement witness derived?

The idea behind this expression is indeed a fairly general one.

$newcommand{bs}[1]{boldsymbol{#1}}newcommand{calS}{mathcal{S}}$An entanglement witness $mathcal W$ is defined as an operator such that $operatorname{Tr}(mathcal Wrho)ge0$ for all separable $rhoinmathcal S$, while for some entangled $rho_{ent}$ we have $operatorname{Tr}(mathcal Wrho_{ent})<0$.

Geometrically, this definition is very easily understood as saying that $mathcal W$ defines a hyperplane in the space of states that separates the separable states from the non-separable ones. Because of the convexity of the space of separable states, any non-separable state can be separated by such an operator (see e.g. (Horodecki 2007) or (Gühne 2008)).

Now forget for a second about states and quantum mechanics. Let $calS$ denote a convex subset of $mathbb R^n$ for some $n$, let $ vnotin calS$, and let $ v_0incalS$ be the vector in $calS$ that is the closest to $ v$ (in standard euclidean distance). This means that the line (or more generally hyperplane) that is orthogonal to $ v- v_0$ and touches $ v_0$ is tangent to $calS$ at $ v_0$. Such a "line" is an "optimal" linear separation between $calS$ and $ v$:

We now simply need to define an operator that tells us on which side of such separation we are in. A natural candidate would be an operator which projects a candidate vector $ w$ on the line $ v- v_0$, or, more precisely, an operator $A$ defined via

$$A wequivlangle v- v_0, w- v_0rangle.$$

Clearly, we then have $A v>0$, and $A v_0=0$, while all vectors in $calS$ (together with the points on the $calS$ side of the separation) correspond to $Aw<0$.

To obtain the given expression for the witness you now simply change the sign (because we conventionally define witnesses to be positive on the separable).

In conclusion, you have $A_{opt} w=langle v- v_0, v_0- wrangle$, that corresponds to $$A_{opt}=( v_0^*-v^*)-langle v_0, v_0-vrangle I.$$ where $v^*$ denotes the linear functional $v^*(w)equiv langle v,wrangle$ (or, if you prefer, the bra $langle vrvert$).

To get to the expression given in the paper you now just add a normalisation factor, which I guess was added to make something simpler later on in the paper.