Frank Wolfe

In this notebook, we are going to use the Frank-Wolfe algorithm to solve the following optimization problem.

$$\begin{align} \min \quad 2(x_1 - 1)^2 &+ (x_2 - 2)^2 \\ \mathrm{s.t.} \quad x_1 + 4x_2 - 2 &\le 0 \\ \quad -x_1 + x_2 &\le 0 \\ \quad x_1, x_2 &\ge 0 \end{align} $$
In [1]:
import math
from scipy.optimize import minimize_scalar
In [2]:
x1 = 0.0
x2 = 0.0
k = 1

while k <= 100:
    g1 = 4.0*(x1-1)
    g2 = 2.0*(x2-2)
    MinObj = 10000;
    tempminobj = g1*2 + g2*0
    if(tempminobj < MinObj):
        MinObj = tempminobj 
        y1 = 2.0
        y2 = 0.0
    tempminobj = g1*0.0 + g2*0.0
    if(tempminobj < MinObj):
        MinObj = tempminobj 
        y1 = 0.0
        y2 = 0.0
    tempminobj = g1*0.4 + g2*0.4
    if(tempminobj < MinObj):
        MinObj = tempminobj 
        y1 = 0.4
        y2 = 0.4

    def fun(l):
        return 2*( x1 + l*(y1-x1) - 1 )**2 + ( x2 + l*(y2-x2) - 2)**2

    lam = minimize_scalar(fun, bounds=(0, 1), method='bounded') 
    print(k,",", x1, "," , x2, "," , y1 , "," , y2, ",", lam.x)
    x1 = x1 + (lam.x)*(y1-x1)
    x2 = x2 + (lam.x)*(y2-x2)
    k = k + 1

1 , 0.0 , 0.0 , 2.0 , 0.0 , 0.5
2 , 1.0 , 0.0 , 0.4 , 0.4 , 0.909090909091
3 , 0.454545454545 , 0.363636363636 , 2.0 , 0.0 , 0.222222222222
4 , 0.79797979798 , 0.282828282828 , 0.4 , 0.4 , 0.122249388753
5 , 0.749327010941 , 0.297152453632 , 2.0 , 0.0 , 0.0376211169633
6 , 0.796378725745 , 0.285973246418 , 0.4 , 0.4 , 0.103970228557
7 , 0.755167139034 , 0.297828634049 , 2.0 , 0.0 , 0.0321829348364
8 , 0.795229513881 , 0.288243634527 , 0.4 , 0.4 , 0.0906026138601
9 , 0.759420686849 , 0.298369053355 , 2.0 , 0.0 , 0.0281650327902
10 , 0.794361643882 , 0.289965479183 , 0.4 , 0.4 , 0.0803685105159
11 , 0.762667385959 , 0.298808789727 , 2.0 , 0.0 , 0.0250654065084
12 , 0.793681630916 , 0.291319025944 , 0.4 , 0.4 , 0.0722650988442
13 , 0.765232188945 , 0.299172867276 , 2.0 , 0.0 , 0.0225965250532
14 , 0.793133650722 , 0.292412600086 , 0.4 , 0.4 , 0.0656805326094
15 , 0.767312423156 , 0.299478997814 , 2.0 , 0.0 , 0.0205808580628
16 , 0.792682191211 , 0.293315463067 , 0.4 , 0.4 , 0.0602189467269
17 , 0.769035283258 , 0.299739893514 , 2.0 , 0.0 , 0.0189024474645
18 , 0.792303529147 , 0.294074075923 , 0.4 , 0.4 , 0.0556122410188
19 , 0.770486650731 , 0.299964853943 , 2.0 , 0.0 , 0.0174821482372
20 , 0.791981185363 , 0.294720823901 , 0.4 , 0.4 , 0.0516720576073
21 , 0.771726710972 , 0.300160815553 , 2.0 , 0.0 , 0.0162639944273
22 , 0.7917033409 , 0.295279001721 , 0.4 , 0.4 , 0.0482620086956
23 , 0.772798950855 , 0.300333047451 , 2.0 , 0.0 , 0.0152072385483
24 , 0.791461289956 , 0.295765811154 , 0.4 , 0.4 , 0.0452808084565
25 , 0.773735606268 , 0.300485619494 , 2.0 , 0.0 , 0.0142814771313
26 , 0.791248473164 , 0.296194240991 , 0.4 , 0.4 , 0.0426516028934
27 , 0.774561098654 , 0.300621723002 , 2.0 , 0.0 , 0.0134635457616
28 , 0.79105985138 , 0.296574288678 , 0.4 , 0.4 , 0.0403149848686
29 , 0.775294279389 , 0.300743894665 , 2.0 , 0.0 , 0.0127354741339
30 , 0.790891487415 , 0.296913778573 , 0.4 , 0.4 , 0.0382242853317
31 , 0.775949939667 , 0.300854175715 , 2.0 , 0.0 , 0.0120831001485
32 , 0.790740259132 , 0.29721892458 , 0.4 , 0.4 , 0.0363423172162
33 , 0.776539852686 , 0.300954227026 , 2.0 , 0.0 , 0.0114951070443
34 , 0.790603658044 , 0.297494725971 , 0.4 , 0.4 , 0.034639073143
35 , 0.777073509363 , 0.301045413656 , 2.0 , 0.0 , 0.0109623397228
36 , 0.790479645009 , 0.297745251559 , 0.4 , 0.4 , 0.0330900651917
37 , 0.7775586481 , 0.301128867852 , 2.0 , 0.0 , 0.0104773098771
38 , 0.79036654495 , 0.29797384739 , 0.4 , 0.4 , 0.0316751065281
39 , 0.778001643054 , 0.301205536643 , 2.0 , 0.0 , 0.0100338315926
40 , 0.790262968774 , 0.298183291013 , 0.4 , 0.4 , 0.0303774031514
41 , 0.778407793236 , 0.30127621823 , 2.0 , 0.0 , 0.00962674886069
42 , 0.790167754621 , 0.298375907739 , 0.4 , 0.4 , 0.0291828671741
43 , 0.778781540862 , 0.301341590125 , 2.0 , 0.0 , 0.00925172897622
44 , 0.790079923067 , 0.298553659404 , 0.4 , 0.4 , 0.028079590902
45 , 0.779126638408 , 0.301402231147 , 2.0 , 0.0 , 0.00890510390485
46 , 0.789998642548 , 0.298718212961 , 0.4 , 0.4 , 0.0270574393276
47 , 0.779446277939 , 0.301458638769 , 2.0 , 0.0 , 0.00858374707632
48 , 0.789923202383 , 0.29887099406 , 0.4 , 0.4 , 0.0261077309851
49 , 0.77974319231 , 0.301511242942 , 2.0 , 0.0 , 0.00828497668304
50 , 0.789852991509 , 0.299013229324 , 0.4 , 0.4 , 0.025222985543
51 , 0.78001973514 , 0.301560417181 , 2.0 , 0.0 , 0.00800647904578
52 , 0.789787481567 , 0.29914598002 , 0.4 , 0.4 , 0.0243967223643
53 , 0.780277944598 , 0.301606487544 , 2.0 , 0.0 , 0.00774624733917
54 , 0.789726213324 , 0.299270169093 , 0.4 , 0.4 , 0.0236232983928
55 , 0.780519594696 , 0.301649739945 , 2.0 , 0.0 , 0.00750253219391
56 , 0.789668785696 , 0.29938660306 , 0.4 , 0.4 , 0.0228977766721
57 , 0.780746236865 , 0.301690426154 , 2.0 , 0.0 , 0.00727380156791
58 , 0.789614846799 , 0.299495989859 , 0.4 , 0.4 , 0.0222158189379
59 , 0.780959233907 , 0.301728768751 , 2.0 , 0.0 , 0.00705870791465
60 , 0.789564086611 , 0.299598953503 , 0.4 , 0.4 , 0.0215735972816
61 , 0.781159787891 , 0.301764965246 , 2.0 , 0.0 , 0.00685606114304
62 , 0.789516230909 , 0.299696046194 , 0.4 , 0.4 , 0.0209677210421
63 , 0.781348963238 , 0.301799191517 , 2.0 , 0.0 , 0.00666480620855
64 , 0.789471036234 , 0.299787758391 , 0.4 , 0.4 , 0.0203951759419
65 , 0.781527705926 , 0.30183160469 , 2.0 , 0.0 , 0.00648400443397
66 , 0.789428285683 , 0.299874527227 , 0.4 , 0.4 , 0.0198532731365
67 , 0.78169685956 , 0.301862345586 , 2.0 , 0.0 , 0.00631281785414
68 , 0.789387785377 , 0.299956743581 , 0.4 , 0.4 , 0.0193396063399
69 , 0.781857178894 , 0.301891540778 , 2.0 , 0.0 , 0.00615049602711
70 , 0.789349361476 , 0.300034758055 , 0.4 , 0.4 , 0.0188520155659
71 , 0.782009341253 , 0.301919304353 , 2.0 , 0.0 , 0.00599636486921
72 , 0.78931285765 , 0.300108886043 , 0.4 , 0.4 , 0.018388556328
73 , 0.782153956238 , 0.301945739418 , 2.0 , 0.0 , 0.00584981716047
74 , 0.789278132923 , 0.30017941205 , 0.4 , 0.4 , 0.0179474733534
75 , 0.782291574006 , 0.301970939393 , 2.0 , 0.0 , 0.00571030443485
76 , 0.789245059831 , 0.300246593398 , 0.4 , 0.4 , 0.0175271780622
77 , 0.782422692358 , 0.301994989118 , 2.0 , 0.0 , 0.00557733002536
78 , 0.789213522834 , 0.300310663398 , 0.4 , 0.4 , 0.0171262291951
79 , 0.782547762836 , 0.302017965825 , 2.0 , 0.0 , 0.00545044307614
80 , 0.789183416952 , 0.300371834094 , 0.4 , 0.4 , 0.0167433160842
81 , 0.782667195988 , 0.302039939967 , 2.0 , 0.0 , 0.00532923336779
82 , 0.789154646586 , 0.30043029864 , 0.4 , 0.4 , 0.0163772441587
83 , 0.782781365924 , 0.30206097595 , 2.0 , 0.0 , 0.00521332682998
84 , 0.789127124487 , 0.30048623336 , 0.4 , 0.4 , 0.0160269223413
85 , 0.782890614282 , 0.30208113277 , 2.0 , 0.0 , 0.00510238163684
86 , 0.789100770861 , 0.300539799545 , 0.4 , 0.4 , 0.0156913520548
87 , 0.782995253681 , 0.302100464566 , 2.0 , 0.0 , 0.00499608479906
88 , 0.789075512595 , 0.300591145027 , 0.4 , 0.4 , 0.0153696176038
89 , 0.783095570747 , 0.302119021114 , 2.0 , 0.0 , 0.00489414917905
90 , 0.78905128256 , 0.300640405555 , 0.4 , 0.4 , 0.0150608777333
91 , 0.783191828762 , 0.302136848259 , 2.0 , 0.0 , 0.0047963108711
92 , 0.789028019021 , 0.300687706009 , 0.4 , 0.4 , 0.0147643582
93 , 0.783284269999 , 0.302153988291 , 2.0 , 0.0 , 0.00470232689338
94 , 0.789005665098 , 0.300733161466 , 0.4 , 0.4 , 0.0144793452178
95 , 0.783373117781 , 0.30217048029 , 2.0 , 0.0 , 0.00461197315057
96 , 0.788984168296 , 0.300776878148 , 0.4 , 0.4 , 0.0142051796582
97 , 0.783458578301 , 0.30218636042 , 2.0 , 0.0 , 0.00452504263069
98 , 0.788963480096 , 0.300818954257 , 0.4 , 0.4 , 0.0139412519082
99 , 0.783540842237 , 0.3022016622 , 2.0 , 0.0 , 0.00444134380414
100 , 0.788943555581 , 0.30085948072 , 0.4 , 0.4 , 0.0136869972972

FW using linprog

In the following example, I use linprog solver to solve the LP subproblem.

In [3]:
from scipy.optimize import linprog
x1 = 0
x2 = 0
k = 1

while k <= 100:
    g1 = 4.0*(x1-1)
    g2 = 2.0*(x2-2)
    MinObj = 10000;
    c = [g1,g2]
    A = [[1,4],[-1,1]]
    b = [2,0]
    res = linprog(c, A_ub=A, b_ub=b)
    y1 = res.x[0]
    y2 = res.x[1]
    def fun(l):
        return 2*( x1 + l*(y1-x1) - 1 )**2 + ( x2 + l*(y2-x2) - 2)**2
    lam = minimize_scalar(fun, bounds=(0, 1), method='bounded') 
    print(k,",", x1, "," , x2, "," , y1 , "," , y2, ",", lam.x)
    x1 = x1 + (lam.x)*(y1-x1)
    x2 = x2 + (lam.x)*(y2-x2)
    k = k + 1

1 , 0 , 0 , 2.0 , 0.0 , 0.5
2 , 1.0 , 0.0 , 0.4 , 0.4 , 0.909090909091
3 , 0.454545454545 , 0.363636363636 , 2.0 , 0.0 , 0.222222222222
4 , 0.79797979798 , 0.282828282828 , 0.4 , 0.4 , 0.122249388753
5 , 0.749327010941 , 0.297152453632 , 2.0 , 0.0 , 0.0376211169633
6 , 0.796378725745 , 0.285973246418 , 0.4 , 0.4 , 0.103970228557
7 , 0.755167139034 , 0.297828634049 , 2.0 , 0.0 , 0.0321829348364
8 , 0.795229513881 , 0.288243634527 , 0.4 , 0.4 , 0.0906026138601
9 , 0.759420686849 , 0.298369053355 , 2.0 , 0.0 , 0.0281650327902
10 , 0.794361643882 , 0.289965479183 , 0.4 , 0.4 , 0.0803685105159
11 , 0.762667385959 , 0.298808789727 , 2.0 , 0.0 , 0.0250654065084
12 , 0.793681630916 , 0.291319025944 , 0.4 , 0.4 , 0.0722650988442
13 , 0.765232188945 , 0.299172867276 , 2.0 , 0.0 , 0.0225965250532
14 , 0.793133650722 , 0.292412600086 , 0.4 , 0.4 , 0.0656805326094
15 , 0.767312423156 , 0.299478997814 , 2.0 , 0.0 , 0.0205808580628
16 , 0.792682191211 , 0.293315463067 , 0.4 , 0.4 , 0.0602189467269
17 , 0.769035283258 , 0.299739893514 , 2.0 , 0.0 , 0.0189024474645
18 , 0.792303529147 , 0.294074075923 , 0.4 , 0.4 , 0.0556122410187
19 , 0.770486650731 , 0.299964853943 , 2.0 , 0.0 , 0.0174821482372
20 , 0.791981185363 , 0.294720823901 , 0.4 , 0.4 , 0.0516720576073
21 , 0.771726710972 , 0.300160815553 , 2.0 , 0.0 , 0.0162639944273
22 , 0.7917033409 , 0.295279001721 , 0.4 , 0.4 , 0.0482620086956
23 , 0.772798950855 , 0.300333047451 , 2.0 , 0.0 , 0.0152072385483
24 , 0.791461289956 , 0.295765811154 , 0.4 , 0.4 , 0.0452808084565
25 , 0.773735606268 , 0.300485619494 , 2.0 , 0.0 , 0.0142814771313
26 , 0.791248473164 , 0.296194240991 , 0.4 , 0.4 , 0.0426516028934
27 , 0.774561098654 , 0.300621723002 , 2.0 , 0.0 , 0.0134635457616
28 , 0.79105985138 , 0.296574288678 , 0.4 , 0.4 , 0.0403149848686
29 , 0.775294279389 , 0.300743894665 , 2.0 , 0.0 , 0.0127354741339
30 , 0.790891487415 , 0.296913778573 , 0.4 , 0.4 , 0.0382242853317
31 , 0.775949939667 , 0.300854175715 , 2.0 , 0.0 , 0.0120831001485
32 , 0.790740259132 , 0.29721892458 , 0.4 , 0.4 , 0.0363423172162
33 , 0.776539852686 , 0.300954227026 , 2.0 , 0.0 , 0.0114951070443
34 , 0.790603658044 , 0.297494725971 , 0.4 , 0.4 , 0.034639073143
35 , 0.777073509363 , 0.301045413656 , 2.0 , 0.0 , 0.0109623397228
36 , 0.790479645009 , 0.297745251559 , 0.4 , 0.4 , 0.0330900651917
37 , 0.7775586481 , 0.301128867852 , 2.0 , 0.0 , 0.0104773098771
38 , 0.79036654495 , 0.29797384739 , 0.4 , 0.4 , 0.0316751065281
39 , 0.778001643054 , 0.301205536643 , 2.0 , 0.0 , 0.0100338315926
40 , 0.790262968774 , 0.298183291013 , 0.4 , 0.4 , 0.0303774031514
41 , 0.778407793236 , 0.30127621823 , 2.0 , 0.0 , 0.00962674886071
42 , 0.790167754621 , 0.298375907739 , 0.4 , 0.4 , 0.0291828671741
43 , 0.778781540862 , 0.301341590125 , 2.0 , 0.0 , 0.00925172897623
44 , 0.790079923067 , 0.298553659404 , 0.4 , 0.4 , 0.028079590902
45 , 0.779126638408 , 0.301402231147 , 2.0 , 0.0 , 0.00890510390483
46 , 0.789998642548 , 0.298718212961 , 0.4 , 0.4 , 0.0270574393276
47 , 0.779446277939 , 0.301458638769 , 2.0 , 0.0 , 0.00858374707631
48 , 0.789923202383 , 0.29887099406 , 0.4 , 0.4 , 0.0261077309851
49 , 0.77974319231 , 0.301511242942 , 2.0 , 0.0 , 0.00828497668307
50 , 0.789852991509 , 0.299013229324 , 0.4 , 0.4 , 0.025222985543
51 , 0.78001973514 , 0.301560417181 , 2.0 , 0.0 , 0.00800647904578
52 , 0.789787481567 , 0.29914598002 , 0.4 , 0.4 , 0.0243967223644
53 , 0.780277944598 , 0.301606487544 , 2.0 , 0.0 , 0.00774624733919
54 , 0.789726213324 , 0.299270169093 , 0.4 , 0.4 , 0.0236232983927
55 , 0.780519594696 , 0.301649739945 , 2.0 , 0.0 , 0.0075025321939
56 , 0.789668785696 , 0.29938660306 , 0.4 , 0.4 , 0.0228977766721
57 , 0.780746236865 , 0.301690426154 , 2.0 , 0.0 , 0.0072738015679
58 , 0.789614846799 , 0.299495989859 , 0.4 , 0.4 , 0.0222158189379
59 , 0.780959233907 , 0.301728768751 , 2.0 , 0.0 , 0.00705870791464
60 , 0.789564086611 , 0.299598953503 , 0.4 , 0.4 , 0.0215735972816
61 , 0.781159787891 , 0.301764965246 , 2.0 , 0.0 , 0.00685606114304
62 , 0.789516230909 , 0.299696046194 , 0.4 , 0.4 , 0.0209677210421
63 , 0.781348963238 , 0.301799191517 , 2.0 , 0.0 , 0.00666480620852
64 , 0.789471036234 , 0.299787758391 , 0.4 , 0.4 , 0.0203951759419
65 , 0.781527705926 , 0.30183160469 , 2.0 , 0.0 , 0.00648400443396
66 , 0.789428285683 , 0.299874527227 , 0.4 , 0.4 , 0.0198532731365
67 , 0.78169685956 , 0.301862345586 , 2.0 , 0.0 , 0.00631281785411
68 , 0.789387785377 , 0.299956743581 , 0.4 , 0.4 , 0.0193396063397
69 , 0.781857178894 , 0.301891540778 , 2.0 , 0.0 , 0.0061504960271
70 , 0.789349361476 , 0.300034758055 , 0.4 , 0.4 , 0.018852015566
71 , 0.782009341253 , 0.301919304353 , 2.0 , 0.0 , 0.00599636486919
72 , 0.78931285765 , 0.300108886043 , 0.4 , 0.4 , 0.018388556328
73 , 0.782153956238 , 0.301945739418 , 2.0 , 0.0 , 0.00584981716048
74 , 0.789278132923 , 0.30017941205 , 0.4 , 0.4 , 0.0179474733534
75 , 0.782291574006 , 0.301970939393 , 2.0 , 0.0 , 0.00571030443485
76 , 0.789245059831 , 0.300246593398 , 0.4 , 0.4 , 0.0175271780622
77 , 0.782422692358 , 0.301994989118 , 2.0 , 0.0 , 0.00557733002536
78 , 0.789213522834 , 0.300310663398 , 0.4 , 0.4 , 0.0171262291951
79 , 0.782547762836 , 0.302017965825 , 2.0 , 0.0 , 0.00545044307616
80 , 0.789183416952 , 0.300371834094 , 0.4 , 0.4 , 0.0167433160842
81 , 0.782667195988 , 0.302039939967 , 2.0 , 0.0 , 0.00532923336776
82 , 0.789154646586 , 0.30043029864 , 0.4 , 0.4 , 0.0163772441586
83 , 0.782781365924 , 0.30206097595 , 2.0 , 0.0 , 0.00521332682992
84 , 0.789127124487 , 0.30048623336 , 0.4 , 0.4 , 0.0160269223412
85 , 0.782890614282 , 0.30208113277 , 2.0 , 0.0 , 0.00510238163683
86 , 0.789100770861 , 0.300539799545 , 0.4 , 0.4 , 0.0156913520546
87 , 0.782995253681 , 0.302100464566 , 2.0 , 0.0 , 0.00499608479903
88 , 0.789075512595 , 0.300591145027 , 0.4 , 0.4 , 0.0153696176038
89 , 0.783095570747 , 0.302119021114 , 2.0 , 0.0 , 0.00489414917905
90 , 0.78905128256 , 0.300640405555 , 0.4 , 0.4 , 0.0150608777335
91 , 0.783191828762 , 0.302136848259 , 2.0 , 0.0 , 0.00479631087113
92 , 0.789028019021 , 0.300687706009 , 0.4 , 0.4 , 0.0147643582
93 , 0.783284269999 , 0.302153988291 , 2.0 , 0.0 , 0.00470232689341
94 , 0.789005665098 , 0.300733161466 , 0.4 , 0.4 , 0.0144793452177
95 , 0.783373117781 , 0.30217048029 , 2.0 , 0.0 , 0.00461197315058
96 , 0.788984168296 , 0.300776878148 , 0.4 , 0.4 , 0.0142051796582
97 , 0.783458578301 , 0.30218636042 , 2.0 , 0.0 , 0.00452504263066
98 , 0.788963480096 , 0.300818954257 , 0.4 , 0.4 , 0.0139412519083
99 , 0.783540842237 , 0.3022016622 , 2.0 , 0.0 , 0.00444134380418
100 , 0.788943555581 , 0.30085948072 , 0.4 , 0.4 , 0.0136869972975