# Discontinuity phenomenon in polynomial optimization

Let $Q(x,y)$ be a polynomial in the two variables $x$ and $y$, with real coefficients. Let $a<b$; for any fixed $x$ the polynomial $Q(x,.)$ has a minimum $m(x)$ when $y$ varies in $[a,b]$. We know that this minimum is attained ; call $\eta (x)$ the smallest value in $[a,b]$ where $Q(x,.)$ reaches this minimum. It is also well-known that $\eta (x)$ is either $a$, or $b$, or that $\frac{\partial Q}{\partial y}(x,\eta(x))=0$.

Now there are cases when the fonction $\eta$ is not continuous everywhere : I provide a complicated example below. My example has total degree 12 (degree $6$ in both $x$ and $y$) . I am looking for simpler examples, so here goes my question : what is the smallest total degree of $Q$ for such a phenomenon to appear ?

The example : let $a=0,b=4$ and

$$Q(x,y)=12348(x^6 + y^6 + 1)+64344(x^5(y+1)+y^4(x+1)+x+y)+111977((y^2 + 1)x^4 + (x^2 + 1)y^4 + x^2 + y^2)+113162((xy)^3+x^3+y^3)+136346xy(x^3+y^3+1)-150890xy((y + 1)x^2+(x+1)y^2+x+y)-938154(xy)^2$$

Then one can check with GP that : The polynomial $R(x)={\sf Res}_y(Q(x,y)-Q(x,0),\frac{\partial Q}{\partial x}(x,y))$ is a product of three factors : it is $(x+1)^2$ times a polynomial of degree $4$ times a polynomial $S(x)$ of degree $20$. Then $S(x)$ has eight real roots. The fifth root, $\alpha$, is approximately $\alpha=0.5267883330835579971974199435$.

The polynomial $T(y)=\frac{\partial Q}{\partial x}(\alpha,y)$ has five real roots. The largest, $\beta$, is approximately $\beta=0.5185888479238405761315858539$.

And one has $\eta(x)=0$ for $x \in [0,\alpha[$, $\eta(x)>\beta$ for $x\in ]\alpha,1]$. So $\eta$ has a jump at $\alpha$.

-

Take $Q(x,y) = xy$ and see what happens at $x=0$. Note that $Q(x, \cdot)$ is linear for each $x$

-

What about $Q(x,y) = -(x-y)^2$, $[a,b] = [0,1]$, where $\eta(x) = 0$ if $x \le 1/2$ and $1$ if $x > 1/2$?

-
Yes. In a certain sense, your example reduces to WimC's example. –  Ewan Delanoy Mar 18 '12 at 8:34

If I understand correctly, you're asking about discontinuities in the function $$\eta(x) = \operatorname{arg\,min}\limits_{y \in [a,b]}\ Q(x,y).$$

Consider the function $y^4 - y^2 + xy$. For small $x$, this looks like a Mexican hat potential with two local minima; the value of $x$ determines which one is the global minimum.

I think this sort of thing is studied in catastrophe theory.

But the answer to your question of the smallest total degree is just two. Let $Q(x,y) = xy$. Depending on the sign of $x$, the value of $\eta(x)$ is either $a$ or $b$.

-
Thanks for the feedback mentioning catstrophe theory. By the way, WimC gave the optimal solution minutes before you edited your post. –  Ewan Delanoy Mar 18 '12 at 8:41