Showing posts with label convexity. Show all posts
Showing posts with label convexity. Show all posts

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.


Friday, November 22, 2013

Speeding up the solution of quadratic problems

Over and over again  MOSEK users asks one of the following questions:

  • How should I formulate my quadratic optimization problem so it solves faster?
  • Why does MOSEK say my problem is nonconvex and what can I do about it?
The answer to both questions is that the problem should be reformulated so quadratic terms becomes separable i.e. the Hessian of the quadratic terms should be diagonal matrices. This is always possible and will make the convexity check extremely simple and robust. Moreover, in most cases the problem will also solve faster after the reformulation.

Details about the reformulations tricks can be seen in our whitepaper.