更改
跳到导航
跳到搜索
无编辑摘要
{{Navbox with collapsible groups
| name = Optimization_algorithms
| title = [[Mathematical optimization|Optimization]]: [[Optimization algorithm|Algorithms]], [[iterative method|methods]], and [[heuristic algorithm|heuristics]]
| state = {{{state<includeonly>|uncollapsed</includeonly>}}}
| selected = {{{1|}}}
| bodyclass = hlist
| image = [[File:Max_paraboloid.svg|150x150px|right|alt=Graph of a strictly concave quadratic function with unique maximum.|Optimization computes maxima and minima.]]
| group1 = [[Nonlinear programming|Unconstrained nonlinear]]
| abbr1 = unconstrained
| list1 =
{{Navbox|child
| group1 = [[function (mathematics)|Function]]s
| list1 =
*[[Golden-section search]]
*[[Powell's method|Interpolation method]]s
*[[Line search]]
*[[Nelder–Mead method]]
*[[Successive parabolic interpolation]]
| group2 = [[gradient|Gradient]]s
| list2 =
{{Navbox|child
| group1 = [[Local convergence|Convergence]]
| list1 =
*[[Trust region]]
*[[Wolfe conditions]]
| group2 = [[Quasi-Newton method|Quasi–Newton]]
| list2 =
*[[Berndt–Hall–Hall–Hausman algorithm|Berndt–Hall–Hall–Hausman]]
*[[Broyden–Fletcher–Goldfarb–Shanno algorithm|Broyden–Fletcher–Goldfarb–Shanno]] and [[Limited-memory BFGS|L-BFGS]]
*[[Davidon–Fletcher–Powell formula|Davidon–Fletcher–Powell]]
*[[Symmetric rank-one|Symmetric rank-one (SR1)]]
| group3 = [[Iterative method|Other method]]s
| list3 =
*[[Nonlinear conjugate gradient method|Conjugate gradient]]
*[[Gauss–Newton algorithm|Gauss–Newton]]
*[[Gradient descent|Gradient]]
*[[Mirror descent|Mirror]]
*[[Levenberg–Marquardt algorithm|Levenberg–Marquardt]]
*[[Powell's dog leg method]]
*[[Truncated Newton method|Truncated Newton]]
}}
| group3 = [[Hessian matrix|Hessian]]s
| list3 =
*[[Newton's method in optimization|Newton's method]]
}}
| group2 = [[Nonlinear programming|Constrained nonlinear]]
| abbr2 = constrained
| list2 =
{{Navbox|child
| group1 = General
| list1 =
*[[Barrier function|Barrier methods]]
*[[Penalty method]]s
| group2 = Differentiable
| list2 =
*[[Augmented Lagrangian method]]s
*[[Sequential quadratic programming]]
*[[Successive linear programming]]
}}
| group3 = [[Convex optimization]]
| abbr3 = convex
| list3 =
{{Navbox|child
| group1 = [[Convex minimization|Convex<br/> minimization]]
| list1 =
*[[Cutting-plane method]]
*[[Frank–Wolfe algorithm|Reduced gradient (Frank–Wolfe)]]
*[[Subgradient method]]
| group2 = [[Linear programming|Linear]] and<br />[[Quadratic programming|quadratic]]
| list2 =
{{Navbox|child
| evenodd = swap
| group1 = [[Linear_programming#Interior_point|Interior point]]
| list1 =
*[[Affine scaling]]
*[[Ellipsoid method|Ellipsoid algorithm of Khachiyan]]
*[[Karmarkar's algorithm|Projective algorithm of Karmarkar]]
| group2 = [[Matroid|Basis-]][[exchange algorithm|exchange]]
| list2 =
*[[Simplex algorithm|Simplex algorithm of Dantzig]]
*[[Revised simplex method|Revised simplex algorithm]]
*[[Criss-cross algorithm]]
*[[Lemke's algorithm|Principal pivoting algorithm of Lemke]]
}}
}}
| group4 = [[Combinatorial optimization|Combinatorial]]
| abbr4 = combinatorial
| list4 =
{{Navbox|child
| group1 = Paradigms
| list1 =
*[[Approximation algorithm]]
*[[Dynamic programming]]
*[[Greedy algorithm]]
*[[Integer programming]]
**[[Branch and bound]]/[[Branch and cut|cut]]
| group2 = [[Graph algorithm|Graph<br/> algorithms]]
| list2 =
{{Navbox|child
| evenodd = swap
| group1 = [[Minimum spanning tree|Minimum<br/> spanning tree]]
| list1 =
*[[Borůvka's algorithm|Borůvka]]
*[[Prim's algorithm|Prim]]
*[[Kruskal's algorithm|Kruskal]]
}}
{{Navbox|child
| evenodd = swap
| group1 = [[Shortest path problem|Shortest path]]
| list1 =
*[[Bellman–Ford algorithm|Bellman–Ford]]
**[[Shortest Path Faster Algorithm|SPFA]]
*[[Dijkstra's algorithm|Dijkstra]]
*[[Floyd–Warshall algorithm|Floyd–Warshall]]
}}
| group3 = [[Flow network|Network flows]]
| list3 =
*[[Dinic's algorithm|Dinic]]
*[[Edmonds–Karp algorithm|Edmonds–Karp]]
*[[Ford–Fulkerson algorithm|Ford–Fulkerson]]
*[[Push–relabel maximum flow algorithm|Push–relabel maximum flow]]
}}
| group5 = [[Metaheuristic]]s
| abbr5 = heuristic
| list5 =
*[[Evolutionary algorithm]]
*[[Hill climbing]]
*[[local search (optimization)|Local search]]
*[[Simulated annealing]]
*[[Tabu search]]
| below =
*[[Comparison of optimization software|Software]]
}}<noinclude>
<!-- Add categories and interwikis to the /doc subpage, not here! -->
<!-- PLEASE ADD CATEGORIES AND INTERWIKIS AT THE BOTTOM OF THIS PAGE -->
{{documentation}}
</noinclude>
| name = Optimization_algorithms
| title = [[Mathematical optimization|Optimization]]: [[Optimization algorithm|Algorithms]], [[iterative method|methods]], and [[heuristic algorithm|heuristics]]
| state = {{{state<includeonly>|uncollapsed</includeonly>}}}
| selected = {{{1|}}}
| bodyclass = hlist
| image = [[File:Max_paraboloid.svg|150x150px|right|alt=Graph of a strictly concave quadratic function with unique maximum.|Optimization computes maxima and minima.]]
| group1 = [[Nonlinear programming|Unconstrained nonlinear]]
| abbr1 = unconstrained
| list1 =
{{Navbox|child
| group1 = [[function (mathematics)|Function]]s
| list1 =
*[[Golden-section search]]
*[[Powell's method|Interpolation method]]s
*[[Line search]]
*[[Nelder–Mead method]]
*[[Successive parabolic interpolation]]
| group2 = [[gradient|Gradient]]s
| list2 =
{{Navbox|child
| group1 = [[Local convergence|Convergence]]
| list1 =
*[[Trust region]]
*[[Wolfe conditions]]
| group2 = [[Quasi-Newton method|Quasi–Newton]]
| list2 =
*[[Berndt–Hall–Hall–Hausman algorithm|Berndt–Hall–Hall–Hausman]]
*[[Broyden–Fletcher–Goldfarb–Shanno algorithm|Broyden–Fletcher–Goldfarb–Shanno]] and [[Limited-memory BFGS|L-BFGS]]
*[[Davidon–Fletcher–Powell formula|Davidon–Fletcher–Powell]]
*[[Symmetric rank-one|Symmetric rank-one (SR1)]]
| group3 = [[Iterative method|Other method]]s
| list3 =
*[[Nonlinear conjugate gradient method|Conjugate gradient]]
*[[Gauss–Newton algorithm|Gauss–Newton]]
*[[Gradient descent|Gradient]]
*[[Mirror descent|Mirror]]
*[[Levenberg–Marquardt algorithm|Levenberg–Marquardt]]
*[[Powell's dog leg method]]
*[[Truncated Newton method|Truncated Newton]]
}}
| group3 = [[Hessian matrix|Hessian]]s
| list3 =
*[[Newton's method in optimization|Newton's method]]
}}
| group2 = [[Nonlinear programming|Constrained nonlinear]]
| abbr2 = constrained
| list2 =
{{Navbox|child
| group1 = General
| list1 =
*[[Barrier function|Barrier methods]]
*[[Penalty method]]s
| group2 = Differentiable
| list2 =
*[[Augmented Lagrangian method]]s
*[[Sequential quadratic programming]]
*[[Successive linear programming]]
}}
| group3 = [[Convex optimization]]
| abbr3 = convex
| list3 =
{{Navbox|child
| group1 = [[Convex minimization|Convex<br/> minimization]]
| list1 =
*[[Cutting-plane method]]
*[[Frank–Wolfe algorithm|Reduced gradient (Frank–Wolfe)]]
*[[Subgradient method]]
| group2 = [[Linear programming|Linear]] and<br />[[Quadratic programming|quadratic]]
| list2 =
{{Navbox|child
| evenodd = swap
| group1 = [[Linear_programming#Interior_point|Interior point]]
| list1 =
*[[Affine scaling]]
*[[Ellipsoid method|Ellipsoid algorithm of Khachiyan]]
*[[Karmarkar's algorithm|Projective algorithm of Karmarkar]]
| group2 = [[Matroid|Basis-]][[exchange algorithm|exchange]]
| list2 =
*[[Simplex algorithm|Simplex algorithm of Dantzig]]
*[[Revised simplex method|Revised simplex algorithm]]
*[[Criss-cross algorithm]]
*[[Lemke's algorithm|Principal pivoting algorithm of Lemke]]
}}
}}
| group4 = [[Combinatorial optimization|Combinatorial]]
| abbr4 = combinatorial
| list4 =
{{Navbox|child
| group1 = Paradigms
| list1 =
*[[Approximation algorithm]]
*[[Dynamic programming]]
*[[Greedy algorithm]]
*[[Integer programming]]
**[[Branch and bound]]/[[Branch and cut|cut]]
| group2 = [[Graph algorithm|Graph<br/> algorithms]]
| list2 =
{{Navbox|child
| evenodd = swap
| group1 = [[Minimum spanning tree|Minimum<br/> spanning tree]]
| list1 =
*[[Borůvka's algorithm|Borůvka]]
*[[Prim's algorithm|Prim]]
*[[Kruskal's algorithm|Kruskal]]
}}
{{Navbox|child
| evenodd = swap
| group1 = [[Shortest path problem|Shortest path]]
| list1 =
*[[Bellman–Ford algorithm|Bellman–Ford]]
**[[Shortest Path Faster Algorithm|SPFA]]
*[[Dijkstra's algorithm|Dijkstra]]
*[[Floyd–Warshall algorithm|Floyd–Warshall]]
}}
| group3 = [[Flow network|Network flows]]
| list3 =
*[[Dinic's algorithm|Dinic]]
*[[Edmonds–Karp algorithm|Edmonds–Karp]]
*[[Ford–Fulkerson algorithm|Ford–Fulkerson]]
*[[Push–relabel maximum flow algorithm|Push–relabel maximum flow]]
}}
| group5 = [[Metaheuristic]]s
| abbr5 = heuristic
| list5 =
*[[Evolutionary algorithm]]
*[[Hill climbing]]
*[[local search (optimization)|Local search]]
*[[Simulated annealing]]
*[[Tabu search]]
| below =
*[[Comparison of optimization software|Software]]
}}<noinclude>
<!-- Add categories and interwikis to the /doc subpage, not here! -->
<!-- PLEASE ADD CATEGORIES AND INTERWIKIS AT THE BOTTOM OF THIS PAGE -->
{{documentation}}
</noinclude>