0
$\begingroup$

I have an unknown $n$-dimensional vector $x$ whose analytical expression depends on the following sum $x = z + Ba$ where the vector $z$ and the matrix $B\in \mathbb{R}^{n\times s}$ are given. So the $s$-dimensional vector $a$ is to be computed to find $x$.

The only assumption that we have is $x=0$ when we project $x$ onto the space spanned by $s$ different rows (that we don’t know their indices) of the matrix $B$ which has $n$ rows. To do this projection we can use $P_s\in \mathbb{R}^{n\times n}$ which is $1$ on the diagonal entries that correspond to the $s$ selected rows of $B$ and $0$ elsewhere. Hence, $P_s x= P_s z + P_s Ba=0 \implies a=-(P_sB)^{-1}P_sz$.

The main issue is that we don’t know the positions of these $s$ rows, so the problem is combinatorial and we need to go through all possible $n\choose s$ projections to find the exact $x$ which corresponds to the least cost $f(x)=\|y-Ax\|_2$ where $\|v\|_2=\big(\sum_iv_i^2\big)^{1/2}$, $y\in \mathbb{R}^{m\times 1}$ and the matrix $A\in \mathbb{R}^{m\times n}$ are given.

So my question is how I can reformulate my problem as a mixed-integer quadratic programming to go through all possible $n\choose s$ submatrices of $B$ formed by the $s$ selected rows and finally find the set of rows which corresponds to the least $f(x)$.

$\endgroup$
  • $\begingroup$ @D.W. $0_{n,1}$ refers to $n$-dimensional vector where all entries are zeros. The $s$ rows can be any set from all the $n$ rows of $B$ and so we have $n\choose s$ possible submatrices and we are looking to find the set that corresponds to the least $f(x)$. $\endgroup$ – user2987 Mar 6 '14 at 16:46
  • $\begingroup$ yes assumption means a requirement. In other words, $\exists$ $s$ rows of $B$ that we don't know their indices and minimize $f(x)$ $\endgroup$ – user2987 Mar 6 '14 at 16:52
  • $\begingroup$ Just to make sure I'm clear: given $A,B,y,z$, I want to find the vector $a$ that minimizes $f(z+Ba)$, subject to the constraint that there must exist some matrix $P_s$ with exactly $s$ 1's on its diagonal and 0's everywhere else, satisfying $P_s (z+Ba)=0$? $\endgroup$ – D.W. Mar 6 '14 at 17:45
  • $\begingroup$ By the way, the notation $(P_s B)^{-1}$ doen't make sense. You can't take the inverse of a $n\times s$ matrix. $\endgroup$ – D.W. Mar 6 '14 at 18:01
  • $\begingroup$ Are you sure you've got the constraints right? The constraint that there must exist $P_s$ such that $P_s x =0$ just amounts to requiring that $n-s$ of the entries of $x$ are zero. Is that really what you meant? $\endgroup$ – D.W. Mar 6 '14 at 18:04
1
$\begingroup$

So it sounds like the problem is the following:

Given $A,B,y,z$, I want to find the vector $a \in \mathbb{R}^n$ that minimizes $||y-Az-ABa||_2$, subject to the constraint that there must exist some matrix $P_s$ with exactly $s$ 1's on its diagonal and 0's everywhere else, satisfying $P_s (z+Ba)=0$.

Mixed-integer QCQP

This can be formulated as a mixed-integer quadratically constrained quadratic programming problem, as follows.

We have $n$ unknowns $a_1,\dots,a_n$, so $a=(a_1,\dots,a_n)$. Also introduce $n$ integer zero-or-one unknowns $p_1,\dots,p_n$, with the intention that $P_s$ will be the diagonal matrix whose diagonal is $p_1,\dots,p_n$. Add the cosntraint that $p_1+\dots + p_n=s$, to ensure that exactly $s$ of the entries on the diagonal are $1$. Note that each entry of $z+Ba$ is a linear expression in the unknowns, so the constraint $P_s (z+Ba)=0$ can be expressed as $n$ quadratic constraints, each of the form $p_i \cdot e_i=0$ where $e_i$ is linear in $a_1,\dots,a_n$.

Now note that each entry of $y-Az-ABa$ is a linear expression of the $n$ unknowns $a_1,\dots,a_n$, so the objective function is a quadratic function of the unknowns.

Unfortunately, mixed-integer QCQP is a pretty challenging form of non-linear programming, so I don't know how well this will work in practice. You might have to try it out with some solvers.

This is a pretty brain-dead approach. There may be smarter approaches that are more effective than this, by taking advantage of the structure of your problem.

$\endgroup$
  • $\begingroup$ Many thanks! Can you suggest me any technique/algorithm that I can use to solve my problem. Even a suboptimal solution would be enough. $\endgroup$ – user2987 Mar 6 '14 at 19:48

Your Answer

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

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