[Solved]: Suboptimal Solution for a combinatorial problem

Problem Detail: 

I have a cost function $f(X)=\|\hat{X}-X\|_2$ to minimize which depends on a $s\times s$ matrix $X$ where $\hat{X}$ is given and $\|X\|_2=\big(\sum_{i,j}x_{ij}^2\big)^{1/2} $. This matrix $X$ is generated by selecting only $s$ different rows from a matrix $B$ of dimension $n\times s$. At the end, we are going to choose one matrix $X$ that generates the least cost $f(X)$ within all possible $n\choose s$ submatrices of B. And so, this is a combinatorial problem that becomes complicated mostly when $n$ is big.

So my question is can we find a suboptimal solution without going through all possible $n\choose s$ submatrices and what kind of algorithm that I can apply to find such solution.

My second question is can we apply a feature selection algorithm to find a suboptimal solution for a combinatorial problem.

Asked By : user2987

Answered By : D.W.

Mixed-integer quadratic programming

Given your updated question, this can be formulated as a mixed-integer quadratic programming problem.

Let $y_1,\dots,y_n$ be $n$ zero-or-one integer variables, subject to the constraint $y_1+\dots+y_n=s$, with the intent that if $y_i=1$ then we are selecting the $i$th row from $B$. Then for each $i,j$, the entry $(\hat{X}-X)_{i,j}$ can be expressed as a linear function of $y_1,\dots,y_n$. We are asking to minimize the objective function $\sum_i,j (\hat{X}-X)_{i,j}^2$, which is a quadratic objective function. Therefore, this can be expressed as a mixed-integer quadratic programming problem.

So, you could try throwing an off-the-shelf solver for mixed-integer quadratic programming at this and see how it does.

Closest vector problem

If everything in sight is an integer, I think this problem could also be approached as the problem of finding the closest point in a lattice to a given vector, the closest vector problem (CVP).

Consider the following lattice over a $n+s^2$-dimensional space. For each $i$, we have a basis vector of the form

$$(0,\dots,0,K,0,\dots,0,B_i,0,\dots,0),$$

where $K$ is a large constant (to be chosen later) and in the above, $K$ appears in the $i$th column, and $B_i$ is the $i$th row of $B$ and it appears starting in the $n+(i-1)s+1$th column. This gives us $n$ basis vectors, which form a basis for the lattice. Now we want to find the lattice point that is closest to the vector

$$(0,\dots,0,\hat{X}_1,\hat{X}_2,\dots,\hat{X}_s),$$

where the first $n$ columns of this vector are zero and $\hat{X}_i$ is the $i$th row of $\hat{X}$. If we choose $K$ appropriately, the closest lattice point has a good chance of being a sum of just $s$ of the basis vectors and thus forming a solution to this problem.

Now you could try to see if you can find any off-the-shelf CVP solvers, and see if they are effective at this problem. This is only going to work if everything is an integer: if you've got real numbers, I don't think this will work.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22316

 Ask a Question

 Download Related Notes/Documents