1658:
1339:
2679:
252:
1653:{\displaystyle {\begin{aligned}f(\mathbf {x} ^{*})&\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )\\&\geq \min _{\mathbf {y} \in D}\left\{f(\mathbf {x} )+(\mathbf {y} -\mathbf {x} )^{T}\nabla f(\mathbf {x} )\right\}\\&=f(\mathbf {x} )-\mathbf {x} ^{T}\nabla f(\mathbf {x} )+\min _{\mathbf {y} \in D}\mathbf {y} ^{T}\nabla f(\mathbf {x} )\end{aligned}}}
1922:
1309:
1169:
836:
704:
1927:
Such lower bounds on the unknown optimal value are important in practice because they can be used as a stopping criterion, and give an efficient certificate of the approximation quality in every iteration, since always
938:
The iterations of the algorithm can always be represented as a sparse convex combination of the extreme points of the feasible set, which has helped to the popularity of the algorithm for sparse greedy optimization in
2001:
1072:
437:
157:
887:
back to the feasible set in each iteration, the Frank–Wolfe algorithm only needs the solution of a convex problem over the same set in each iteration, and automatically stays in the feasible set.
1344:
607:
2150:
1781:
471:
240:
2576:
1206:
2046:
736:
530:
317:
1690:
1201:
1080:
381:
868:
752:
206:
1773:
554:
341:
108:
287:
1331:
2447:
2571:
627:
1000:
925:
2073:
1737:
1710:
1028:
500:
3167:
2585:
632:
3065:
2440:
2385:
2328:
1931:
3146:
2608:
1002:
can not be improved in general, faster convergence can be obtained for special problem classes, such as some strongly convex problems.
2660:
2521:
2628:
2739:
2433:
1037:
389:
3016:
2678:
890:
The convergence of the Frank–Wolfe algorithm is sublinear in general: the error in the objective function to the optimum is
124:
3124:
2744:
1917:{\displaystyle l_{k}:=\max(l_{k-1},f(\mathbf {x} _{k})+(\mathbf {s} _{k}-\mathbf {x} _{k})^{T}\nabla f(\mathbf {x} _{k}))}
958:
If the feasible set is given by a set of linear constraints, then the subproblem to be solved in each iteration becomes a
935:
with respect to some norm. The same convergence rate can also be shown if the sub-problems are only solved approximately.
3060:
3028:
3177:
571:
71:
2078:
3109:
2734:
3055:
3011:
2613:
444:
213:
3172:
2904:
2633:
1663:
The latter optimization problem is solved in every iteration of the Frank–Wolfe algorithm, therefore the solution
3182:
2456:
2420:
1304:{\displaystyle f(\mathbf {x} ^{*})\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )}
41:
38:
2979:
884:
78:
of the objective function, and moves towards a minimizer of this linear function (taken over the same domain).
48:
2841:
3023:
2922:
2638:
164:
2516:
3114:
3099:
2989:
2867:
2493:
2460:
2264:
2013:
1164:{\displaystyle f(\mathbf {y} )\geq f(\mathbf {x} )+(\mathbf {y} -\mathbf {x} )^{T}\nabla f(\mathbf {x} )}
709:
3003:
2969:
2872:
2814:
2695:
2501:
2481:
831:{\displaystyle \mathbf {x} _{k+1}\leftarrow \mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k})}
505:
292:
2365:
1666:
1177:
357:
3050:
2877:
2789:
2292:
Fukushima, M. (1984). "A modified Frank-Wolfe algorithm for solving the traffic assignment problem".
932:
841:
180:
171:
167:
75:
2425:
2269:
1742:
535:
322:
89:
3119:
2984:
2937:
2927:
2779:
2767:
2580:
2563:
2468:
266:
51:
1314:
2854:
2823:
2809:
2799:
2590:
959:
2506:
2349:
2255:
Clarkson, K. L. (2010). "Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm".
2862:
2540:
2381:
2324:
952:
944:
612:
2942:
2932:
2836:
2713:
2618:
2600:
2553:
2464:
2301:
2274:
2235:
2204:
2177:
968:
940:
893:
880:
67:
35:
2051:
1715:
478:(Interpretation: Minimize the linear approximation of the problem given by the first-order
2958:
2377:
1031:
160:
2946:
2831:
2718:
2652:
2623:
1695:
1013:
485:
251:
3161:
3104:
3088:
2305:
2240:
2223:
2181:
479:
111:
17:
3042:
2548:
948:
118:
3129:
2511:
2007:
2408:
699:{\displaystyle f(\mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k}))}
114:
2278:
44:
2208:
2409:
Marguerite Frank giving a personal account of the history of the algorithm
2168:
Levitin, E. S.; Polyak, B. T. (1966). "Constrained minimization methods".
2531:
2354:
Journal of
Machine Learning Research: Workshop and Conference Proceedings
2851:
2195:
Frank, M.; Wolfe, P. (1956). "An algorithm for quadratic programming".
74:
in 1956. In each iteration, the Frank–Wolfe algorithm considers a
2402:
1996:{\displaystyle l_{k}\leq f(\mathbf {x} ^{*})\leq f(\mathbf {x} _{k})}
2350:"Revisiting Frank–Wolfe: Projection-Free Sparse Convex Optimization"
250:
2224:"Conditional gradient algorithms with open loop step size rules"
3086:
2902:
2765:
2693:
2479:
2429:
1712:-th iteration can be used to determine increasing lower bounds
2677:
1059:
1006:
Lower bounds on the solution value, and primal-dual analysis
541:
458:
328:
227:
136:
95:
1067:{\displaystyle \mathbf {x} ,\mathbf {y} \in {\mathcal {D}}}
432:{\displaystyle \mathbf {s} ^{T}\nabla f(\mathbf {x} _{k})}
2170:
USSR Computational
Mathematics and Mathematical Physics
152:{\displaystyle f\colon {\mathcal {D}}\to \mathbb {R} }
2081:
2054:
2016:
1934:
1784:
1745:
1718:
1698:
1669:
1342:
1317:
1311:. The best lower bound with respect to a given point
1209:
1180:
1083:
1040:
1016:
971:
947:
problems, as well as for example the optimization of
896:
844:
755:
712:
635:
615:
574:
538:
508:
488:
447:
392:
360:
325:
295:
269:
216:
183:
127:
92:
3041:
3002:
2968:
2957:
2915:
2850:
2822:
2808:
2778:
2727:
2706:
2651:
2599:
2562:
2539:
2530:
2492:
1174:This also holds for the (unknown) optimal solution
2144:
2067:
2040:
1995:
1916:
1767:
1731:
1704:
1684:
1652:
1325:
1303:
1195:
1163:
1066:
1022:
994:
919:
862:
830:
730:
698:
621:
602:{\displaystyle \alpha \leftarrow {\frac {2}{k+2}}}
601:
548:
524:
494:
465:
431:
375:
335:
311:
281:
234:
200:
151:
102:
2228:Journal of Mathematical Analysis and Applications
2145:{\displaystyle f(\mathbf {x} _{k})-l_{k}=O(1/k).}
2075:, decreases with the same convergence rate, i.e.
521:
308:
1798:
1600:
1453:
2294:Transportation Research Part B: Methodological
466:{\displaystyle \mathbf {s} \in {\mathcal {D}}}
235:{\displaystyle \mathbf {x} \in {\mathcal {D}}}
2441:
8:
2372:Nocedal, Jorge; Wright, Stephen J. (2006).
1692:of the direction-finding subproblem of the
965:While the worst-case convergence rate with
3083:
2999:
2965:
2912:
2899:
2819:
2775:
2762:
2703:
2690:
2536:
2489:
2476:
2448:
2434:
2426:
2006:It has been shown that this corresponding
2268:
2239:
2128:
2110:
2094:
2089:
2080:
2059:
2053:
2029:
2024:
2015:
1984:
1979:
1960:
1955:
1939:
1933:
1902:
1897:
1881:
1871:
1866:
1856:
1851:
1835:
1830:
1808:
1789:
1783:
1750:
1744:
1723:
1717:
1697:
1676:
1671:
1668:
1638:
1623:
1618:
1604:
1603:
1588:
1573:
1568:
1556:
1527:
1512:
1503:
1495:
1481:
1457:
1456:
1434:
1419:
1410:
1401:
1396:
1381:
1359:
1354:
1343:
1341:
1318:
1316:
1293:
1278:
1269:
1260:
1255:
1240:
1222:
1217:
1208:
1187:
1182:
1179:
1153:
1138:
1129:
1121:
1107:
1090:
1082:
1058:
1057:
1049:
1041:
1039:
1015:
981:
970:
906:
895:
843:
819:
814:
804:
799:
783:
778:
762:
757:
754:
711:
684:
679:
669:
664:
648:
643:
634:
614:
581:
573:
540:
539:
537:
515:
510:
507:
487:
457:
456:
448:
446:
420:
415:
399:
394:
391:
367:
362:
359:
327:
326:
324:
302:
297:
294:
268:
226:
225:
217:
215:
190:
182:
145:
144:
135:
134:
126:
94:
93:
91:
2682:Optimization computes maxima and minima.
66:, the method was originally proposed by
2160:
931:iterations, so long as the gradient is
883:for constrained optimization require a
170:. The Frank–Wolfe algorithm solves the
2878:Principal pivoting algorithm of Lemke
2405:: a survey of Frank–Wolfe algorithms.
2222:Dunn, J. C.; Harshbarger, S. (1978).
7:
3168:Optimization algorithms and methods
2041:{\displaystyle f(\mathbf {x} _{k})}
731:{\displaystyle 0\leq \alpha \leq 1}
255:A step of the Frank–Wolfe algorithm
2522:Successive parabolic interpolation
2403:https://conditional-gradients.org/
2376:(2nd ed.). Berlin, New York:
2323:. Athena Scientific. p. 215.
2197:Naval Research Logistics Quarterly
1887:
1762:
1629:
1579:
1518:
1425:
1284:
1144:
525:{\displaystyle \mathbf {x} _{k}\!}
405:
312:{\displaystyle \mathbf {x} _{0}\!}
25:
2842:Projective algorithm of Karmarkar
2010:, that is the difference between
1739:during each iteration by setting
2837:Ellipsoid algorithm of Khachiyan
2740:Sequential quadratic programming
2577:Broyden–Fletcher–Goldfarb–Shanno
2090:
2025:
1980:
1956:
1898:
1867:
1852:
1831:
1685:{\displaystyle \mathbf {s} _{k}}
1672:
1639:
1619:
1605:
1589:
1569:
1557:
1528:
1504:
1496:
1482:
1458:
1435:
1411:
1397:
1382:
1355:
1319:
1294:
1270:
1256:
1241:
1218:
1196:{\displaystyle \mathbf {x} ^{*}}
1183:
1154:
1130:
1122:
1108:
1091:
1050:
1042:
879:While competing methods such as
815:
800:
779:
758:
680:
665:
644:
511:
449:
416:
395:
376:{\displaystyle \mathbf {s} _{k}}
363:
298:
218:
191:
863:{\displaystyle k\leftarrow k+1}
201:{\displaystyle f(\mathbf {x} )}
2795:Reduced gradient (Frank–Wolfe)
2257:ACM Transactions on Algorithms
2136:
2122:
2100:
2085:
2035:
2020:
1990:
1975:
1966:
1951:
1911:
1908:
1893:
1878:
1847:
1841:
1826:
1801:
1768:{\displaystyle l_{0}=-\infty }
1643:
1635:
1593:
1585:
1561:
1553:
1532:
1524:
1509:
1492:
1486:
1478:
1439:
1431:
1416:
1392:
1386:
1378:
1365:
1350:
1298:
1290:
1275:
1251:
1245:
1237:
1228:
1213:
1158:
1150:
1135:
1118:
1112:
1104:
1095:
1087:
989:
975:
914:
900:
848:
825:
795:
774:
693:
690:
660:
639:
578:
549:{\displaystyle {\mathcal {D}}}
426:
411:
336:{\displaystyle {\mathcal {D}}}
273:
195:
187:
141:
103:{\displaystyle {\mathcal {D}}}
1:
3125:Spiral optimization algorithm
2745:Successive linear programming
352:Direction-finding subproblem:
282:{\displaystyle k\leftarrow 0}
2863:Simplex algorithm of Dantzig
2735:Augmented Lagrangian methods
2306:10.1016/0191-2615(84)90029-8
2241:10.1016/0022-247X(78)90137-3
2182:10.1016/0041-5553(66)90114-5
1326:{\displaystyle \mathbf {x} }
64:convex combination algorithm
2319:Bertsekas, Dimitri (1999).
532:constrained to stay within
56:conditional gradient method
3199:
60:reduced gradient algorithm
3142:
3095:
3082:
3066:Push–relabel maximum flow
2911:
2898:
2868:Revised simplex algorithm
2774:
2761:
2702:
2689:
2675:
2488:
2475:
2421:Proximal gradient methods
2366:The Frank–Wolfe algorithm
2591:Symmetric rank-one (SR1)
2572:Berndt–Hall–Hall–Hausman
609:, or alternatively find
566:Step size determination:
3115:Parallel metaheuristics
2923:Approximation algorithm
2634:Powell's dog leg method
2586:Davidon–Fletcher–Powell
2482:Unconstrained nonlinear
2279:10.1145/1824777.1824783
953:transportation networks
622:{\displaystyle \alpha }
3100:Evolutionary algorithm
2683:
2374:Numerical Optimization
2348:Jaggi, Martin (2013).
2209:10.1002/nav.3800030109
2146:
2069:
2042:
1997:
1918:
1769:
1733:
1706:
1686:
1654:
1327:
1305:
1197:
1165:
1068:
1024:
996:
995:{\displaystyle O(1/k)}
921:
920:{\displaystyle O(1/k)}
864:
832:
732:
700:
623:
603:
550:
526:
496:
467:
433:
377:
337:
313:
283:
256:
236:
202:
153:
104:
27:Optimization algorithm
2873:Criss-cross algorithm
2696:Constrained nonlinear
2681:
2502:Golden-section search
2321:Nonlinear Programming
2147:
2070:
2068:{\displaystyle l_{k}}
2043:
1998:
1919:
1770:
1734:
1732:{\displaystyle l_{k}}
1707:
1687:
1655:
1328:
1306:
1198:
1166:
1069:
1034:, for any two points
1025:
997:
922:
865:
833:
733:
701:
624:
604:
551:
527:
497:
468:
434:
378:
338:
314:
284:
254:
237:
203:
154:
105:
32:Frank–Wolfe algorithm
18:Frank-Wolfe algorithm
2790:Cutting-plane method
2079:
2052:
2048:and the lower bound
2014:
1932:
1782:
1743:
1716:
1696:
1667:
1340:
1315:
1207:
1178:
1081:
1038:
1014:
969:
933:Lipschitz continuous
894:
842:
753:
710:
633:
613:
572:
536:
506:
486:
480:Taylor approximation
445:
390:
358:
323:
293:
267:
214:
181:
172:optimization problem
168:real-valued function
125:
90:
76:linear approximation
54:. Also known as the
3178:First order methods
3120:Simulated annealing
2938:Integer programming
2928:Dynamic programming
2768:Convex optimization
2629:Levenberg–Marquardt
52:convex optimization
2800:Subgradient method
2684:
2609:Conjugate gradient
2517:Nelder–Mead method
2142:
2065:
2038:
1993:
1914:
1765:
1729:
1702:
1682:
1650:
1648:
1616:
1469:
1323:
1301:
1193:
1161:
1064:
1020:
992:
949:minimum–cost flows
917:
860:
828:
728:
696:
619:
599:
546:
522:
492:
463:
429:
373:
333:
309:
279:
257:
232:
198:
149:
100:
3173:Iterative methods
3155:
3154:
3138:
3137:
3078:
3077:
3074:
3073:
3037:
3036:
2998:
2997:
2894:
2893:
2890:
2889:
2886:
2885:
2757:
2756:
2753:
2752:
2673:
2672:
2669:
2668:
2647:
2646:
2387:978-0-387-30303-1
2330:978-1-886529-00-7
1705:{\displaystyle k}
1599:
1452:
1023:{\displaystyle f}
945:signal processing
870:and go to Step 1.
597:
495:{\displaystyle f}
82:Problem statement
16:(Redirected from
3190:
3183:Gradient methods
3084:
3000:
2966:
2943:Branch and bound
2933:Greedy algorithm
2913:
2900:
2820:
2776:
2763:
2704:
2691:
2639:Truncated Newton
2554:Wolfe conditions
2537:
2490:
2477:
2450:
2443:
2436:
2427:
2391:
2362:(Overview paper)
2361:
2335:
2334:
2316:
2310:
2309:
2289:
2283:
2282:
2272:
2252:
2246:
2245:
2243:
2219:
2213:
2212:
2192:
2186:
2185:
2165:
2151:
2149:
2148:
2143:
2132:
2115:
2114:
2099:
2098:
2093:
2074:
2072:
2071:
2066:
2064:
2063:
2047:
2045:
2044:
2039:
2034:
2033:
2028:
2002:
2000:
1999:
1994:
1989:
1988:
1983:
1965:
1964:
1959:
1944:
1943:
1923:
1921:
1920:
1915:
1907:
1906:
1901:
1886:
1885:
1876:
1875:
1870:
1861:
1860:
1855:
1840:
1839:
1834:
1819:
1818:
1794:
1793:
1774:
1772:
1771:
1766:
1755:
1754:
1738:
1736:
1735:
1730:
1728:
1727:
1711:
1709:
1708:
1703:
1691:
1689:
1688:
1683:
1681:
1680:
1675:
1659:
1657:
1656:
1651:
1649:
1642:
1628:
1627:
1622:
1615:
1608:
1592:
1578:
1577:
1572:
1560:
1543:
1539:
1535:
1531:
1517:
1516:
1507:
1499:
1485:
1468:
1461:
1445:
1438:
1424:
1423:
1414:
1406:
1405:
1400:
1385:
1364:
1363:
1358:
1332:
1330:
1329:
1324:
1322:
1310:
1308:
1307:
1302:
1297:
1283:
1282:
1273:
1265:
1264:
1259:
1244:
1227:
1226:
1221:
1202:
1200:
1199:
1194:
1192:
1191:
1186:
1170:
1168:
1167:
1162:
1157:
1143:
1142:
1133:
1125:
1111:
1094:
1073:
1071:
1070:
1065:
1063:
1062:
1053:
1045:
1029:
1027:
1026:
1021:
1001:
999:
998:
993:
985:
941:machine learning
926:
924:
923:
918:
910:
881:gradient descent
869:
867:
866:
861:
837:
835:
834:
829:
824:
823:
818:
809:
808:
803:
788:
787:
782:
773:
772:
761:
737:
735:
734:
729:
705:
703:
702:
697:
689:
688:
683:
674:
673:
668:
653:
652:
647:
628:
626:
625:
620:
608:
606:
605:
600:
598:
596:
582:
555:
553:
552:
547:
545:
544:
531:
529:
528:
523:
520:
519:
514:
501:
499:
498:
493:
472:
470:
469:
464:
462:
461:
452:
438:
436:
435:
430:
425:
424:
419:
404:
403:
398:
382:
380:
379:
374:
372:
371:
366:
342:
340:
339:
334:
332:
331:
319:be any point in
318:
316:
315:
310:
307:
306:
301:
288:
286:
285:
280:
241:
239:
238:
233:
231:
230:
221:
207:
205:
204:
199:
194:
158:
156:
155:
150:
148:
140:
139:
109:
107:
106:
101:
99:
98:
68:Marguerite Frank
21:
3198:
3197:
3193:
3192:
3191:
3189:
3188:
3187:
3158:
3157:
3156:
3151:
3134:
3091:
3070:
3033:
2994:
2971:
2960:
2953:
2907:
2882:
2846:
2813:
2804:
2781:
2770:
2749:
2723:
2719:Penalty methods
2714:Barrier methods
2698:
2685:
2665:
2661:Newton's method
2643:
2595:
2558:
2526:
2507:Powell's method
2484:
2471:
2454:
2417:
2399:
2388:
2378:Springer-Verlag
2371:
2347:
2344:
2339:
2338:
2331:
2318:
2317:
2313:
2291:
2290:
2286:
2270:10.1.1.145.9299
2254:
2253:
2249:
2221:
2220:
2216:
2203:(1–2): 95–110.
2194:
2193:
2189:
2167:
2166:
2162:
2157:
2106:
2088:
2077:
2076:
2055:
2050:
2049:
2023:
2012:
2011:
1978:
1954:
1935:
1930:
1929:
1896:
1877:
1865:
1850:
1829:
1804:
1785:
1780:
1779:
1746:
1741:
1740:
1719:
1714:
1713:
1694:
1693:
1670:
1665:
1664:
1647:
1646:
1617:
1567:
1541:
1540:
1508:
1474:
1470:
1443:
1442:
1415:
1395:
1368:
1353:
1338:
1337:
1313:
1312:
1274:
1254:
1216:
1205:
1204:
1181:
1176:
1175:
1134:
1079:
1078:
1036:
1035:
1012:
1011:
1008:
967:
966:
892:
891:
885:projection step
877:
840:
839:
813:
798:
777:
756:
751:
750:
708:
707:
678:
663:
642:
631:
630:
629:that minimizes
611:
610:
586:
570:
569:
534:
533:
509:
504:
503:
484:
483:
443:
442:
414:
393:
388:
387:
361:
356:
355:
321:
320:
296:
291:
290:
265:
264:
261:Initialization:
249:
212:
211:
179:
178:
123:
122:
88:
87:
84:
28:
23:
22:
15:
12:
11:
5:
3196:
3194:
3186:
3185:
3180:
3175:
3170:
3160:
3159:
3153:
3152:
3150:
3149:
3143:
3140:
3139:
3136:
3135:
3133:
3132:
3127:
3122:
3117:
3112:
3107:
3102:
3096:
3093:
3092:
3089:Metaheuristics
3087:
3080:
3079:
3076:
3075:
3072:
3071:
3069:
3068:
3063:
3061:Ford–Fulkerson
3058:
3053:
3047:
3045:
3039:
3038:
3035:
3034:
3032:
3031:
3029:Floyd–Warshall
3026:
3021:
3020:
3019:
3008:
3006:
2996:
2995:
2993:
2992:
2987:
2982:
2976:
2974:
2963:
2955:
2954:
2952:
2951:
2950:
2949:
2935:
2930:
2925:
2919:
2917:
2909:
2908:
2903:
2896:
2895:
2892:
2891:
2888:
2887:
2884:
2883:
2881:
2880:
2875:
2870:
2865:
2859:
2857:
2848:
2847:
2845:
2844:
2839:
2834:
2832:Affine scaling
2828:
2826:
2824:Interior point
2817:
2806:
2805:
2803:
2802:
2797:
2792:
2786:
2784:
2772:
2771:
2766:
2759:
2758:
2755:
2754:
2751:
2750:
2748:
2747:
2742:
2737:
2731:
2729:
2728:Differentiable
2725:
2724:
2722:
2721:
2716:
2710:
2708:
2700:
2699:
2694:
2687:
2686:
2676:
2674:
2671:
2670:
2667:
2666:
2664:
2663:
2657:
2655:
2649:
2648:
2645:
2644:
2642:
2641:
2636:
2631:
2626:
2621:
2616:
2611:
2605:
2603:
2597:
2596:
2594:
2593:
2588:
2583:
2574:
2568:
2566:
2560:
2559:
2557:
2556:
2551:
2545:
2543:
2534:
2528:
2527:
2525:
2524:
2519:
2514:
2509:
2504:
2498:
2496:
2486:
2485:
2480:
2473:
2472:
2455:
2453:
2452:
2445:
2438:
2430:
2424:
2423:
2416:
2413:
2412:
2411:
2406:
2398:
2397:External links
2395:
2394:
2393:
2386:
2369:
2363:
2343:
2340:
2337:
2336:
2329:
2311:
2300:(2): 169–177.
2284:
2247:
2214:
2187:
2159:
2158:
2156:
2153:
2141:
2138:
2135:
2131:
2127:
2124:
2121:
2118:
2113:
2109:
2105:
2102:
2097:
2092:
2087:
2084:
2062:
2058:
2037:
2032:
2027:
2022:
2019:
1992:
1987:
1982:
1977:
1974:
1971:
1968:
1963:
1958:
1953:
1950:
1947:
1942:
1938:
1925:
1924:
1913:
1910:
1905:
1900:
1895:
1892:
1889:
1884:
1880:
1874:
1869:
1864:
1859:
1854:
1849:
1846:
1843:
1838:
1833:
1828:
1825:
1822:
1817:
1814:
1811:
1807:
1803:
1800:
1797:
1792:
1788:
1764:
1761:
1758:
1753:
1749:
1726:
1722:
1701:
1679:
1674:
1661:
1660:
1645:
1641:
1637:
1634:
1631:
1626:
1621:
1614:
1611:
1607:
1602:
1598:
1595:
1591:
1587:
1584:
1581:
1576:
1571:
1566:
1563:
1559:
1555:
1552:
1549:
1546:
1544:
1542:
1538:
1534:
1530:
1526:
1523:
1520:
1515:
1511:
1506:
1502:
1498:
1494:
1491:
1488:
1484:
1480:
1477:
1473:
1467:
1464:
1460:
1455:
1451:
1448:
1446:
1444:
1441:
1437:
1433:
1430:
1427:
1422:
1418:
1413:
1409:
1404:
1399:
1394:
1391:
1388:
1384:
1380:
1377:
1374:
1371:
1369:
1367:
1362:
1357:
1352:
1349:
1346:
1345:
1321:
1300:
1296:
1292:
1289:
1286:
1281:
1277:
1272:
1268:
1263:
1258:
1253:
1250:
1247:
1243:
1239:
1236:
1233:
1230:
1225:
1220:
1215:
1212:
1190:
1185:
1172:
1171:
1160:
1156:
1152:
1149:
1146:
1141:
1137:
1132:
1128:
1124:
1120:
1117:
1114:
1110:
1106:
1103:
1100:
1097:
1093:
1089:
1086:
1061:
1056:
1052:
1048:
1044:
1019:
1007:
1004:
991:
988:
984:
980:
977:
974:
960:linear program
916:
913:
909:
905:
902:
899:
876:
873:
872:
871:
859:
856:
853:
850:
847:
827:
822:
817:
812:
807:
802:
797:
794:
791:
786:
781:
776:
771:
768:
765:
760:
740:
739:
727:
724:
721:
718:
715:
695:
692:
687:
682:
677:
672:
667:
662:
659:
656:
651:
646:
641:
638:
618:
595:
592:
589:
585:
580:
577:
559:
558:
543:
518:
513:
491:
475:
474:
473:
460:
455:
451:
439:
428:
423:
418:
413:
410:
407:
402:
397:
370:
365:
345:
344:
330:
305:
300:
278:
275:
272:
248:
245:
244:
243:
229:
224:
220:
208:
197:
193:
189:
186:
165:differentiable
147:
143:
138:
133:
130:
97:
83:
80:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
3195:
3184:
3181:
3179:
3176:
3174:
3171:
3169:
3166:
3165:
3163:
3148:
3145:
3144:
3141:
3131:
3128:
3126:
3123:
3121:
3118:
3116:
3113:
3111:
3108:
3106:
3105:Hill climbing
3103:
3101:
3098:
3097:
3094:
3090:
3085:
3081:
3067:
3064:
3062:
3059:
3057:
3054:
3052:
3049:
3048:
3046:
3044:
3043:Network flows
3040:
3030:
3027:
3025:
3022:
3018:
3015:
3014:
3013:
3010:
3009:
3007:
3005:
3004:Shortest path
3001:
2991:
2988:
2986:
2983:
2981:
2978:
2977:
2975:
2973:
2972:spanning tree
2967:
2964:
2962:
2956:
2948:
2944:
2941:
2940:
2939:
2936:
2934:
2931:
2929:
2926:
2924:
2921:
2920:
2918:
2914:
2910:
2906:
2905:Combinatorial
2901:
2897:
2879:
2876:
2874:
2871:
2869:
2866:
2864:
2861:
2860:
2858:
2856:
2853:
2849:
2843:
2840:
2838:
2835:
2833:
2830:
2829:
2827:
2825:
2821:
2818:
2816:
2811:
2807:
2801:
2798:
2796:
2793:
2791:
2788:
2787:
2785:
2783:
2777:
2773:
2769:
2764:
2760:
2746:
2743:
2741:
2738:
2736:
2733:
2732:
2730:
2726:
2720:
2717:
2715:
2712:
2711:
2709:
2705:
2701:
2697:
2692:
2688:
2680:
2662:
2659:
2658:
2656:
2654:
2650:
2640:
2637:
2635:
2632:
2630:
2627:
2625:
2622:
2620:
2617:
2615:
2612:
2610:
2607:
2606:
2604:
2602:
2601:Other methods
2598:
2592:
2589:
2587:
2584:
2582:
2578:
2575:
2573:
2570:
2569:
2567:
2565:
2561:
2555:
2552:
2550:
2547:
2546:
2544:
2542:
2538:
2535:
2533:
2529:
2523:
2520:
2518:
2515:
2513:
2510:
2508:
2505:
2503:
2500:
2499:
2497:
2495:
2491:
2487:
2483:
2478:
2474:
2470:
2466:
2462:
2458:
2451:
2446:
2444:
2439:
2437:
2432:
2431:
2428:
2422:
2419:
2418:
2414:
2410:
2407:
2404:
2401:
2400:
2396:
2389:
2383:
2379:
2375:
2370:
2367:
2364:
2360:(1): 427–435.
2359:
2355:
2351:
2346:
2345:
2341:
2332:
2326:
2322:
2315:
2312:
2307:
2303:
2299:
2295:
2288:
2285:
2280:
2276:
2271:
2266:
2262:
2258:
2251:
2248:
2242:
2237:
2233:
2229:
2225:
2218:
2215:
2210:
2206:
2202:
2198:
2191:
2188:
2183:
2179:
2175:
2171:
2164:
2161:
2154:
2152:
2139:
2133:
2129:
2125:
2119:
2116:
2111:
2107:
2103:
2095:
2082:
2060:
2056:
2030:
2017:
2009:
2004:
1985:
1972:
1969:
1961:
1948:
1945:
1940:
1936:
1903:
1890:
1882:
1872:
1862:
1857:
1844:
1836:
1823:
1820:
1815:
1812:
1809:
1805:
1795:
1790:
1786:
1778:
1777:
1776:
1759:
1756:
1751:
1747:
1724:
1720:
1699:
1677:
1632:
1624:
1612:
1609:
1596:
1582:
1574:
1564:
1550:
1547:
1545:
1536:
1521:
1513:
1500:
1489:
1475:
1471:
1465:
1462:
1449:
1447:
1428:
1420:
1407:
1402:
1389:
1375:
1372:
1370:
1360:
1347:
1336:
1335:
1334:
1287:
1279:
1266:
1261:
1248:
1234:
1231:
1223:
1210:
1188:
1147:
1139:
1126:
1115:
1101:
1098:
1084:
1077:
1076:
1075:
1054:
1046:
1033:
1017:
1005:
1003:
986:
982:
978:
972:
963:
961:
956:
954:
950:
946:
942:
936:
934:
930:
911:
907:
903:
897:
888:
886:
882:
874:
857:
854:
851:
845:
820:
810:
805:
792:
789:
784:
769:
766:
763:
748:
745:
742:
741:
725:
722:
719:
716:
713:
685:
675:
670:
657:
654:
649:
636:
616:
593:
590:
587:
583:
575:
567:
564:
561:
560:
557:
516:
489:
481:
476:
453:
440:
421:
408:
400:
385:
384:
368:
353:
350:
347:
346:
303:
276:
270:
262:
259:
258:
253:
246:
222:
209:
184:
176:
175:
174:
173:
169:
166:
162:
131:
128:
120:
116:
113:
81:
79:
77:
73:
69:
65:
61:
57:
53:
50:
46:
43:
40:
37:
33:
19:
3110:Local search
3056:Edmonds–Karp
3012:Bellman–Ford
2794:
2782:minimization
2614:Gauss–Newton
2564:Quasi–Newton
2549:Trust region
2457:Optimization
2373:
2357:
2353:
2342:Bibliography
2320:
2314:
2297:
2293:
2287:
2260:
2256:
2250:
2231:
2227:
2217:
2200:
2196:
2190:
2173:
2169:
2163:
2005:
1926:
1662:
1333:is given by
1173:
1009:
964:
957:
937:
928:
889:
878:
746:
743:
565:
562:
477:
351:
348:
260:
119:vector space
85:
72:Philip Wolfe
63:
59:
55:
42:optimization
31:
29:
3130:Tabu search
2541:Convergence
2512:Line search
2368:description
2263:(4): 1–30.
2008:duality gap
1203:. That is,
706:subject to
441:Subject to
210:subject to
49:constrained
39:first-order
3162:Categories
2961:algorithms
2469:heuristics
2461:Algorithms
2234:(2): 432.
875:Properties
289:, and let
115:convex set
2916:Paradigms
2815:quadratic
2532:Gradients
2494:Functions
2265:CiteSeerX
2104:−
1970:≤
1962:∗
1946:≤
1888:∇
1863:−
1813:−
1763:∞
1760:−
1630:∇
1610:∈
1580:∇
1565:−
1519:∇
1501:−
1463:∈
1450:≥
1426:∇
1408:−
1403:∗
1373:≥
1361:∗
1285:∇
1267:−
1262:∗
1232:≥
1224:∗
1189:∗
1145:∇
1127:−
1099:≥
1074:we have:
1055:∈
849:←
811:−
793:α
775:←
723:≤
720:α
717:≤
676:−
658:α
617:α
579:←
576:α
454:∈
406:∇
386:Minimize
274:←
247:Algorithm
223:∈
177:Minimize
142:→
132::
45:algorithm
36:iterative
3147:Software
3024:Dijkstra
2855:exchange
2653:Hessians
2619:Gradient
2415:See also
2176:(5): 1.
383:solving
86:Suppose
62:and the
2990:Kruskal
2980:Borůvka
2970:Minimum
2707:General
2465:methods
747:Update:
744:Step 3.
563:Step 2.
502:around
349:Step 1.
112:compact
2852:Basis-
2810:Linear
2780:Convex
2624:Mirror
2581:L-BFGS
2467:, and
2384:
2327:
2267:
1032:convex
1010:Since
927:after
838:, let
161:convex
34:is an
3051:Dinic
2959:Graph
2155:Notes
354:Find
159:is a
117:in a
110:is a
3017:SPFA
2985:Prim
2579:and
2382:ISBN
2325:ISBN
1775:and
943:and
749:Let
568:Set
263:Let
121:and
70:and
47:for
30:The
2947:cut
2812:and
2302:doi
2275:doi
2236:doi
2205:doi
2178:doi
1799:max
1601:min
1454:min
1030:is
951:in
482:of
3164::
2463:,
2459::
2380:.
2358:28
2356:.
2352:.
2298:18
2296:.
2273:.
2259:.
2232:62
2230:.
2226:.
2199:.
2172:.
2003:.
1796::=
962:.
955:.
556:.)
163:,
58:,
2945:/
2449:e
2442:t
2435:v
2392:.
2390:.
2333:.
2308:.
2304::
2281:.
2277::
2261:6
2244:.
2238::
2211:.
2207::
2201:3
2184:.
2180::
2174:6
2140:.
2137:)
2134:k
2130:/
2126:1
2123:(
2120:O
2117:=
2112:k
2108:l
2101:)
2096:k
2091:x
2086:(
2083:f
2061:k
2057:l
2036:)
2031:k
2026:x
2021:(
2018:f
1991:)
1986:k
1981:x
1976:(
1973:f
1967:)
1957:x
1952:(
1949:f
1941:k
1937:l
1912:)
1909:)
1904:k
1899:x
1894:(
1891:f
1883:T
1879:)
1873:k
1868:x
1858:k
1853:s
1848:(
1845:+
1842:)
1837:k
1832:x
1827:(
1824:f
1821:,
1816:1
1810:k
1806:l
1802:(
1791:k
1787:l
1757:=
1752:0
1748:l
1725:k
1721:l
1700:k
1678:k
1673:s
1644:)
1640:x
1636:(
1633:f
1625:T
1620:y
1613:D
1606:y
1597:+
1594:)
1590:x
1586:(
1583:f
1575:T
1570:x
1562:)
1558:x
1554:(
1551:f
1548:=
1537:}
1533:)
1529:x
1525:(
1522:f
1514:T
1510:)
1505:x
1497:y
1493:(
1490:+
1487:)
1483:x
1479:(
1476:f
1472:{
1466:D
1459:y
1440:)
1436:x
1432:(
1429:f
1421:T
1417:)
1412:x
1398:x
1393:(
1390:+
1387:)
1383:x
1379:(
1376:f
1366:)
1356:x
1351:(
1348:f
1320:x
1299:)
1295:x
1291:(
1288:f
1280:T
1276:)
1271:x
1257:x
1252:(
1249:+
1246:)
1242:x
1238:(
1235:f
1229:)
1219:x
1214:(
1211:f
1184:x
1159:)
1155:x
1151:(
1148:f
1140:T
1136:)
1131:x
1123:y
1119:(
1116:+
1113:)
1109:x
1105:(
1102:f
1096:)
1092:y
1088:(
1085:f
1060:D
1051:y
1047:,
1043:x
1018:f
990:)
987:k
983:/
979:1
976:(
973:O
929:k
915:)
912:k
908:/
904:1
901:(
898:O
858:1
855:+
852:k
846:k
826:)
821:k
816:x
806:k
801:s
796:(
790:+
785:k
780:x
770:1
767:+
764:k
759:x
738:.
726:1
714:0
694:)
691:)
686:k
681:x
671:k
666:s
661:(
655:+
650:k
645:x
640:(
637:f
594:2
591:+
588:k
584:2
542:D
517:k
512:x
490:f
459:D
450:s
427:)
422:k
417:x
412:(
409:f
401:T
396:s
369:k
364:s
343:.
329:D
304:0
299:x
277:0
271:k
242:.
228:D
219:x
196:)
192:x
188:(
185:f
146:R
137:D
129:f
96:D
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
