## Wednesday, September 18, 2019

### 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