# Proof of convexity in a quadratic function

I have the following quadratic objective function (almost variance function); where $f_n, i=1,...,n$ are $n$ function and $\overline f$ is the mean of $f_n$ for all $i=1,...,n$

$$\min \sum(f_i(x_i)- \overline f(x))^2$$

At first I thought it is not a convex objective. So, the hessian matrixes are calculated for some examples and the results show that the determinant of the matrices are zero; however, the eigenvalues are nonnegative (i.e $\ge 0$). I realized the function is semidefinite. Now, I think it may be a convex function but I don't know how I can proof the convexity.

• (i) with respect to what is the minimisation carried out? is it wrt $x_i$? (ii) you mentioned that $\bar{f}$ is the expectation of $f_n$; shouldn't it be $\bar{f}_n$? (iii) expectation with respect to what? What exactly is random here? (iv) if randomness is involved, aren't $f_i(x_i)$ random variables? and, if so, shouldn't there is an expectation operator (or other operator, e.g., a risk measure) in your cost function? – Pantelis Sopasakis Dec 9 '15 at 15:41
• Thank you PantelisSopasakis for your reply! $x_i$ are decision variables that they are not random. The model is a deterministic model not stochastic one. $\overline f_n(x_i)$ is correct your right ! – rezzz Dec 9 '15 at 15:48
• Do you then mean that for $x=(x_1,\ldots, x_n)$, it is $\bar{f}(x)=\frac{1}{n}\sum_{i=1}^n f_i(x)$? In any case, could you please update your question to make it more clear? – Pantelis Sopasakis Dec 9 '15 at 15:53

## 1 Answer

It seems to me that your problem is not convex unless you assume something about your functions $f_i$ (given that the minimisation is with respect to $x_i$). If, however, $f_i$ are linear functions, i.e.,

$$f_i(x_i) = c_i'x_i + d_i,$$

then,

$$\bar{f}(x) = \frac{1}{n}\sum_{i=1}^{n}c_i x_i + d_i$$

and the cost function becomes the square of a linear function

$$\sum_{i=1}^n \left(c_i x_i + d_i - \frac{1}{n}\sum_{j=1}^{n}c_j x_j + d_j \right)^2,$$

which is convex.

However, in general, this cost function may not be convex. Take for example $f_i(x_i) = \sin(x_i)$.

There is a little trick one may consider using here. If $f_i$ are invertible and $f_i^{-1}$ is known or can be computed, then we can replace $f_i(x_i)$ with $y_i$ and then the problem becomes:

$$\min_{y_1,\ldots, y_n} \sum_{i=1}^{n}(y_i - \frac{1}{n}\sum_{j=1}^{n}y_j)^2,$$

Then, once we have determined the optimisers $y_i^\star$, we can retrieve $x_i^\star=f_i^{-1}(y_i^\star)$.

Note. The square of a linear function $\phi(x) = cx + d$, where $c$ is a column vector and $x\in\mathbb{R}^n$, that is the function $\psi(x) = \phi(x)^2 = (cx + d)^2$, is covex. Indeed,

$$\psi(x) = (cx+d)^2 = (cx)^2 + 2cx + d^2 = x'(c'c) x + 2cx + d^2,$$

And notice here that $cc'\in\mathbb{R}^{n\times n}$ is a symmetric positive semidefinite matrix, therefore, $\psi$ is convex.

• Actually $f_i(x_i)= x_i$ in the simple version of my problem. How can I proof the square of a linear function is convex? Is there any theorem to proof that? – rezzz Dec 9 '15 at 16:30
• @rezi There you go then... by the way, these problems are called least squares problems and there are very efficient numerical methods to solve them. They are convex problems. A comprehensive presentation is provided here and you can also take a look a the corresponding Wikipedia entry. – Pantelis Sopasakis Dec 9 '15 at 16:37
• @rezi I updated my answer with a note. – Pantelis Sopasakis Dec 9 '15 at 16:38
• @ Pantelis thank you so much! if the function is $\phi (x)=cx-d$ , do you think the proof is still valid or not? – rezzz Dec 9 '15 at 16:52
• @ Pantelis sorry if my question was basic! I know the sum of square function is semi definite but there is another part $2cx$ , that I am not sure does not have any effect in convexity. – rezzz Dec 9 '15 at 17:03