# Mixed integer non convex optimization problem

If an optimization problem is mixed integer non-convex problem. The optimal solution by applying brute exhaustive search is infeasible to be applied in practice due to high complexity i.e. $$O(N^K)$$. Can we say that it's NP hard problem? If yes, can someone explain with more details.

• You can't say it is NP-hard without giving a proof.
– zdm
Nov 22 '19 at 18:20
• You can take the following mixed integer non-convex program. $\max xy$ subject to $x\geq0$, $y\in\{0,1\}$, and $xy\leq1$. The optimal solution is trivially $x=y=1$.
– zdm
Nov 22 '19 at 19:18
• I don't know how can I use the above example to prove that the problem is NP-hard. However, my problem can be solved with brute force exhaustive search but it is impractical for larger values. Using continuous relaxation the problem is transformed to convex optimization problem. Then using Lagrange duality technique the optimal solution is obtained. Nov 27 '19 at 17:28
• @zdm Can you please check the edited problem? Nov 27 '19 at 19:16

For example, consider the problem of sorting $$n$$ integers. Suppose the first algorithm I give you is a one that tries all $$n!$$ permutations. Can we now safely conclude that this problem is somehow hard? Of course not and we know that there are many much faster polynomial-time algorithms for the problem.