# Constraint Optimization and Feasible Regions

Someone asked me this question the other day:

• If constraints reduce the feasible region of an optimization problem (e.g. linear programming), then why is constraint optimization considered more difficult than the same optimization problem without constraints?

I tried to use the following logic to answer this question (they used a continuous example, I answered using a discrete example):

• Imagine you are trying to plan a party in the month of December, there are 31 days where you can have the party. You invite 3 guests to this party : each guest has 5 days in the month of December when they are unavailable (these are the constraints). Days amongst guests can overlap. You want all 3 guests to attend your party.

• Even though there are now less days where you can have the party - it obviously becomes more difficult to accommodate everyone's schedule. Without the constraints, indeed there were more days to consider, but you could have had the party on any day. On the other hand, now there are fewer days to consider - but each day, you have to use some "energy" to check whether or not all guests are available.

• With constraints, you will spend "energy" each time you consider a potential day for the party. Without constraints, you don't need to spend any energy at all.

Is my example correct? Even though constraints result in a smaller feasible region for an optimization problem - it still becomes more difficult to solve the problem?

Is there a better explanation I can use?

• Unconstrained optimization: find the warmest winter jacket. Constrained optimization: find the warmest winter jacket that satisfies my daughter's requirements. As simple as that
– Sune
Commented Jan 29, 2022 at 11:25
• Your example looks OK to me. Note that constraints do not always make the problem harder. Trivial example: minimize f(x) v. minimize f(x) s.t. x = 0, where f() is smooth but nonconvex with lots of local minima.
– prubin
Commented Jan 29, 2022 at 16:40