Wednesday, March 14, 2018

Harmonic mean, p-norms and extremely disciplined conic modeling

Contrary to what we inadverently claim in our modeling cookbook, there IS a conic quadratic model of the harmonic mean. More precisely, we can model the constraint
$$0\leq t\leq \frac{n}{\frac{1}{x_1}+\cdots+\frac{1}{x_n}},\quad x_i>0$$
Here is the model, which at the same time demonstrates the non-obvious fact that the right-hand side of (1) is actually concave. We call this approach extremely disciplined modelling, since by definition it prevents users from creating a non-convex model. We first notice that (1) is equivalent to
$$\sum_{i=1}^n\frac{t^2}{x_i}\leq nt$$
which can be written using rotated quadratic cones $2uv\geq w^2$, $u,v\geq 0$, as follows:
$$
\begin{eqnarray}
t^2\leq 2x_iy_i, &\quad i=1,\ldots,n \\
2\sum_i y_i = nt. &
\end{eqnarray}
$$
For the special case $n=2$ we can model $t\leq \frac{2xy}{x+y}$ with just one rotated cone: this inequality is equivalent to $2(x-\frac12 t)(y-\frac12 t)\geq (\frac12t)^2$.

The same way we can model (and prove concativity of) a general "negative $p$-norm":
$$ 0\leq t\leq (\sum_i x_i^{-p})^{-1/p} $$
where $p>0$, $x_i>0$ and the harmonic mean corresponds to $p=1$ (up to a factor $n$). The equivalent version is
$$ \sum_{i=1}^n\frac{t^{p+1}}{x_i^p}\leq t$$
which leads to
$$
\begin{eqnarray}
|t|\leq x_i^{\frac{p}{p+1}} y_i^{\frac{1}{p+1}}, &\quad i=1,\ldots,n \\
\sum_i y_i = t. &
\end{eqnarray}
$$
Constraint (7) defines the three-dimensional power cone with exponents $(\frac{p}{p+1},\frac{1}{p+1})$. Conic models with the power cone will be expressible in Mosek 9, see https://themosekblog.blogspot.dk/2018/01/version-9-roadmap_31.html.