In 2018, we challenged our community to find convex functions that could not be reformulated in terms of the cones supported in MOSEK. A long-standing contender for this challenge was
\frac{1}{x^4 + x^2}\quad \text{ for } x \geq 0, \label{eq:challenge}
but as of today, we are finally able to present a conic reformulation of this function guided by past experiences. In this blogpost we take a look at the insights that enabled this.
Before diving into the details, however, we would like to clarify that conic optimization is able to encompass any convex function, including \eqref{eq:challenge}, via perspective reformulation. The problem, however, is that the resulting cones have widely different computational properties (some even being NP-hard to optimize over!). Restricting attention to the set of cones supported in MOSEK, we effectively limiting ourselves to representations with practical large-scale performance. As suggested by the community challenge, however, it turns out to be quite hard to find convex functions without a computationally efficient conic representation.
So what makes \eqref{eq:challenge} so difficult?
Insight 1: Polynomial denominators
For a polynomial g(x) with real roots g_1 \leq \ldots \leq g_k, we can represent
t \geq \frac{1}{g(x)} = \frac{1}{\alpha(x - g_1)\cdots(x - g_k)}
on a convex subinterval, [g_p, g_{p+1}], via a single power cone
t \alpha (x - g_1)\cdots(x - g_p)(g_{p+1} - x)\cdots(g_k - x) \geq 1,
by flipping signs of the factors, (x - g_i), so that they are all nonnegative on the subinterval of interest. This method can also represent the left and right tail, [-\infty, g_1] and [g_k, \infty], if convex. The issue with g(x) = x^4 + x^2 is that it has a complex conjugate root pair, \pm i, and so the closest we can get in this direction is
t x^2 (x^2 + 1) \geq 1. \label{eq:step1}
Insight 2: Nonlinear substitution
A natural first attempt would be to substitute out the convex term, x^2 + 1, from \eqref{eq:step1} using
t x^2 r \geq 1,\quad r \geq x^2 + 1,
but this fails since r \rightarrow \infty satisfy both constraints without enforcing the desired relation. We thus resort to a lesser known trick, namely to rewrite x^2 + 1 = f(f^{-1}(x^2 + 1)) and then substitute out f^{-1}(x^2 + 1). With this in mind, it would be natural to try
t x^2 r^p \geq 1,\quad r \leq (x^2 + 1)^{1/p},
for some suitable power p, but this fails because (x^2 + 1)^{1/p} is not concave on all of x > 0 for any p \geq 1. Nevertheless, with a bit of persistence, we finally manage to satisfy all composition rules with
t x r^4 \geq 1,\quad r \leq (x^3 + x)^{1/4}, \label{eq:step2}
where the latter is a convex set in need of a conic reformulation.
Insight 3: Signed sum-of-quartics decomposition
The signed sum-of-squares decomposition was introduced in a previous talk on our MOSEK channel, as a new reformulation tool with great applicability. In case of (x^3 + x)^{1/4}, the fourth root suggests need of a signed sum-of-quartics instead. We do not know of any algorithm to perform this decomposition, but using the method of undetermined coefficients (guessing the final form, and mapping coefficients via quantifier elimination), we obtain
x^3 + x = (ax + a)^4 - (ax - a)^4,
where a = \frac{1}{2^{3/4}}. This allows us to rewrite \eqref{eq:step2} as
t x r^4 \geq 1,\quad r^4 + (ax - a)^4 \leq (ax + a)^4, \label{eq:step3}
where the former is a power cone and the latter is the p-norm cone of order 4, which is a well-known conic representable set (we refer to the MOSEK Cookbook).
This concludes our reformulation from the convex function \eqref{eq:challenge} to the conic representation \eqref{eq:step3}. In time, we shall see if this process extends to a wider range of polynomial denominators.
