How to reformulate my problem as a mixed-integer quadratic problem
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.