# Linear system with an l1-norm constraint

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.

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 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.
• In general, you'd need to use an integer programming branch and bound approach to deal with non-convex absolute value inequality constraints. In this case, because the only decision to make Is whether $x_{1}$ is positive or negative, the branch and bound tree only has two leaf nodes and you can handle this as I suggested. – Brian Borchers Jul 9 '20 at 22:28