Content deleted Content added
No edit summary |
No edit summary |
||
Line 1:
In [[mathematical optimization]], '''constrained optimization''' (in some contexts called '''constraint optimization''') is the process of optimizing an objective function with respect to some [[variable (mathematics)|variables]] in the presence of [[Constraint (mathematics)|constraints]] on those variables. The objective function is either a [[Loss function|cost function]] or [[energy function]], which is to be [[Maxima and minima|minimized]], or a [[reward function]] or [[utility function]], which is to be [[maximize]]d. Constraints can be either '''hard constraints''', which set conditions for the variables that are required to be satisfied, or '''soft constraints''', which have some variable values that are penalized in the objective function if, and based on the extent that, the conditions on the variables are not satisfied.
===Relation to Constraint Satisfaction Problems===
Constraint Optimization Problem (COP) is the most significant generalizations of the classic [[Constraint satisfaction problem|Constraint Satisfaction Problems]] (CSP) model<ref>{{Citation|last=Rossi|first=Francesca|title=Chapter 1 - Introduction|date=2006-01-01|url=http://www.sciencedirect.com/science/article/pii/S1574652606800052|work=Foundations of Artificial Intelligence|volume=2|pages=3–12|editor-last=Rossi|editor-first=Francesca|series=Handbook of Constraint Programming|publisher=Elsevier|doi=10.1016/s1574-6526(06)80005-2|access-date=2019-10-04|last2=van Beek|first2=Peter|last3=Walsh|first3=Toby|editor2-last=van Beek|editor2-first=Peter|editor3-last=Walsh|editor3-first=Toby}}</ref>. Actually, COP is a CSP solve with an ''objective function''. An ''optimal solution'' to a minimization (maximization) COP is a solution that minimizes (maximizes) the value of the ''objective function''. Many algorithms are used to handle optimization part.▼
==General form==
Line 29 ⟶ 32:
===Inequality constraints===
With inequality constraints, the problem can be characterized in terms of the [[geometric optimality conditions]], [[Fritz John conditions]] and [[Karush–Kuhn–Tucker conditions]], under which simple problems may be solvable.
====Linear programming====
If the objective function and all of the hard constraints are linear and some hard constraints are inequalities, then the problem is a [[linear programming]] problem. This can be solved by the [[simplex method]], which usually works in [[polynomial time]] in the problem size but is not guaranteed to, or by [[interior point method]]s which are guaranteed to work in polynomial time.
====Nonlinear programming====
If the objective function or some of the constraints are nonlinear
▲If the objective function or some of the constraints are nonlinear(equalities or inequalities), then the problem is a [[nonlinear programming]] problem.
====Quadratic programming====
If all the hard constraints are linear and some are inequalities, but the objective function is quadratic, the problem is a [[quadratic programming]] problem. It is one type of nonlinear programming. It can still be solved in polynomial time by the [[ellipsoid method]] if the objective function is [[Convex function|convex]]; otherwise the problem is [[NP hard]].
====KKT conditions====
Allowing inequality constraints, the [[Karush-Kuhn-Tucker conditions|KKT approach]] to nonlinear programming generalizes the method of Lagrange multipliers
▲Constraint Optimization Problem (COP) is the most significant generalizations of the classic [[Constraint satisfaction problem|Constraint Satisfaction Problems]] (CSP) model<ref>{{Citation|last=Rossi|first=Francesca|title=Chapter 1 - Introduction|date=2006-01-01|url=http://www.sciencedirect.com/science/article/pii/S1574652606800052|work=Foundations of Artificial Intelligence|volume=2|pages=3–12|editor-last=Rossi|editor-first=Francesca|series=Handbook of Constraint Programming|publisher=Elsevier|doi=10.1016/s1574-6526(06)80005-2|access-date=2019-10-04|last2=van Beek|first2=Peter|last3=Walsh|first3=Toby|editor2-last=van Beek|editor2-first=Peter|editor3-last=Walsh|editor3-first=Toby}}</ref>. Actually, COP is a CSP solve with an ''objective function''. An ''optimal solution'' to a minimization (maximization) COP is a solution that minimizes (maximizes) the value of the ''objective function''. Many algorithms are used to handle optimization part.
====Branch and bound====
Constraint optimization can be solved by [[branch and bound]] algorithms. These are backtracking algorithms storing the cost of the best solution found during execution and using it to avoid part of the search. More precisely, whenever the algorithm encounters a partial solution that cannot be extended to form a solution of better cost than the stored best cost, the algorithm backtracks, instead of trying to extend this solution.
| |||