why are constrained problems hard to solve? I was reading about solving optimization problems using meta heuristic techniques. In most of the cases, constrained related problems are converted to unconstrained using penalty functions. I was trying to understand as why constrained problems are hard to solve? Suitable example will be of great help
 A: Well, it depends on what sort of metaheuristic and what types of constraint. One key properties that I look out for is how do I ensure that the final solution is feasible.
There are meta heuristic that approach the constrained problem directly such as $2$-opt and $3$-opt in traveling salesman problem. However, in general, this need not be the case  and we even come out with the notation of projections to ensure feasibility in the end.
Also, sometimes we have a fast solver for the unconstrained problem such as Ising model and QUBO (quadratic unconstrained optimization problem) and there are no ways to incorporate the constrained directly into the solver. It is known that if we penalize the constrained with a large penalty coefficient, then the unconstrained version of the problem is equivalent to the constrained problem.
A: They are as hard as parameterizing the constraints edge ($C(x)= 0$) with unconstrained variables:

*

*if parameterizing of $C(x)= 0$ is hard, solving the optimization problem for various parameterized objective function would give you a parameterization for $C(x)= 0$.

*if parameterizing of $C(x)= 0$ is not hard, then change the variable and solve unconstrained optimization.

