Skip to main content

L1 minimization

Answered

Comments

7 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi,

    Currently, to model the L1 norm, you have to make use of the abs general constraint function.

    In the upcoming release, there will be a specialized general constraint for the L1 norm. The release is planned for November 2021.

    Best regards,
    Jaromił

    0
  • L1fe
    First Comment
    First Question

    Hi Jaromil,

    Thanks! I have two follow up questions if you don't mind.

    - How would I write/encode the conditions: (Xi, Yi) != (Xj, Yj) when i !=j ?

    - In terms of performance, is it okay to keep the absolute value, or should I try to linearize the equation, e.g. by introducing additional variables and solve something like that intead?

    min t0 + t1 where -t0 < Xi - xi < t0 and -t1 < Yi - yi < t1

     

    Thanks.

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi,

    - How would I write/encode the conditions: (Xi, Yi) != (Xj, Yj) when i !=j ?

    Since one cannot access solution point values while constructing the model, you have to model this condition via the usage of binary variables and additional inequalities.

    I will provide an example for the condition \((x_1,y_1) \neq (x_2,y_2)\). You can use the abs function to create constraints

    \[\begin{align}
    |x_1 - x_2| &\geq \epsilon\delta_x \\
    |y_1 -y_2| &\geq \epsilon\delta_y \\
    \delta_x + \delta_y &\geq 1\\
    \delta_x,\delta_y &\in \{0,1\}
    \end{align}\]

    The above states that at least one of the coordinates has to be different by at least \(\epsilon\), i.e., not equal. Please note that we have to use a tolerance because strict inequality constraints are not supported in Gurobi.

    In terms of performance, is it okay to keep the absolute value, or should I try to linearize the equation, e.g. by introducing additional variables and solve something like that intead?

    It is OK to keep the absolute value. So you should not see any benefit by linearizing the equations by hand.

    Best regards,
    Jaromił

     

    0
  • L1fe
    First Comment
    First Question

    Hi Jaromil,

    Thank you a lot for your quick answer!

    One last question. For the inequalities for all pairs (i,j) i!=j, I should use the same delta x and delta y?

    Thanks.

     

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi,

    Using the same delta for all pairs would restrict all pairs to either differ in the \(x\) or in the \(y\) coordinate or in both. Thus, it is best to introduce separate \(\delta_{x,ij},\delta_{y,ij}\) for each \(i,j\) pair.

    Best regards,
    Jaromił

    0
  • L1fe
    First Comment
    First Question

    Hi Jaromil,

    How should the epsilon be chosen?

    Also, could we write the condition as |Xi - Xj| + |Yi-Yj| >= 1, which would force the pairs to be different as they take integer values?

    Thanks!

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi,

    How should the epsilon be chosen?

    \(\epsilon\) should be some small value which is still above the FeasibilityTol, e.g., \(10^{-5}\). This small tolerance is only required if \(X,Y\) are continuous variables.

    Since \(X,Y\) are integers, you can use the constraint you proposed.

    Best regards,
    Jaromił

    0

Please sign in to leave a comment.

Powered by Zendesk