Proof of convexity of in a quadratic function

264 Views Asked by At

Let $ X= \{(x_1,d_1),(x_2,d_2),...,(x_n,d_n)\}$ where $x_i$ for $i=1,...,n$ are variable and $d_i$ for $i=1,...,n$ have constant values, then we define:

$$ F(X) = \min\sum_{i=1}^{n} \left(\frac{x_i}{d_i}-\frac{\sum_{j=1}^{n}x_j} {\sum_{j=1}^{n}d_j} \right)^2$$

I need to prove the convexity of $F$. My argument is that $\left(\frac{ x_i} {d_i}-\frac{\sum_{j=1}^{n}x_j}{\sum_{j=1}^{n}d_j}\right)$ is affine in $x_i$ and the square of an affine function is convex, thus a sum of convex function is convex, but I do not know how I prove that. Do you have any idea how I prove $F$ is convex?

1

There are 1 best solutions below

1
On

Let $g_i(x) := (a_i^T x)^2$, where $$ a_i = ( -1/d, -1/d, ..., 1/d_i - 1/d, -1/d, ..., -1/d), \;\; d := \sum_{j=1}^{n} d_j \:. $$ Here, the $1/d_i-1/d$ occurs at the $i$-th coordinate. We can now show the function $g(x) := \sum_{i=1}^{n} g_i(x)$ is convex, which is what I think you want to show. It suffices, as you mention, to show that each $g_i(x)$ is convex, since the sum of convex functions is itself convex. But $g_i(x) = x^T a_ia_i^T x$, so immediately $\nabla^2 g_i(x) = a_ia_i^T \succeq 0$.