1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Having no experience with optimization, could you point me to a reliable resource or examples of actually setting up a problem like this with the two subproblems, and solving? It doesn't even have to be Matlab. I just can't seem to find examples of constraints of this type. $\endgroup$ – VarunShankar Jul 9 at 20:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Brian Borchers Jul 9 at 22:28

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.