Calculating the maximum value of a quadratic polynomial on several variables with some restrictions

maxima-minimanumber theoryoptimizationquadratic programming

Consider the following function on seven variables: $$f(x_1,\dots,x_7)=-x_1^2-2x_2^2-5x_3^2-4x_4^2-2x_5^2-71x_6^2-2x_7^2+2x_1x_2+2x_1x_3+2x_1x_4+2x_1x_6+2x_4x_5+2x_6x_7. $$

In another form, we have $$ f=3x_1^2-x_2^2-4x_3^2-2x_4^2-x_5^2-69x_6^2-x_7^2-(x_1-x_2)^2-(x_1-x_3)^2-(x_1-x_4)^2-(x_1-x_6)^2-(x_4-x_5)^2-(x_6-x_7)^2.$$

Can we find the maximum value $M$ of $f(x_1,\dots,x_n)$ with the following restrictions? The $x_i$'s are integers with $x_1,x_3,x_6$ odd and $x_2,x_4,x_5,x_7$ even.

What I know is that $(0,\dots,0)$ is the unique global maximum point of $f$ (as a function on real variables) with $f(0,\dots,0)=0$. Also $f(1,0,1,0,0,1,0)=-73$, so $0>M>-73$.

P.S. The result that I am hoping is $M<-7$.

Best Answer

$f(x)=-5$ when $x=(x_1, x_2, x_3,x_4, x_5,x_6,x_7)$ is one of the following 16 tuples,

$$\begin{array}{rrrrrrr} &(55, &28, &11, &16, &8, &1, &0) \\ &(57, &28, &11, &16, &8, &1, &0) \\ &(63, &32, &13, &18, &8, &1, &0) \\ &(63, &32, &13, &18, &10, &1, &0) \\ &(65, &32, &13, &18, &8, &1, &0) \\ &(65, &32, &13, &18, &10, &1, &0) \\ &(67, &34, &13, &20, &10, &1, &0) \\ &(69, &34, &13, &20, &10, &1, &0) \\ &(71, &36, &15, &20, &10, &1, &0) \\ &(73, &36, &15, &20, &10, &1, &0) \\ &(75, &38, &15, &22, &10, &1, &0) \\ &(75, &38, &15, &22, &12, &1, &0) \\ &(77, &38, &15, &22, &10, &1, &0) \\ &(77, &38, &15, &22, &12, &1, &0) \\ &(83, &42, &17, &24, &12, &1, &0) \\ &(85, &42, &17, &24, &12, &1, &0)\\ \end{array}$$


Claim: $f(x)\le-5$ when $x_1,x_3,x_6$ are odd and $x_2,x_4,x_5,x_7$ are even.

Proof: $$f(x)= -(x_1-x_2-x_3-x_4-x_6)^2 -(x_2-x_3-x_4-x_6)^2\\ -3 x_3^2 - 2 x_4^2 - 2 x_5^2 - 68 x_6^2 - (x_6-x_7)^2- x_7^2\\ + 4 x_3 x_4 + 4 x_3 x_6 + 2 x_4 x_5 + 4 x_4 x_6$$ Since $(\text{an even number})^2\equiv0$, $(\text{an odd number})^2\equiv1$, $2(\text{odd number})\equiv2$ $\pmod4$, we have $$f(x)\equiv-1-0-3-0-0-68-1-0+0+0+2+0=-71\equiv3\pmod4$$

Thanks to Will Jagy's answer, we can express $f(x)$ as a negative combination of squares.

$$\begin{aligned}f(x) = -(x_1-x_2-x_3-x_4-x_6)^2&\\ -(x_2-x_3-x_4-x_6)^2&\\ - 3(x_3-\frac23x_4-\frac23x_6)^2&\\ - \frac23(x_4-\frac32x_5-5x_6)^2&\\ - \frac12 (x_5-10x_6)^2&\\ - (x_6-x_7)^2 &\\ - x_7^2& \end{aligned}$$

Since $x_6$ is odd while $x_7$ is even, $x_6\not=x_7$. So $(x_6-x_7)^2\ge1$.

Since $f(x)\le -(x_6-x_7)^2\le-1$, all we need to prove is $f(x) \not= -1$.

Suppose $f(x)=-1$. Since $(x_6-x_7)^2\ge1$, we must have $$\begin{aligned} x_1-x_2-x_3-x_4-x_6&=0\\ x_2-x_3-x_4-x_6&=0\\ x_3-\frac23x_4-\frac23x_6&=0\\ x_4-\frac32x_5-5x_6&=0\\ x_5-10x_6&=0\\ x_6-x_7&=1\\ x_7&=0\\ \end{aligned}$$ That means, $x_7=0$, $x_6=1$, $x_5=10$, $x_4=20$, $x_3=14$. However, we require $x_3$ be odd. Hence $f(x)\not=-1$. $\quad\checkmark$


Hence $M=-5$.

Related Question