<s>[INST] Function as difference of convex functions I want to express the following function as the difference of two convex functions:
$f(x)=(x_2-2)^3+x_1^2-6x_1x_2+5x_1+max\{x_1^2,3-x_1^2\}+10$.
I have already seen answers that addressed these tasks, but I couldn't see a pattern in them. Is there an algorithmic approach to solve this?
 [/INST] Before beginning to answer your question I need to say that I do not know if the method I am about to propose is the best ; it is only how I would do right now, and I never had a class about this particular topic. But it is a method nonetheless.
Since the sum of convex functions is a convex function, it would be enough to tackle one term after the other.
I would begin with $\, \max\left(x_1^2 \,,\, 3-x_1^2\right) \,$ : $\,$ since $\, \max(a,b) = \max(a-b,0) + b \,$ we have $\, \max\left(x_1^2 \,,\, 3-x_1^2\right) \,=\, \max\left(2x_1^2 - 3 \,,\, 0\right) + 3-x_1^2 \,$. Moreover $\, \max\left(2x_1^2 - 3 \,,\, 0\right) \,$ is convex : the set of the points above its graph is the intersection of two convex sets : the set of the points that are above the graph of the convex function $\, 2x_1^2 - 3 \,$ and the half-plane above the x-axis, hence it is a convex 
(if geometry is not your thing at all, you can cut $\, \max\left(2x_1^2 - 3 \,,\, 0\right) \,$ into three parts : when $\, x_1 < - \sqrt{\frac{3}{2}} \,$ where the $\max$ is equal to $\, 2x_1^2 - 3 \,$ whose second derivative equals $4>0$ hence the derivative is increasing ; then you continuously go into the second part, $\, - \sqrt{\frac{3}{2}} \leq x_1 < \sqrt{\frac{3}{2}} \,$ where the $\max$ equals $0$, so you have a left derivative at $\, - \sqrt{\frac{3}{2}} \,$ equal to $-4\sqrt{\frac{3}{2}}$ which is less than the right derivative which equals $0$, and so on) 
Hence $\, \max\left(x_1^2 \,,\, 3-x_1^2\right) \,=\, \max\left(2x_1^2 - 3 \,,\, 0\right) - \left(x_1^2 - 3\right) \,$ is the difference of two convex functions.
Then I would tackle $\, -6\,x_1\,x_2 \,$ : the Hessian associated with $\, -6 \, x_1 \, x_2 \,$ is $\, \begin{pmatrix} 0 & -6 \\ -6 & 0 \end{pmatrix}$ whose eigenvalues are $-6$ and $6$ (because their sum is $0$ and their product is $-36$) so $\, -6\,x_1\,x_2 \,$ is neither convex nor concave. This allows us to see how to solve the problem : just write
\begin{equation*}
-6 \, x_1 \, x_2 \,=\, \left( 3 \, x_1^2 + 3 \, x_2^2 - 6 \, x_1 \, x_2 \right) - 3 \, \left(x_1^2 + x_2^2\right) \,=\, 3 \, \left(x_1-x_2\right)^2 - 3 \, \left(x_1^2 + x_2^2 \right)
\end{equation*}
The first term of the right-hand side has a Hessian $\, \begin{pmatrix} 6 & -6 \\ -6 & 6 \end{pmatrix} \,$ whose eigenvalues are $0$ and $12$, so it is convex, while $\, 3 \, \left(x_1^2 + x_2^2\right) \,$ has a Hessian $\, 6\,I \,$ where $I$ is the identity matrix, so it is also convex. Hence $\, -6\,x_1\,x_2 \,$ may be written as the difference of two convex functions.
Then $\, \left(x_2-2\right)^3 \,$ : $\;$ for the odd monomials (as opposed to the even ones), the idea is to use the Newton's binomial formula, like so :
\begin{equation*} \begin{split}
\left(x+1\right)^4 \,-\, \left(x-1\right)^4 \;=\; 8\,x^3 \,+\, 8\,x \\
\mbox{so} \;\; x^3 \;=\; \frac{1}{8} \, \left(x+1\right)^4 \,-\, \frac{1}{8} \, \left(x-1\right)^4 - x
\end{split} \end{equation*}
moreover, in the same way,
\begin{equation*}
x \;=\; \frac{1}{4} \, \left(x+1\right)^2 \,-\, \frac{1}{4} \, \left(x-1\right)^2
\end{equation*}
so, joining last both equations and translating
\begin{equation*}
\left(x-2\right)^3 \;=\; \left[ \frac{1}{8} \, \left(x-1\right)^4 \,+\, \frac{1}{4} \, \left(x-3\right)^2 \right] - \left[ \frac{1}{8} \, \left(x-3\right)^4 \,+\, \frac{1}{4} \, \left(x-1\right)^2 \right]
\end{equation*}
Both brackets are sums of convex functions, hence are convex themselves, so we can write $\, \left(x_2-2\right)^3 \,$ as the difference of two convex functions.
You can certainly deal with $\, 5 \, x_1 \,$ yourself, following what we just did. And I bet you know that $\, x_1^2 \,+\, 10 \,$ is convex. So I let you conclude on your own.
</s>