# How to do the scaling to remove bias in QP problem?

I have a MIQP problem as below

minimize $$\min {\bf x}^T{\bf Qx}-{\bf c}^T{\bf x}$$

$${\bf x}$$ is a binary variable. The range of values in $${\bf Q}$$ and $${\bf x}$$ are quite different. The elements of $${\bf Q}$$ lies in the range of 0 and 1 while the values in $${\bf c}$$ have mean around 20.

I want to put equal importance on both of these parameters. It seems from the result that $${\bf c}$$ has quite strong influence. The results is more biased towards $${\bf c}$$.

How do I scale one of these so that both $${\bf Q}$$ and $${\bf c}$$ have equal influence on the results, i.e., we remove the bias.

How I do it...

To balance the influence of the terms involving $${\bf Q}$$ and $${\bf c}$$ in your objective function, I scale one of them appropriately. Since the elements of $${\bf Q}$$ are in the range of 0 and 1 while the values in $${\bf c}$$ have a mean around 20, I scale $${\bf Q}$$ to have a similar magnitude as $${\bf c}$$. Here's how I can do it:

I compute the average value of $${\bf c}$$, let's call it $$\bar{c}$$. Then I compute the average value of the elements in $${\bf Q}$$, let's call it $$\bar{Q}$$. Then I scale $${\bf Q}$$ by multiplying it by $$\frac{\bar{c}}{\bar{Q}}$$.

$$\min {\mathbf{x}}^T \left(\frac{\bar{c}}{\bar{Q}} \mathbf{Q}\right)\mathbf{x} - \mathbf{c}^T\mathbf{x}$$

Am I doing it right?

• Is Q positive semi-definite? Commented May 1 at 18:02
• @ErlingMOSEK unfortunately not
– KGM
Commented May 1 at 18:24

If $$x$$ is binary vector, you have $$x^T D x = d^T x$$ for any diagonal matrix $$D$$ with diagonal $$d$$. This has two important consequences:
1. You can assume Q to be convex without loss of generality. In particular, given nonconvex $$Q$$, let $$Q = H D H^T$$ be its eigendecomposition and let $$D^+ = \lambda I$$ for some $$\lambda > 0$$ be a scaled identity matrix such that $$D_{ii} + D^+_{ii} \geq 0$$. Then $$H (D + D^+) H^T = Q + D^+$$ is positive semidefinite. Moreover, minimizing $$x^T Q x - c^T x$$ is the same a minimizing $$x^T (Q + D^+) x - (d^+ + c)^T x$$, where $$d^+ = \lambda \mathbf{1}$$ is the diagonal entries of $$D^+$$.
2. To balance the scaling of $$x^T Q x$$ and $$c^T x$$, note that the former can be rewritten as $$x^T Q x = (Hx)^T D (Hx)$$ for the eigendecomposition $$Q = H D H^T$$, and the latter is just $$x^T C x$$ where $$C$$ is the diagonal matrix with diagonal $$c$$. The scaling of $$x$$ and $$Hx$$ are in balance, as on is just an orthogonal transformation of the other, so you just need to balance $$D$$ and $$C$$, that is, the eigenvalues of $$Q$$ and $$c$$. This can be done by scaling $$c$$ such that the norm of $$c$$ matches the norm of eigenvalues of Q. You may want to experiment with the one-norm, two-norm and infinity-norm to find what suit your needs the best.
• ... that is, the eigenvalues of $Q$ and $c$. Will it be $C$ in stead of $c$ here?
• The eigenvalues of $C$ is the vector $c$. So you are right, but the text is also not wrong. Commented May 6 at 11:05