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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Would you see this link? $\endgroup$– A.OmidiCommented Oct 13, 2019 at 6:16
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
$\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$ Commented 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$ Commented 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$ Commented Oct 13, 2019 at 8:52