Constrained optimization: Difference between revisions

Revision as of 14:57, 30 April 2021

Latest revision as of 01:05, 24 May 2025

(15 intermediate revisions by 13 users not shown)

Line 1:

{{Short description|Optimizing objective functions that have constrained variables}}

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 ==

The constrained-optimization problem (COP) is a significant generalization of the classic [[constraint-satisfaction problem]] (CSP) model.<ref>{{Citation|lastlast1=Rossi|firstfirst1=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|url-access=subscription}}</ref> COP is a CSP that includes an ''objective function'' to be optimized. Many algorithms are used to handle the optimization part.

==General form==

A general constrained minimization problem may be written as follows:<ref name="edo2021">{{Cite book|url=https://www.researchgate.net/publication/352413464|title=Engineering Design Optimization|last1=Martins|first1=J. R. R. A.|last2=Ning|first2=A.|date=2021|publisher=Cambridge University Press|isbn=978-1108833417|language=en}}</ref>

: <math>

Line 13 ⟶ 14:

\min &~& f(\mathbf{x}) & \\

\mathrm{subject~to} &~& g_i(\mathbf{x}) = c_i &\text{for } i=1,\ldots,n \quad \text{Equality constraints} \\

&~& h_j(\mathbf{x}) \geqqgeq d_j &\text{for } j=1,\ldots,m \quad \text{Inequality constraints}

\end{array}

</math>

Line 23 ⟶ 24:

==Solution methods==

Many constrained optimization algorithms can be adapted to the unconstrained case, often via the use of a [[penalty method]]. However, search steps taken by the unconstrained method may be unacceptable for the constrained problem, leading to a lack of convergence. This is referred to as the Maratos effect.<ref>Wenyu Sun; Ya-Xiang YuaYuan (2010). ''Optimization Theory and Methods: Nonlinear Programming'', Springer, {{ISBN|978-1441937650}}. p. 541</ref>

===Equality constraints===

Line 32 ⟶ 33:

====Lagrange multiplier====

{{main|Lagrange multipliers}}

If the constrained problem has only equality constraints, the method of [[Lagrange multipliers]] can be used to convert it into an unconstrained problem whose number of variables is the original number of variables plus the original number of equality constraints. Alternatively, if the constraints are all equality constraints and are all linear, they can be solved for some of the variables in terms of the others, and the former can be substituted out of the objective function, leaving an unconstrained problem in a smaller number of variables.

Line 54 ⟶ 55:

Allowing inequality constraints, the [[Karush-Kuhn-Tucker conditions|KKT approach]] to nonlinear programming generalizes the method of Lagrange multipliers. It can be applied under differentiability and convexity.

====Branch and bound====

Line 76:

In particular, the cost estimate of a solution having <math>x_{i+1},\ldots,x_n</math> as unassigned variables is added to the cost that derives from the evaluated variables. Virtually, this corresponds on ignoring the evaluated variables and solving the problem on the unassigned ones, except that the latter problem has already been solved. More precisely, the cost of soft constraints containing both assigned and unassigned variables is estimated as above (or using an arbitrary other method); the cost of soft constraints containing only unassigned variables is instead estimated using the optimal solution of the corresponding problem, which is already known at this point.

There is similarity between the Russian Doll Search method and [[Dynamicdynamic programming|Dynamic Programming]]. Like Dynamicdynamic Programmingprogramming, Russian Doll Search solves sub-problems in order to solve the whole problem. But, whereas Dynamic Programming

directly combines the results obtained on sub-problems to get the result of the whole problem, Russian Doll Search only uses them as bounds during its search.

Line 91:

* [[Constrained least squares]]

* [[Distributed constraint optimization]]

*[[Constraint satisfaction problem|Constraint Satisfaction Problems]] (CSP)

* [[Constraint programming]]

* [[Integer programming]]

* [[Metric projection]]

* [[Penalty method]]

* [[Superiorization]]

Line 114 ⟶ 115:

| url-access=registration

}}

{{Optimization algorithms}}

[[Category:Mathematical optimization]]