1
$\begingroup$

I am interested in maximizing the variance of a random variable $X$ supported on $[0,1]$. Formally,

$$\max_{P_X: X \in [0,1]} {\rm Var}(X),$$

where $P_X$ is a distribution of $X$. This question is well-studied on this forum. For example, see this question. The solution to this question is given by $P_X(0) = P_X(1) = \frac 12$.

My question is about a specific approach to solving this. Concretely, I am interested in applying the convex optimization method to this problem.

Here is the outline of the proof/method:

  1. Note that space of distribution over $[0,1]$ $$\mathcal{P} = \left\{ P_X : X \in [0,1] \right\}$$ is convex and compact in weak-topology.

  2. $P_X \to {\rm Var}(X)$ is concave.

  3. Combining 1) and 2) we conclude that this is a well-defined convex optimization problem.

  4. Find the KKT conditions by using the directional derivative. These are given by the following: $P_X$ is an optimizer if and only if

\begin{align} &(x-E_{P_X}[X])^2 < {\rm Var}_{P_X}(X), x\in [0,1] \setminus {\rm supp}(P_X)\\ &(x-E_{P_X}[X])^2 = {\rm Var}_{P_X}(X), x \in {\rm supp}(P_X)\\ \end{align}

My question: How to solve the above equations and produce an optimal $P_X$?

Of course, at this point, we can just plug-in our distribution and check it. However, this would be cheating. I would like to solve for the optimal distribution starting with the above equations with no extra help. For example, at this point, we don't even know that the distribution is discrete.

Why is this interesting: Since variance is one of the simplest concave operators over the space of distributions, solving it via convex optimization method serves as an interesting example.

Improve this question
$\endgroup$
6
  • $\begingroup$ @RodrigodeAzevedo It's in a bullet point 1). I will clarify this. $\endgroup$
    – Boby
    Commented Jul 19, 2020 at 11:24
  • $\begingroup$ I think that duality may help here. The (pre-)dual should be a convex minimization problem on the space of continuous functions. But I didn't think any further than that... On a second thought: I think that optimality conditions should say a bit more, namely that you have equality only on the support (i.e. the inequality is strict outside the support). $\endgroup$
    – Dirk
    Commented Jul 19, 2020 at 12:34
  • $\begingroup$ @Dirk Yes, there should be an inequality outside of support. I will correct it. I would be very interested in looking at a dual approach, so if you have time please add some details or thoughts on how in. $\endgroup$
    – Boby
    Commented Jul 19, 2020 at 13:13
  • $\begingroup$ The second KKT condition implies that there exists a nontrivial quadratic function $q$ such that $q(X) = 0$ almost surely. Therefore $P_X$ is supported on at most 2 points, and by the first equation these must be 0 and 1. The second equation then yields that indeed he made must be balanced. Or are you looking for something less hands on than this? $\endgroup$
    – Alf
    Commented Jul 19, 2020 at 19:59
  • $\begingroup$ @J. Thanks. This is nice. Also, yes, less hands-on would be good. I want to use this optimization problem as an introductory example to convex optimization over p.d. spaces. Therefore, it would be good to use things that are less hands-on and easily generalize. $\endgroup$
    – Boby
    Commented Jul 19, 2020 at 20:21

0

Reset to default

You must log in to answer this question.