CoCalc Public Filestmp / piyavski-dimakov / piyavski-solution.ipynbOpen in with one click!
Author: Evgenij Grines
Views : 74
In [1]:
def minorantEstimate(X, pivotPt,func, lipschitzConst): return (func(pivotPt) - lipschitzConst * abs(X - pivotPt)) def minorantPoint(xLeft, xRight, func, lipschitzConst): return ((lipschitzConst * (xLeft + xRight) - (func(xRight) - func(xLeft))) / (2.0*lipschitzConst)) def calculateMinorant(nodes, L, func): minorantPts = [] N = len(nodes) for i in range(N-1): xLeft, xRight = nodes[i], nodes[i+1] minorantPts.append((xLeft, func(xLeft))) middlePoint = minorantPoint(xLeft, xRight, func, L) middleVal = minorantEstimate(middlePoint, xLeft, func, L) minorantPts.append((middlePoint, middleVal)) minorantPts.append((nodes[-1], func(nodes[-1]))) return minorantPts
In [2]:
import numpy as np import matplotlib.pyplot as plt import math from math import sin def f(x): return sin(x) L = 1.0 xFunc = np.linspace(-np.pi, +np.pi, 1000) yFunc = [f(x) for x in xFunc]
In [3]:
startPoint = 1.9 nodes = [-np.pi, startPoint, +np.pi] minorant = calculateMinorant(nodes, L, f) minorantX, minorantY = zip(*minorant) minorantMinCoord, minorantMin = min(minorant, key = lambda x: x[1]) evaluationMinCoord, evaluationMin = min([(x, f(x)) for x in nodes], key = lambda x: x[1]) eps = 1e-3 iterNumber = 0 # initial graph and info print("Iteration number = 0".format(iterNumber)) print("Minorant minimum = {} at x = {}".format(minorantMin, minorantMinCoord)) print("Evaluation minimum = {} at x = {}\n\n".format(evaluationMin, evaluationMinCoord)) plt.figure() plt.title('Iteration 0'.format(iterNumber)) plt.scatter(nodes, [f(n) for n in nodes], color='red', label='Initial nodes') plt.plot(minorantX, minorantY, 'b--', label='Minorant') plt.plot(xFunc, yFunc, 'k-', label='Optimized function') plt.legend() while (abs(evaluationMin - minorantMin) > eps): iterNumber += 1 print("Iteration number = {}".format(iterNumber)) # using current nodes calculate minorant minorant = calculateMinorant(nodes, L, f) #print(minorant) # find the point where minimum value of minorant is attained minCoord, _ = min(minorant, key=lambda x: x[1]) #print(minCoord) #print(nodes) # add it to the new list of nodes newNodes = nodes newNodes.append(minCoord) newNodes.sort() # use newNodes to plot minorant plt.figure() plt.title('Iteration {}'.format(iterNumber)) #plt.title('Iteration {}\nMinorant minimum = {} at x = {}\nEvaluation minimum = {} at x = {}'.format(iterNumber, minorantMin, minorantMinCoord, evaluationMin, evaluationMinCoord)) # plot previous nodes plt.scatter(nodes, [f(n) for n in nodes], color='red', label='Previous nodes') # plot new node plt.scatter([minCoord], [f(minCoord)], color='green', label='New node') # calculate new minorant and plot it newMinorant = calculateMinorant(newNodes, L, f) newMinorantX, newMinorantY = zip(*newMinorant) plt.plot(newMinorantX, newMinorantY, 'b--', label='Minorant') # plot true function graph plt.plot(xFunc, yFunc, 'k-', label='Optimized function') plt.legend() # recalculate mins for stopping condition minorantMinCoord, minorantMin = min(newMinorant, key = lambda x: x[1]) evaluationMinCoord, evaluationMin = min([(x, f(x)) for x in newNodes], key = lambda X: X[1]) # update nodes nodes = newNodes # print auxiliary information print("Minorant minimum = {} at x = {}".format(minorantMin, minorantMinCoord)) print("Evaluation minimum = {} at x = {}\n\n".format(evaluationMin, evaluationMinCoord))
Iteration number = 0 Minorant minimum = -2.047646282951189 at x = -1.093946370638604 Evaluation minimum = -1.2246467991473532e-16 at x = -3.141592653589793 Iteration number = 1 Minorant minimum = -1.4680457136257328 at x = -1.6735469399640606 Evaluation minimum = -0.8884451443002762 at x = -1.093946370638604 Iteration number = 2 Minorant minimum = -1.4680457136257328 at x = -0.5143458013131473 Evaluation minimum = -0.994725798478638 at x = -1.6735469399640606 Iteration number = 3 Minorant minimum = -1.2313857560521855 at x = -1.9102068975376079 Evaluation minimum = -0.994725798478638 at x = -1.6735469399640606 Iteration number = 4 Minorant minimum = -1.2313857560521855 at x = -1.436886982390513 Evaluation minimum = -0.994725798478638 at x = -1.6735469399640606 Iteration number = 5 Minorant minimum = -1.1112166447751297 at x = -1.5570560936675688 Evaluation minimum = -0.994725798478638 at x = -1.6735469399640606 Iteration number = 6 Minorant minimum = -1.1112166447751295 at x = -1.3167178711134575 Evaluation minimum = -0.9999056044819263 at x = -1.5570560936675688 Iteration number = 7 Minorant minimum = -1.0871684124245247 at x = -2.0544242411652687 Evaluation minimum = -0.9999056044819263 at x = -1.5570560936675688 Iteration number = 8 Minorant minimum = -1.087168412424524 at x = -1.765989553909947 Evaluation minimum = -0.9999056044819263 at x = -1.5570560936675688 Iteration number = 9 Minorant minimum = -1.0555611246285281 at x = -1.501400573520967 Evaluation minimum = -0.9999056044819263 at x = -1.5570560936675688 Iteration number = 10 Minorant minimum = -1.055561124628528 at x = -1.6127116138141706 Evaluation minimum = -0.9999056044819263 at x = -1.5570560936675688 Iteration number = 11 Minorant minimum = -1.039555992431476 at x = -1.245057218769804 Evaluation minimum = -0.9999056044819263 at x = -1.5570560936675688 Iteration number = 12 Minorant minimum = -1.0395559924314757 at x = -1.3883785234571113 Evaluation minimum = -0.9999056044819263 at x = -1.5570560936675688 Iteration number = 13 Minorant minimum = -1.0340893113556202 at x = -1.712910452841043 Evaluation minimum = -0.9999056044819263 at x = -1.5570560936675688 Iteration number = 14 Minorant minimum = -1.03408931135562 at x = -1.819068654978851 Evaluation minimum = -0.9999056044819263 at x = -1.5570560936675688 Iteration number = 15 Minorant minimum = -1.0273414037945838 at x = -1.5844918929802259 Evaluation minimum = -0.9999056044819263 at x = -1.5570560936675688 Iteration number = 16 Minorant minimum = -1.0273414037945834 at x = -1.6409313346481151 Evaluation minimum = -0.9999062171993373 at x = -1.5844918929802259 Iteration number = 17 Minorant minimum = -1.0265771027528932 at x = -1.530384595396602 Evaluation minimum = -0.9999062171993373 at x = -1.5844918929802259 Iteration number = 18 Minorant minimum = -1.026577102752893 at x = -1.4724165516453322 Evaluation minimum = -0.9999062171993373 at x = -1.5844918929802259 Iteration number = 19 Minorant minimum = -1.0136238104969602 at x = -1.5982094862778493 Evaluation minimum = -0.9999062171993373 at x = -1.5844918929802259 Iteration number = 20 Minorant minimum = -1.0136238104969602 at x = -1.5707742996826028 Evaluation minimum = -0.9999062171993373 at x = -1.5844918929802259 Iteration number = 21 Minorant minimum = -1.012880329928142 at x = -1.5440813682213532 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 22
/ext/anaconda-2019.03/lib/python3.7/site-packages/ipykernel/__main__.py:35: RuntimeWarning: More than 20 figures have been opened. Figures created through the pyplot interface (`matplotlib.pyplot.figure`) are retained until explicitly closed and may consume too much memory. (To control this warning, see the rcParam `figure.max_open_warning`).
Minorant minimum = -1.012880329928142 at x = -1.5166878225718508 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 23 Minorant minimum = -1.012441476061492 at x = -1.6260314069150235 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 24 Minorant minimum = -1.0124414760614917 at x = -1.6558312623812068 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 25 Minorant minimum = -1.0120040415780436 at x = -1.6908251830634662 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 26 Minorant minimum = -1.0120040415780434 at x = -1.73499572261862 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 27 Minorant minimum = -1.0114819758395506 at x = -1.3603045068651856 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 28 Minorant minimum = -1.0114819758395504 at x = -1.4164525400490366 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 29 Minorant minimum = -1.0108708572680305 at x = -1.488122797130195 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 30 Minorant minimum = -1.0108708572680305 at x = -1.4567103061604694 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 31 Minorant minimum = -1.0068119051271818 at x = -1.5639623943128242 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 32 Minorant minimum = -1.0068119051271816 at x = -1.5775862050523815 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 33 Minorant minimum = -1.006624046685063 at x = -1.6052092500897468 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 34 Minorant minimum = -1.006624046685063 at x = -1.5912097224659516 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 35 Minorant minimum = -1.006261753322422 at x = -1.5374627916156334 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 36 Minorant minimum = -1.0062617533224218 at x = -1.5506999448270733 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 37 Minorant minimum = -1.0057084109644203 at x = -1.5238597415355724 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 38 Minorant minimum = -1.0057084109644203 at x = -1.509515903608129 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 39 Minorant minimum = -1.0054582034103214 at x = -1.6330146795661937 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 40 Minorant minimum = -1.0054582034103214 at x = -1.619048134263853 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 41 Minorant minimum = -1.0044140920027067 at x = -1.6638586464399918 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 42 Minorant minimum = -1.0044140920027065 at x = -1.6478038783224218 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 43 Minorant minimum = -1.0037276735361047 at x = -1.4952659808621205 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 44 Minorant minimum = -1.0037276735361047 at x = -1.4809796133982696 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 45 Minorant minimum = -1.003394426996183 at x = -1.5810036831833802 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 46 Minorant minimum = -1.003394426996183 at x = -1.5741687269213824 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 47 Minorant minimum = -1.0033942769507387 at x = -1.5673800224892673 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 48 Minorant minimum = -1.0033942769507385 at x = -1.5605447661363814 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 49 Minorant minimum = -1.003207850279369 at x = -1.5946259188716454 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 50 Minorant minimum = -1.0032078502793689 at x = -1.5877935260602578 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 51 Minorant minimum = -1.0030299139171701 at x = -1.5474681054218211 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 52 Minorant minimum = -1.00302991391717 at x = -1.5539317842323253 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 53 Minorant minimum = -1.0030159902365865 at x = -1.608817306538223 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 54 Minorant minimum = -1.0030159902365865 at x = -1.6016011936412708 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 55 Minorant minimum = -1.0028531212391594 at x = -1.540871423698896 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 56 Minorant minimum = -1.0028531212391592 at x = -1.5340541595323705 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 57 Minorant minimum = -1.002404611285479 at x = -1.7004246133560308 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 58 Minorant minimum = -1.0024046112854788 at x = -1.6812257527709016 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 59 Minorant minimum = -1.002303545828305 at x = -1.5272646066716877 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 60 Minorant minimum = -1.002303545828305 at x = -1.5204548763994572 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 61 Minorant minimum = -1.0021850513764268 at x = -1.465396112052073 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 62 Minorant minimum = -1.0021850513764268 at x = -1.4480245002688659 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 63 Minorant minimum = -1.0021471553963741 at x = -1.6223591822778003 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 64 Minorant minimum = -1.0021471553963741 at x = -1.6157370862499059 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 65 Minorant minimum = -1.001915676674886 at x = -1.5133086378976632 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 66 Minorant minimum = -1.001915676674886 at x = -1.5057231693185948 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 67 Minorant minimum = -1.0017616330094126 at x = -1.6367112499671026 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 68 Minorant minimum = -1.0017616330094123 at x = -1.6293181091652853 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 69 Minorant minimum = -1.0017138598362476 at x = -1.8514441064982234 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 70 Minorant minimum = -1.0017138598362476 at x = -1.7866932034594785 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 71 Minorant minimum = -1.0016943702301329 at x = -1.5758687836874326 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 72 Minorant minimum = -1.0016943702301329 at x = -1.5724686701553325 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 73 Minorant minimum = -1.00169422069443 at x = -1.569080078745576 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 74 Minorant minimum = -1.00169422069443 at x = -1.5656799662329586 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 75 Minorant minimum = -1.0016711661931383 at x = -1.5827269439864249 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 76 Minorant minimum = -1.0016711661931383 at x = -1.5792804223803356 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 77 Minorant minimum = -1.0016708650814858 at x = -1.562268178005634 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 78 Minorant minimum = -1.0016708650814858 at x = -1.5588213542671285 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 79 Minorant minimum = -1.001531700682826 at x = -1.589469675656801 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 80 Minorant minimum = -1.001531700682826 at x = -1.5861173764637142 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 81 Minorant minimum = -1.0014619694926923 at x = -1.5963717996583222 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 82 Minorant minimum = -1.0014619694926923 at x = -1.5928800380849688 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 83 Minorant minimum = -1.0014438554448295 at x = -1.5555178427046656 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 84 Minorant minimum = -1.0014438554448295 at x = -1.5523457257599846 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 85 Minorant minimum = -1.001378911650367 at x = -1.5491191076886244 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 86 Minorant minimum = -1.001378911650367 at x = -1.5458171031550179 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 87 Minorant minimum = -1.0012707789224855 at x = -1.6033464049553718 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 88 Minorant minimum = -1.0012707789224855 at x = -1.5998559823271699 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 89 Minorant minimum = -1.00120270236942 at x = -1.5425218425686353 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 90 Minorant minimum = -1.0012027023694199 at x = -1.539221004829157 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 91 Minorant minimum = -1.0011466399273812 at x = -1.6106866568474285 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 92 Minorant minimum = -1.0011466399273812 at x = -1.6069479562290174 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 93 Minorant minimum = -1.001089101872095 at x = -1.5358181788994347 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 94 Minorant minimum = -1.0010891018720947 at x = -1.5322901401653062 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028 Iteration number = 95 Minorant minimum = -1.0008464859321506 at x = -1.5733165544533145 Evaluation minimum = -0.9999999997574032 at x = -1.5707742996826028
In [ ]:
In [ ]: