9
$\begingroup$

I was wondering if the KKT conditions are applicable for for MINLPs, and if not, why not? What about the case when the integer variables are modeled using constraints involving just continuous variables?

$\endgroup$
1
  • $\begingroup$ Would you see this link? $\endgroup$
    – A.Omidi
    Oct 13, 2019 at 6:16

1 Answer 1

14
$\begingroup$

No, the KKT conditions aren't applicable to mixed-integer programming problems with integer variables. The theory behind the KKT conditions depends on the objective and constraint functions being differentiable but functions of integer variables aren't differentiable.

It's certainly possible to enforce integrality constraints using continuous variables. For example, the constraint that $x_{i}$ is 0 or 1 can be written as the nonconvex nonlinear equality constraint $x_{i}(1-x_{i})=0$. You could apply the KKT conditions to such a problem, but you would end up with locally optimal points for every possible combination of the integer variable values.

$\endgroup$
3
  • $\begingroup$ Thanks, and just to follow up on your second point - are the standard constraint qualifications satisfied at every feasible point for the NLP where the integer variables are reformulated as nonconvex equality constraints? $\endgroup$
    – Josh Allen
    Oct 12, 2019 at 22:54
  • 1
    $\begingroup$ No. For example there won't be strictly interior feasible points so Slater's is out. $\endgroup$ Oct 12, 2019 at 23:40
  • $\begingroup$ Great, and finally, does that therefore imply that the KKT conditions may not be satisfied at the locally optimal points. $\endgroup$
    – Josh Allen
    Oct 13, 2019 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.