Convex combination of constraints that makes the problem infeasible
Answered
Hi,
I am trying to solve a quadratic programming problem:
min x^{T} Q x
s.t.
G_{1}(x) <= 0
G_{2}(x) <= 0
...
G_{n}(x) <= 0
Specifically, if the problem is infeasible, I want to get a convex combination of constraints that makes the problem infeasible:
infimum_{x} sum_{i}[lambda_{i}*G{i}(x)] > 0
where
lambda_{i}>0, sum_{i}(lambda_{i}) = 1
You can think of lambda_{i} as a nonnegative weight vector that sums up to one which, if the constraints are combined according to it, will make the constraint system infeasible (>0).
According to this paper:
https://link.springer.com/article/10.1007/BF00934810
Page 243, after equation (11-2), it says "most dual type algorithms addressed to it yields such a lambda".
I was looking into Gurobi "diagnose with infeasibility": (https://www.gurobi.com/documentation/10.0/examples/diagnose_and_cope_with_inf.html), and computes Irreducible Inconsistent Subsystem, but it does not give me such a vector which helps identify which constraint is more important in terms of causing infeasibility. I wonder if Gurobi has this function?
-
Hi Xuan,
You can think of lambda_{i} as a nonnegative weight vector that sums up to one which, if the constraints are combined according to it, will make the constraint system infeasible (>0).
[...] but it does not give me such a vector which helps identify which constraint is more important in terms of causing infeasibility. I wonder if Gurobi has this function?
Gurobi does not have a feature which computes such \(\lambda\) for nonlinear (constrained) models.
As Jonasz pointed out, Gurobi can compute an IIS, which is a subset of constraints causing infeasibility. It might be possible to compute a convex combination of constraint in an IIS to get a single infeasible constraints. However, this is not something currently available in Gurobi.
Best regards,
Jaromił1 -
Hi Xuan,
Jaromił and I had a discussion and there is possibly a way forward if your constraints are linear.
It would involve creating a LP with those constraints identified in the IIS, leaving the default objective of 0, solving via simplex to produce infeasibility (you may need to turn presolve off so that the simplex is run) and then retrieving the Model.FarkasDual to get a vector whose length is equal to the number of constraints. I think if you normalize it to a unit vector you may get what you are after. But this all relies in your initial constraints being linear. Is this the case?
- Riley1 -
Hi Xuan,
IIS - as per its definition - is a minimal system of constraints which together cause infeasibility. They are "equally important" - if you remove any of them, the system (but not necessarily the entire model) will be feasible.
I am not aware of the functionality you are after in Gurobi. Perhaps someone from Gurobi team can confirm this?
Additionally, maybe this article will be of interest to you.
Best regards
Jonasz0 -
Hi Riley,
Thanks for the discussion and reply! Yes, the original QP problem has linear constraints and a quadratic objective function. I am trying the method you suggested. It might be the case that a uniform weight assigned to each constraint in IIS is sufficient - I need to have further test.
If there is any further updates, I will post it here. Thank you!
0 -
Thanks Xuan, we'll be keen to hear if it works for you!
0 -
Hi,
I have a follow-up question: When Gurobi compute Farkas dual for linear programming problem with mixed equality and inequality constraints, does it find a Farkas dual that satisfies the conditions presented in slide 5-5 here: http://www.seas.ucla.edu/~vandenbe/ee236a/lectures/alternatives.pdf?
I understand that Farkas dual is not unique. So maybe Gurobi just find a Farkas dual that satisfies the inequality condition lamda^{T}*A*x <= lambda^{T}*b as shown in your documentation (https://www.gurobi.com/documentation/9.1/refman/farkasdual.html#attr:FarkasDual), and turn the equality constraints into inequalities, so the equality condition A^{T}z + C^{T}y = 0 in the slides is not necessarily satisfied?
My objective function is 0 and I already set InfUnbdInfo to 1.Thank you!
0 -
Hi Xuan,
For an equality, only one of the directions \(\leq, \geq\) is responsible for the infeasibility. Thus, depending on the sign of the Farkas Dual value \(\lambda\), you can determine which direction of an equality constraint has been used to determine an infeasible combination of inequalities. This \(\lambda\) will satisfy the equality condition. Let's have a look at the following infeasible model
\[\begin{align*}
\min_{x,y}\,& 0\\
\text{s.t.}\, & x + 2\cdot y = 6\\
& x + y = 0.1
& x,y \geq 0
\end{align*}\]
The FarkasDual computed by Gurobi is \(\lambda^T = (-1, 2)\). This fulfills the definition we state in the docs because\[\begin{align*}
\lambda^T A x = x + 0\cdot y \leq -5.8 = \lambda^T b
\end{align*}\]
which is trivially infeasible, given that both variables are non-negative. This exactly fulfills the definition on slide 5-3.The definition you refer to on slide 5-5 is also fulfilled. Note that on your slides, the Farkas Lemma on slide 5-2 is defined for \(Ax = b\) but slides 5-1 and 5-5 use \(Ax \leq b\) which may lead to confusion. This is because Gurobi uses \(Ax = b\) and then the certificate has to fulfill \(A^T z + C^T y \geq 0\), \(b^T z + d^T y < 0\) which it fulfilled as you can see above.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
7 comments