Linear system with an l1-norm constraint

Question

I have a saddle-point system of the form \begin{equation} \begin{bmatrix} A & B \\ B^T & O \end{bmatrix}\begin{bmatrix} x\\ y \end{bmatrix} = \begin{bmatrix} f \\ \vec{0} \end{bmatrix}, \end{equation} where $A$, $B$ are matrices, and $O$ is a matrix of zeros, and $x$ is a solution vector of length $n$. Clearly, $y$ is a (vector) Lagrange multiplier enforcing $B^T x = \vec{0}$.

In this setting, is it possible to look for solution vectors $x$ such that $|x_1| > \sum\limits_{i=2}^n |x_i| $? I'd also want the solution to satisfy the linear system in at least a least-squares sense.

Does anyone have any ideas on how to do this in Matlab? I have no intuition on how to mix $l_1$ and $l_2$ constraints of this type, or if it's even possible. I'm willing to add more degrees of freedom to the system if it will help.

Answer 1

The set of $x$ such that $|x_{1}| \geq \sum_{i=2}^{n} | x_{i} |$ is a non-convex set, but it's relatively easy to look for solutions where $x_{1} \geq \sum_{i=2}^{n} | x_{i} | $ and then look for solutions where $-x_{1} \geq \sum_{i=1}^{n} | x_{i} |$. The two subproblems can be solved as linear programming problems feasibility problems.

If you want the linear equation constraints to be satisfied up to some 2-norm tolerance, then you'd still have a pair of convex optimization problems, but this time they would be SOCP's.

If it's important to have $x_{1}$ strictly greater than $\sum_{i=2}^{n} | x_{i} |$, then you need to add some tolerance to turn this into a $\geq$ constraint.