“Active set method”的意思、由来-开放百科全书

词条

Active set method

释义

Active set methods
References
Bibliography

In mathematical optimization, a problem is defined using an objective function to minimize or maximize, and a set of constraints

that define the feasible region, that is, the set of all x to search for the optimal solution. Given a point in the feasible region, a constraint

is called active at if and inactive at if Equality constraints are always active. The active set at is made up of those constraints that are active at the current point {{harv|Nocedal|Wright|2006|p=308}}.

The active set is particularly important in optimization theory as it determines which constraints will influence the final result of optimization. For example, in solving the linear programming problem, the active set gives the hyperplanes that intersect at the solution point. In quadratic programming, as the solution is not necessarily on one of the edges of the bounding polygon, an estimation of the active set gives us a subset of inequalities to watch while searching the solution, which reduces the complexity of the search.

Active set methods

In general an active set algorithm has the following structure:

Find a feasible starting point

repeat until "optimal enough"

solve the equality problem defined by the active set (approximately)

compute the Lagrange multipliers of the active set

remove a subset of the constraints with negative Lagrange multipliers

search for infeasible constraints

end repeat

Methods that can be described as active set methods include:^[1]

Successive linear programming (SLP)
Sequential quadratic programming (SQP)
Sequential linear-quadratic programming (SLQP)
Reduced gradient method (RG)
Generalized reduced gradient method (GRG)

References

1. ^{{harvnb|Nocedal|Wright|2006|pp=467–480}}

Bibliography

{{cite book|last=Murty|first=K. G.|title=Linear complementarity, linear and nonlinear programming|series=Sigma Series in Applied Mathematics|volume=3|publisher=Heldermann Verlag|location=Berlin|year=1988|pages=xlviii+629 pp.|isbn=3-88538-403-5|url=http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/|ref=harv|MR=949214|access-date=2010-04-03|archive-url=https://web.archive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/|archive-date=2010-04-01|dead-url=yes|df=}}
{{Cite book | last1=Nocedal | first1=Jorge | last2=Wright | first2=Stephen J. | title=Numerical Optimization | publisher=Springer-Verlag | location=Berlin, New York | edition=2nd | isbn=978-0-387-30303-1 | year=2006 | ref=harv | postscript=}}.

1 : Optimization algorithms and methods

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。