Why is it convex optimization problem?

112 Views Asked by At

I've got following function: $(1-\theta)\int_{y<q}|y-q|dF(y)+\theta\int_{y\geq q}|y-q|dF(y)$, where $\theta \in (0,1)$ which I need to minimize over $q$. So, I can calculate the first derivative to find which point could be a minimum. But how can I be sure that this point is indeed minimum, and not maximum? The justification of this provided in the source text is that we handle the convex minimization problem. And here is my question: what is reasoning behind this? Of course, I can do some calculations and proof the inequality from definition of convex function, but I bet that there is some neat way to proof that much faster. Of course, the absolute value under the integral is convex function of q. From what I know the sum of two convex function is also convex and I believe that due to the fact that $\theta \in (0,1)$, this linear combination is also convex. But why both integrals are convex?

Full answer to @copper.hat comment: $\theta$ is fixed, I need to minimize just over $q$. I forgot to mention that F is a distribution function of continuous random variable, so I believe the problem is differantiable.

So to calculate the derivative I write it as follows: $\left(\theta-1\right)\int_{y<q}\left(y-q\right)dF\left(y\right)+\theta\int_{y\geq q}(y-q)dF\left(y\right) $ and then the first derivative is: $\left(1-\theta \right)\int_{y<q}dF\left(y\right)-\theta\int_{y\geq q}dF\left(y\right)= \left(1-\theta \right)F\left(q\right)-\theta\left[1-F\left(q\right)\right]= F\left(q\right)-\theta F\left(q\right)-\theta+\theta F\left(q\right)= F\left(q\right)-\theta$, so the minimum can be in a point $q=F^{-1}(\theta)$

Thanks to @Syuizen, I have a justification based on calculation of second derivative. But to be honest I still hope for some reason that would provide justificatio and avoid calculating the second derivative.

2

There are 2 best solutions below

13
On BEST ANSWER

Not an answer, but too long for a comment \begin{eqnarray} (1-\theta)\int_{y<q}|y-q|dF(y)+\theta\int_{y\geq q}|y-q|dF(y) &=& (1-\theta)\int (q-y)_+ dF(y)+\theta\int (y-q)_+ dF(y) \end{eqnarray} where $x_+ = \max(x,0)$.

The function $q \mapsto (1-\theta)(q-y)_+ +\theta(y-q)_+$ is convex for each $y$, hence the integral over $y$ is as well.

12
On

The second derivative of your function is exactly the density function $F'(x)$, which is non-negative. Hence your function is convex.