Convexity of the variance of a mixture distribution

Operations Research Asked by independentvariable on September 25, 2020

$$X$$ is a random variable that is sampled from the mixture of uniform distributions. In other words:
$$X sim sum_{i=1}^N w_i cdot mathbb{U}(x_i, x_{i+1}),$$
where $$mathbb{U}(x_i, x_{i+1})$$ denotes a random variable that follows a uniform distribution in $$[x_i, x_{i+1}]$$.
For feasibility, we need $$w geq 0, sum_{i=1}^N w_i = 1$$.

In an optimization problem my variables are $$w_i$$ for $$i=1,ldots,N$$, and I would like to upper bound the variance of $$X$$. According to Wikipedia, the variance of $$X$$ is:
$$mathrm{Var}(X) = sum_{i=1}^N w_i(sigma_i^2+ mu_i^2 – mu^2)$$
where $$sigma_i^2$$ and $$mu_i$$ are the variance and mean of $$mathbb{U}(x_i, x_{i+1})$$, respectively (which are parameters), and $$mu$$ is the mean of the mixture, which is $$mu = sum_{i=1}^N w_i frac{x_i + x_{i+1}}{2}.$$

Thus, if my derivation is not wrong:
$$mathrm{Var}(X) = sum_{i=1}^N w_ileft(sigma_i^2+ mu_i^2 – left(sum_{j=1}^N w_j frac{x_j + x_{j+1}}{2}right)^2right)$$
which is very ugly and appears to be non-convex to upper bound this function (edit: I want to constrain $$mathrm{Var}(X) leq mathrm{constant}$$).

My question is, is there any trick, or any other convex approximation of such a variance, such that I can include an upper bound on the variance constraint?

In order to find the best upper bound for variance, for given input values of $$u_i$$ and $$sigma_i^2$$, you should globally maximize variance with respect to the $$w_i$$, subject to the constraints $$w_i ge 0, Sigma w_i = 1$$.

This can be formulated as a convex QP (Quadratic Programming problem), i.e., maximizing a concave quadratic subject to linear constraints. Hence it is easy to solve, unless $$n$$ is gigantic, which hardly seems likely for any reasonable mixture distribution. I leave to the OP as an exercise, whether the KKT conditions can yield a closed form solution.

The convex QP takes the form:

maximize $$(Sigma_{i=1}^n w_i (sigma_i^2 +mu_i^2)) - mu^2$$ with respect to $$mu, w_i$$

subject to $$Sigma_{i=1}^n w_i mu_i = mu, w_i ge 0 forall i, Sigma_{i=1}^n w_i = 1$$.

If all $$u_i$$ are equal to each other, this would be a Linear Programming problem with compact constraints. Therefore the optimum would be at a vertex of the constraints, and in this case, that vertex would be $$w_i = 1$$ for the $$i$$ corresponding to the largest $$sigma_i^2$$, and all other $$w_i = 0$$.

Edit: In response to edit to question: "I want to constrain Var(X) $$le$$ constant)"

If the naive approach of adding the constraint Var(X) $$le$$ constant to my above convex QP formulation were performed, that would add a non-convex quadratic constraint, making the problem a non-convex Quadratically-Constrained Quadratic Program (QCQP), which requires a global optimizer, such as Gurobi 9.x or BARON to solve to global optimality.

However, there is an easier, faster method: Solve the (pre-Edit) convex QP formulation. Then maximum variance, accounting for the constraint Var(X) $$le$$ constant), equals

min(optimal objective value of convex QP formulation,constant).

Correct answer by Mark L. Stone on September 25, 2020

Related Questions

What is a general procedure to prove that the LP relaxation of an IP delivers the optimal IP solution?

2  Asked on August 19, 2021 by k88074

CPLEX MIP warm start seems slow down the program?

1  Asked on August 19, 2021 by mengfan-ma

(Iterative?) Solutions to a certain quadratic program with non-convex constraints

2  Asked on August 19, 2021 by cfp

Problem with implementing squared terms in the objective function

1  Asked on August 19, 2021 by poofybridge

Two M/M/1 queues working independently

0  Asked on August 19, 2021 by cookiemonster

Scheduling with setup cost

0  Asked on August 19, 2021 by dirk-nachbar

Is a convex or MILP (without big-M) formulation possible for this problem

1  Asked on August 19, 2021 by batwing

MINLP Solution same as Global Optimum?

2  Asked on August 19, 2021 by clement

Linear objective function with non-linear constraints

2  Asked on August 19, 2021 by fightmilk

Meta papers on operations research

2  Asked on August 19, 2021 by luke599999

Verifying the correctness of KKT conditions

0  Asked on August 19, 2021 by s_scouse

How can I use warm start in C#

1  Asked on August 19, 2021 by fhm-ider

Feasible sets represented as point clouds

1  Asked on August 19, 2021 by harry-cohen

Is this the same as Agent Based DES or something different?

0  Asked on August 19, 2021 by brendan-hill

Column generation when intractable variables appear in the objective function

1  Asked on August 19, 2021 by mostafa

Is there any OR way to solve this problem?

3  Asked on August 19, 2021 by samiczy

Find a particular optimal solution

1  Asked on August 19, 2021 by ljg

How to find all vertices of a polyhedron

3  Asked on August 19, 2021

Can every convex problem use Lagrangian dual method?

0  Asked on August 19, 2021

Does strong duality hold when I dualize only a subset of the constraints?

1  Asked on August 19, 2021 by george-chang