CoCalc Shared Filestmp / piyavski-dimakov / piyavski-solution.ipynb
Author: Evgenij Grines
Views : 33
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 [ ]: