given a binary point, design a quadratic which is minimized at that point!

Question

Given a binary vector $x$, I need to efficiently construct a matrix $A$ such that $x$ is a global minimizer of $z^TAz$ over binary $z$'s. I need the diagonal elements to be positive.

Answer 1

Suppose the system is of dimension $d$, let $f_A(z)=z^\textsf{T}Az$ and let $n$ be the number of $1$'s in $x$, we have the following cases:

$(1)\ n=0:$ Let $A=I$, the idenetity matrix, then $f_A(z)=z_1^2+\cdots+z_d^2$ is minimised at $x=0$.

$(2)\ n=1:$ No such $A$ exists. Indeed, suppose only the $j$-th element of $x$ is $1$, then $f_A(x)=A_{jj}>0$ since $A$ has positive diagonal elements. But then $x$ is not the minimiser since $f_A(0)=0$ for all $A$.

$(3)\ n\geq2:$ Let $i_1,i_2,...,i_n$ be the indices of non-zero elements in $x$, sorted in increasing order. Let $S$ be the index set below $$S=\{(i_1,i_2),(i_3,i_4),...,(i_{n-1},i_n)\}\ \text{if $n$ is even;}$$ $$S=\{(i_1,i_2),(i_2,i_3),...,(i_{n-1},i_n)\}\ \text{if $n$ is odd}.$$ We define $A$ as follows:

• Initiate $A=I$;
• For every pair $(j,k)$ in $S$, let $A_{jk}=-3$.

For example,

• If $x=(1,0,1)$, then $A=\left(\begin{smallmatrix}1&0&-3\\0&1&0\\0&0&1\end{smallmatrix}\right)$
• If $x=(1,1,0,1)$, then $A=\left(\begin{smallmatrix}1&-3&0&0\\0&1&0&-3\\0&0&1&0\\0&0&0&1\end{smallmatrix}\right)$

By such construction, $x$ is the unique minimiser of $f_A$. Indeed, if $A$ is as above then $$f_A(z)=P_1(z)+P_2(z)\text{ where }P_1=\sum_{j=1}^dz_j^2\text{ and }P_2=-3\sum_{(j,k)\in S}z_jz_k.$$

Note that

• If $z$ has more $1$'s than $x$, then $P_1(z)>P_1(x)$; as for $P_2(x)$, first note that for each pair $(j,k)\in S$ the term $x_jx_k$ is $1$, so $P_2(x)=-3|S|$; since $z$ has more $1$'s, for each pair $(j,k)\in S$ the term $z_jz_k$ is also $1$, this means $P_2(z)=-3|S|=P_2(x)$, so in summary $f_A(z)>f_A(x)$.
• If $z$ has $N$ more $0$'s than $x$, then $P_1(z)-P_1(x)=-N$; for $P_2$, note that these $N$ extra $0$'s in $z$ will make at least $\lceil N/2\rceil$ pairs $z_jz_k$ become $0$ in the sum of $P_2$; for each extra pair $z_jz_k=0$, we have $P_2(z)$ is $3$ more than $P_2(x)$, so for these $\lceil N/2\rceil$ pairs we have $P_2(z)-P_2(x)\geq3\lceil N/2\rceil$; in summary $f_A(z)-f_A(x)\geq3\lceil N/2\rceil-N>0$ if $N>0$.

This shows $x$ is the unique minimiser.

---

There might be better constructions, but the above method seems to make $A$ as sparse as possible, and the algorithm complexity is $\mathcal O(d)$ which should be efficient enough.

Answer 2

You want to minimize $$\sum_j (z_j-x_j)^2.$$ Expanding this will yield a quadratic part, a linear part, and a constant part. You can omit the constant part because shifting an objective by a constant does not affect optimality. To avoid the linear part, rewrite $z_j$ as $z_j^2$ and combine it with the quadratic part.

---

As @RobertIsrael noted, this approach yields objective function $$\sum_j (1-2x_j)z_j^2,$$ which does not have positive diagonal elements when $x_j=1$. If you allow a linear part of the objective, you can use the fact that $z$ is binary to add any multiple of $z_j^2-z_j$ without changing the objective value. In particular, taking $\lambda_j > 1-2x_j$ and adding $$\sum_j \lambda_j (z_j^2-z_j)$$ yields positive diagonal elements.