2
$\begingroup$

As we all know, KKT point and stationary point are well defined when the optimization variables are continuous in the problem.

Now, I want to know whether there exist some special points except for the globally optimal solution in discrete optimization problems. For example, suppose $f$'s are differentiable with respect to $x$ for any given $y$. $$\begin{aligned}\min_{x,y}\quad& f_0(x,y), \\ \mathrm{s.t.}\quad&f_k(x,y)\leq 0,\forall k\\ &x\in\mathcal X,\\ & y\in\mathbb Z.\end{aligned}$$ where $\mathcal X$ is a compact and convex set. Except for the globally optimal solution, what else do some special points (e.g. stationary point) exist? And how to define these points?

Thanks a lot for any help.

$\endgroup$
2
$\begingroup$

Welcome to OR Stack Exchange.

Your question is not clear. You are interested in special points in discrete optimization spaces. But you describe a mixed-variable problem involving both continuous variables $x$ and integer variables $y$.

For a given $y$, the theory of calculus of variations applies to the continuous subproblem on $x$. But I don't think you are interested in such a trivial answer.

If you're interested in the discrete part of the problem, the notion "local optimum" can be defined too, in an analog way defined for continuous spaces. Please have a look at Polynomial Local Search complexity class definition and, even better, at the seminal paper by David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis on this topic, namely "How easy is local search?".

$\endgroup$

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.