# How to reformulate my problem as a mixed-integer quadratic problem

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)$.

• @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)$. – user2987 Mar 6 '14 at 16:46
• yes assumption means a requirement. In other words, $\exists$ $s$ rows of $B$ that we don't know their indices and minimize $f(x)$ – user2987 Mar 6 '14 at 16:52
• 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$? – D.W. Mar 6 '14 at 17:45
• 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. – D.W. Mar 6 '14 at 18:01
• 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? – D.W. Mar 6 '14 at 18:04

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.

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