7
$\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$
  • $\begingroup$ Would you see this link? $\endgroup$ – A.Omidi Oct 13 '19 at 6:16
10
$\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.

| improve this answer | |
$\endgroup$
  • $\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 '19 at 22:54
  • 1
    $\begingroup$ No. For example there won't be strictly interior feasible points so Slater's is out. $\endgroup$ – Brian Borchers Oct 12 '19 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 '19 at 8:52

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.