1282:
25:
902:
The method is useful for calculating the local minimum of a continuous but complex function, especially one without an underlying mathematical definition, because it is not necessary to take derivatives. The basic algorithm is simple; the complexity is in the linear searches along the search vectors,
392:
897:
739:
588:
213:
648:) becomes a new search vector, and is added to the end of the search vector list. Meanwhile, the search vector which contributed most to the new direction, i.e. the one which was most successful (
143:
The function must be a real-valued function of a fixed number of real-valued inputs. The caller passes in the initial point. The caller also passes in a set of initial search vectors. Typically
646:
1179:
197:
1050:
748:
448:
202:
The method minimises the function by a bi-directional search along each search vector, in turn. The bi-directional line search along each search vector can be done by
1174:
477:
421:
504:
1770:
1188:
1668:
1043:
996:
952:
Powell, M. J. D. (1964). "An efficient method for finding the minimum of a function of several variables without calculating derivatives".
1749:
1211:
42:
1263:
1124:
1231:
1019:
108:
651:
387:{\textstyle \{x_{0}+\alpha _{1}s_{1},{x}_{0}+\sum _{i=1}^{2}\alpha _{i}{s}_{i},\dots ,{x}_{0}+\sum _{i=1}^{N}\alpha _{i}{s}_{i}\}}
1342:
1036:
89:
61:
1619:
1281:
509:
46:
1727:
1347:
1663:
1631:
68:
1712:
1337:
1658:
1614:
1216:
1507:
1236:
75:
1397:
35:
1059:
593:
1582:
1444:
57:
1626:
1525:
1241:
1119:
1717:
1702:
1592:
1470:
1096:
1063:
1606:
1572:
1475:
1417:
1298:
1104:
1084:
203:
150:
928:
1653:
1480:
1392:
133:
1028:
1722:
1587:
1540:
1530:
1382:
1370:
1183:
1166:
1071:
892:{\textstyle \{s_{1},\dots ,s_{i_{d}-1},s_{i_{d}+1},\dots ,s_{N},\sum _{i=1}^{N}\alpha _{i}s_{i}\}}
1457:
1426:
1412:
1402:
1193:
899:. The algorithm iterates an arbitrary number of times until no significant improvement is made.
82:
1465:
1143:
1015:
992:
904:
207:
137:
1007:
426:
1545:
1535:
1439:
1316:
1221:
1203:
1156:
1067:
969:
961:
1561:
453:
397:
1549:
1434:
1321:
1255:
1226:
482:
140:
of a function. The function need not be differentiable, and no derivatives are taken.
1764:
1707:
1691:
1645:
1151:
984:
1732:
1114:
24:
974:
965:
129:
506:) can then be expressed as a linear combination of the search vectors i.e.
1134:
1454:
985:"Section 10.7. Direction Set (Powell's) Methods in Multidimensions"
199:) are passed in which are simply the normals aligned to each axis.
210:. Let the minima found during each bi-directional line search be
1689:
1505:
1368:
1296:
1082:
1032:
983:
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007).
18:
734:{\textstyle i_{d}=\arg \max _{i=1}^{N}|\alpha _{i}|\|s_{i}\|}
1280:
450:
is the scalar determined during bi-directional search along
741:), is deleted from the search vector list. The new set of
583:{\textstyle x_{1}=x_{0}+\sum _{i=1}^{N}\alpha _{i}s_{i}}
991:(3rd ed.). New York: Cambridge University Press.
751:
654:
596:
512:
485:
456:
429:
400:
216:
153:
1644:
1605:
1571:
1560:
1518:
1453:
1425:
1411:
1381:
1330:
1309:
1254:
1202:
1165:
1142:
1133:
1095:
49:. Unsourced material may be challenged and removed.
16:
Algorithm for finding a local minimum of a function
989:Numerical Recipes: The Art of Scientific Computing
891:
733:
640:
582:
498:
471:
442:
415:
386:
191:
675:
1012:Algorithms for minimization without derivatives
929:"Module for Powell Search Method for a Minimum"
1044:
8:
886:
752:
728:
715:
641:{\textstyle \sum _{i=1}^{N}\alpha _{i}s_{i}}
381:
217:
186:
154:
1686:
1602:
1568:
1515:
1502:
1422:
1378:
1365:
1306:
1293:
1139:
1092:
1079:
1051:
1037:
1029:
1014:. Englewood Cliffs, N.J.: Prentice-Hall.
973:
922:
920:
880:
870:
860:
849:
836:
809:
804:
783:
778:
759:
750:
722:
710:
704:
695:
689:
678:
659:
653:
632:
622:
612:
601:
595:
574:
564:
554:
543:
530:
517:
511:
490:
484:
463:
458:
455:
434:
428:
407:
402:
399:
375:
370:
363:
353:
342:
329:
324:
308:
303:
296:
286:
275:
262:
257:
247:
237:
224:
215:
180:
161:
152:
109:Learn how and when to remove this message
1285:Optimization computes maxima and minima.
916:
933:California State University, Fullerton
1481:Principal pivoting algorithm of Lemke
7:
47:adding citations to reliable sources
1771:Optimization algorithms and methods
192:{\textstyle \{s_{1},\dots ,s_{N}\}}
126:Powell's conjugate direction method
1125:Successive parabolic interpolation
423:is the initial starting point and
14:
1445:Projective algorithm of Karmarkar
1008:"Section 7.3: Powell's algorithm"
1440:Ellipsoid algorithm of Khachiyan
1343:Sequential quadratic programming
1180:Broyden–Fletcher–Goldfarb–Shanno
23:
590:. The new displacement vector (
34:needs additional citations for
1398:Reduced gradient (Frank–Wolfe)
711:
696:
1:
1728:Spiral optimization algorithm
1348:Successive linear programming
1466:Simplex algorithm of Dantzig
1338:Augmented Lagrangian methods
1787:
1006:Brent, Richard P. (1973).
903:which can be achieved via
1745:
1698:
1685:
1669:Push–relabel maximum flow
1514:
1501:
1471:Revised simplex algorithm
1377:
1364:
1305:
1292:
1278:
1091:
1078:
1194:Symmetric rank-one (SR1)
1175:Berndt–Hall–Hall–Hausman
443:{\textstyle \alpha _{i}}
1718:Parallel metaheuristics
1526:Approximation algorithm
1237:Powell's dog leg method
1189:Davidon–Fletcher–Powell
1085:Unconstrained nonlinear
1703:Evolutionary algorithm
1286:
966:10.1093/comjnl/7.2.155
893:
865:
735:
694:
642:
617:
584:
559:
500:
473:
444:
417:
388:
358:
291:
193:
1476:Criss-cross algorithm
1299:Constrained nonlinear
1284:
1105:Golden-section search
894:
845:
736:
674:
643:
597:
585:
539:
501:
474:
445:
418:
389:
338:
271:
204:Golden-section search
194:
1393:Cutting-plane method
749:
652:
594:
510:
483:
479:. The new position (
472:{\textstyle {s}_{i}}
454:
427:
416:{\textstyle {x}_{0}}
398:
214:
151:
134:Michael J. D. Powell
43:improve this article
1723:Simulated annealing
1541:Integer programming
1531:Dynamic programming
1371:Convex optimization
1232:Levenberg–Marquardt
147:search vectors (say
1403:Subgradient method
1287:
1212:Conjugate gradient
1120:Nelder–Mead method
975:10338.dmlcz/103029
889:
745:search vectors is
731:
638:
580:
499:{\textstyle x_{1}}
496:
469:
440:
413:
384:
189:
1758:
1757:
1741:
1740:
1681:
1680:
1677:
1676:
1640:
1639:
1601:
1600:
1497:
1496:
1493:
1492:
1489:
1488:
1360:
1359:
1356:
1355:
1276:
1275:
1272:
1271:
1250:
1249:
998:978-0-521-88068-8
927:Mathews, John H.
119:
118:
111:
93:
58:"Powell's method"
1778:
1687:
1603:
1569:
1546:Branch and bound
1536:Greedy algorithm
1516:
1503:
1423:
1379:
1366:
1307:
1294:
1242:Truncated Newton
1157:Wolfe conditions
1140:
1093:
1080:
1053:
1046:
1039:
1030:
1025:
1002:
979:
977:
954:Computer Journal
944:
943:
941:
939:
924:
898:
896:
895:
890:
885:
884:
875:
874:
864:
859:
841:
840:
822:
821:
814:
813:
796:
795:
788:
787:
764:
763:
740:
738:
737:
732:
727:
726:
714:
709:
708:
699:
693:
688:
664:
663:
647:
645:
644:
639:
637:
636:
627:
626:
616:
611:
589:
587:
586:
581:
579:
578:
569:
568:
558:
553:
535:
534:
522:
521:
505:
503:
502:
497:
495:
494:
478:
476:
475:
470:
468:
467:
462:
449:
447:
446:
441:
439:
438:
422:
420:
419:
414:
412:
411:
406:
393:
391:
390:
385:
380:
379:
374:
368:
367:
357:
352:
334:
333:
328:
313:
312:
307:
301:
300:
290:
285:
267:
266:
261:
252:
251:
242:
241:
229:
228:
198:
196:
195:
190:
185:
184:
166:
165:
114:
107:
103:
100:
94:
92:
51:
27:
19:
1786:
1785:
1781:
1780:
1779:
1777:
1776:
1775:
1761:
1760:
1759:
1754:
1737:
1694:
1673:
1636:
1597:
1574:
1563:
1556:
1510:
1485:
1449:
1416:
1407:
1384:
1373:
1352:
1326:
1322:Penalty methods
1317:Barrier methods
1301:
1288:
1268:
1264:Newton's method
1246:
1198:
1161:
1129:
1110:Powell's method
1087:
1074:
1057:
1022:
1005:
999:
982:
951:
948:
947:
937:
935:
926:
925:
918:
913:
876:
866:
832:
805:
800:
779:
774:
755:
747:
746:
718:
700:
655:
650:
649:
628:
618:
592:
591:
570:
560:
526:
513:
508:
507:
486:
481:
480:
457:
452:
451:
430:
425:
424:
401:
396:
395:
369:
359:
323:
302:
292:
256:
243:
233:
220:
212:
211:
176:
157:
149:
148:
122:Powell's method
115:
104:
98:
95:
52:
50:
40:
28:
17:
12:
11:
5:
1784:
1782:
1774:
1773:
1763:
1762:
1756:
1755:
1753:
1752:
1746:
1743:
1742:
1739:
1738:
1736:
1735:
1730:
1725:
1720:
1715:
1710:
1705:
1699:
1696:
1695:
1692:Metaheuristics
1690:
1683:
1682:
1679:
1678:
1675:
1674:
1672:
1671:
1666:
1664:Ford–Fulkerson
1661:
1656:
1650:
1648:
1642:
1641:
1638:
1637:
1635:
1634:
1632:Floyd–Warshall
1629:
1624:
1623:
1622:
1611:
1609:
1599:
1598:
1596:
1595:
1590:
1585:
1579:
1577:
1566:
1558:
1557:
1555:
1554:
1553:
1552:
1538:
1533:
1528:
1522:
1520:
1512:
1511:
1506:
1499:
1498:
1495:
1494:
1491:
1490:
1487:
1486:
1484:
1483:
1478:
1473:
1468:
1462:
1460:
1451:
1450:
1448:
1447:
1442:
1437:
1435:Affine scaling
1431:
1429:
1427:Interior point
1420:
1409:
1408:
1406:
1405:
1400:
1395:
1389:
1387:
1375:
1374:
1369:
1362:
1361:
1358:
1357:
1354:
1353:
1351:
1350:
1345:
1340:
1334:
1332:
1331:Differentiable
1328:
1327:
1325:
1324:
1319:
1313:
1311:
1303:
1302:
1297:
1290:
1289:
1279:
1277:
1274:
1273:
1270:
1269:
1267:
1266:
1260:
1258:
1252:
1251:
1248:
1247:
1245:
1244:
1239:
1234:
1229:
1224:
1219:
1214:
1208:
1206:
1200:
1199:
1197:
1196:
1191:
1186:
1177:
1171:
1169:
1163:
1162:
1160:
1159:
1154:
1148:
1146:
1137:
1131:
1130:
1128:
1127:
1122:
1117:
1112:
1107:
1101:
1099:
1089:
1088:
1083:
1076:
1075:
1058:
1056:
1055:
1048:
1041:
1033:
1027:
1026:
1020:
1003:
997:
980:
960:(2): 155–162.
946:
945:
915:
914:
912:
909:
905:Brent's method
888:
883:
879:
873:
869:
863:
858:
855:
852:
848:
844:
839:
835:
831:
828:
825:
820:
817:
812:
808:
803:
799:
794:
791:
786:
782:
777:
773:
770:
767:
762:
758:
754:
730:
725:
721:
717:
713:
707:
703:
698:
692:
687:
684:
681:
677:
673:
670:
667:
662:
658:
635:
631:
625:
621:
615:
610:
607:
604:
600:
577:
573:
567:
563:
557:
552:
549:
546:
542:
538:
533:
529:
525:
520:
516:
493:
489:
466:
461:
437:
433:
410:
405:
383:
378:
373:
366:
362:
356:
351:
348:
345:
341:
337:
332:
327:
322:
319:
316:
311:
306:
299:
295:
289:
284:
281:
278:
274:
270:
265:
260:
255:
250:
246:
240:
236:
232:
227:
223:
219:
208:Brent's method
188:
183:
179:
175:
172:
169:
164:
160:
156:
136:for finding a
117:
116:
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
1783:
1772:
1769:
1768:
1766:
1751:
1748:
1747:
1744:
1734:
1731:
1729:
1726:
1724:
1721:
1719:
1716:
1714:
1711:
1709:
1708:Hill climbing
1706:
1704:
1701:
1700:
1697:
1693:
1688:
1684:
1670:
1667:
1665:
1662:
1660:
1657:
1655:
1652:
1651:
1649:
1647:
1646:Network flows
1643:
1633:
1630:
1628:
1625:
1621:
1618:
1617:
1616:
1613:
1612:
1610:
1608:
1607:Shortest path
1604:
1594:
1591:
1589:
1586:
1584:
1581:
1580:
1578:
1576:
1575:spanning tree
1570:
1567:
1565:
1559:
1551:
1547:
1544:
1543:
1542:
1539:
1537:
1534:
1532:
1529:
1527:
1524:
1523:
1521:
1517:
1513:
1509:
1508:Combinatorial
1504:
1500:
1482:
1479:
1477:
1474:
1472:
1469:
1467:
1464:
1463:
1461:
1459:
1456:
1452:
1446:
1443:
1441:
1438:
1436:
1433:
1432:
1430:
1428:
1424:
1421:
1419:
1414:
1410:
1404:
1401:
1399:
1396:
1394:
1391:
1390:
1388:
1386:
1380:
1376:
1372:
1367:
1363:
1349:
1346:
1344:
1341:
1339:
1336:
1335:
1333:
1329:
1323:
1320:
1318:
1315:
1314:
1312:
1308:
1304:
1300:
1295:
1291:
1283:
1265:
1262:
1261:
1259:
1257:
1253:
1243:
1240:
1238:
1235:
1233:
1230:
1228:
1225:
1223:
1220:
1218:
1215:
1213:
1210:
1209:
1207:
1205:
1204:Other methods
1201:
1195:
1192:
1190:
1187:
1185:
1181:
1178:
1176:
1173:
1172:
1170:
1168:
1164:
1158:
1155:
1153:
1150:
1149:
1147:
1145:
1141:
1138:
1136:
1132:
1126:
1123:
1121:
1118:
1116:
1113:
1111:
1108:
1106:
1103:
1102:
1100:
1098:
1094:
1090:
1086:
1081:
1077:
1073:
1069:
1065:
1061:
1054:
1049:
1047:
1042:
1040:
1035:
1034:
1031:
1023:
1021:0-486-41998-3
1017:
1013:
1009:
1004:
1000:
994:
990:
986:
981:
976:
971:
967:
963:
959:
955:
950:
949:
934:
930:
923:
921:
917:
910:
908:
906:
900:
881:
877:
871:
867:
861:
856:
853:
850:
846:
842:
837:
833:
829:
826:
823:
818:
815:
810:
806:
801:
797:
792:
789:
784:
780:
775:
771:
768:
765:
760:
756:
744:
723:
719:
705:
701:
690:
685:
682:
679:
671:
668:
665:
660:
656:
633:
629:
623:
619:
613:
608:
605:
602:
598:
575:
571:
565:
561:
555:
550:
547:
544:
540:
536:
531:
527:
523:
518:
514:
491:
487:
464:
459:
435:
431:
408:
403:
376:
371:
364:
360:
354:
349:
346:
343:
339:
335:
330:
325:
320:
317:
314:
309:
304:
297:
293:
287:
282:
279:
276:
272:
268:
263:
258:
253:
248:
244:
238:
234:
230:
225:
221:
209:
205:
200:
181:
177:
173:
170:
167:
162:
158:
146:
141:
139:
138:local minimum
135:
131:
127:
123:
113:
110:
102:
91:
88:
84:
81:
77:
74:
70:
67:
63:
60: –
59:
55:
54:Find sources:
48:
44:
38:
37:
32:This article
30:
26:
21:
20:
1713:Local search
1659:Edmonds–Karp
1615:Bellman–Ford
1385:minimization
1217:Gauss–Newton
1167:Quasi–Newton
1152:Trust region
1109:
1060:Optimization
1011:
988:
957:
953:
936:. Retrieved
932:
901:
742:
201:
144:
142:
132:proposed by
125:
121:
120:
105:
96:
86:
79:
72:
65:
53:
41:Please help
36:verification
33:
1733:Tabu search
1144:Convergence
1115:Line search
124:, strictly
99:August 2009
1564:algorithms
1072:heuristics
1064:Algorithms
911:References
69:newspapers
1519:Paradigms
1418:quadratic
1135:Gradients
1097:Functions
868:α
847:∑
827:…
790:−
769:…
729:‖
716:‖
702:α
672:
620:α
599:∑
562:α
541:∑
432:α
361:α
340:∑
318:…
294:α
273:∑
235:α
171:…
130:algorithm
1765:Category
1750:Software
1627:Dijkstra
1458:exchange
1256:Hessians
1222:Gradient
394:, where
128:, is an
1593:Kruskal
1583:BorĹŻvka
1573:Minimum
1310:General
1068:methods
938:16 June
83:scholar
1455:Basis-
1413:Linear
1383:Convex
1227:Mirror
1184:L-BFGS
1070:, and
1018:
995:
85:
78:
71:
64:
56:
1654:Dinic
1562:Graph
90:JSTOR
76:books
1620:SPFA
1588:Prim
1182:and
1016:ISBN
993:ISBN
940:2017
62:news
1550:cut
1415:and
970:hdl
962:doi
676:max
669:arg
206:or
45:by
1767::
1066:,
1062::
1010:.
987:.
968:.
956:.
931:.
919:^
907:.
1548:/
1052:e
1045:t
1038:v
1024:.
1001:.
978:.
972::
964::
958:7
942:.
887:}
882:i
878:s
872:i
862:N
857:1
854:=
851:i
843:,
838:N
834:s
830:,
824:,
819:1
816:+
811:d
807:i
802:s
798:,
793:1
785:d
781:i
776:s
772:,
766:,
761:1
757:s
753:{
743:N
724:i
720:s
712:|
706:i
697:|
691:N
686:1
683:=
680:i
666:=
661:d
657:i
634:i
630:s
624:i
614:N
609:1
606:=
603:i
576:i
572:s
566:i
556:N
551:1
548:=
545:i
537:+
532:0
528:x
524:=
519:1
515:x
492:1
488:x
465:i
460:s
436:i
409:0
404:x
382:}
377:i
372:s
365:i
355:N
350:1
347:=
344:i
336:+
331:0
326:x
321:,
315:,
310:i
305:s
298:i
288:2
283:1
280:=
277:i
269:+
264:0
259:x
254:,
249:1
245:s
239:1
231:+
226:0
222:x
218:{
187:}
182:N
178:s
174:,
168:,
163:1
159:s
155:{
145:N
112:)
106:(
101:)
97:(
87:·
80:·
73:·
66:·
39:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
