In the paper [Dissimilarity in Graph-Based Semi-Supervised Classification](http://pages.cs.wisc.edu/%7Eswright/papers/dissim_final.pdf), there are few things I could not understand.
Given that $x\_1, x\_2,..., x\_n$ are the vector representation of $n$ items, $f : X \rightarrow \mathbb{R}$ is the discriminant function, and $w\_{ij}$ are all non-negative,


why is $ \frac{1}{2} \sum\_{i, j = 1}^n w\_{ij} (f(x\_i)- f(x\_j))^2$ convex w.r.t to $f$?  

Also, why does changing any $w\_{ij}$ to negative value make it non-convex?


I read on [wikipedia](https://en.wikipedia.org/wiki/Convex_function) that



> 
> "A twice-differentiable function of a single variable is convex if and
> only if its second derivative is nonnegative on its entire domain"
> 
> 
> 


But I don't understand derivative should be take w.r.t to what?



Why is this function convex?
Call the sum $S(f)$. Let $0<b<1$, and let $f$ and $g$ be two functions mapping $X$ to $\Bbb R$. Then
$$
S(bf+(1-b)g)=b^2S(f)+(1-b)^2S(g)+b(1-b)\sum\_{i,j}w\_{i,j} [f(x\_i)-f(x\_j)]\cdot[g(x\_i-g(x\_j)].
$$
By Cauchy-Schwarz,
$$
\sum\_{i,j}w\_{i,j} [f(x\_i)-f(x\_j)]\cdot[g(x\_i-g(x\_j)]\le 2\sqrt{S(f)S(g)}.
$$
(The non-negativity of $w\_{i,j}$ is used here: $w\_{i,j} = \sqrt{w\_{i,j}}\cdot \sqrt{w\_{i,j}}$.)
Therefore
$$
\eqalign{
S(bf+(1-b)g)
&\le b^2S(f)+(1-b)^2S(g)+2b(1-b)\sqrt{S(f)S(g)}\cr
&= \left[b\sqrt{S(f)}+(1-b)\sqrt{S(g)}\right]^2\cr
&\le bS(f)+(1-b)S(g),
}
$$
the final inequality because the square function is convex. This shows that $f\mapsto S(f)$ is convex. (Intuitively, $f\mapsto [f(x\_i)-f(x\_j)]^2$ is convex because the square is convex; and then $S$ is convex becasue it's a positive-linear combination of such functions of $f$.)


