3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Unconstrained optimization: find the warmest winter jacket. Constrained optimization: find the warmest winter jacket that satisfies my daughter's requirements. As simple as that $\endgroup$
    – Sune
    Jan 29, 2022 at 11:25
  • $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Jan 29, 2022 at 16:40

1 Answer 1

Reset to default
1
$\begingroup$

Please, be aware that the constraints more than reduce the feasibility space, shaping what you have tried to model that. This is usually referred the art of modeling. This is where there exists more than one unique formulation for the same problem. Also, the constraints, really, represent the limits/requirements based on what you need and NO more. Since if a problem needs to be unconstrained, what are the reasons to constraint it or vice versa!!?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.