1
$\begingroup$

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?

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ ... that is, the eigenvalues of $Q$ and $c$. Will it be $C$ in stead of $c$ here? $\endgroup$
    – KGM
    Commented May 6 at 10:55
  • $\begingroup$ The eigenvalues of $C$ is the vector $c$. So you are right, but the text is also not wrong. $\endgroup$ Commented May 6 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.