Sign of dual (pi) value
Answered
From the online doc, I know the sign of dual depends on the sense of constraints, but I'm confused with the following example:
m.addConstr(x <= y)
m.addConstr(x - y <= 0)
m.addConstr(0 <= y - x)
m.addConstr(y - x >= 0)
Whose dual value should be the same and why?
-
The first two constraints will be handled as \(\leq\) constraints. The first one is reformulated to standard form because it has non-constant expressions on both sides of the inequality sign. The second one is already properly defined as a \(\leq\) inequality.
The last two constraints will be handled as \(\geq\) constraints. Both have a constant on one side and a non-constant on the other.
To avoid confusion with dual values, I would strongly recommend to formulate all constraints in a standard form, i.e., either \(a^T x \leq b\) or \(a^T x \geq b\).
Best regards,
Jaromił0 -
Thanks a lot,
- What's the standard form for gurobi? Does it mean gurobi would move all variables to the LHS, and leave constant in the RHS as a standard form?
- Since the 2nd and 3rd constraints are both in standard form, why does the 1st constraint is the same as the 2nd one? Because gurobi doesn't change the sense of constraints?
0 -
What's the standard form for gurobi? Does it mean gurobi would move all variables to the LHS, and leave constant in the RHS as a standard form?
Yes. The standard form is \(a^T x \leq/\geq/= b\), i.e., one side holds the expression object and the other is constant.
Since the 2nd and 3rd constraints are both in standard form, why does the 1st constraint is the same as the 2nd one? Because gurobi doesn't change the sense of constraints?
Yes.
0 -
Sorry to bother you. I have an additional question,
I want to use lagrangian relaxation to both inequality and equality constraints. In the online doc, it says,
For minimization problems, it's relatively easy to determine the sign of dual values for inequality constraints. But how can I determine whether to negate the dual value of equality constraints? For example, a constraint x == 10, dual value 1. I want to penalize the constraint in the objective, should it be obj + 1*(x - 10) or obj + 1*(10 -x )？
0 -
For equality constraints, you can use the classical reformulation
\[\begin{align*}
x &= b\\
\Leftrightarrow x &\leq b \land x \geq b
\end{align*}\]i.e., you have two inequality constraints instead of one equality constraint. You can then construct your relaxation.
0 -
I understand I can do that, but that will generate 2 times the number of equality constraints and I think in certain situations, this reformulation will lead to numerical issues near the boundary.
Hence, if not doing this reformulation, is there a way to determine the sign of dual value for equality constraints?
Thanks.
0 -
It is quite some time when I last worked with Lagrangian relaxation, but I think that the multiplier for the equality constraint is unbounded, i.e., it can be positive or negative. The solution of the Lagrangian relaxation is then only just a lower bound of the original problem.
I guess it is best to make a literature review to confirm the above and possibly find a better solution.
0 -
IMO, it's a question about the definition of dual variable in gurobi.
People may define the equality constraint `Ax= b` with dual variable `y` in Lagrange function as: `\min c^Tx + y^T(b - Ax)` or `\min c^Tx + y^T(Ax - b)`. They will have the exact opposite signs.
According to the definition of dual variables of inequality constraints, I think it would be the former one.
0 -
Could you briefly explain how exactly you are using the Lagrange function? I think, usually, one solves the Lagrange function for some fixed \(x\) repeatedly in some iterative algorithm. Is this what you are doing? If yes, then you can evaluate the term in parentheses, i.e., evaluate \(Ax -b\) or \(b - Ax\), to obtain its sign. You then know how to bound your \(y\).
If you are not fixing any variables, then you are solving a nonconvex quadratic problem with possibly very bad numerical properties and I am not sure how you want to benefit from this.
0 -
I use lagrangian iteration, which means lagrange multipliers `y` are indeed parameters in the model, which will be updated once we have a new `x`. The only variables are `x` in the model. For example, I solve a trivial model
`\min_{x\ge 0} x\text{ s.t. } x = 1`
The Lagrangian can be written as:
`\min_{x\ge 0} \max_{y} x + y(1-x) = \max_{y} y \text{ s.t. } 1 \ge y`
The optimal `y=1`.
But if you define Lagrangian as: `\min_{x\ge 0} \max_{y} x + y(x-1)`, then the optimal `y=-1`. They have the opposite sign.
0 -
As far as I know, both Lagrange relaxations are valid. The optimal values for the Lagrange multipliers (i.e., the dual variables y) might have opposite signs when you switch to the other relaxation, but you are basically searching for the optimal solution x of the Lagrange relaxation, and this should be the same, independent of the way you formulate the relaxation.
0 -
Yes, the value of `x` will be the same, but `y` will have the opposite sign. I want to do lagrangian relaxations, so I need to get the dual value and use the dual value as coefficients of the constraint. If negate the sign of dual value in the lagrangian relaxation by mistake, it won't be a valid lagrangian relaxation.
Once I get a dual value `y=1`, I need to know which one is right, `x + 1 (x-1)` or `x + 1 (1-x)`. From the previous example, it's obvious that the latter one is right, but in practice, I cannot decide on the sign.
Which form above does gurobi use? `y^T(b-Ax)` or `y^T(Ax-b)`? As for inequalities, I'm sure gurobi uses the former one, but for equalities, I have no idea.
0 -
Which form above does gurobi use? or ? As for inequalities, I'm sure gurobi uses the former one, but for equalities, I have no idea.
It should be \(y^T (Ax - b) \).
0 -
Thanks, that matches my experiments.
I think it's better to put this on documentation. Although the multiplier for the equality constraint is unbounded, the sign of the multiplier still matters.
0
Please sign in to leave a comment.
Comments
14 comments