8
$\begingroup$

When solving best subset regression as a mixed integer program, how do you decide how tightly to bound the range of values of the $X$ values? When the box is tight, the solver finds a solution quickly, but potential solutions are ignored. How quickly should I expand the box?

I built my constraints to estimate variance using the following approach:

Rather than apply cuts on the covariance matrix directly, the cuts are applied on the principal components.

I want to minimize the variance of the sum of a vector $X$ ($1\times N$):

$$\text{Variance} = X \Sigma X^\top= X(Q\Lambda Q^\top)X^\top.$$

Let

$E_i:$ Eigenvalue $i$ ($1\times1$)

$V_i:$ Eigenvector $i$ ($N\times1$)

$= \sum_{i} E_i (XV_i)^2 = \sum_{i}\text{ComponentContribution}_i$

Near a reference vector $X_0$:

$$\text{ComponentContribution}_i \ge E_i (X_0V_i)^2+ 2E_i (X_0V_i)(XV_i-X_0V_i).$$

Note that there are many potential $X_0$ that have an equal value for $X_0V_i$. The above estimate for the component's contribution to variance does not depend on $X_0$. It only depends on $X_0V_i$. This allows the approximation to be useful near many different $X_0$. It is an approximation near a load value. Substituting:

\begin{align}L_0 &= X_0V_i\quad(1\times1)\\\text{ComponentContribution}_i &\ge E_iL^2 + 2E_iL(XV_i - L)\\\text{ComponentContribution}_i &\ge E_i(2LXV_i - L^2).\end{align}

This allows each component's contribution to be estimated independently. One benefit is that more constraints (more $L$ values) can be made for estimating the first component than for the smallest.

However, this leads to a second question, when evaluating the sources of error for an intermediate solution, how should I decide which components are contributing enough to error in the estimate to justify adding a constraint? Which should be lumped together into a single constraint?

I posted a working test to github.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.