Share to:

Frank-Wolfe-algoritme

Het Frank-Wolfe-algoritme, ook bekend als convexe-combinatiealgoritme, is een klassiek algoritme in het operationeel onderzoek (OR). Het werd in 1956 gepresenteerd door Marguerite Frank and Phil Wolfe als een procedure voor het oplossen van kwadratische programmeerproblemen met lineaire randvoorwaarden. Bij elke stap (iteratie) wordt de doelfunctie gelineariseerd en wordt een richting gekozen waarbij de doelfunctie wordt gereduceerd. Het algoritme kan worden gezien als een generalisatie van de simplexmethode voor lineair programmeren.

Probleemformulering

Minimaliseer

f(\mathbf {x} )={\frac {1}{2}}\mathbf {x} ^{\mathrm {T} }E\mathbf {x} +\mathbf {h} ^{\mathrm {T} }\mathbf {x}

met

\mathbf {x} \epsilon \mathbf {P}

Waarin de n×n matrix E positief-semidefiniet is, h een n×1 vector is, en $\mathbf {P}$ een mogelijk gebied definieert door een mix van lineaire ongelijkheden en gelijkheden (bijvoorbeeld Ax ≤ b, Cx = d).

Algoritme

Stap 1. Initialisatie. Laat $k\leftarrow 0$ en laat $x_{0}$ een punt zijn in $\mathbf {P}$ .

Stap 2. Convergentietest. Indien $\nabla f(x_{k})=0$ stop, het minimum is gevonden.

Stap 3. Richting vinden door benadering van het probleem door vervangen van de functie f door een eerste-order Taylorreeks rond $x_{k}$ . Los op voor ${\bar {x}}_{k}$ :

Minimaliseer

f(x_{k})+\nabla ^{T}f(x_{k}){\bar {x}}_{k}

Onder voorwaarde

{\bar {x}}_{k}\epsilon \mathbf {P}

(LP)

x_{k}

is vast in stap 3, terwijl de minimalisatie plaatsvindt door de

{\bar {x}}_{k}

te variëren, en is equivalent aan de minimalisatie van

\nabla ^{T}f(x_{k}){\bar {x}}_{k}

Stap 4. Bepaal de stapgrootte. Vind $\lambda$ waarbij $f(x_{k}+\lambda ({\bar {x}}_{k}-x_{k}))$ wordt geminimaliseerd onder voorwaarde van $0\leq \lambda \leq 1$ . Als $\lambda =0$ stop, het minimum is gevonden.

Stap 5. Pas de waarden aan. Laat $x_{k+1}\leftarrow x_{k}+\lambda ({\bar {x}}_{k}-x_{k})$ , laat $k\leftarrow k+1$ en ga naar stap 2.

Opmerkingen

Het algoritme gaat vlot bij de eerste iteraties maar het rendement neemt af naarmate het minimum wordt bereikt. De toepassing van het algoritme vindt onder andere plaats bij verkeersmodellen waarbij iteratief een evenwichtstoedeling van verkeersstromen wordt berekend.

Referenties

M. Frank and P. Wolfe, An algorithm for quadratic programming, Naval Research Logistics Quarterly, 3 (1956), pp. 95–110.
The Frank-Wolfe algorithm description
Combined Traffic Signal Control and Traffic Assignment: Algorithms, Implementation and Numerical Results, Chungwon Lee and Randy B. Machemehl, University of Texas at Austin, March 2005

Read other articles:

Historia de los judíos en Hungría

Una familia de judíos húngaros frente a su tienda, en los años 30. La comunidad judía tiene una larga historia en Hungría. A comienzos del siglo XX los judíos constituían el 5 % de la población total húngara, mientras que constituían el 25 % de la población de la capital del país, Budapest. La comunidad sufrió grandes calamidades durante los últimos años de la Segunda Guerra Mundial, con el exterminio de más de 600 000 judíos húngaros durante el Holocaust...

Pternopetalum

Pternopetalum Pternopetalum tanakaeTaxonomíaReino: PlantaeDivisión: MagnoliophytaClase: MagnoliopsidaOrden: ApialesFamilia: ApiaceaeSubfamilia: ApioideaeGénero: PternopetalumFranch.Especies Ver texto. Sinonimia Cryptotaeniopsis Dunn[1] [editar datos en Wikidata] Pternopetalum es un género con 26 especies perteneciente a la familia Apiaceae, se encuentran en China.[2] Taxonomía El género fue descrito por Adrien René Franchet y publicado en Nouvelles archiv...

1952–53 Wisconsin Badgers men's basketball team

American college basketball season 1952–53 Wisconsin Badgers men's basketballConferenceBig Ten ConferenceRecord13–9 (10–8 Big Ten)Head coachHarold E. FosterHome arenaUW FieldhouseSeasons← 1951–521953–54 → 1952–53 Big Ten Conference men's basketball standings vte Conf Overall Team W L PCT W L PCT No. 1 Indiana 17 – 1 .944 23 – 3 .885 No. 11 Illinois 14 – 4 .778 18 – 4 .81...

ميار النوري

ميار النوري معلومات شخصية مكان الميلاد سوريا مواطنة سوريا الحياة العملية المهنة ممثل المواقع السينما.كوم صفحته على موقع السينما تعديل مصدري - تعديل هو ميار ابن الممثل المشهور عباس النوري.[1] لم يتعلّق ميّار النوري بالتلفزيون كثيراً رغم نجومية والده التي فت

جوردن دي يونج

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (فبراير 2017) جوردن دي يونج معلومات شخصية الميلاد 12 أبريل 1979 (44 سنة) أورانج سيتي الجنسية الولايات المتحدة الأمريكية الحياة العملية المهنة لاعب كرة قاعدة[1] ال

А (кирилиця)

Літера А Unicode (hex) велика: U+1040 мала: U+1072 Кирилиця А Б В Г Ґ Д Ѓ Ђ Е Ѐ Є Ё Ж З З́ Ѕ И Ѝ І Ї Й Ј К Л Љ М Н Њ О П Р С С́ Т Ћ Ќ У Ў Ф Х Ц Ч Џ Ш Щ Ъ Ы Ь Э Ю Я Неслов'янські літери А̄ А́ А̀ Ӑ А̂ А̊ Ӓ Ӓ̄ А̃ А̨ Ә Ә́ Ә̃ Ӛ Ӕ Ғ Г̧ Г̑ Г̄ Ӻ Ӷ Ԁ Ԃ Ꚃ Ꚁ Ꚉ Ԫ Ԭ Ӗ Е̄ Е̃ Ё̄ Є̈ Ӂ Җ Ꚅ Ӝ Ԅ Ҙ Ӟ Ԑ Ԑ̈ Ӡ Ԇ Ӣ И̃ Ҋ Ӥ Қ Ӄ Ҡ Ҟ Ҝ Ԟ Ԛ Ӆ Ԯ Ԓ ...

KingsGate Community Church

Church in United KingdomKingsgate Community ChurchKingsGate Community Church logoCountryUnited KingdomDenominationIndependentWebsitekingsgate.churchHistoryFounded1988ClergySenior pastor(s)Dave and Karen Smith KingsGate Community Church is a Christian megachurch, originating in Peterborough, England. The church was established in 1988, originally called Peterborough Community Church, by Dave and Karen Smith.[1] History Its first service in 1988, held in a house, was attended by nine pe...

جيف ريمان

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (أبريل 2019) جيف ريمان (بالإنجليزية: Geoff Ryman)‏ معلومات شخصية اسم الولادة (بالإنجليزية: Geoffrey Charles Ryman)‏ الميلاد 9 مايو 1951 (72 سنة) كندا مواطنة كندا الحياة ا�...

Paroisse de Sainte-Anne

Paroisse de Sainte-Anne Situation de Sainte-Anne dans le comté de Madawaska Administration Pays Canada Province Nouveau-Brunswick Subdivision régionale Madawaska Statut municipal District de services locaux Constitution 9 novembre 1966 Démographie Population 949 hab. (2011 ) Densité 2,6 hab./km2 Géographie Coordonnées 47° 24′ 36″ nord, 67° 51′ 00″ ouest Superficie 36 930 ha = 369,30 km2 Divers Langue(s) Français...

In Cold Blood (miniseries)

1996 television miniseries by Jonathan Kaplan In Cold BloodBased onIn Cold Bloodby Truman CapoteWritten byBenedict FitzgeraldDirected byJonathan KaplanStarring Anthony Edwards Eric Roberts Sam Neill ComposerHummie MannCountry of originUnited StatesOriginal languageEnglishNo. of episodes2ProductionExecutive producerRobert HalmiProducerTom RoweProduction locationsAlberta, CanadaCinematographyPeter WoesteEditorMichael D. OrnsteinRunning time180 minutesProduction companyPacific Motion PicturesOri...

Zofia Jaroszewska

Zofia JaroszewskaLahir(1902-09-25)25 September 1902Irbit, Uyezd Irbitsky, Kegubernuran Perm, Kekaisaran Rusia (kini Oblast Sverdlovsk, Rusia)Meninggal25 September 1985(1985-09-25) (umur 83)Kraków, PolandiaPekerjaanPemeranTahun aktif1922-1983 Zofia Jaroszewska dalam peran Balladyna, 1938 Zofia Jaroszewska (25 September 1902 – 25 September 1985) adalah seorang pemeran film asal Polandia.[1] Filmografi pilihan Jealousy (1922) Dvanáct křesel (1933) The Maids o...

Костел Святого Антонія (Львів)

У Вікіпедії є статті про інші значення цього терміна: Костел Святого Антонія. У Вікіпедії є статті про інші значення цього терміна: Костел францисканців. Костел Святого Антонія 49°50′27″ пн. ш. 24°02′47″ сх. д. / 49.8410556° пн. ш. 24.0465833° сх. д. / 49.841055...

Prima Charter

Defunct Polish charter airline Prima Charter IATA ICAO Callsign - FFP FLYING FISH Founded2003 (as Fischer Air Polska)2006 (as Prima Charter)Commenced operations12 May 2005Ceased operations14 January 2008DestinationsChartersHeadquartersWarsaw, PolandWebsitewww.primacharter.com Prima Charter was a Polish charter airline, previously known as Fischer Air Polska.[1] It commenced operations on 12 May 2005 and ceased operations on 14 January 2008.[2] History Established as Fischer Ai...

Lê Văn Khoa

Lê Văn KhoaLê Văn Khoa phát biểu tại lễ cất nóc Ngôi nhà Đức tại Thành phố Hồ Chí MinhChức vụPhó Chủ tịch Ủy ban nhân dân Thành phố Hồ Chí MinhNhiệm kỳ11 tháng 12 năm 2015 – 21 tháng 5 năm 20182 năm, 161 ngàyTiền nhiệmTất Thành CangKế nhiệmVõ Văn Hoan Thông tin chungSinh1961 (61–62 tuổi)Đảng chính trịĐảng Cộng sản Việt NamQuê quánthị xã Điện Bàn, tỉnh Quảng ...

Han dynasty#Eastern Han

Imperial dynasty in China from 202 BC to 220 AD Eastern Han and House of Liu redirect here. For the Five Dynasties-era kingdom, see Northern Han. For other uses, see House of Liu (disambiguation). Han漢 202 BC – 9 AD; 25–220 AD (9–23 AD: Xin) A map of the Western Han dynasty in 2 AD[1] Principalities and centrally-administered commanderies Protectorate of the Western Regions (Tarim Basin) CapitalChang'an(206 BC – 9 AD, 190–195 AD)Luoyang(23–190 AD, 196 ...

Redlands Mall

Redlands Mall was a mall in Redlands, California with two anchors, CVS Pharmacy and Gottschalks. The mall, located on about 12 acres on Orange Street and Eureka Street between Redlands Boulevard and Citrus Avenue, was built in 1977. The mall permanently closed in 2010.[1][2]Former Gottschalks North Entrance at the Redlands Mall The mall is scheduled for demolition and redevelopment since 2023. History The mall was planned in 1977 to revitalize the city of Redlands. After demol...

Włókniarz Częstochowa

Polish speedway team Włókniarz CzęstochowaClub informationTrack addressArena CzęstochowaCzęstochowaCountryPolandFounded1946Team managerLech KedzioraTeam captainLeon MadsenLeagueEkstraligaWebsiteOfficial WebsiteClub factsColoursWhite and GreenNicknameLionsTrack size359 metres (393 yd)Track record time61.26 secondsTrack record date7 August 2020Track record holderMartin VaculikMajor team honours Team Polish Champions1959, 1974, 1996, 2003 tier 2 champions1956, 1964, 1965, 1965/66, 1999...

Південна провінція Пхьонан

У Вікіпедії є статті про інші значення цього терміна: Пхьонан. Південна провінція Пхьонан Адм. центр Пхйонсон Найбільше місто Пхйонсон Країна КНДР Регіон регіон Кваннам Межує з: сусідні адмінодиниці Пхеньян ? Населення - повне 4 051 696 осіб (2008) Площа - повна ...

Crepuscular rays

Sunbeams that originate when the Sun is just below the horizon Look up crepuscular ray in Wiktionary, the free dictionary. Sunlight shining through clouds, giving rise to crepuscular rays Crepuscular rays are sunbeams that originate when the Sun is just above or below a layer of clouds, during the twilight period.[1] Crepuscular rays are noticeable when the contrast between light and dark is most obvious. Crepuscular comes from the Latin word crepusculum, meaning twilight.[2] ...

Masamune

Japanese swordsmith (c.1264–1343) For other uses, see Masamune (disambiguation). Masamune正宗Masamune PortraitPersonal detailsBornc. 1264JapanDied1343 (aged 79)Children1, Hikoshiro Sadamune[1]OccupationSwordsmithInfluencedChogiKanemitsuShizu Saburo KaneujiKinjuKunishigeKunitsuguSaemonzaburoSaeki NorishigeGo YoshihiroNaotsunaHiromitsuSadamuneAkihiro Gorō Nyūdō Masamune (五郎入道正宗, Priest Gorō Masamune, c.1264–1343),[2] was a medieval Japanese blacksmith...

Морська змія спіральна

Бої на Світлодарській дузі

Perkebunan Tanjung Kasau, Laut Tador, Batu Bara

Kapal tiang

الدوري الإسباني الدرجة الثانية 2013–14

Vũ Văn Dũng

Kuntz Agus

Doombot