Demo problem with constraint on standard deviation

In [1] a hypothetical demo problem is shown. I don't think it is a real problem, but rather contrived as an example. Nevertheless, there are things to say about it.

The problem is:

Original Problem
\[\begin{align}\min\>&\sum_i \color{darkred}x_i\\ & \mathbf{sd}(\color{darkred}x) \lt \color{darkblue}\alpha\\ & \color{darkred}x_i \in \{0,1\}\end{align}\]

Notes:

• Here sd is the standard deviation. 
• We assume \(x\) has \(n\) components.
• Of course, \(\lt\) is problematic in optimization. So the equation should become a \(\le\) constraint.
• The standard formula for the standard deviation is: \[ \sqrt{\frac{\sum_i (x_i-\bar{x})^2}{n-1}}\] where \(\bar{x}\) is the average of \(x\).
• This is an easy problem. Just choose \(x_i=0\).
• When we use  \(\max \sum_i x_i\) things are equally simple. In that case choose \(x_i = 1\).
• There is symmetry: \(\mathbf{sd}(x) = \mathbf{sd}(1-x)\).
• A more interesting problem is to have \(\mathbf{sd}(x)\ge\alpha\).

Updated problem

A slightly different problem, and somewhat reformulated is:

MIQCP problem
\[\begin{align}\min\>&\bar{\color{darkred}x} \\ & \bar{\color{darkred}x}= \frac{\sum_i \color{darkred}x_i}{\color{darkblue}n}\\ & \frac{\sum_i (\color{darkred}x_i - \bar{\color{darkred}x})^2}{\color{darkblue}n-1} \ge \color{darkblue}\alpha^2 \\ & \color{darkred}x_i \in \{0,1\}\end{align}\]

First, we replaced \(\lt\) by \(\ge\) to make the problem more interesting. Furthermore I got rid of the square root. This removes a possible problem with being non-differentiable at zero. The remaining problem is a non-convex quadratically constrained (MIQCP=Mixed Integer Quadratically Constrained Problem). The non-convexity implies we want a global solver.

This model solves easily with solvers like Baron or Couenne.

Integer variable

When we look at the problem a bit more, we see we are not really interested in which \(x_i\)'s are zero or one. Rather, we need only to worry about the number. Let \(k = \sum_i x_i\), Obviously \(\bar{x}=k/n\). But more interestingly: \[\mathbf{sd}(x) = \sqrt{\frac{k (1-\bar{x})^2+(n-k)(0-\bar{x})^2}{n-1}}\] The integer variable \(k\) is restricted to \(k=0,2,\dots,n\).

Thus we can write:

MINLP problem
\[\begin{align}\min\>&\color{darkred}k \\  & \frac{\color{darkred}k (1-\color{darkred}k/\color{darkblue}n)^2+(\color{darkblue}n-\color{darkred}k) (\color{darkred}k/\color{darkblue}n)^2}{\color{darkblue}n-1} \ge \color{darkblue}\alpha^2 \\ & \color{darkred}k = 0,1,\dots,\color{darkblue}n \end{align}\]

The constraint can be simplified into \[\frac{k-k^2/n}{n-1}\ge \alpha^2\] This is now so simple we can do this by enumerating \(k=0,\dots,n\), check the constraint, and pick the best.

Because of the form of the standard deviation curve (note the symmetry), we can specialize the enumeration loop and restrict the loop to \(k=1,\dots,\lfloor n/2 \rfloor\). Pick the first \(k\) that does not violate the constraint (and when found exit the loop). For very large \(n\) we can use something like a bisection to speed things up even further.

So this example optimization problem does not really need to use optimization at all.

References

1. Constrained optimisation with function in the constraint and binary variable, https://stackoverflow.com/questions/57850149/constrained-optimisation-with-function-in-the-constraint-and-binary-variable
2. Another problem that minimizes the standard deviation, https://yetanothermathprogrammingconsultant.blogspot.com/2017/09/minimizing-standard-deviation.html