1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ (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? $\endgroup$ – Pantelis Sopasakis Dec 9 '15 at 15:41
  • $\begingroup$ 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 ! $\endgroup$ – rezzz Dec 9 '15 at 15:48
  • $\begingroup$ 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? $\endgroup$ – Pantelis Sopasakis Dec 9 '15 at 15:53
2
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ 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? $\endgroup$ – rezzz Dec 9 '15 at 16:30
  • $\begingroup$ @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. $\endgroup$ – Pantelis Sopasakis Dec 9 '15 at 16:37
  • $\begingroup$ @rezi I updated my answer with a note. $\endgroup$ – Pantelis Sopasakis Dec 9 '15 at 16:38
  • $\begingroup$ @ Pantelis thank you so much! if the function is $ \phi (x)=cx-d $ , do you think the proof is still valid or not? $\endgroup$ – rezzz Dec 9 '15 at 16:52
  • $\begingroup$ @ 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. $\endgroup$ – rezzz Dec 9 '15 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.