Method of Successive Averages

In this notebook, we are going to use the method of successive averages 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} $$

import math
from scipy.optimize import minimize_scalar

x1 = 0
x2 = 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
    print(k,",", x1, "," , x2, "," , y1 , "," , y2)
    x1 = x1 + (1/(k+1))*(y1-x1)
    x2 = x2 + (1/(k+1))*(y2-x2)
    k = k + 1

1 , 0 , 0 , 2.0 , 0.0
2 , 1.0 , 0.0 , 0.4 , 0.4
3 , 0.8 , 0.13333333333333333 , 0.4 , 0.4
4 , 0.7000000000000001 , 0.2 , 2.0 , 0.0
5 , 0.96 , 0.16 , 0.4 , 0.4
6 , 0.8666666666666667 , 0.2 , 0.4 , 0.4
7 , 0.8 , 0.2285714285714286 , 0.4 , 0.4
8 , 0.75 , 0.25 , 2.0 , 0.0
9 , 0.8888888888888888 , 0.2222222222222222 , 0.4 , 0.4
10 , 0.84 , 0.24 , 0.4 , 0.4
11 , 0.7999999999999999 , 0.2545454545454545 , 0.4 , 0.4
12 , 0.7666666666666666 , 0.26666666666666666 , 2.0 , 0.0
13 , 0.8615384615384615 , 0.24615384615384614 , 0.4 , 0.4
14 , 0.8285714285714285 , 0.2571428571428571 , 0.4 , 0.4
15 , 0.7999999999999999 , 0.26666666666666666 , 0.4 , 0.4
16 , 0.7749999999999999 , 0.275 , 2.0 , 0.0
17 , 0.8470588235294116 , 0.25882352941176473 , 0.4 , 0.4
18 , 0.8222222222222221 , 0.2666666666666667 , 0.4 , 0.4
19 , 0.7999999999999998 , 0.27368421052631586 , 0.4 , 0.4
20 , 0.7799999999999998 , 0.2800000000000001 , 2.0 , 0.0
21 , 0.8380952380952379 , 0.2666666666666667 , 0.4 , 0.4
22 , 0.818181818181818 , 0.27272727272727276 , 0.4 , 0.4
23 , 0.7999999999999998 , 0.27826086956521745 , 0.4 , 0.4
24 , 0.7833333333333332 , 0.2833333333333334 , 2.0 , 0.0
25 , 0.8319999999999999 , 0.272 , 0.4 , 0.4
26 , 0.8153846153846153 , 0.27692307692307694 , 0.4 , 0.4
27 , 0.7999999999999999 , 0.2814814814814815 , 0.4 , 0.4
28 , 0.7857142857142857 , 0.28571428571428575 , 2.0 , 0.0
29 , 0.8275862068965517 , 0.2758620689655173 , 0.4 , 0.4
30 , 0.8133333333333334 , 0.28 , 0.4 , 0.4
31 , 0.8 , 0.2838709677419355 , 0.4 , 0.4
32 , 0.7875000000000001 , 0.2875 , 0.4 , 0.4
33 , 0.7757575757575759 , 0.2909090909090909 , 2.0 , 0.0
34 , 0.811764705882353 , 0.2823529411764706 , 0.4 , 0.4
35 , 0.8000000000000002 , 0.2857142857142857 , 0.4 , 0.4
36 , 0.7888888888888891 , 0.28888888888888886 , 0.4 , 0.4
37 , 0.7783783783783785 , 0.29189189189189185 , 2.0 , 0.0
38 , 0.8105263157894739 , 0.2842105263157894 , 0.4 , 0.4
39 , 0.8000000000000002 , 0.2871794871794871 , 0.4 , 0.4
40 , 0.7900000000000001 , 0.2899999999999999 , 0.4 , 0.4
41 , 0.7804878048780489 , 0.2926829268292682 , 2.0 , 0.0
42 , 0.8095238095238096 , 0.28571428571428564 , 0.4 , 0.4
43 , 0.8000000000000002 , 0.2883720930232557 , 0.4 , 0.4
44 , 0.790909090909091 , 0.29090909090909084 , 0.4 , 0.4
45 , 0.7822222222222223 , 0.2933333333333333 , 2.0 , 0.0
46 , 0.808695652173913 , 0.2869565217391304 , 0.4 , 0.4
47 , 0.8 , 0.28936170212765955 , 0.4 , 0.4
48 , 0.7916666666666667 , 0.29166666666666663 , 0.4 , 0.4
49 , 0.7836734693877552 , 0.29387755102040813 , 2.0 , 0.0
50 , 0.808 , 0.288 , 0.4 , 0.4
51 , 0.8 , 0.2901960784313725 , 0.4 , 0.4
52 , 0.7923076923076924 , 0.29230769230769227 , 0.4 , 0.4
53 , 0.7849056603773585 , 0.29433962264150937 , 2.0 , 0.0
54 , 0.8074074074074075 , 0.2888888888888888 , 0.4 , 0.4
55 , 0.8 , 0.29090909090909084 , 0.4 , 0.4
56 , 0.7928571428571429 , 0.2928571428571428 , 0.4 , 0.4
57 , 0.7859649122807019 , 0.29473684210526313 , 2.0 , 0.0
58 , 0.806896551724138 , 0.28965517241379307 , 0.4 , 0.4
59 , 0.8 , 0.2915254237288135 , 0.4 , 0.4
60 , 0.7933333333333333 , 0.2933333333333333 , 0.4 , 0.4
61 , 0.7868852459016393 , 0.2950819672131147 , 2.0 , 0.0
62 , 0.8064516129032258 , 0.29032258064516125 , 0.4 , 0.4
63 , 0.7999999999999999 , 0.292063492063492 , 0.4 , 0.4
64 , 0.79375 , 0.29374999999999996 , 0.4 , 0.4
65 , 0.7876923076923077 , 0.29538461538461536 , 0.4 , 0.4
66 , 0.7818181818181819 , 0.29696969696969694 , 2.0 , 0.0
67 , 0.8 , 0.2925373134328358 , 0.4 , 0.4
68 , 0.7941176470588236 , 0.2941176470588235 , 0.4 , 0.4
69 , 0.7884057971014493 , 0.29565217391304344 , 0.4 , 0.4
70 , 0.7828571428571429 , 0.2971428571428571 , 2.0 , 0.0
71 , 0.8 , 0.2929577464788732 , 0.4 , 0.4
72 , 0.7944444444444445 , 0.2944444444444444 , 0.4 , 0.4
73 , 0.789041095890411 , 0.29589041095890406 , 0.4 , 0.4
74 , 0.7837837837837839 , 0.29729729729729726 , 2.0 , 0.0
75 , 0.8 , 0.2933333333333333 , 0.4 , 0.4
76 , 0.7947368421052632 , 0.29473684210526313 , 0.4 , 0.4
77 , 0.7896103896103897 , 0.2961038961038961 , 0.4 , 0.4
78 , 0.7846153846153846 , 0.29743589743589743 , 2.0 , 0.0
79 , 0.8 , 0.2936708860759494 , 0.4 , 0.4
80 , 0.795 , 0.295 , 0.4 , 0.4
81 , 0.7901234567901235 , 0.2962962962962963 , 0.4 , 0.4
82 , 0.7853658536585366 , 0.2975609756097561 , 2.0 , 0.0
83 , 0.8 , 0.2939759036144578 , 0.4 , 0.4
84 , 0.7952380952380953 , 0.2952380952380952 , 0.4 , 0.4
85 , 0.7905882352941177 , 0.29647058823529404 , 0.4 , 0.4
86 , 0.7860465116279071 , 0.2976744186046511 , 2.0 , 0.0
87 , 0.8 , 0.29425287356321833 , 0.4 , 0.4
88 , 0.7954545454545455 , 0.2954545454545454 , 0.4 , 0.4
89 , 0.7910112359550563 , 0.296629213483146 , 0.4 , 0.4
90 , 0.7866666666666667 , 0.29777777777777775 , 2.0 , 0.0
91 , 0.8 , 0.29450549450549446 , 0.4 , 0.4
92 , 0.7956521739130435 , 0.29565217391304344 , 0.4 , 0.4
93 , 0.7913978494623657 , 0.2967741935483871 , 0.4 , 0.4
94 , 0.7872340425531916 , 0.2978723404255319 , 0.4 , 0.4
95 , 0.7831578947368423 , 0.29894736842105263 , 2.0 , 0.0
96 , 0.7958333333333335 , 0.29583333333333334 , 0.4 , 0.4
97 , 0.7917525773195878 , 0.29690721649484536 , 0.4 , 0.4
98 , 0.7877551020408166 , 0.2979591836734694 , 0.4 , 0.4
99 , 0.7838383838383841 , 0.29898989898989903 , 2.0 , 0.0
100 , 0.7960000000000003 , 0.29600000000000004 , 0.4 , 0.4

MSA using linprog

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

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]
    print(k,",", x1, "," , x2, "," , y1 , "," , y2)
    x1 = x1 + (1/(k+1))*(y1-x1)
    x2 = x2 + (1/(k+1))*(y2-x2)
    k = k + 1

1 , 0 , 0 , 2.0 , 0.0
2 , 1.0 , 0.0 , 0.4 , 0.4
3 , 0.8 , 0.133333333333 , 0.4 , 0.4
4 , 0.7 , 0.2 , 2.0 , 0.0
5 , 0.96 , 0.16 , 0.4 , 0.4
6 , 0.866666666667 , 0.2 , 0.4 , 0.4
7 , 0.8 , 0.228571428571 , 0.4 , 0.4
8 , 0.75 , 0.25 , 2.0 , 0.0
9 , 0.888888888889 , 0.222222222222 , 0.4 , 0.4
10 , 0.84 , 0.24 , 0.4 , 0.4
11 , 0.8 , 0.254545454545 , 0.4 , 0.4
12 , 0.766666666667 , 0.266666666667 , 2.0 , 0.0
13 , 0.861538461538 , 0.246153846154 , 0.4 , 0.4
14 , 0.828571428571 , 0.257142857143 , 0.4 , 0.4
15 , 0.8 , 0.266666666667 , 0.4 , 0.4
16 , 0.775 , 0.275 , 2.0 , 0.0
17 , 0.847058823529 , 0.258823529412 , 0.4 , 0.4
18 , 0.822222222222 , 0.266666666667 , 0.4 , 0.4
19 , 0.8 , 0.273684210526 , 0.4 , 0.4
20 , 0.78 , 0.28 , 2.0 , 0.0
21 , 0.838095238095 , 0.266666666667 , 0.4 , 0.4
22 , 0.818181818182 , 0.272727272727 , 0.4 , 0.4
23 , 0.8 , 0.278260869565 , 0.4 , 0.4
24 , 0.783333333333 , 0.283333333333 , 2.0 , 0.0
25 , 0.832 , 0.272 , 0.4 , 0.4
26 , 0.815384615385 , 0.276923076923 , 0.4 , 0.4
27 , 0.8 , 0.281481481481 , 0.4 , 0.4
28 , 0.785714285714 , 0.285714285714 , 0.4 , 0.4
29 , 0.772413793103 , 0.289655172414 , 2.0 , 0.0
30 , 0.813333333333 , 0.28 , 0.4 , 0.4
31 , 0.8 , 0.283870967742 , 0.4 , 0.4
32 , 0.7875 , 0.2875 , 0.4 , 0.4
33 , 0.775757575758 , 0.290909090909 , 2.0 , 0.0
34 , 0.811764705882 , 0.282352941176 , 0.4 , 0.4
35 , 0.8 , 0.285714285714 , 0.4 , 0.4
36 , 0.788888888889 , 0.288888888889 , 0.4 , 0.4
37 , 0.778378378378 , 0.291891891892 , 2.0 , 0.0
38 , 0.810526315789 , 0.284210526316 , 0.4 , 0.4
39 , 0.8 , 0.287179487179 , 0.4 , 0.4
40 , 0.79 , 0.29 , 0.4 , 0.4
41 , 0.780487804878 , 0.292682926829 , 2.0 , 0.0
42 , 0.809523809524 , 0.285714285714 , 0.4 , 0.4
43 , 0.8 , 0.288372093023 , 0.4 , 0.4
44 , 0.790909090909 , 0.290909090909 , 0.4 , 0.4
45 , 0.782222222222 , 0.293333333333 , 2.0 , 0.0
46 , 0.808695652174 , 0.286956521739 , 0.4 , 0.4
47 , 0.8 , 0.289361702128 , 0.4 , 0.4
48 , 0.791666666667 , 0.291666666667 , 0.4 , 0.4
49 , 0.783673469388 , 0.29387755102 , 2.0 , 0.0
50 , 0.808 , 0.288 , 0.4 , 0.4
51 , 0.8 , 0.290196078431 , 0.4 , 0.4
52 , 0.792307692308 , 0.292307692308 , 0.4 , 0.4
53 , 0.784905660377 , 0.294339622642 , 2.0 , 0.0
54 , 0.807407407407 , 0.288888888889 , 0.4 , 0.4
55 , 0.8 , 0.290909090909 , 0.4 , 0.4
56 , 0.792857142857 , 0.292857142857 , 0.4 , 0.4
57 , 0.785964912281 , 0.294736842105 , 2.0 , 0.0
58 , 0.806896551724 , 0.289655172414 , 0.4 , 0.4
59 , 0.8 , 0.291525423729 , 0.4 , 0.4
60 , 0.793333333333 , 0.293333333333 , 0.4 , 0.4
61 , 0.786885245902 , 0.295081967213 , 0.4 , 0.4
62 , 0.78064516129 , 0.296774193548 , 2.0 , 0.0
63 , 0.8 , 0.292063492063 , 0.4 , 0.4
64 , 0.79375 , 0.29375 , 0.4 , 0.4
65 , 0.787692307692 , 0.295384615385 , 0.4 , 0.4
66 , 0.781818181818 , 0.29696969697 , 2.0 , 0.0
67 , 0.8 , 0.292537313433 , 0.4 , 0.4
68 , 0.794117647059 , 0.294117647059 , 0.4 , 0.4
69 , 0.788405797101 , 0.295652173913 , 0.4 , 0.4
70 , 0.782857142857 , 0.297142857143 , 2.0 , 0.0
71 , 0.8 , 0.292957746479 , 0.4 , 0.4
72 , 0.794444444444 , 0.294444444444 , 0.4 , 0.4
73 , 0.78904109589 , 0.295890410959 , 0.4 , 0.4
74 , 0.783783783784 , 0.297297297297 , 2.0 , 0.0
75 , 0.8 , 0.293333333333 , 0.4 , 0.4
76 , 0.794736842105 , 0.294736842105 , 0.4 , 0.4
77 , 0.78961038961 , 0.296103896104 , 0.4 , 0.4
78 , 0.784615384615 , 0.297435897436 , 2.0 , 0.0
79 , 0.8 , 0.293670886076 , 0.4 , 0.4
80 , 0.795 , 0.295 , 0.4 , 0.4
81 , 0.79012345679 , 0.296296296296 , 0.4 , 0.4
82 , 0.785365853659 , 0.29756097561 , 2.0 , 0.0
83 , 0.8 , 0.293975903614 , 0.4 , 0.4
84 , 0.795238095238 , 0.295238095238 , 0.4 , 0.4
85 , 0.790588235294 , 0.296470588235 , 0.4 , 0.4
86 , 0.786046511628 , 0.297674418605 , 2.0 , 0.0
87 , 0.8 , 0.294252873563 , 0.4 , 0.4
88 , 0.795454545455 , 0.295454545455 , 0.4 , 0.4
89 , 0.791011235955 , 0.296629213483 , 0.4 , 0.4
90 , 0.786666666667 , 0.297777777778 , 2.0 , 0.0
91 , 0.8 , 0.294505494505 , 0.4 , 0.4
92 , 0.795652173913 , 0.295652173913 , 0.4 , 0.4
93 , 0.791397849462 , 0.296774193548 , 0.4 , 0.4
94 , 0.787234042553 , 0.297872340426 , 0.4 , 0.4
95 , 0.783157894737 , 0.298947368421 , 2.0 , 0.0
96 , 0.795833333333 , 0.295833333333 , 0.4 , 0.4
97 , 0.79175257732 , 0.296907216495 , 0.4 , 0.4
98 , 0.787755102041 , 0.297959183673 , 0.4 , 0.4
99 , 0.783838383838 , 0.29898989899 , 2.0 , 0.0
100 , 0.796 , 0.296 , 0.4 , 0.4